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

数理逻辑_复习题及参考答案数理逻辑_复习题及参考答案数理逻辑_复习题及参考答案数理逻辑_复习题及参考答案编制仅供参考审核批准生效日期地址：电话：传真:邮编:从一份模拟试题中抽取出来的《数理逻辑》复习题及参考答案一、单选题（每小题2分，共20分）1以下语句是命题的是（）。y等于x。每个自然数都是奇数。请爱护环境。你今天有空吗2设α是一赋值，α(p)=α(q)=1，α(r)=0，下列公式的值为假的是（）。A．p∧(q∨r) B．(pr)(¬rq)C．(rq)∧(qp) D．(rq)3以下联结词的集合（）不是完备集。A．{¬,∧,∨,,}B．{¬,∧,∨} C．{¬,} D．{∧,∨}4公式A的对偶式为A*，下列结果成立的是（）。A．AA* B．¬AA* C．A|=|A* D．¬A|=|A*5假设论域是正整数集合，下列自然语言的符号化表示中，（）的值是真的。A．xyG(x,y)，其中G(x,y)表示xy=y B．xyF(x,y)，其中F(x,y)表示x+y=yC．xyH(x,y)，其中H(x,y)表示x+y=xD．xyM(x,y)，其中M(x,y)表示xy=x6．以下式子错误的是（）。A．x¬A(x)|=|¬xA(x)B．x(A(x)∧B(x))|=|xA(x)∧xB(x)C．x(A(x)∨B(x))|=|xA(x)∨xB(x)D．x(A(x)∨B(x))|=|xA(x)∨xB(x)7.下列式子（）不正确。A．{x}∈{{x}} B．{x}∈{{x},x} C．{x}{{x}} D．{x}{{x},x}二、填空题（每小题2分，共20分）1．句子“只有小王爱唱歌，他才会弹钢琴。”中，把“小王爱唱歌”形式化为命题符p，“小王会弹钢琴”形式化为命题符q，则句子形式化为公式。2．公式¬(¬p∧¬q)∨(¬p∧q)∨t的对偶是。3．公式的前束范式是。4．公式xA(x)∨B(y)中，量词的辖域是，自由变元是。三、计算题（30分）1．（6分）用等值演算法计算命题公式的析取范式和主析取范式。四、证明题（20分）1．（6分）用讨论指派的方法证明A→(B→C)|=|(A→B)→(A→C)五、综合题（10分）在谓词逻辑自然推理系统FND中，构造下面的证明。要求写出所有谓词的含义，分别写出前提、结论和证明过程。“某学术会议的每个成员都是专家也是工人。有些成员是青年人。所以，有些成员是青年专家。”参考答案一、单选题（20分）1B 2B 3D 4D 5A 6．D 7.C 二、填空题（20分）1．q→p2．¬(¬p∨¬q)∧(¬p∨q)∧f3．三、计算题（30分）1．倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。四、证明题（20分）1．证明：当赋值α使左式为真时，有α(A)=0或α(A)=1且α(B→C)=1。当α(A)=0时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A→C))＝1。α(A)=1且α(B→C)=1时，有α(B)＝0或α(B)＝1且α(C)＝1。α(A)=1且α(B)＝0时，α(A→B)＝0，α((A→B)→(A→C))＝1。α(A)=1且α(B)＝1且α(C)＝1时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A→C))＝1。因此A→(B→C)|=(A→B)→(A→C)。当赋值α使右式为真时，为证α((A→B)→(A→C))＝1时有α(A→(B→C))＝1，等价于证α(A→(B→C))＝0时有α((A→B)→(A→C))＝0。α(A→(B→C))＝0时，α(A)=1且α(B→C)=0，即α(A)=1且α(B)＝1且α(C)＝0。此时α(A→B)＝1，α(A→C)＝0，所以α((A→B)→(A→C))＝0。因此(A→B)→(A→C)|=A→(B→C)。因此A→(B→C)|=|(A→B)→(A→C)。五、综合题（10分）解答：设谓词：S(x):x是专家；W(x):x是工人；Y(x):x是青年人。前提：结论：证明过程：（1）