离散1(数理逻辑)复习题

1、离散数学1（数理逻辑）复习题一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列为两个命题变元P，Q的小项是（）APQP BPQ CPQ DPPQ2下列语句中是真命题的是（）A我正在说谎 B严禁吸烟 C如果1+2=3，那么雪是黑的 D如果1+2=5，那么雪是黑的3设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）APQ BPQ C（PQ） D（PQ）4命题公式（P（PQ）Q是（）A矛盾式 B蕴含式 C重言式 D等价式5命题公式（PQR）的成真指派是（）A000，001，110 B001，011，101

2、，110，111C全体指派 D无6在公式（）F（x，y）（y）G（x，y）中变元x是（）A自由变元 B约束变元C既是自由变元，又是约束变元 D既不是自由变元，又不是约束变元二、填空题请在每小题的空格中填上正确答案。错填、不填均无分。1（）（y）（P（x，y）Q（y，z）xP（x，y）中的辖域为_，x的辖域为_。2两个重言式的析取是_式，一个重言式与一个矛盾式的析取是_式。三、计算题1构造命题公式（PQ）P）R的真值表。2求下列公式的主合取范式和主析取范式：P（P（Q（QR）四、证明题构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，

3、当小赵去看电影时，小李也去。一、单项选择题(30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.命题公式(ab)(abc)(bc)的等价式是( )A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)2.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):xy.下列公式在R下为真的是( )A.(x)(y)(z)(A(x,y)A(f(x,z),f(y,z)B.(x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x)D.(x)(y)(A(x,y)A(f(x,a),a)3.设B是不含变

4、元x的公式，谓词公式(x)(A(x)B)等价于( )A.(x)A(x)B B.(x)A(x)BC.A(x)B D.(x)A(x)(x)B4.谓词公式(x)(P(x,y)(z)Q(x,z)(y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元5.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.PQ B.PQ C.PQ D.PQ6.以下命题公式中，为永假式的是( )A.p(pqr) B.(pp)pC.(qq)p D.(qp)(pp)二、填空题(20分)1.使公式(x)( y)(A(

5、x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x。2.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)_,其中量词(x)的辖域是_。3.若H1H2Hn是_，则称H1,H2,Hn是相容的，若H1H2Hn是_，则称H1,H2,Hn是不相容的。4.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。三、计算题 (共20分)1.求(PQ)的主合取范式并给出所有使命题为真的赋值。2.求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。四、证明题 (共30分)1.在个体域D=a1,a2,，an中证明等价式：

6、 (x)(A(x)B(x)(x)A(x)(x)B(x)2.如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。离散数学复习题及答案一、证明题（10分）1)(PQ)(P(QR)(PQ)(PR)T证明: 左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律) (PQ)(PR)(PQ)(PR) (等幂律) T(代入)2)x(P(x)Q(x)xP(x)x(P(x)Q(x

7、)证明：x(P(x)Q(x)xP(x)x(P(x)Q(x)P(x)x(P(x)Q(x)P(x)x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式（10分）。解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题（10分）1)(P(QS)(RP)QRS证明：（1）R 附加前提（2）RP P（3）P T(1)(2)，I（4）P(QS) P（5）QS T(3)(4)，I（6）Q P（7）S T(5)(6)，I（8）RS CP2) x(P(x)Q(x)，xP(x)

8、$x Q(x)证明：(1)xP(x) P(2)P(c) T(1)，US(3)x(P(x)Q(x) P(4)P(c)Q(c) T(3)，US(5)Q(c) T(2)(4)，I(6)$x Q(x) T(5)，EG一、证明题（10分）1)(P(QR)(QR)(PR)R证明: 左端(PQR)(QP)R)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R(PQ)(PQ)RTR(置换)R2)$x(A(x)B(x) xA(x)$xB(x)证明 ：$x(A(x)B(x)$x(A(x)B(x)$xA(x)$xB(x)xA(x)$xB(x)xA(x)$xB(x)二、求命题公式(P(QR)(PQR)

9、的主析取范式和主合取范式（10分）。证明：(P(QR)(PQR)(P(QR)(PQR)（P(QR)）(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m0m1m2m7M3M4M5M6三、推理证明题（10分）1） CD， (CD) E， E(AB)， (AB)(RS)RS证明：(1) (CD)E P(2) E(AB) P(3) (CD)(AB) T(1)(2)，I(4) (AB)(RS) P(5) (CD)(RS) T(3)(4)， I(6) CD P(7) RS T(5)，I 2) x(P(x)Q(y)R(x)，$xP(x)Q(y)$x(P(x)R(x)证明(1)$xP(x) P(2)P(a) T(1)，ES(3)x(P(x)Q(y)R(x) P