离散数学讲义 武汉科技大学计算机学院
如P值取1，在有小项中则还原为1，如P,Q,R之解释为010，则对应的有小项为乛P∧乛Q∧乛R；极大项与解释之间的对应为：如P取值0，在极大项中则还原为P，如P取值1，在极大项中则还原为0，如P,Q,R之解释为110，则对应的极大项为乛P∧乛Q∧R。
3、主要定理
(1) 任一命题公式都存在与其等值的析取范式和合取范式； (2) 任一命题公式都存在与其等值的主析取范式和主合取范式；
(3) 如果一个命题公式是永真公式?它的主析取范式包含所有的极小项，此时无主
合取范式或者说主合取范式为空；
(4) 如果一个命题公式是永假公式?它的主合取范式包含所有的极大项，此时无主
析取范式或者说主析取范式为空；
(5) 两个命题公式是相等的?它们所对应的主析取范式上等和主合取范式相等； (6) 任一公式对应主析取范式包括的极小项的个数加对应主合取范式包括的极大项
的个数为2n。
3.6 推理理论 1. 推理的形式结构
设G1, G2, ?, Gn，H是命题公式，称
G1∧G2∧?∧Gn→H
为推理的形式结构，其中G1, G2, ?, Gn为前提，H为结论。当G1∧G2∧?∧Gn→H
为永真式时，则此时推理正确，并称G1, G2, ?, Gn逻辑蕴涵H是G1, G2, ?, Gn的逻辑结果，并且记为G1∧G2∧?∧Gn?H或记为G1, G2, ?, Gn?H。
说明：G1, G2, ?, Gn?H仅描述了公式G1, G2, ?, Gn与公式H之间的逻辑蕴涵关系，
G1, G2, ?, Gn?H本身并不是一个公式，它不能作直接的计算。
要判断G1, G2, ?, Gn?H可采用：
G1, G2, ?, Gn?H当且仅当G1∧G2∧?∧Gn→H是一个永真公式。 2. 判断推理是否正确的方法
(1) 真值表法：利用真值表法，可建立如下推理定律：
设G，H，S是任意的命题公式，则： ① 附加定律：G?G∨H，H?G∨H ② 化简定律：G∧H?G，G∧H?H ③ 合并定律：G，H?G∧H
－3.6－
离散数学讲义 武汉科技大学计算机学院
④ 假言推理：G，G→H?H ⑤ 拒取式：G→H，乛H?乛G ⑥ 析取三段论：G∨H，乛G?H ⑦ 假言三段论：G→H，H→S?G→S ⑧ 二难推论：G∨H，G→S，H→S?S ⑨ 等价三段论：G?H；H?S?G?S (2) 等值演算法；
(3) 主析取（主合取）范式法； (4) 构造证明法。
① 推理规则：规则P（前提引入规则）：在推导的过程中，可以随时引入前提集合
中的任一前提及附加前提。
规则T（逻辑结果引用规则）：在推导的过程中，可以随时引用公式S，该公式S
是由其前的一个或多个公式推导出的逻辑结果。
规则P（附加前提规则）：如果能从给定理前提集合P与公式P推导出S，则能从
此前提集中P推导出P→S。
② 直接证明方法：此证明法是一个描述推理过程的命题公式序列C1, C2, ?, Cn，其
中C1, C2, ?, Cn或者为已知的前提和附加前提，或者是由某些前提或中间结论应用推理规则得到的中间结论或结论，Cn为最终的结论。
③ 间接证明法（反证法或归谬法）：要证明G1, G2, ?,Gn?H，等价地证明G1, G2, ?,
Gn， 乛H?R∧乛R，其中R可以是任意的公式，此时证明G1, G2, ?, Gn, 乛H?R∧乛R即
可采取直接证明方法。
④ 带CP规则的直接证明方法：带CP规则的证明法主要是针对结论为P→S（或乛
P∨S）的公式十分方便，即要证明G1, G2, ?, Gn?P→S，等价地证明G1, G2, ?, Gn，P?S，
此时证明G1, G2, ?, Gn, P?S可采用直接证明方法（此时P为附加前提）。当推出结论S后，采用CP规则，即可由G1,?, Gn推出P→S。上述三种方法对命题逻辑中的任何推理问题都是适用的，只是不同的逻辑推理问题采用不同的方法其方便程度不同而已。
3.7 总结
通过本章的学习，应达到下面的基本要求：
(1) 要弄清命题与陈述句之间的关系与差别。命题都是陈述句；但陈述句不一定都
是命题，只有陈述句所表达的判断结果查惟一确定的，它才是命题；
－3.7－
离散数学讲义 武汉科技大学计算机学院
(2) 掌握并能熟练应用6种基本的联结词（乛，∧，∨，?，→，?）来对复合命题
进行翻译及判断真值；
(3) 记住24个基本的等价公式，并能熟练地应用到公式的转换中；
(4) 会利用真值表技术和公式的演算方法求一公式所对应的主析取范式和主合取范
式，并能利用范式判断两公式是否相等，是否为永真式、永假式、可满足式；
(5) 掌握并能熟练地应用推理的三种证明方法。
例题精选
例3.1 设P表示命题“天下雨”，Q表示命题“他骑自行车上班”，R表示命题“他乘公共汽车上班”，试以符号形式写出下列命题（西南交大1995年考研试题）：
（1）只要不下雨，他才骑自行车上班； （2）只要不下雨，他就骑自行车上班； （3）除非下雨，否则他就骑自行车上班； （4）他或者骑自行上班，或者乘公共汽车上班。
分析 对于命题只要Q才P，只要P就Q，除非Q，否则P等，都可以翻译成P→Q，所以上述(1)，(2)，(3)分别可翻译为：(1) Q→乛P，(2) 乛P→Q，(3) 乛Q→P。句子(4)可翻译
为Q?R。
例3.2 (1) 使用连接词乛，∨，构造三个命题变项P,Q,R的公式L（P,Q,R），使得：乛L（P,Q,R）=L(乛P,Q,R)=L(P,乛Q,R)=L(P,Q,乛R) （2）求（1）中公式L（P,Q,R）的主合取范式，（北师大2001年考研试题）。
解 (1) 设L（P,Q,R）=i?0其中ai??(aiMi)7?
01，Mi为关于P,Q,R的极大项。
i?0则乛L(P,Q,R)=
?((1?a)Mi)
7L(乛P,Q,R)= a0M4∧a1M5∧a2M6∧a3M7∧a4M0∧a5M1∧a6M2∧a7M3 L(P,乛Q,R)= a0M2∧a1M3∧a2M0∧a3M1∧a4M6∧a5M7∧a6M1∧a7M2 L(P,Q,乛R)= a0M1∧a1M0∧a2M3∧a3M2∧a4M5∧a5M4∧a6M7∧a7M6 由乛L(P,Q,R)=L(乛P,Q,R)=L(P,乛Q,R)=L(P,Q,乛R) 对应极大项Mi的系数应相等，为此有： (1?a0)= a4= a2= a1，(1?a4)= a0= a6= a5 (1?a1)= a5= a3= a0，(1?a5)= a1= a7= a4 (1?a2)= a6= a0= a3，(1?a6)= a2= a4= a7 (1?a3)= a7= a1= a2，(1?a7)= a3= a5= a6 所以 a0= a3= a5= a6 a1= a2= a4= a7
－3.8－
离散数学讲义 武汉科技大学计算机学院
如令 a0= a3= a5= a6=0，则a1= a2= a4= a7=1 此时 L(P,Q,R)=M1∧M2∧M4∧M7=
乛(乛M1∨乛M2∨乛M4∨乛M7)=
乛(乛(P∨Q∨乛R)∨乛(P∨乛Q∨R)∨乛(乛P∨Q∨R)∨ 乛(乛P∨乛Q∨乛R)) 如令 a0= a3= a5= a6=1，则a1= a2= a4= a7=0
此时 L(P,Q,R)=M0∧M3∧M5∧M6=乛(乛M0∨乛M3∨乛M5∨乛M6)= 乛(乛(P∨Q∨R)∨乛(P∨乛Q∨乛R)∨乛(乛P∨Q∨乛R)∨ 乛(乛P∨乛Q∨R)) (2) L(P,Q,R)=M1∧M2∧M4∧M7=
(P∨Q∨乛R)∧乛(P∨乛Q∨R)∨(乛P∨Q∨R)∨(乛P∨乛Q ∨乛R)?主合取范式= M0∧M3∧M5∧M6=
(P∨Q∨R)∧(P∨乛Q∨乛R)∧(乛P∨Q∨乛R)∧(乛P∨ 乛Q∨R)?主合取范式
例3.3 没有命题P：明天上午七点下雨 Q：明天上午七点下雪 R：我将去学校 符号化下列语句：
（1）除非明天上午七点不下雨且不下雪，否则我将不去学校； （2）只要明天上午七点不下雨或不下雪，我就去学校； （3）只有明天上午七点不是雨夹雪，我才去学校； （4）明天上午七点我将雨雪无阻一定去学校。
分析 根据命题P→Q的定义，它可对应语句除非Q，否则乛P；只要P，就Q；只有Q才P。所以上述（1），（2），（3）可分别对应符号化为：
（1）R→（乛P∧乛Q） （2）乛P∨乛Q→R （3）R→乛（P∧Q）
句子（4）是雨雪无阻一定去学校，即无论任何天气都不影响去学校，即去学校与天气无关，因此，句子（4）可简单地符号化为：R
但为了完整的表达出该句子的全部意思，应将雨雪无阻符号化。所谓雨雪无阻即是：
（P∧Q）∨（乛P∧Q）∨（P∧乛Q）∨（乛P∧乛Q）
所以句子（4）完整地符合号为：
（（P∧Q）∨（乛P∧Q）∨（P∧乛Q）∨（乛P∧乛Q）∧R
或 （P∧Q∧R）∨（乛P∧Q∧R）∨（P∧乛Q∧R）∨（乛P∧乛Q∧R）
说明 由于雨雪无阻与R是同时发生，没有因果关系，所以天气与去学校之间用合取。
－3.9－
离散数学讲义 武汉科技大学计算机学院
例3.4 求公式G1(P，Q，R)?(P→Q)∧(P∧Q)
G2(P，Q)?(P→Q)∧(P∧Q)
的主析取范式和主合取范式。
分析 公式G1，G2的右端虽然是相同的，但公式的左岸表明两个公式所含的命题变元不同，在求主析取，主合取范式时，由于其极小项，极大项依赖于命题变元，所以不能仅根据右端的公式来求，还应该根据该公司所含的命题变元的情况来求。因此，上述两个公式的主析取范式，主合取范式安全不同。下面采用两种方式来求。
方法1 采用真值表技术。
建立公式G1(P，Q，R)?(P→Q)∧(P∧Q)的真值表如表2．4所示。
表2．4 P，Q，R (P→Q)∧(P∧Q) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 则公式G1(P，Q，R)所对应的主析取范式、主合取范分别为：
G1（P，Q，R）?（P∧Q∧乛R）∨（P∧Q∧R）?主析取范式
G1（P，Q，R）?（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）的真值表如表2．5所示。
表2．5 P Q （P→Q）∧（P∧Q） 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 则公式G2(P，Q)所对应的主析取范式、主合取范式分别为：
G2（P，Q）=（P∧Q）?主析取范式
G2（P，Q）=（P∨Q）∧（乛P∨Q）∧（P∨乛Q）?主合取范式 方法2 采用公式转换法。
G1（P，Q，R）?（P→Q）∧(P∧Q)?（乛P∨Q）∧P∧Q?P∧Q?
P∧Q∧(乛R∨R)?（P∧Q∧乛R）∨（P∧Q∧R）?主析取范式
G1（P，Q，R）?乛（乛G1(P，Q，R)）?
乛（(P∧乛Q∧R)∨(乛P∧Q∧R)∨(P∧乛Q∧乛R)
∨（乛P∧Q∧乛R）∨（乛P∧乛Q∧R）∨（乛P∧乛Q∧乛R）? (乛P∨Q∨乛R)∧（P∨乛Q∨乛R）∧（乛P∨Q∨R）∧ (乛P∨Q∨R)∧（P∨Q∨乛R）∧（P∨Q∨R）?
－3.10－