1数理逻辑习题 离散数学.docx

《1数理逻辑习题 离散数学.docx》由会员分享，可在线阅读，更多相关《1数理逻辑习题 离散数学.docx（7页珍藏版）》请在三一办公上搜索。

1、1数理逻辑习题 离散数学第1章 命题逻辑 一、单项选择题 1. 下列命题公式等值的是( ) (A)PQ,PQ(C)Q(PQ),QPQ(B)A(AB),A(AB)(D)A(AB),BP(QR),则使公式G取真值为1的P，2. 设命题公式G：Q，R赋值分别是 ( ) (A)0,0,0(B)0,0,1(C)0,1,0(D)1,0,0 3. 命题公式(PQ)Q为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 4 命题公式(PQ)的主析取范式是( ) (A) PQ (B) PQ (C) PQ (D) PQ 5. 前提条件PQ,P的有效结论是( ) (A) P (B) P

2、(C) Q (D)Q 6. 设P：我将去市里，Q：我有时间命题“我将去市里，仅当我有时间时”符号化为( ) (A)QP(B)PQ(C)PQ(D)PQ 二、填空题 1. 设命题公式G：P(QP)，则使公式G为假的真值指派是 2. 设P：我们划船，G：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为 3. 含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 4. 若命题变元P，Q，R赋值为(1,0,1)，则命题公式G(PQ)R)(PQ)的真值是 5. 命题公式P(PQ)的类型是 6. 设A，B为任意命题公式，C为重言式，若ACBC，那么AB是 式(重言式、矛盾式或可满足式) 三、解答化简

3、计算题 1. 判别下列语句是否命题？如果是命题，指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数. (3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人. 2.作命题公式(PQ)(PQ)P)的真值表，并判断该公式的类型 3. 试作以下二题：(1) 求命题公式(PQ)(PQ)的成真赋值 (2) 设命题变元P,Q,R的真值指派为(0,1,1),求命题公式 (PR)(PQ)(RQ)的真值 4. 化简下式命题公式(PQ)(PQ)P) 5. 求命题公式P(QP)(PQ)的主合取范式. 6. 求命题公式(PQ)(PQ)的主析取范式，并求该命题公式的成假赋值 7. 求

4、命题公式(PQ)(PQ)的真值表. 四、证明题 1. 证明(PQ)(QR)R(PS)S 2. 构造推理证明：(P(QS)(RP)QRS 3. 证明命题公式(PQ)(RQ)与(PR)Q有相同的主析取范式 参考答案 一、1. C 2. D 3. B 4. A 5. D 6. B 二、1. 1,0；1,1 2. (PQ)或PQ 3. (PQR)(PQR) 4. 0 5. 非永真式的可满足式 6. 重言 三、1. (1) 是命题，真值为1. (2) 是命题，真值为0. (3), (4)不是命题. (5) 是命题. 1. 判别下列语句是否命题？如果是命题，指出其真值. (1) 中国是一个人口众多的国家.

5、 (2) 存在最大的质数. (3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人. 2. 命题公式(PQ)(PQ)P)的真值表 (PQ)(PQ)P) P Q PQ PQ (PQ)P 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 原式为可满足式. 3. (1) (PQ)(PQ)(PQ)(PQ)(PP)QQ 可见(PQ)(PQ)的成真赋值为(0,1)，(1,1) (2) (PR)(PQ)(RQ) (01)(10)(01)0 4. (PQ)(PQ)P) (PQ)(PQ)P (PQP)(QPP) (PQ)0 PQ 5. P(QP)(PQ

6、) P(QP)(PQ) P(QPQ)(PPQ) P(00) P(QQ) (PQ)(PQ) 6. (PQ)(PQ)(PQ)(PQ) PQ 因为成真赋值是，故成假赋值为， 7. 作真值表 P Q 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 PQ P Q PQ (PQ)(PQ) 四、证明题 1. 证明(PQ)(QR)R(PS)S QR P R P Q T，析取三段论 PQ P P T，拒取式 PS P S ，析取三段论 2. 构造推理证明：(P(QS)(RP)QRS .前提：(P(QS),RP,Q 结论：RS 证明： R 附加前提

7、RP 前提引入 P ，假言推理 P(QS) 前提引入 QS ,假言推理 Q 前提引入 S ,假言推理 3. 证明命题公式(PQ)(RQ)与(PR)Q有相同的主析取范式 证明.方法1 (PQ)(RQ)(PQ)(RQ) (PR)Q(PR)Q 因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同 3 证明命题公式(PQ)(RQ)与(PR)Q有相同的主析取范式 方法2 (PQ)(RQ)(PQ)(RQ) PRQPQR (PR)QPRQPQR 因为它们的主合取范式相同，可知它们的主析取范式也相同 第2章谓词逻辑 一、 单项选择题 1. 谓词公式x(P(x)$yR(y)Q(x)中量词x

8、的辖域是( ) (A) x(P(x)$yR(y) (B) P(x) (C) P(x)$yR(y) (D) Q(x) 2. 谓词公式$xA(x)$xA(x)的类型是 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 不属于(A),(B),(C)任何类型 3 设个体域为整数集，下列公式中其真值为1的是( ) (A) x$y(x+y=0) (B) $yx(x+y=0) (C)xy(x+y=0) (D) $x$y(x+y=0) 4 设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( ) (A) xL(x)A(x,y) (B

9、) x(L(x)$y(J(y)A(x,y) (C) x$y(L(x)J(y)A(x,y) (D) x$y(L(x)J(y)A(x,y) 5. 设个体域是整数集合，P代表x$y(xy)(x-y0)，下面4个命题中为真的是( ) (A) P是真命题 (B) P是逻辑公式，但不是命题 (C) P是假命题 (D) 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. 设个体域D1,2,那么谓词公式$xA(x)yB(y)消去量词后的等值式为 . 2. 设个体域Da,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. D 二、1. A(1)A(2)(B(1)B(2) 2. (G(a)(H(a,a)H(a,b) (G(b)(H(b,a)H(b,b) 3. x(N(x)Z(x)$x(Z(x)N(x)