(9) P?S P (10) F T(8)(9)E
例1-1-4.6和例1-1-4.7的推演步骤分别如下图所示：
（1） （5） （3） （1） （2） （4）
（2） （6）（7）（4） （3） （5）
（8） （9） （6）
（7） （10）
（11） （8） （9）
（12） （10）
图1-1-4.2
1-1-4 习 题
1.用直接证法推演下列蕴涵式。
(1) {?A?B，C??B}?A??C； (2) A?B?C?D，D?E?G?A?G；
(3) A?(B?C)，C?D?E，?G?D??E?A?(B?G)； (4) (A?B?C)?(?B?D)?((E??G)??D)?(B?A??E)?B?E； (5) (A?B)?(C?D)，(B?E)?(D?G)，?(E?G)，A?C??A； 2．用间接证法证明上题。
3．将上题中推演步骤的图示作出来。 4．在下列前提下，结论是否有效？
今天或着天晴或者下雨。如果天晴，我去看电影，若我去看电影，我就不看书，故我在看书时说明今天下雨。
5．如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂
撤换了厂长。问：若厂方拒绝增加工资，而罢工刚开始，罢工是否能够停止？
6．下列命题相容吗？
(1) P?Q ，Q?R ，?R?S ，?P→S ，?S；
26
(2) P?Q ，?R?S ，?Q ，?S。
7．下面的推导正确吗？如果不正确要指出原因。
(1) A?B，C?B，D?(A?C)，D?B。 ① D?(A?C) P ② D P ③ A?C T①②I ④ A?B P ⑤ C?B P ⑥ A?C?B T ④⑤I ⑦ B T ③⑥I (2) A?(C?B)，?D?A，C?D?B。 ① ?D?A P ② D P(附加前提) ③ A T ①② I ④ A?(C?B) P ⑤ C?B T ③④ I ⑥ C P ⑦ B T⑤⑥I ⑧ D?B CP
8．对下面的每一组前提，写出可能导出的结论和所用的推理规则： （1）我跑步就感到累，我不累。
（2）若他犯了错误，则他的神色慌张，他神色慌张。
（3）如果我编的程序通过了，那么我很快活，若我很快活，则天气很好，现在是半夜天很好。
（4）如果我学习，那么我的功课不会不及格。若我不热衷于玩扑克，则我学习，但我的功课不及格。
（5）人总是要死的，苏格拉底是人。
27
§1-1-5 对偶与范式
在§1-1-4中我们已经看到基本等价式在推论中是非常有用的，而§1-1-3列出基本等价式(2)～(10)都是成对出现的，即把一个公式的?换成?。T换成F就可得出另一式，反过来将另一公式的?换成?，F换成T也可以得到这一个公式，我们认为逻辑联结词?和?，重言式T与矛盾式F是互为对偶的。
定义1-1-5.1 在只含逻辑联结词?，?，?的公式A中将?换成?，?换成?，如果A中有T或者F就分别换成F或T，所得到的新公式A* 称为A的对偶式。
显然(A*)* =A。
例1-1-5.1 求 (1) (P→R)→(P?Q→R?Q)；
(2) (P?Q)?F； (3) P?(Q?T)
的对偶式。
解：(1) 令A=(P→R)→(P?Q→R?Q)， 则 A=?(?P?R)?(?(P?Q)?R?Q)。 故 A* =?(?P?R)?(?(P?Q)?R?Q)。
(2)，(3)中二式的对偶式分别为(P?Q)?T，P?(Q?F)。
定理 1-1-5.1 设P1，P2，?，P n 是公式A和A*中出现的原子命题变元，现采用函数记法分别为 A(P1，P2，?，P n )，A*(P1，P2，?，P n )，则
?A(P1，P2，?，P n )? A*(?P1，?P2，?，?P n)， A(?P1，?P2，?，?P n)??A*(P1，P2，?，P n )。 证明: 根据德·摩根定律
?(P?Q)??P??Q ，?(P?Q)??P??Q ，
又因?T?F，?F?T，这正好表明?应用于?（或?）上将原子命题变元
换为他们否定的?（或?），故：
?A(P1，P2，?，P n )? A*(?P1，?P2，?，?P n)。 令Qi = ?Pi，则Pi = ?Qi （i=1，2，?，n）。
故：?A(?Q1，?Q2，?，?Q n)? A*(Q1，Q2，?，Q n )。 即：A（?Q1，?Q2，?，?Q n）?? A*(Q1，Q2，?，Q n )。 二式均得证。
定理1-1-5.2 若A，B为二合式公式，A?B则A*?B* 。
28
证明： 设P1，P2，?，P n 是出现在A，B中的原子命题变元。 因A(P1，P2，?，P n )? B(P1，P2，?，P n )，
故A(P1，P2，?，P n )? B(P1，P2，?，P n )是重言式。
即：A（?P1，?P2，?，?P n）?B(?P1，?P2，?，?P n)是重言式， 故A(?P1，?P2，?，?P n)?B(?P1，?P2，?，?P n)。
由定理1-1-5.1有 A(?P1，?P2，?，?P n)?? A*(P1，P2，?，P n )，
B(?P1，?P2，?，?Pn)??B*(P1，P2，?，Pn )，
由合式公式的等价具有传递性，可得
?A*（P1，P2，?，Pn ）??B*(P1，P2，?，Pn )。
由§1-1-3习题8可知A*?B*。
利用对偶律可以使一些命题公式的推证简化， 如S=A?(?A?(B??B))?A?(?A?F)?(A??A)? T， 则S* =A?(?A?(B??B))? F(T*)。
§1-1-2例1-1-2.4里曾经指出：一个真值函数可以由几个不同的公式表示，即是说合式公式可以有几个相互等价的表达式，那么，对于两个不同的公式如何判断他们是否等价呢？当然可以用真值表，但是，当原子命题变元的个数很多时，即使用计算机有时也不能得出全部真值表来，如果利用基本等价式进行逻辑演算来判断，有时由于观察不够或经验不足，常常会出现循环或走弯路的情形，后一情形就浪费时间，精力，前一情形就得不出结果，这是因为使用基本等价式与人的智慧有关，是非常灵活的，要能够在计算机上机械地进行判断，或者使人们能够明确地判断，下面介绍公式的范式，它既能判定公式是否等价，也能判定公式是否为重言式或矛盾式。
定义1-1-5.2 原子命题公式或它的否定称为句节（literal ，或称文字）。
定义1-1-5.3 有限个句节的析取式称为一个子句（clause）；对偶地，有限个句节的合取式称为一个短语（phrase）。
定义1-1-5.4 有限个子句的合取式（即析取式的合取式）称为合取范式；对偶地，有限个的短语的析取式（即合取式的析取式）称为析取范式。
例1-1-5.2 设P，Q为原子命题公式，则P，Q，?P，?Q，都是句节。 P? Q，P??Q，?P?Q ，?P??Q 都是子句，P? Q，P??Q，?P?Q，?P??Q都
29
是短语。P?Q，(P?Q)?(?P?Q)都是合取范式，?P?Q，(P?Q)?(?P??Q)都是析取范式。又如P，Q，R为原子命题公式，P ? Q，?Q?R 是子句，P?Q?R，P??R是短语，R?(P?Q)是合取范式，(?P?R)?(P?Q)是析取范式。
例1-1-5.3 一个子句或一个短语既是合取范式又是析取范式。 定理 1-1-5.3 给定任一个命题公式，必有与之等价的合取范式和析取范式。
证明： 若A为任一命题公式，用下列算法可以得出与A等价的合（析）取范式：
(1) 若A不含“→”或“?”，转(2)。若A含“→”或“?”，用基本等价式删去 “→”或“?”使A等价于只含?，?或 ? 的公式。
(2) 用德·摩根律将A中“?”移到原子命题变元前面并用对合律化简之。 (3) 反复使用分配律，交换律，结合律等就可得到等价于A的合取范式或析取范式。
例1-1-5.4 求?P→(P→Q)的合取和析取范式。 解： ?P→(P→Q)??P?(?P?Q)
?P?(?P? Q) （合析取范式） ?(P??P)?Q
?T?Q （合析取范式） ?T?P??P。
例1-1-5.5 求?(P?Q)?P?Q的合取和析取范式。 解： ?(P?Q)?(P?Q)
? (?(P?Q)?(P?Q))?(P?Q??(P?Q)) ? ((P?Q)?(P?Q))?(?(P?Q)??(P?Q))
? ((P?Q)?P)?( (P?Q)?Q))?((?P??Q)?(?P??Q))
? (P?Q)? ((?P??Q)??P)?( (?P??Q)??Q)) ? (P?Q)? (?P??Q) (合取范式) ? ( (P?Q)??P)?( (P?Q)??Q) ? (?P?Q)?(P??Q) (析取范式)
从上面的例子可以看出一个命题公式的合取范式和析取范式仍然有若干个，并不是唯一的，因而讨论时还是不够方便，故再引入下列的主范式概念
30