离散数学复习题

复习1：数理逻辑部分

一、 主要内容

(一) 命题逻辑基本概念 主要内容

1. 命题与联结词 命题与真值

命题：判断结果惟一的陈述句 命题的真值：判断的结果 真值的取值：真与假 真命题与假命题

例1 下列句子中那些是命题？ (1) 是有理数（假命题）. (2) 2 + 5 = 7（真命题）.

(3) 2050年元旦下大雪.（命题，但真值现在不知道） 命题分类：简单命题（也称原子命题）与复合命题 简单命题符号化

用小写英文字母 p, q, r, …, pi, qi, ri (i≥1)表示简单命题 用“1”表示真，用“0”表示假 例如，令

p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1

定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作?p，符号?称作否定联结词. 规定?p 为真当且仅当p为假.

定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”)称为p与q的合取式，记作p∧q，∧称作合取联结词. 规定p∧q为真当且仅当p与q同时为真.

定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词. 规定p∨q为假当且仅当p与q同时为假. 例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 令p:吴颖用功, q:吴颖聪明 (1) p?q (2) p?q (3) ?p?q

(4) 设p:张辉是三好生, q:王丽是三好生

p?q

(5) p:张辉与王丽是同学

(1)—(3) 说明描述合取式的灵活性与多样性 (4)—(5) 要求分清 “与” 所联结的成分. 例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数.

(4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年

解 (1) 令p:2是素数, q:4是素数, p?q (2) 令p:2是素数, q:3是素数, p?q (3) 令p:4是素数, q:6是素数, p?q

(4) 令p:小元元拿一个苹果, q:小元元拿一个梨 (p??q)?(?p?q)

(5) p:王小红生于 1975 年, q:王小红生于1976 年, (p??q)?(?p?q) 或 p?q (1)—(3) 为相容或

(4)—(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能

定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作p?q，并称p是蕴涵式的前件，q为蕴涵式的后件，?称作蕴涵联结词. 规定：p?q为假当且仅当p为真q为假.

(1) p?q 的逻辑关系：q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法： 若p，就q 只要p，就q p仅当q 只有q 才p

除非q, 才p 或 除非q，否则非p，…． (3) 当 p 为假时，p?q恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件

例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服.（p?q） (2) 因为天冷，所以小王穿羽绒服（p?q）. (3) 若小王不穿羽绒服，则天不冷.（p?q） (4) 只有天冷，小王才穿羽绒服.（q?p） (5) 除非天冷，小王才穿羽绒服.（q?p） (6) 除非小王穿羽绒服，否则天不冷（p?q）. (7) 如果天不冷，则小王不穿羽绒服.（q?p） (8) 小王穿羽绒服仅当天冷的时候.（q?p） 注意： p?q 与 ?q??p 等值（真值相同）

定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 规定p?q为真当且仅当p与q同时为真或同时为假.

p?q 的逻辑关系：p与q互为充分必要条件 例5 求下列复合命题的真值

(1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. （1） (2) 2 + 2 ＝ 4 当且仅当 3 是偶数.（0）

(3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起.（1） (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲.（0）

(5) 函数 f (x) 在 x0 可导的充要条件是 它在 x0 连续.（0） 小节

本小节中p, q, r, ? 均表示命题. 联结词集为{?, ?, ?, ?, ?}，?p, p?q, p?q, p?q, p?q为基本复合命题. 其中要特别注意理解p?q的涵义. 反复使用{?, ?, ?, ?, ?}中的联结词组成更为复杂的复合命题.

设 p: 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转

则复合命题 (p?q) ? ((r??s) ??p) 是假命题.

联结词的运算顺序：?, ?, ?, ?, ?, 同级按先出现者先运算.

2.命题公式及其赋值 命题变项与合式公式 命题变项 合式公式

合式公式的层次 公式的赋值 公式赋值 公式类型 真值表 命题常项

命题变项（命题变元）

常项与变项均用 p, q, r, ?, pi, qi, ri, ?, 等表示. 定义1.6 合式公式（简称公式）的递归定义：

(1) 单个命题变项和命题常项是合式公式, 称作原子命题公式 (2) 若A是合式公式，则 (?A)也是

(3) 若A, B是合式公式，则(A?B), (A?B), (A?B), (A?B)也是 (4) 只有有限次地应用(1)—(3) 形成的符号串才是合式公式 几点说明：

归纳或递归定义, 元语言与对象语言, 外层括号可以省去 定义1.7

(1) 若公式A是单个命题变项，则称A为0层公式. (2) 称 A 是 n+1(n≥0) 层公式是指下面情况之一： (a) A=?B, B 是 n 层公式；

(b) A=B?C, 其中B,C 分别为 i 层和 j 层公式， 且 n=max(i,j)；

(c) A=B?C, 其中 B,C 的层次及 n 同(b)；

(d) A=B?C, 其中B,C 的层次及 n 同(b)； (e) A=B?C, 其中B,C 的层次及 n 同(b). (3) 若公式A的层次为k, 则称A为k层公式.

例如 公式 A=p, B=?p, C=?p?q, D=?(p?q)?r, E=((?p?q) ?r) ?(?r?s)

分别为0层，1层，2层，3层，4层公式.

定义1.8 设p1, p2, … , pn是出现在公式A中的全部命题变项, 给p1, p2, … , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组 值为A的成假赋值. 几点说明：

1) A中仅出现 p1, p2, … , pn，给A赋值?=?1?2…?n是指 p1=?1, p2=?2, …, pn=?n, ?i=0或1, ?i之间不加标点符号 2) A中仅出现 p, q, r, …, 给A赋值?1?2?3…是指 p=?1, q=?2 , r=?3 …

3) 含n个命题变项的公式有2n个赋值.

如 000, 010, 101, 110是?(p?q)?r的成真赋值 001, 011, 100, 111是成假赋值.

定义1.9 将命题公式A在所有赋值下取值的情况列成表, 称作 A的真值表.

构造真值表的步骤:

(1) 找出公式中所含的全部命题变项p1, p2, ? , pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从00?0开始, 按 二进制加法, 每次加1, 直至11?1为止. (2) 按从低到高的顺序写出公式的各个层次.

(3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.

例6 写出下列公式的真值表, 并求它们的成真赋值和成假 赋值:

(1) (p?q) ??r (2) (q?p) ?q?p (3) ? (?p?q) ?q 解：(1) A = (p?q) ??r p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 p?q 0 0 1 1 1 1 1 1 ?r 1 0 1 0 1 0 1 0 (p?q)??r 1 1 1 0 1 0 1 0 成真赋值:000,001,010,100,110; 成假赋值:011,101,111

(2) B＝(q?p)?q?p q?p p q 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 (q?p)?q (q?p)?q?p 成真赋值:00,01,10,11; 无成假赋值 (3) C＝? (?p?q)?q的真值表 p q ?p 0 0 0 1 1 0 1 1 1 1 0 0 ?p?q 1 1 0 1 (?p?q) 0 0 1 0 ? (?p?q)?q 0 0 0 0 成假赋值:00,01,10,11; 无成真赋值 定义1.10

(1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式; (2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式; (3) 若A不是矛盾式, 则称A是可满足式.

由例1可知, (p?q) ??r, (q?p) ?q?p, ? (?p?q) ?q 分别为非重言式的可满足式, 重言式, 矛盾式 注意：重言式是可满足式，但反之不真.（即可满足式包括重言式和非重言式） 真值表的用途:

求出公式的全部成真赋值与成假赋值, 判断公式的类型

(二) 命题逻辑等值演算 主要内容

1. 等值式与基本的等值式

定义2.1 若等价式A?B是重言式，则称A与B等值，记作A?B，并称A?B是等值式

几点说明：

? 定义中，A, B, ?均为元语言符号 ? A或B中可能有哑元出现.

例如 (p?q) ? ((?p?q)?(?r?r)) r为左边公式的哑元. ? 用真值表可检查两个公式是否等值 请验证：

p?(q?r) ? (p?q) ?r

p?(q?r) 不与 (p?q) ?r 等值 例1 判断下列各组公式是否等值: (1) p?(q?r) 与 (p?q) ?r

重复这个过程, 直到所有简单析取式都是长度为n的极 大项为止

(3) 消去重复出现的极大项, 即用Mi代替Mi?Mi (4) 将极大项按下标从小到大排列

例6 (1) 求公式 A=(p??q)?r的主析取范式和主合取范式 解 (p??q)?r

? (p?q)?r （析取范式） ①

(p?q) ? (p?q)?(?r?r)

? (p?q??r)?(p?q?r)

? m6?m7 ② r

? (?p?p)?(?q?q)?r

? (?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5?m7 ③ ②, ③代入①并排序，得

(p??q)?r ? m1?m3?m5? m6?m7 （主析取范式） (p??q)?r

? (p?r)?(q?r) （合取范式） ④ p?r

? p?(q??q)?r

? (p?q?r)?(p??q?r) ? ⑤

q?r ? (p??p)?q?r

? (p?q?r)?(?p?q?r)

? M0?M4 ⑥ ⑤, ⑥代入④ 并排序，得

(p??q)?r ? M0?M2?M4 （主合取范式） 1.求公式的成真成假赋值

设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值

例如 (p??q)?r ? m1?m3?m5? m6?m7 成真赋值为 001, 011, 101, 110, 111， 成假赋值为 000, 010, 100.

类似地，由主合取范式也立即求出成假赋值和成真赋值. 2. 判断公式的类型

设A含n个命题变项.

A为重言式 ? A的主析取范式含全部2n个极小项

? A的主合取范式不含任何极大项, 记为1. A为矛盾式 ? A的主合析取范式含全部2n个极大项

M0?M2

? A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式

? A的主析取范式中至少含一个、但不是全 部极小项

? A的主合取范式中至少含一个、但不是全 部极大项. 例7 用主析取范式判断公式的类型:

(1) A? ?(p?q)?q (2) B? p?(p?q) (3) C? (p?q)?r 解

(1) A ? ?(? p?q)?q ? ( p??q)?q ? 0 矛盾式 (2) B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式 (3) C ? ?(p?q)?r ? (?p??q)?r

? (?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r)

? m0?m1?m3? m5?m7 非重言式的可满足式 3. 判断两个公式是否等值

例8 用主析取范式判以下每一组公式是否等值 ⑴ p?(q?r) 与 (p?q)?r ⑵ p?(q?r) 与 (p?q)?r

解 p?(q?r) = m0?m1?m2?m3? m4?m5? m7

(p?q)?r = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m1?m3? m4?m5? m7 显见，⑴中的两公式等值，而⑵的不等值. 4. 解实际问题

例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下 述条件:

(1) 若A去, 则C必须去; (2) 若B去, 则C不能去;

(3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?

解 记 p:派A去, q:派B去, r:派C去

(1) p?r, (2) q??r, (3) (p??q)?(?p?q) 求下式的成真赋值

A=(p?r)?(q??r)?((p??q)?(?p?q)) 求A的主析取范式

A=(p?r)?(q??r)?((p??q)?(?p?q)) ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q))

? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ? (p??q?r)?(?p?q??r) 成真赋值:101,010

结论: 方案1 派A与C去, 方案2 派B去 由主析取范式确定主合取范式

例10 设A有3个命题变项, 且已知A= m1?m3?m7, 求A的主合取 范式.

解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取 范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示, 它 们恰好是A的主合取范式的极大项的下角标, 故 A ? M0?M2?M4?M5?M6 由主合取范式确定主析取范式 用真值表确定主范式

4. 联结词完备集

定义2.6 称F:{0,1}n? {0,1} 为n元真值函数.

{0,1}n={00…0, 00…1, …, 11…1}，包含 个长为n的0,1符号串. 共有 个n元真值函数. 1元真值函数 p

1元真值函数

p F0(1)F1(1)F2(1)F3(1) 0 0 0 1 1 1 0 1 0 1

2元真值函数 p q 0 0 0 1 1 0 1 1 p q 0 0 0 1 1 0 1 1 F0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 F8(2)F9(2)(2)F10(2) (2)F11F12(2)F13(2)F14(2)F151 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 任何一个含n个命题变项的命题公式A都对应惟一的一个n元

真值函数 F , F 恰好为A的真值表. 等值的公式对应的真值函数相同. 例如：p?q, ?p?q 都对应

定义2.7 设S是一个联结词集合，如果任何n(n?1) 元真值函 数都可以由仅含S中的联结词构成的公式表示，则称S是联结 词完备集

若S是联结词完备集, 则任何命题公式都可由S中的联结词表示 定理2.6 S = {?, ?, ?}是联结词完备集 证明 由范式存在定理可证 推论 以下都是联结词完备集

(1) S1 = {?, ?, ?, ?} (2) S2 = {?, ?, ?, ?, ?} (3) S3 = {?, ?} (4) S4 = {?, ?} (5) S5 = {?, ?} 证明

(1),(2) 在联结词完备集中加入新的联结词后仍为完备集 (3) A?B ? ?(?A??B) (4) A?B ? ?(?A??B) (5) A?B??A?B

{?,?,?,?}不是联结词完备集, 0不能用它表示

它的子集{?},{?},{?},{?},{?,?},{?,?,?}等都不是

定义2.8 设 p, q 为两个命题, ?(p?q)称作p与q的与非式, 记作 p?q, 即 p?q ? ?(p?q), ?称为与非联结词

?(p?q) 称作 p 与 q 的或非式, 记作 p?q, 即 p?q ? ?(p?q), ? 称为或非联结词

定理2.7 {?}与{?}为联结词完备集. 证明 {?, ?, ?}为完备集

?p ? ?p??p ? ?(p?p) ? p?p p?q ? ?(?p??q) ? ?p??q ? (p?p)?(q?q) p?q ? ??(p?q) ? ?(p?q) ? (p?q)?(p?q) 得证{?}为联结词完备集. 对{?}类似可证

5. 可满足性问题与消解法

不含任何文字的简单析取式称作空简单析取式,记作?. 规定?是不可满足的.

约定:简单析取式不同时含某个命题变项和它的否定

S:合取范式, C:简单析取式, l:文字, ?:赋值, 带下角标或 ? 文字l的补lc:若l=p,则lc=?p;若l=?p,则lc=p. S?S?:S是可满足的当且仅当S? 是可满足的

定义2.9 设C1=l?C1?, C2=lc?C2?, C1?和C2?不含l和lc, 称C1??C2?为 C1和C2(以l和lc为消解文字)的消解式或消解结果, 记作 Res(C1,C2)

例如, Res(?p?q?r, p?q??s)= q?r??s 定理2.8 C1?C2?Res(C1,C2)

证 记C= Res(C1,C2)=C1??C2?, 其中l和lc为消解文字, C1=l?C1?, C2=lc?C2?, 且

C1?和C2?不含l和lc.

假设C1?C2是可满足的, ?是它的满足赋值, 不妨设?(l)=1. C2必含有文字l? ?l, lc且?(l? )=1. C中含有l?, 故?满足C.

反之, 假设C是可满足的, ?是它的满足赋值. C必有l? 使得 ?(l? )=1, 不妨设C1?含l?, 于是?满足C1. 把扩张到l(和lc)上: 若l=p, 则令?(p)=0; 若lc=p, 则令?(p)=1. 恒有?(lc)=1, 从而? 满足C2. 得证C1?C2是可满足的.

注意: C1?C2与Res(C1,C2)有相同的可满足性, 但不一定等值. 定义2.10 设S是一个合取范式, C1,C2,?,Cn是一个简单析取式 序列. 如果对每一个i(1?i?n), Ci是S的一个简单析取式或者是 Res(Cj,Ck)(1?j

定理2.9 一个合取范式是不可满足的当且仅当它有否证.

例11 用消解规则证明S=(?p?q)?(p?q??s)?(q?s)??q是不可 满足的.

证 C1=?p?q, C2= p?q??s, C3=Res(C1,C2)=q??s, C4=q?s,

C5=Res(C3,C4)=q, C6=?q, C7=Res(C5,C6)=?, 这是S的否证. 消解算法

输入: 合式公式A

输出: 当A是可满足时, 回答“Yes”; 否则回答“No”. 1. 求A的合取范式S

2. 令S0??, S2??, S1?S的所有简单析取式 3. For C1?S0和C2?S1

4. If C1, C2可以消解 then

5. 计算C?Res(C1,C2) 6. If C=? then

7. 输出“No”, 计算结束 8. If C?S0且C? S1 then 9. S2?S2?{C} 10. For C1?S1, C2?S1且C1?C2 11. If C1, C2可以消解 then

12. 计算C?Res(C1,C2) 13. If C=? then

14. 输出“No”, 计算结束 15. If C?S0且C? S1 then 16. S2?S2?{C} 17. If S2=? then

18. 输出“Yes”, 计算结束

19. Else S0?S0?S1, S1?S2, S2??, goto 3

例12 用消解算法判断下述公式是否是可满足的: p?(p?q)?(p??q)?(q??r)?(q?r) 解 S= p?(p?q)?(p??q)?(q??r)?(q?r)

循环1 S0=?, S1={p, p?q, p??q, q??r, q?r}, S2=?

Res(p?q, p??q)=p

Res(p??q, q??r)=p??r Res(p??q, q?r)= p?r Res(q??r, q?r)=q S2={p?r, p?r, q}

循环2 S0={p, p?q, p??q, q??r, q?r}, S1={p?r, p?r, q}, S2=?

Res(p??q, q)=p Res(q??r, p?r)=p?q

Res(q?r, p??r)=p?q Res(p?r, p??r)=p S2=? 输出“Yes”

第一章 习题课 主要内容

? 命题、真值、简单命题与复合命题、命题符号化 ? 联结词?, ?, ?, ?, ?及复合命题符号化 ? 命题公式及层次 ? 公式的类型 ? 真值表及应用 基本要求

? 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 ? 会求复合命题的真值

? 深刻理解合式公式及重言式、矛盾式、可满足式等概念

? 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型 1. 将下列命题符号化

(1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员.

(4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了.

(6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交通阻塞. 提示：

分清复合命题与简单命题 分清相容或与排斥或

分清必要与充分条件及充分必要条件

答案: (1) 是简单命题 (2) 是合取式

(3) 是析取式（相容或）(4) 是析取式（排斥或） 设 p: 交通阻塞，q: 他迟到

(5) p?q, (6) ?p??q或q?p (7) ?q??p 或p?q, (8) q?p或?p??q

(9) p?q 或?p??q 可见(5)与(7)，(6)与(8) 相同（等值） 2. 设 p : 2是素数

q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值

(1) (p?q)?r （0） (2) (q?r)?(p??r) （1） (3) (q?r)?(p??r) （0） (4) (q?p)?((p??r)?(?r??q)) （0） 3. 用真值表判断下面公式的类型 (1) p?r??(q?p)

(2) ((p?q) ?(?q??p)) ?r (3) (p?q) ?(p?r) (1) p?r??(q?p) p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 q?p 1 1 0 0 1 1 1 1 ?(q?p) p?r??(q?p) 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 矛盾式

(2) ((p?q) ?(?q??p)) ?r

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

p?q 1 1 1 1 0 0 1 1

?q??p 1 1 1 1 0 0 1 1

((p?q) ?(?q??p)) ?r

1 1 1 1 1 1 1 1

永真式

(3) (p?q) ?(p?r) 非永真式的可满足式

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 p?q 1 1 1 1 0 0 1 1 p?r 1 1 1 1 0 1 0 1 (p?q) ?(p?r) 1 1 1 1 1 0 0 1 第二章 习题课 主要内容

? 等值式与等值演算

? 基本等值式（16组，24个公式） ? 主析取范式与主合取范式 ? 联结词完备集 ? 消解法

? 深刻理解等值式的概念

? 牢记基本等值式的名称及它们的内容

? 熟练地应用基本等值式及置换规则进行等值演算

? 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念

? 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解

简单析取式与极小项的关系

? 熟练掌握求主范式的方法（等值演算、真值表等）

? 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等

值

? 会将公式等值地化成指定联结词完备集中的公式 ? 会用命题逻辑的概念及运算解决简单的应用问题 ? 掌握消解规则及其性质

? 会用消解算法判断公式的可满足性

1. 设A与B为含n个命题变项的公式，判断下列命题是否为真？ (1) A?B当且仅当A与B有相同的主析取范式 (2) 若A为重言式，则A的主合取范式为0 (3) 若A为矛盾式，则A的主析取范式为1 (4) 任何公式都能等值地化成{?, ?}中的公式 (5) 任何公式都能等值地化成{?, ?, ?}中的公式 说明:

(2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主合析范式不含任何极小项, 为0.

(4) {?, ?}不是完备集，如矛盾式不能写成{?, ?}中的公式. (5) {?, ?}是完备集. 2. 判断下列公式的类型: (1) (p?q)?(?q??p) 解 用等值演算法求主范式

(p?q)?(?q??p)

? ?(?p?q)?(q??p) ? (p??q)?(q??p)

? (p??q)?(?p?q)?(p?q)?(?p??q)

? m2 ? m1 ? m3 ? m0

? m0 ? m1 ? m2 ? m3 主析取范式 ? 1 主合取范式 重言式

(2) ?(p?q)?q

解 用等值演算法求公式的主范式 ?(p?q)?q

? ?(?p?q)?q ? p??q?q

? 0 主析取范式 ? M0 ? M1 ? M2 ? M3 主合取范式 矛盾式

(3) (p?q)??p

解 用等值演算法求公式的主范式 (p?q)??p ? (?p?q)??p ? ?p

? (?p??q)?(?p?q)

? m0 ? m1 主析取范式 ? M2 ? M3 主合取范式 非重言式的可满足式

3．已知命题公式A中含3个命题变项p, q, r，并知道它的成真 赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对 应的真值函数.

解：A的主析取范式为m1 ? m2 ? m7

A的主合取范式为M0 ? M3 ? M4 ? M5 ? M6 p q r F p q r F 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1

4．将A = (p??q)?r改写成下述各联结词集中的公式: (1) {?, ?, ?} (2) {?, ?} (3) {?, ?} (4) {?, ?} (5) {?} (6) {?} 解

(1) (p??q)?r ? (?p??q)?r

(2) (p??q)?r ? ?(p?q)?r (3) (p??q)?r ? (?p??q)?r

? ?(?(?p??q)??r) (4) (p??q)?r ? ?(?(p??q)??r)

? ?((p??q)??r) (5) (p??q)?r ? ?(p?q)?r

? (p?q)?r ? ? ?((p?q)?r)

? ((p?q)?r)?((p?q)?r) (6) (p??q)?r ?(?p??q)?r

? ?(?(?p??q)??r) ? (?p??q)??r

? ((p?p)?(q?q)?(r?r) 说明：答案不惟一

5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选 派一些人出国学习. 选派必须满足以下条件： (1) 若赵去，钱也去.

(2) 李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人. (4) 孙、李两人同去或同不去. (5) 若周去，则赵、钱也去.

用等值演算法分析该公司如何选派他们出国？ 解此类问题的步骤： 1.设简单命题并符号化 2. 用复合命题描述各条件

3. 写出由复合命题组成的合取式

4. 将合取式成析取式（最好是主析取范式） 5. 求成真赋值, 并做出解释和结论 解

1. 设简单命题并符号化

设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去

2. 写出复合命题

(1) 若赵去，钱也去 p?q (2) 李、周两人中至少有一人去 s?u

(3) 钱、孙两人中去且仅去一人 (q??r)?(?q?r) (4) 孙、李两人同去或同不去 (r?s)?(?r??s) (5) 若周去，则赵、钱也去 u?(p?q) 3. 设(1)—(5)构成的合取式为A

A = (p?q)?(s?u)?((q??r)?(?q?r))? ((r?s)?(?r??s))?(u?(p?q))

4. 化成析取式

A ? (?p??q?r?s??u)?(p?q??r??s?u)

结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去） A ? (?p?q)?((q??r)?(?q?r))? (s?u)?(?u?(p?q))?

((r?s)?(?r??s)) B1=(?p?q)?((q??r)?(?q?r))

? ((?p?q??r)?(?p??q?r)?(q??r)) （分配律） B2=(s?u)?(?u?(p?q))

? ((s??u)?(p?q?s)?(p?q?u)) （分配律） B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u) 再令 ((r?s)?(?r??s))=B3，则

B1?B2?B3 ? (?p??q?r?s??u)?(p?q??r??s?u)

6. 构造公式A=(p?q)?( ?q?r)? (?p?q)??r的否证, 从而证明 它是矛盾式. 解 消解序列:

① p?q A的简单析取式 ② ?p?q A的简单析取式 ③ q ①,②消解 ④ ?q?r A的简单析取式 ⑤ ?r A的简单析取式 ⑥ ?q ④,⑤消解 ⑦ ? ③,⑥消解

这是A的一个否证, 从而证明A是矛盾式. 7. 用消解法判断下述公式是否是可满足的: (p??q)?(q??r)?(?q??r) 解 S=(p??q)?(q??r)?(?q??r)

第1次循环 S0=?,S1={p??q, q??r, ?q??r}, S2=? p??q, q??r 消解得到p??r q??r, ?q??r消解得到?r S2={p??r,?r}

第2次循环 S0={p??q, q??r, ?q??r},S1={p??r,?r}, S2=? S2=?

输出“Yes”,计算结束.

(三) 命题逻辑推理理论 二、

结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去） A ? (?p?q)?((q??r)?(?q?r))? (s?u)?(?u?(p?q))?

((r?s)?(?r??s)) B1=(?p?q)?((q??r)?(?q?r))

? ((?p?q??r)?(?p??q?r)?(q??r)) （分配律） B2=(s?u)?(?u?(p?q))

? ((s??u)?(p?q?s)?(p?q?u)) （分配律） B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u) 再令 ((r?s)?(?r??s))=B3，则

B1?B2?B3 ? (?p??q?r?s??u)?(p?q??r??s?u)

6. 构造公式A=(p?q)?( ?q?r)? (?p?q)??r的否证, 从而证明 它是矛盾式. 解 消解序列:

① p?q A的简单析取式 ② ?p?q A的简单析取式 ③ q ①,②消解 ④ ?q?r A的简单析取式 ⑤ ?r A的简单析取式 ⑥ ?q ④,⑤消解 ⑦ ? ③,⑥消解

这是A的一个否证, 从而证明A是矛盾式. 7. 用消解法判断下述公式是否是可满足的: (p??q)?(q??r)?(?q??r) 解 S=(p??q)?(q??r)?(?q??r)

第1次循环 S0=?,S1={p??q, q??r, ?q??r}, S2=? p??q, q??r 消解得到p??r q??r, ?q??r消解得到?r S2={p??r,?r}

第2次循环 S0={p??q, q??r, ?q??r},S1={p??r,?r}, S2=? S2=?

输出“Yes”,计算结束.

(三) 命题逻辑推理理论 二、

本文来源：https://www.bwwdw.com/article/hb36.html