《数理逻辑习题离散数学.docx》由会员分享，可在线阅读，更多相关《数理逻辑习题离散数学.docx（9页珍藏版）》请在三一文库上搜索。
1、第 1 章 命题逻辑1. 下列命题公式等值的是()(A) P Q, P Q(C)Q (P Q), Q P Q(B)A (A B), A (A B) (D) A (A B), B2. 设命题公式G： P (Q R) ,则使公式G取真值为1 的 P， Q， R赋值分别是()(A) 0,0,0(B)0,0,1(C)0,1,0(D) 1,0,03. 命题公式(P Q) Q为 ()(A) 矛盾式(B) 仅可满足式(C) 重言式 (D) 合取范式4. 命题公式( P Q) 的主析取范式是()(A) P Q (B) P Q (C) P Q (D) P5. 前提条件P Q, P 的有效结论是()(A) P(B
2、) P (C) Q(D) Q6. 设P：我将去市里，Q：我有时间命题“我将去市里，仅当我有时间时”符号化为()(A)Q P (B)P Q(C)P Q (D) P Q1. 设命题公式G： P(Q P)，则使公式G 为假的真值指派是2. 设P：我们划船，G：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为3. 含有三个命题变项P， Q， R的命题公式P Q 的主析取范式是4. 若命题变元P， Q， R赋值为(1,0,1)， 则命题公式G (P Q) R) ( P Q) 的真值是5. 命题公式P P Q 的类型是6. 设A，B 为任意命题公式，C 为重言式，若A C B C ，那么 A B 是
3、式 (重言式、矛盾式或可满足式)三、解答化简计算题1. 判别下列语句是否命题如果是命题，指出其真值.(1) 中国是一个人口众多的国家.(2) 存在最大的质数.(3) 这座楼可真高啊！(4) 请你跟我走!(5) 火 星上也有人.2. 作命题公式(P Q) ( P Q) P)的真值表，并判断该公式的类型3. 试作以下二题：(1) 求命题公式(P Q) (P Q)的成真赋值(2) 设命题变元P,Q,R的真值指派为(0,1,1),求命题公式(P R) ( P Q) ( R Q)的真值4. 化简下式命题公式( P Q) ( P Q) P)5. 求命题公式P (Q P) ( P Q) 的主合取范式.6.
4、求命题公式(P Q) (P Q) 的主析取范式，并求该命题公式的成假赋值7. 求命题公式(P Q) ( P Q) 的真值表.四、证明题1. 证明 (P Q) ( Q R) R (P S) S2. 构造推理证明：(P (Q S) (R P) Q R S3. 证明命题公式(P Q) (R Q) 与 (P R) Q 有相同的主析取范式1. C 2. D3. B4. A 5. D 6. B1. 1,0； 1,12. (P Q)或 P Q 3. (P Q R) (P Q R)4. 05. 非永真式的可满足式6. 重言1. (1) 是命题，真值为1.(2) 是命题，真值为0. (3), (4)不是命题.
5、(5) 是命题 .1. 判别下列语句是否命题如果是命题，指出其真值.(1) 中国是一个人口众多的国家.(2) 存在最大的质数.(3) 这座楼可真高啊！(4) 请你跟我走!(5) 火 星上也有人2. 命题公式 (P Q) ( P Q) P)的真值表PQPQPQ(P Q) P(P Q) (P Q) P)001000011000100011111111原式为可满足式3. (1) (PQ)(P可见 (PQ)(PQ) ( P Q)Q)的成真赋值为(P Q) ( P P) Q Q(0,1)， (1,1)(2)(PR)(Q) (Q)4.(P5.6.(01)(10) (01)Q)(P (P (PP (Q PP
6、PP(PQ) P)Q) QQ) P(PP) ( 0QP) ( ( Q (Q (0 0)(QQ)(P Q) (PQ)QP)PP)PQ)PQ) (P Q)Q)(P PQ)Q)Q) (P Q)( P Q)PQ7.作真值表1，0) ，故成假赋值为(0， 0) ， ( 0， 1 ) ， ( 1 ， 1 )PQPQ(P Q) ( PQ)1. 证明 (P Q) ( Q R)R (P S) QR R Q PQ P P S SPPT，析取三段论PT，拒取式P，析取三段论2. 构造推理证明：(P(Q S) (R P) Q R S.前提： (P (Q S), R P,Q结论： R S证明：R附加前提 RP前提引入
7、P，假言推理 P(QS)前提引入 QS,假言推理 Q前提引入 S,假言推理3. 证明命题公式(PQ) (R Q) 与 (P R) Q 有相同的主析取范式证明 .方法 1(P Q) (RQ) ( P Q) ( R Q)(P R) Q (P R) Q3 证明命题公式(P Q) (R Q) 与 (P R) Q 有相同的主析取范式方法2(P Q) (RQ) ( P Q) ( R Q)P(P R)RQ PQ RQ P RQ PQ第 2 章谓词逻辑单项选择题1. 谓词公式x( P(x) yR(y) Q(x)中量词 x的辖域是()(A) x(P(x) yR(y) (B) P(x) (C) P(x) yR(y
8、) (D) Q(x)2. 谓词公式xA(x)xA(x)的类型是()(A) 永真式(B) 矛盾式(C) 非永真式的可满足式(D) 不属于(A),(B),(C)任何类型3 设个体域为整数集，下列公式中其真值为1 的是 ()(A) x y(x y 0)(B) y x(x y 0)(C) x y(x y 0)(D) x y(x y 0)4 设 L(x)： x 是演员，J(x)： x 是老师，老师”符号化为 ()(A)xL(x) A(x, y)(C)x y(L(x) J(y)A(x, y)5. 设个体域是整数集合，P 代表 x()(A) P 是真命题(B)(C) P 是假命题(D)A(x,y)： x佩服
9、 y. 那么命题“所有演员都佩服某些(B) x(L(x) y(J(y) A(x,y)(D) x y(L(x) J(y) A(x,y)y(x y) (x y 0)，下面4 个命题中为真的是P 是逻辑公式，但不是命题P 不是逻辑公式6. 表达式 x(P(x,y) Q(z) y(R(x,y)zQ(z) 中x的辖域是()(A) P(x,y)(B)R(x,y)(C)P(x,y) R(x,y) (D) P(x,y) Q(z)二、 填空题1. 设 个 体 域 D 1,2, 那 么 谓 词 公 式 xA(x) yB( y) 消 去 量 词 后 的 等 值 式 为.2. 设个体域D a,b,公式x(G(x) yH (x, y) 消去量词化为3. 设 N(x)： x 是自然数，Z(y)；y 是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为1. C； 2. B； 3 A； 4. B； 5. A 6. DH(b,b)1. A(1) A(2) (B(1) B(2) 2. (G(a) (H(a,a) H(a,b)(G(b) (H(b,a)3. x(N(x) Z(x) x(Z(x) N(x)