离散数学-公式分类与等价式

公式分类：永真式、永假式和可满足式.

永真式（重言式）：一个命题公式A，若对A所有可能的真值指派（解释），

（1）A都为真，则称A为永真式（重言式）.

（2）A都为假，则称A为永假式（矛盾式）.

（3）至少存在一个真值指派使A为真，则称A为可满足式.

命题公式的等价：设A和B是命题公式，若对A和B所有可能的解释，A和B的真值相同，则称A与B是等价的或逻辑相等的，记作A⇔B.

证明两个公式等价的方法：真值表法、公式法（利用等价的传递性）和主范式法.

基本等价式：设A，B，C是任意命题公式，则命题运算有下列性质.

幂等律：A∧A⇔A，A∨A⇔A

双否律：¬（¬A）⇔A

德·摩根律：¬（A∧B）⇔¬A∨¬B，¬（A∨B）⇔¬A∧¬B

交换律：A∧B⇔B∧A，A∨B⇔B∨A

结合律：A∧（B∧C）⇔（A∧B）∧C，A∨（B∨C）⇔（A∨B）∨C

分配律：A∧（B∨C）⇔（A∧B）∨（A∧C），A∨（B∧C）⇔（A∨B）∧（A∨C）(www.xing528.com)

同一律：A∧T⇔A，A∨F⇔A

零律（支配律）：A∨T⇔T，A∧F⇔F

补余律（有补律）：A∨¬A⇔T，A∧¬A⇔F

吸收律：A∨（A∧B）⇔A，A∧（A∨B）⇔A

条件式转化律：A→B⇔¬A∨B⇔¬B→¬A

双条件式转化律：A↔B⇔（A→B）∧（B→A）⇔（A∧B）∨（¬A∧¬B）

代入原理（代入规则）：在一个永真式A中，任何一个原子命题变元P出现的地方都用另一个公式代入由此得到的公式B仍然是永真式.

替换原理：若A1是一个公式A的一个子公式，且A1⇔B1，并将A中的A1用B1代替由此得到公式B，则A⇔B.

对偶式：设A是仅含¬，∧和∨这三种命题联结词的公式，在A中将∧和∨互换、T和F（若有的话）所得到的公式称为A的对偶式.

对偶原理：若A⇔B，则A*⇔B*.

设A和A*互为对偶式，且P1，P2，…，Pn是A和A*中所有的原子命题变元，则

¬A（P1，P2，…，Pn）⇔A*（¬P1，¬P2，…，¬Pn）

¬A*（P1，P2，…，Pn）⇔A（¬P1，¬P2，…，¬Pn）