数理逻辑_复习题及参考答案

从一份模拟试题中抽取出来的数理逻辑复习题及参考答案一、单选题（每小题2分，共20分）1 以下语句是命题的是（ ）。A y等于x。B 每个自然数都是奇数。C 请爱护环境。D 你今天有空吗？2 设是一赋值，(p)= (q)=1，(r)=0，下列公式的值为假的是（ ）。Ap(qr)B(pr) (rq)C(rq) (qp)D(rq)3 以下联结词的集合（ ）不是完备集。A, , B,C, D,4 公式A的对偶式为A*，下列结果成立的是（ ）。AAA*BAA*CA|=|A*DA|=|A*5 假设论域是正整数集合，下列自然语言的符号化表示中，（ ）的值是真的。AxyG(x,y)，其中G(x,y)表示xy=yBxyF(x,y)，其中F(x,y)表示x+y=yCxyH(x,y)，其中H(x,y)表示x+y=xDxyM(x,y)，其中M(x,y)表示xy=x6以下式子错误的是（ ）。AxA(x) |=| xA(x)Bx(A(x)B(x) |=| xA(x)x B(x)Cx(A(x)B(x) |=| xA(x)x B(x)Dx(A(x)B(x) |=| xA(x)x B(x)7. 下列式子（ ）不正确。AxxBxx,xCxxDxx,x二、填空题（每小题2分，共20分）1句子“只有小王爱唱歌，他才会弹钢琴。”中，把“小王爱唱歌”形式化为命题符p，“小王会弹钢琴”形式化为命题符q，则句子形式化为公式 。2公式(pq)(pq)t的对偶是 。3公式的前束范式是 。4公式xA(x)B(y)中，量词的辖域是 ，自由变元是 。三、计算题（30分）1（6分）用等值演算法计算命题公式的析取范式和主析取范式。四、证明题（20分）1（6分）用讨论指派的方法证明A(BC)|=| (AB)(AC)五、综合题（10分）在谓词逻辑自然推理系统FND中，构造下面的证明。要求写出所有谓词的含义，分别写出前提、结论和证明过程。“某学术会议的每个成员都是专家也是工人。有些成员是青年人。所以，有些成员是青年专家。”参考答案一、单选题（20分）1 B2 B3 D4 D 5 A 6D7. C二、填空题（20分）1qp 2(pq)(pq)f3 三、计算题（30分）1 倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。四、证明题（20分）1证明：当赋值使左式为真时，有(A)=0或(A)=1且(BC)=1。当(A)=0时，(AB)(AC)1，所以(AB)(AC)1。(A)=1且(BC)=1时，有(B)0或(B)1且(C)1。(A)=1且(B)0时，(AB)0，(AB)(AC)1。(A)=1且(B)1且(C)1时，(AB)(AC)1，所以(AB)(AC)1。因此A(BC)|= (AB)(AC)。当赋值使右式为真时，为证(AB)(AC)1时有(A(BC)1，等价于证(A(BC)0时有(AB)(AC)0。(A(BC)0时，(A)=1且(BC)=0，即(A)=1且(B)1且(C)0。此时(AB)1，(AC)0，所以(AB)(AC)0。因此(AB)(AC)|= A(BC)。因此A(BC)|=| (AB)(AC)。五、综合题（10分）解答：设谓词：S(x): x是专家；W(x): x是工人；Y(x): x是青年人。前提：结论：证明过程：（1） 前提引入（2）Y(c)（1），ES（