离散数学讲义 武汉科技大学计算机学院
(P∨Q∨R)∧（P∨Q∨乛R）∧（P∨乛Q∨R）∧（P∨乛Q∨乛R）∧
(乛P∨Q∨R)∨（乛P∨Q∨乛R）?主合取范式
G2（P，Q）?（P→Q）∧（P∧Q）?（乛P∨Q）∧P∧Q?（P∧Q）?主析取范式 G2（P，Q）?乛（乛G2(P，Q)）?乛（(P∨乛Q)∨(乛P∨Q)∨(乛P∨乛Q)）?
（乛P∨Q）∧（P∨乛Q）∧（P∨Q）?
（P∨Q）∧（乛P∨Q）∧（P∨乛Q）?主合取范式
从上可以看出，两个公式的主析取，主合取范式安全不同。
例3.5 判断下面公式的类型（重言式，矛质式，可满足式） （1）（P→Q）→（乛Q→乛P） （2）（P←→ Q）→乛（P∨Q） （北师大2000年考研试题）
解 判断一个公式是否是重方式、矛盾式，可满足公式，可采用三种方式：(1)真值表技术；(2)公式等值演算；(3)求主析取，主合取范式。下面分别采用三种方法：
方法1 真值表技术。
建立公式(1)，(2)的真值表如表2．6所示。
表2．6 P Q （P→Q）∧（乛Q→乛P） （P←→ Q）→乛（P∨Q） 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 由上述真值可知，公式(1)是重言式，公式(2)是可满足式。 方法2 公式等值演算。
① （P→Q）→（乛Q→乛P）?（P←→ Q）→乛（P∨Q）?
乛（乛P∨Q）∨（乛P∨Q）?1
所以公式①是永真式（重言式）。
方法3 求公式的主析取、主合取范式。 （P←→ Q）→乛（P∨Q）?乛（P←→ Q）∨乛（P∨Q）? 乛（P→Q）∨乛（Q→P）∨（乛P∧乛Q）?
乛（乛P∨Q）∨乛（乛Q∨P）∨（乛P∧乛Q）?
（P∧乛Q）∨（乛P∧Q）∨（乛P∧乛Q）?主析取范式? 乛（乛((P←→ Q)→乛(P∨Q))）?乛（P∧Q）?（乛P∨乛Q）?主合取范式 显然公式②所对应的主析取范式不包括所有的极小项，所以不是重言式，公式②所对应的主合取范式不包括所有的极大项，所以不是矛盾式，因此，②仅是可满足式。
例3.6 符号化下列命题，并证明其结论：一公安人员审查一件盗窃案，已知事实如下： （1）张平或王磊盗窃了机房的计算机一台；
（2）若张平盗窃了计算机，则作案时间不可能发生在午夜之前； （3）若王磊的证词正确，则午夜时机房里的灯未灭； （4）若王磊的证词不正确，则作案时间发生在午夜之前； （5）午夜时机房灯光灭了。
问：盗窃计算机的是张平？王磊？
－3.11－
离散数学讲义 武汉科技大学计算机学院
分析 首先将事实符号化： 设P：张平盗窃了计算机； Q：王磊盗窃了计算机； R：作案时间发生在午夜前； S：王磊的证词正确； T：午夜时灯光灭了。 则前提可符号化为：
P∨Q，P → 乛R，S → 乛T，乛S → R，T 证明的结论为P或Q。
证明 （1）T P （2）S → 乛T P （3）乛S T，(1)，(2)，I （4）乛S → R P （5）R T，(3)，(4)，I （6）P → 乛R P （7）乛P T，(5)，(6)，I （8）P∨Q P （9）Q T，(7)，(8)，I 此结论说明是王磊盗窃了机房的计算机。
例3.7 符号化下列命题，并用演译法加以证明：如果6是偶数，则2不能整除7；或者5不是素数，或2整除7；5是素数。因此，6是奇数。
解 首先将上述事实符号化 设P：6是偶数 Q：2能整除7 R：5是素数 则命题可符号化为
P→乛Q，乛R∨Q，R?乛P 证明 （1）乛R∨Q P （2）R P （3）Q T，(1)，(2)，I （4）P→乛Q P （5）乛P T，(3)，(4)，I
说明 本例的证明十分简单，但该例却说明了一个十分重要的情况： 该列的结论是一个错误的结论。我们不能误认为该推导是错误的，或认为该前提不能逻辑地蕴涵结论。实际上，在逻辑推理中，完全允许在错误的假设下逻辑推导出一个错误的结论。一问题正是在错误的前提下（如6是偶数，则2不能整除7），导致了错误的结论，它们之间仍有逻辑蕴涵关系。
例3.8 符号化下列句子，并用反证法（归谬法）加以证明。 （1）如果A因病缺了许多课，那么也中学考试不及格； （2）如果A中学考试不及格，则他没有知识； （3）如果A读了许多书，则他有知识。
（4）所以，A没有缺很多课或没有读很多书。
－3.12－
离散数学讲义 武汉科技大学计算机学院
解 首先将事实符号化： 设P：A因病缺了许多刘； Q：他中学考试及格； R：他有知识； S：他读了许多书。 则上述句子可符号化为：
P→乛Q，乛Q→乛R，S→R?乛P∨乛S
证明 采用归谬法就是将结论的否定作为附加前提加入到前提集合之中，导致与已知条件的矛盾。
（1）乛（乛P∨乛S） P(附加前提) （2）P∧S T，(1)，(2)，E （3）P T，(2)，I （4）S T，(2)，I （5）P→乛Q P （6）乛Q T，(3)，(5)，I （7）S→R P （8）R T，(4)，(7)，I （9）乛Q→乛R P （10）Q T，(8)，(9)，I （11）Q→乛Q T，(6)，(10)，I
所以，由归谬法知：P→乛Q，乛Q→乛R，S→R?乛P∨乛S。
例3.9 设前提集合为P?{P∨Q，P→R，Q→S}，G?S∨R，证明P?G。 解 对于该题分别有用三种证明方法加以证明。 证法1 直接证明法。 （1）P∨Q P （2）乛P→Q T，(1)，E （3）Q→S P （4）乛P→S T，(2)，(3)，I （5）乛S→P T，(4)，E （6）P→R P （7）乛S→R T，(5)，(6)，I （8）S∨R T，(7)，E 证法2 带CP规则的直接证明法。
因G? S∨R?乛S→R，为此，可将乛S作为附加前提加入前提集合中，如能证明P，乛S?R，则由CP规则知：P?乛S→R即P?S∨R。
（1）乛S P(附加前提) （2）Q→S P （3）乛Q T，(1)，(2)，I （4）P∨Q P （5）P T，(3)，(4)，I （6）P→R P （7）R T，(5)，(6)，I
（8）乛S→R （9）S∨R
CP，(1)，(7) T，(8)，E
－3.13－
离散数学讲义 武汉科技大学计算机学院
证法3 归谬法。 （1）乛（S∨R） （2）乛S∧乛R （3）乛S （4）乛R （5）P→R （6）乛P （7）Q→S （8）乛Q （9）乛P∧乛Q （10）乛（P∨Q） （11）P∨Q
（12）（P∨Q）∧乛(P∨Q)
例3.10 证明P→(Q→S)是{P→(Q→R)，R→(Q→S)}的逻辑结果。
分析 对于这类问题(结论是蕴涵的形式)，采用带CP规则的直接证明法最方便。 （1）P
（2）P→（Q→R） （3）Q→R （4）R→（Q→S） （5）Q→（Q→S） （6）Q （7）Q→S （8）P→（Q→S）
例3.11 一个排队线路，输入为A，B，C，其输出分别为FA，FB，FC，在同一时间内只能有一个信号通过。如果同时有两个或两个以上信号通过时，则按A，B，C的顺序输出，例如：A，B，C同时输入时，只能A有输出，写出FA，FB，FC的逻辑表达式，并化成全功能集{↓}中的表达式。
解 设P：A输入 Q：B输入 R：C输入
由提所给的条件，易写出FA，FB，FC的真值表如表2.7所示。
－3.14－
P(附加前提) T，(1)，E T，(2)，I T，(2)，I P
T，(4)，(5)，I P
T，(3)，(7)，I T，(6)，(8)，I T，(9)，E P
T，(10)，(11)，I
P(附加前提) P
T(1)，(2)，I P
T，(3)，(4)，I P(附加前提) T，(5)，(6)，I CP，(1)，(7)
离散数学讲义 武汉科技大学计算机学院
表2.7 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 FA 0 0 0 0 1 1 1 1 FB 0 0 1 1 0 0 0 0 FC 0 1 0 0 0 0 0 0 由真值表知：它们的主析取范式分别为：
FA?（P∧Q∨R）∨（P∧Q∧乛R）∨（P∧乛Q∧R）∨（P∧乛Q∧乛R）?
（（P∧Q）∧（R∨乛R））∨（（P∧乛Q）∧（R∨乛R））? （P∧Q）∨（P∧乛Q）? P∧（Q∨乛Q）? P ∧ 1? P ? 乛乛（P∨P）?乛（P↓P）?（P↓P）↓（P↓P）
FB＝（乛P∧Q∧乛R）∨（乛P∧Q∧R）?（乛P∧Q）∧（乛R∨R）? 乛P∧Q?乛乛（乛P∧Q）?乛（P∨乛Q）?P↓乛Q?P↓（Q↓Q）
FC＝（乛P∧乛Q∧R）?乛（P∨Q）∧R?（P↓Q）∧R?乛乛（P↓Q）∧乛乛R?
乛（乛（P↓Q）∨乛R）?乛（P↓Q）↓乛R?（（P↓Q）↓（P↓Q））↓（R↓R）
例3.12 某勘探队有3名队员，有一天取得一块矿样，3人的判断如下： 甲说：这不是铁，也不是铜； 乙说：这不是铁，是锡； 丙说：这不是锡，是铁。
经实验鉴定后发现，其中一人两个判断正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。
分析 设P：矿样是铁；
Q：矿样是铜； R：矿样是锡。
则上述情况可能有：
F1：甲全对、乙对一半，丙全错； F2：甲全对、乙全错、丙对一半； F3：甲对一半、乙全对、丙全错； F4：甲对一半、乙全错、丙全对； F5：甲全错、乙全对、丙对一半； F6：甲全错、乙对一半、丙全对。
由于F＝（一人全对）∧（一人对一半）∧（一人全错），所以，上述F1，F2，?，F6
这六种情况应有一种发生，即：
F＝F1∨F2∨F3∨F4∨F5∨F6＝1
根据命题的表示：F1，F2，?，F6中分别表示如下：
F1＝（乛P∧乛Q）∧（（乛P∧乛R）∨（P∧R））∧（R∧乛P）＝
（乛P∧乛Q∧R∧乛P∧乛P∧乛R）∨（乛P∧乛Q∧R∧乛P∧P∧R）＝ 0∨0＝0
F2＝（乛P∧乛Q）∧（P∧乛R）∧（（乛R∧乛P）∨（R∧P））＝
0∧（（乛R∧P）∨（R∧P））＝0
－3.15－
离散数学讲义 武汉科技大学计算机学院
F3＝（（P∧乛Q）∨（乛P∧Q））∧（（乛P∧R）∧（R∧乛P））＝
（P∧乛Q∧乛P∧R∧R∧乛P）∨（乛P∧Q∧乛P∧R∧R∧乛P）= 0∨（乛P∧Q∧R）= 乛P∧Q∧R F4＝（（P∧乛Q）∨（乛P∧Q））∧（P∧乛R）∧（乛R∧P）=
（P∧乛Q∧P∧乛R∧乛R∧P）∨（乛P∧Q∧乛P∧R∧R∧乛P）= （P∧乛Q∧乛R）∨0?（P∧乛Q∧乛R） F5＝（P∧Q）∧（乛P∧R）∧（（R∧P）∨（乛R∧乛P））=
（P∧Q∧乛P∧R）∧（（R∧P）∨（乛R∧乛P））= 0∧（（R∧P）∨（乛R∧乛
P））
= 0
F6＝（P∧Q）∧（（乛P∧乛R）∨（P∧R））∧（乛R∨P）=
（P∧Q∧乛P∧乛R∧乛R∧P）∨（P∧Q∧P∧R∧乛R∧P）= 0∨0 = 0
所F＝0∨0∨（乛P∧Q∧R）∨（P∧乛Q∧乛R）∨0∨0＝
（乛P∧Q∧R）∨（P∧乛Q∧乛R）= 1
但矿样即不可能既是铜又是锡，所以Q，R中必有假命题，即Q，R不能同为真，所以乛P∧Q∧R = 0，因而必有
P∧乛Q∧乛R = 1
所以P为真，乛Q为真，乛R为真，即P为真，Q为假，R为假，即矿样为铁。
例3.13 用P规则和T规则证明下列命题演算的推理关系。 （1）乛P∨Q，乛Q∨R，R→S?P→S （2）A→（B→C），D→（B∧乛C），A∧D是不相容的（人大2001年考研试题） 证明（1）①乛P∨Q P ② P→Q T，①，E ③ 乛Q∨R P ④ Q→R T，③，E ⑤ P→R T，②，④，I ⑥ R→S P ⑦ P→S T，⑤，⑥，I 故 乛R∨Q，乛Q∨R，R→S?P→S
（2）①Q∧D P ② A→（B→C） P ③ A T，①，I ④ B→C T，②，③，I ⑤ D→（B∧乛C） P ⑥ D T，①，I ⑦ （B∧乛C） T，⑤，⑥，I ⑧ B T，⑦，I ⑨ C T，④，⑧，I ⑩乛C T，⑦，I 11 C∧乛C T，⑨，⑩，I
－3.16－