第一章 数理逻辑
定理 1.2 – 2 若A B, 且A , B为命题变元P1, P2,….., Pn及联结
词∧ , ∨ , 构成的公式, 则A* B*。
证 AB意味着
A(P1, P2, …, Pn) B(P1, P2, …, Pn) 所以
A(P1, P2, … , Pn) B( P1, P2, … , Pn)
第一章 数理逻辑
（3）若A不是永真式，也不是永假式，则 称A为偶然式. （4）若A至少存在一组赋值是成真赋值, 则称A为可满足式.
第一章 数理逻辑
真值表：
(a)若真值表最后一列全为1，则为重言式； (b)若真值表最后一列全为0，则为矛盾式； (c)若真值表最后一列至少有一个1，则为可满 足式； (d)若真值表最后一列至少有一个0，则非永真； （e）既有0也有1，则为偶然式
第一章 数理逻辑
2.替换规则
结论：恒等式和蕴含式表中的字符P、Q、R 等不仅代表命题变元，而且可以代表命题 公式，T和F不仅代表真命题和假命题，而 且可以代表重言式和永假式。
第一章 数理逻辑
证明公式等值的另一个方法是利用已知的等值式通过代换得 到新的等值式。
例2 (a) 证明P∧ Q∨Q P∨Q
第一章 数理逻辑
1.2 重 言 式
• • • • 恒等式 永真蕴含式 二式的性质 对偶原理
第一章 数理逻辑
1.2.1 基本概念 设A(P1，P2，…Pn)为任一命题公式， （1）若A在其各种赋值下的取值均为真， 则称A是重言式或永真式。 （2）若A在其各种赋值下的取值均为假， 则称A是矛盾式或永假式。
第一章 数理逻辑
常见的逻 辑 恒 等 式
第一章 数理逻辑 表 1.2 - 1 逻 辑 恒 等 式
第一章 数理逻辑
1.2.3 永真蕴含式
• 如果A→B是一永真式, 那么称为永真蕴 含式, 记为A B, 读做“A永真蕴含B”。
第一章 数理逻辑
表 1.2 – 2 永真蕴含式
第一章 数理逻辑
永真蕴含式也可用真值表、恒等代换证 明，但也可用以下办法证明: (1) 假定前件是真, 若能推出后件是真, 则 此蕴含式是真。肯定前件法 (2) 假定后件是假, 若能推出前件是假, 则 此蕴含式是真。 否定后件法
第一章 数理逻辑 例 4 若(P∧Q)∨( 得 (P∨Q)∧( P∨( P∧(
P∨Q))
P∧Q))
P∨Q, 则由对偶原理 P∧Q
定理 1.2 -3 如果A B, 且A , B为命题变元P1, P2, … , Pn及联结 词∧ , ∨ , 构成的公式, 则B* A*。


证 A
B意味着
A(P1, P2 , … ,Pn)→B(P1, P2, …. , Pn)永真, B(P1, P2, … , Pn)→ A (P1, P2, … , Pn)永真。
(c) 试将语句“情况并非如此: 如果他不来, 那么我也不去。”
(
P∧Q Q∧ P
E5
化简后的语句是“我去了, 而他不来”。
第一章 数理逻辑 (d) 找出P→(P Q)∨R的仅含∧ 解 P→(P Q)∨R
P→(P→Q)∧(Q→P)∨R
E15和替换规则
E14和替换规则 P∨( P∨Q)∧( Q∨P)∨R P∨Q)∧( P ∨ Q∨P)∨R E9和替换规则 ( P∨ Q)∨R E2 , E20和替换规则 ( P∨Q)∧(T ∨
2. 若AB , A C, 则A B∧C。 ;
证 A是真时, B和C都真, 所以B∧C也真。因此A→B∧C永真, 则A B∧C。
第一章 数理逻辑
1.2.5 代入规则和替换规则 1. 代入规则 一重言式中某个命题变元出现的每一处 均代入以同一公式后, 所得的仍是重言式。 注：对非重言式通常不作代入运算, 特别 是偶然式
Q∧(P→Q)是假。
第一章 数理逻辑
1.2.4 恒等式和永真蕴含式的两个性质
1. 若AB , B C 则A B , B C则A C; 若A C。 这一性质也可叙述为 : 逻辑恒等和永真蕴含都是传递的。前 者留给读者自证, 现证明后者。 证 A→B永真; B→C永真, 所以 (A→B)∧(B→C)永真。 由公式I6得A→C永真, 既A C。
第一章 数理逻辑
1.2.2 恒等式
定义
如果A B是重言式, 则A与B对任何指派都有相同 的真值。 记为A B, 叫做逻辑恒等式, 读做“A恒 等于B”。 注：是逻辑联结词, A和B有逻辑等 价这个关系的符号, 它的作用相当于代数中的“=”。 判断两个公式恒等的方法 1：真值表法（只需要说明A和B的真值表相同即可） 2：利用已知的恒等式通过代换得到新的恒等式
证 P∧ Q∨Q Q∨P∧ Q (Q∨P)∧(Q∨ (Q∨P)∧T
Q∨P
E4 Q) E9 E20和替换规则 E19
P∨Q
E4
第一章 数理逻辑
等值公式用法
• 证明恒等式、永真蕴含式 • 命题化简
第一章 数理逻辑 (b) 证明(P→Q)→(Q∨R) P∨Q∨R 证 (P→Q)→(Q∨R)
对A *采取同样手续, 又得A, 所以A也是A*的对偶。因此, 对
偶是相互的。 例3 (a) P∨(Q∧R) P∧(Q∨R)互为对偶。
(b) P∨F 和P∧T互为对偶。
第一章 数理逻辑
定理 1.2 - 1 设A和A*是对偶式。P 1, P2,…, Pn是出现于A和A * 中的所有命题变元, 于是 ┐A(P1, P2, …, Pn) A *( ┐P1, ┐P2, … , ┐Pn)
由定理 1.2 -1 得
B*( P1, P2 , … , Pn)→A*( P1, P2 , … , Pn) Pi代Pi, 1≤i≤n, 得 证毕。
因为上式是永真式, 可以使用代入规则,

B*
A*。
由定理 1.2 -1 得 A*( P1, P2, … , Pn) B* ( P1, P2, … , Pn)
因为上式是永真式, 可以使用代入规则, 以 Pi代Pi, 1≤i≤n, 得
A*(P1, P2, …, Pn) B*( P1, P2, …, 所以, A* B*。证毕。 Pn) 本定理常称为对偶原理。
( P∨Q)∧T ∨R P∨Q∨R (P∧
所以, (P∧ Q∧ Q∧ R) R)是所求表达式。
E16和替换规则
E19和替换规则
E1, E11
第一章 数理逻辑
1.2.6 对偶原理
定义1.2 - 1 设有公式A, 其中仅有联结词∧ , ∨ , 偶公式。 。在A中 将∧ , ∨ , T , F分别换以∨ , ∧ , F , T得公式A *, 则A*称为A的对
第一章 数理逻辑
例1

Q , P→Q是真。所以, Q是
Q∧(P→Q)是真,
假, P是假。 方法 2:
(i) 若Q为真,
P是真。 故 Q∧(P→Q) P P是假, 则P是真。以下分情况讨论。
Q是假, Q∧(P→Q)是假。
(ii) 若Q是假, 则P→Q是假,
故 Q∧(P→Q) P。
(
(
P∨Q)→(Q∨R) P∨Q)∨(Q∨R)
E14和替换规则 E14 E10、E1和替换规则 E6 例 2(a)和替换规则
P∧ Q∨(Q∨R) (P∧
Q∨Q)∨R)
P∨Q∨R
第一章 数理逻辑 化简。 解 设P: 他来, Q: 我去, 简化此公式 ( P→ Q) P∨ P∧ Q) Q E14和替换规则 E10 E1 和替换规则 ( P→ Q)。