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

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),BØP®(QÙR),则使公式G取真值为1的P，2. 设命题公式G：Q，R赋值分别是 ( ) (A)0,0,0(B)0,0,1(C)0,1,0(D)1,0,0 3. 命题公式(PÚQ)®Q为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 4 命题公式Ø(P®Q)的主析取范式是( ) (A) PÙØQ (B) ØPÙQ (C) ØPÚQ (D) PÚØQ 5. 前提条件P®ØQ,P的有效结论是( ) (A) P (B) ØP (C) Q (D)ØQ 6. 设P：我将去市里，Q：我有时间命题“我将去市里，仅当我有时间时”符号化为( ) (A)Q®P(B)P®Q(C)P«Q(D)ØPÚØQ 二、填空题 1. 设命题公式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是 式(重言式、矛盾式或可满足式) 三、解答化简计算题 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. 求命题公式Ø(P®Q)Ù(P®ØQ)的主析取范式，并求该命题公式的成假赋值 7. 求命题公式(PÙQ)Ù(ØPÚØQ)的真值表. 四、证明题 1. 证明(P®Q)Ù(ØQÚR)ÙØRÙ(PÚØS)ÞØS 2. 构造推理证明：(P®(Q®S)Ù(R®P)ÙQÞR®S 3. 证明命题公式(P®Q)Ú(R®Q)与(PÙR)®Q有相同的主析取范式 参考答案 一、1. C 2. D 3. B 4. A 5. D 6. B 二、1. 1,0；1,1 2. Ø(PÙQ)或ØPÚØQ 3. (PÙQÙR)Ú(PÙQÙØR) 4. 0 5. 非永真式的可满足式 6. 重言 三、1. (1) 是命题，真值为1. (2) 是命题，真值为0. (3), (4)不是命题. (5) 是命题. 1. 判别下列语句是否命题？如果是命题，指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数. (3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人. 2. 命题公式(P®Q)®(PÙQ)ÚP)的真值表 (P®Q)®(PÙQ)ÚP) P Q P®Q PÙQ (PÙQ)Ú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) (PÚØQ)®(PÙQ)Û(ØPÙQ)Ú(PÙQ)Û(ØPÚP)ÙQÛQ 可见(PÚØQ)®(PÙQ)的成真赋值为(0,1)，(1,1) (2) (P«R)Ù(ØP®ØQ)Ú(ØR®Q) Û(0«1)Ù(1®0)Ú(0®1)Û0 4. (PÙQ)Ú(ØPÙØQ)ÙP) Û(PÙQ)Ú(ØPÙØQ)ÙP Û(PÙQÙP)Ú(ØQÙØPÙP) Û(PÙQ)Ú0 ÛPÙQ 5. P®(Q®P)Ù(ØPÙQ) ÛØPÚ(ØQÚP)Ù(ØPÙQ) ÛØPÚ(ØQÙØPÙQ)Ú(PÙØPÙQ) ÛØPÚ(0Ù0) ÛØPÚ(QÙØQ) Û(ØPÚQ)Ù(ØPÚØQ) 6. Ø(P®Q)Ù(P®ØQ)Û(PÙØQ)Ù(ØPÚØQ) ÛPÙØQ 因为成真赋值是，故成假赋值为， 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 PÙQ ØP ØQ ØPÚØQ (PÙQ)Ù(ØPÚØQ) 四、证明题 1. 证明(P®Q)Ù(ØQÚR)ÙØRÙ(PÚØS)ÞØS ØQÚR P ØR P ØQ T，析取三段论 P®Q P ØP T，拒取式 PÚØS P ØS ，析取三段论 2. 构造推理证明：(P®(Q®S)Ù(R®P)ÙQÞR®S .前提：(P®(Q®S),R®P,Q 结论：R®S 证明： R 附加前提 R®P 前提引入 P ，假言推理 P®(Q®S) 前提引入 Q®S ,假言推理 Q 前提引入 S ,假言推理 3. 证明命题公式(P®Q)Ú(R®Q)与(PÙR)®Q有相同的主析取范式 证明.方法1 (P®Q)Ú(R®Q)Û(ØPÚQ)Ú(ØRÚQ) ÛØ(PÙR)ÚQÛ(PÙR)®Q 因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同 3 证明命题公式(P®Q)Ú(R®Q)与(PÙR)®Q有相同的主析取范式 方法2 (P®Q)Ú(R®Q)Û(ØPÚQ)Ú(ØRÚQ) ÛØPÚØRÚQÛØPÚQÚØR (PÙR)®QÛØPÚØRÚQÛØPÚQÚØR 因为它们的主合取范式相同，可知它们的主析取范式也相同 第2章谓词逻辑 一、 单项选择题 1. 谓词公式"x(P(x)Ú$yR(y)®Q(x)中量词"x的辖域是( ) (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) $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(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( ) (A) "xL(x)®A(x,y) (B) "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(x<y)®(x-y<0)，下面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)