离散数学3.8

命题公式的递归定义：

1. 命题是公式（每一个命题变元是命题公式）

2. 如果P是公式，则（?P）是公式

3. 如果P、Q是公式，则（P∧Q）（P∨Q）（P→Q）（P?Q）是公式

4. 公式有且仅由有限次使用(1)(2)(3)而得

指派：（例P、Q是命题公式）给P、Q取真假值

可满足公式：命题公式只要有一组指派使命题公式为T

永真式（重言式）：命题公式所有的指派都为T（是可满足公式的一个特殊形式）

永假式（矛盾式）：命题公式所有的指派都为F

P＜＝＞Q等价关系（公式相等、真值表一样）P、Q为复杂的命题公式

3个性质：自反性，对称性，传递性（之后再讲）

区分

＜＝＞：命题公式与命题公式之间的关系

?：命题公式内部的关系，联结词

一些重要的等价关系：

合取∧、析取∨、双条件?可以换，单条件→不可以换 单条件（非基本运算）改为CPU可操作的逻辑运算

1. 交换律：P∨Q＜＝＞Q∨P ; P∧Q＜＝＞Q∧P

2. 结合律：（P∨Q）∨ R＜＝＞P∨（Q∨R）；（P∧Q）∧R＜＝＞P∧（Q∧R）

3. 分配律：P∨（Q∧R）＜＝＞（P∨Q）∧（P∨ R）；P∧（Q∨R）＜＝＞（P∧Q）∨（P∧R）

4. 等幂律（重复律）：P∨P＜＝＞P ; P∧P＜＝＞P【看作交、并集来理解】

5. 双否定率：??P ＜＝＞ P

6. 德.摩根律（反演律)：?（P∨Q）＜＝＞?P∧?Q；【拆括号，合取变析取、析取变合取】

   ?（P∧Q）＜＝＞?P∨?Q；【拆括号，合取变析取、析取变合取】

   ?（P→Q）＜＝＞P∧?Q【 ?（?P∨Q）当前件为假，后件为真

   ＜＝＞ ? ?P∧? Q

   ＜＝＞ P∧? Q 】

7. 吸收率：P∨（P∧Q）＜＝＞P ; P∧（P∨Q）＜＝＞P【看作交、并集来理解】

   P∨（?P∧Q）＜＝＞ P∨Q【P∨（?P∧Q）

   ＜＝＞（P∨?P）∧（P∨Q）

   ＜＝＞T∧（P∨Q）

   ＜＝＞P∨Q

   或P∨（?P∧Q）吸收掉】

8. P→Q＜＝＞?P∨Q【用前件为假，后件为真带入理解】

离散数学3.8

原文：https://www.cnblogs.com/hngz/p/14502365.html