A，B的真值相同，故A?B。
例1-1-3.4 证明 P?Q??Q??P。 证明:
(P?Q)?(?Q??P)?((P?Q)?(?Q??P))?((?Q??P)?(P?Q))?((?P?Q)?(??Q??P))?((??Q??P)?(?P?Q))?(?(?P?Q)?(??Q??P))?(?(??Q??P)?(?P?Q))?(?(?P?Q)?(?P?Q))?(?(?P?Q)?(?P?Q))?T?T?T故由定理1-1-3.3得证。
例1-1-3.5 P→(Q→R)?(P?Q)→R 证明：
P?(Q?R)??P?(?Q?R)?(?P??Q)?R??(P?Q)?R?(P?Q)?R. 容易验证 wff 等价具有下列性质：
(1) 反身（自反）性: A?A。 (2) 对称性: 若A?B则B?A。
(3) 传递性: 若A?B,B?A，则A?C。
定义 1-1-3.3 设合式公式A和B中出现的原子命题变元为P1,P2,?,Pn，如果对它们的指派使A取值为1时B也取值为1，则称A蕴涵B（或称B是A的逻辑结果），记为A?B。
例1-1-3.6 ?P?P?Q。 证明:
P 1 1 0 0 Q 1 0 1 0 ?P 0 0 1 1 P?Q 1 0 1 1
从上面的真值表可知，使?P取值1的指派0，1和0，0它也使P→Q取值为1，根据定义1-1-3.3得证 ?P?P→Q。
例1-1-3.7 (P?Q)?(Q?R)?P?R。 证明:
16
P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 P?Q 1 1 0 0 1 1 1 1 Q?R 1 0 1 1 1 0 1 1 (P?Q)?(Q?R) 1 0 0 0 1 0 1 1 P?R 1 0 1 0 1 1 1 1 由真值表可知使(P→Q)?(Q→R )取值为1的指派(1，1，1)；(0,1,1)；(0,0,1)；（0，0，0）也使P→R取值为1，根据定义1-1-3.3知
(P?Q)?(Q?P)?P?R。
定理1-1-3.4 合式公式A?B当且仅当A?B是重言式。
证明：必要性：由A?B的定义知当A取值为1时，B取值也为1。再由A?B的运算表知，当A取值为1时，B取值也为1，A?B为重言式。
充分性：因为A?B为重言式，所以，当A取值为1时，B的真值必为1(否则A?B真值为假，与题设矛盾)，所以A?B。
例1-1-3.8 ?Q?(P?Q)??P 证明：
?Q?(P?Q)??P?(?Q?(?P?Q))??P ??(?Q?(?P?Q))??P?Q??(?P?Q)??P ?(?P?Q)??(?P?Q)?T由定理1-1-3.4得证?Q?(P?Q)??P。
用定义1-1-3.3及定理1-1-3.4易证下列常用的基本蕴涵式： (1) P?Q?P，P?Q?Q； (2) P?P?Q，Q?P?Q； (3) ?P ?P→Q； (4) Q?P→Q；
(5) ?(P→Q)?P；?(P→Q)??Q； (6) P?(P→Q)?Q； (分离规则) (7) ?Q?(P→Q)??P；
17
(8) ?P?(P?Q)?Q ； (9) (P→Q)?(Q→R)? P→R； (10) (P?Q)?(P→R) ?(Q→R) ?R； (11) (P→Q) ?(R→S)?(P?R)→(Q?S)； (12) (P?Q) ?(Q ?R)? P? R。 蕴涵具有下列常用性质：
(1) A为重言式，A?B，则B必为重言式； (2) 自反性 A?A；
(3) 反对称性 若A?B且 B?A 则A?B； (4) 传递性 若A?B且 B?C 则A?C； (5) 若A? B且 A? C 则A? B ? C 。 (6) 若A?B且C?B，故A ? C?B。 证明: (1)、(2) 由A?B的定义即可知。
(3) 因为A?B且B?A，所以A?B与B?A为重言式，由基本等价式(12)知A?B为重言式，所以A?B。
(4) 由A?B且B?C知(A→B)?(B→C)为重言式，据基本蕴涵式(9)知(A→B)?(B→C)?A→C，由性质1知A→C为重言式，故A?C。
(5) 因A?B且A?C，故(A→B)，(B→C)都为重言式，如果A取值为1，则B和C都取值为1，因而B?C取值为1；如果A取值为0，无论B?C取值为1还是取0 ，A→B?C取值均为1，故A→B?C为重言式，所以A?B?C 。 (6) 因A?B且C?B故(A→B)?(C→B)?T。
即 (?A ? B)?(?C? B)?T，即 (?A ?? C)? B?T，即 ?(A ? C)? B?T， 即(A ? C)→B?T，故 A?C ? B。
1-1-3 习 题
1．证明（A?B）?（B?C）?（C?A）?（A?B）?（B?C）?（C?A）。 2．不要构造真值表证明下列蕴涵式： (1) P?Q?P?(P?Q)； (2) (P?Q)?Q?P?Q；
18
(3) Q??Q?P； (4) ?P?Q?P?S； (5) P?R?S??S；
(6) (Q?P)?(R?(R?P))??R?(P?Q)。 3．若A?C?B?C是否有A?B？ 若A?C?B?C是否有A?B？ 若?A??B是否有A?B？ 4．证明A?B时?B??A。
5．证明A?B时?A??B┐，反之也对。
19
§1-1-4 命题逻辑的推理理论
逻辑是研究思维结构和规则的科学，要求能够提供正确的思维规律，提供判定一个论断之有效的准则。数理逻辑则研究正确的推理规则，研究论断的有效性,但要注意到：论断的正确性涉及到实践的检验。
什么是论断的有效性呢？回忆§1-1-3中命题公式的蕴涵概念，并把它推广。
定义 1-1-4.1 A1,A2,?,An和B为合式公式，若A1 ?A2 ??? An?B，则称B为前提A1,A2,?,An的有效结论，或说B是A1,A2,?,An的逻辑结果，或者说A1,A2,?,An共同蕴涵B。
例1-1-4.1 证明 R→S是P→(Q→S)，?R?P ，Q的有效结论。 证明：即要证(P→(Q→S))?(?R?P)?Q?R→S，也就是要证明
(P→(Q→S))?(?R?P)?Q?(R→S)为重言式。当然可以应用真值表验证，也可以用等价是验证，往往是比较麻烦的。
因此判定论断的有效性，需要有其他论证方法，希望有比较简明的过程，还要有正确的依据。
定理 1-1-4.1 若A1?A2???An?B?C，则
A1?A2???An?B?C。
证明：已知A1?A2???An?B?C，故A1?A2???An?B?C为重言式。即?(A1?A2???An?B)?C为重言式，即?(A1?A2???An)??B?C为重言式，即A1?A2???An?(B?C)为重言式，
所以 A1?A2???An?B?C。
定义1-1-4.2 设S为若干公式的集合（称为前提集合）。
如果有公式的有限序列A1,A2,?,An其中Ai ?S 或Ai 是A1,A2,?,Ai?1中某些公式的有效结论，且An?B，则称B是S的逻辑结果或有效结论，或者说从S演绎出B。
定理1-1-4.2 设S为公式集，B是一个公式，S能演绎出B的充分必要条件是：B是S的逻辑结果。
证明： 充分性：因为B是S的逻辑结果，由定义1-1-4.2知存在公式的有限
20