2014数理逻辑1.2.pptVIP

1.2 重 言 式;1.2.1 基本概念;（3）若A不是永真式，也不是永假式，则称A为偶然式. （4）若A至少存在一组赋值是成真赋值, 则称A为可满足式. ; 真值表： (a)若真值表最后一列全为1，则为重言式； (b)若真值表最后一列全为0，则为矛盾式； (c)若真值表最后一列至少有一个1，则为可满足式； (d)若真值表最后一列至少有一个0，则非永真； （e）既有0也有1，则为偶然式 ;1.2.2 恒等式;常见的逻 辑 恒 等 式 ;表 1.2 - 1 逻 辑 恒 等 式 ;1.2.3 永真蕴含式;表 1.2 – 2 永真蕴含式 ;永真蕴含式也可用真值表、恒等代换证 明，但也可用以下办法证明: (1) 假定前件是真, 若能推出后件是真, 则此蕴含式是真。肯定前件法 (2) 假定后件是假, 若能推出前件是假, 则此蕴含式是真。 否定后件法 ; 例 1 证明Q∧(P→Q) P 方法 1: 设Q∧(P→Q)是真, 则Q , P→Q是真。所以, Q是假, P是假。因而P是真。 故 Q∧(P→Q) P ;1.2.4 恒等式和永真蕴含式的两个性质 1. 若AB , BC 则AC; 若AB , BC则AC。 这一性质也可叙述为: 逻辑恒等和永真蕴含都是传递的。前者留给读者自证, 现证明后者。 证 A→B永真; B→C永真, 所以 (A→B)∧(B→C)永真。 由公式I6得A→C永真, 既A C。 2. 若AB , AC, 则AB∧C。 ; 证 A是真时, B和C都真, 所以B∧C也真。因此A→B∧C永真, 则A B∧C。 ;1.2.5 代入规则和替换规则;2.替换规则;例 2;等值公式用法;(b) 证明(P→Q)→(Q∨R) P∨Q∨R 证 (P→Q)→(Q∨R)  ( P∨Q)→(Q∨R) E14和替换规则  ( P∨Q)∨(Q∨R) E14  P∧ Q∨(Q∨R) E10、E1和替换规则  (P∧ Q∨Q)∨R) E6  P∨Q∨R 例 2(a)和替换规则 ;( P→ Q) (P∨ Q) E14和替换规则  P∧ Q E10 P∧Q E1和替换规则 Q∧ P E5 化简后的语句是“我去了, 而他不来”。 ;(d) 找出P→(PQ)∨R的仅含∧和两种联结词的等价表达式。 ; 1.2.6 对偶原理 定义1.2 - 1 设有公式A, 其中仅有联结词∧ , ∨ , 。在A中将∧ , ∨ , T , F分别换以∨ , ∧ , F , T得???式A *, 则A*称为A的对偶公式。 对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 – 2 若AB, 且A , B为命题变元P1, P2,….., Pn及联结词∧ , ∨ , 构成的公式, 则A* B*。 证 AB意味着 ; 例 4 若(P∧Q)∨(P∨(P∨Q))P∨Q, 则由对偶原理得 (P∨Q)∧(P∧(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)永真。  由定理 1.2 -1 得 B*(P1, P2 , … , Pn)→A*( P1, P2 , … , Pn) 永真 因为上式是永真式