1. 命题逻辑的等值演算与推理演算

参考

离散数学知识点总结（5）：蕴含式；命题的推理理论；逻辑推演的方法；推理的有效性证明

1.1 命题

命题：我们对确定对象做出的陈述句称为命题（propositions and statements 命题或陈述）。当判断为真时，该命题为真，否则为假。

今天下雨 是命题 √
你在干什么啊 非陈述句 X
我只给所有不给自己理发的人理发 悖论 X

原子命题:通常把不含有逻辑联结词的命题称为原子命题或原子(atoms)
复合命题:把由原子命题和逻辑联结词共同组成的命题称为复合命题(compositive propositions or compound statements 综合命题或复合命题)。

1.2 常用联结词

否定：符号$\neg$ 称作否定联结词
合取： 符号$\wedge$称作合取联结词
析取： 符号$\vee$称作析取联结词 .
蕴含或条件： 符号$\to$称作蕴含或条件联结词 .
双向蕴含或等价： 符号$\leftrightarrow$称作双向蕴含或等价联结词 .

联结词优先级
$()$ > $\neg$ > $\wedge$ > $\vee$ > $\to$ > $\leftrightarrow$

1.3 命题公式

命题常元：代表特定的简单命题
命题变元：代表任意命题，取值为真或假的变量
命题公式：含有命题变元的表达式。即 $P\vee Q$便是一个命题公式

公式的赋值
定义：若命题公式$A$含有的全部命题变元为 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​,给 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​指定一组真值，称为$A$的一个解释或赋值。使$A$的真值为真的赋值称为成真赋值，使A的真值为假的赋值为成假赋值。

指派或赋值:用$\alpha ,\beta$等表示当$A$对取值状况$\alpha$为真时，称指派$\alpha$成真$A$，或是$\alpha$是$A$的成真赋值。记为$\alpha \left(A\right)=1$
对一切可能的指派，公式$A$的取值可用下表描述，真值表

真值表：命题公式在所有可能的赋值下的取值的列表含n个变形的公式有2的n次方个赋值。

命题公式的分类-重言式-矛盾式-可满足式

若A在它的各种情况下赋值的取值均为真，则称A为重言式或永真式
若A在它的各种情况下赋值的取值均为假，则称A为矛盾式或永假式
若至少存在一种赋值能使A的真值为真，则称A为可满足式

等价关系式-逻辑等价 logically equivalent

逻辑等价：当命题公式$A\leftrightarrow B$为重言式时，称$A$逻辑等价于$B$，记为$A\iff B$
注意: $A\leftrightarrow B$ 和 $A\iff B$是有区别的，符号$A\leftrightarrow B$是逻辑联结词，是运算符。而 $A\iff B$是关系符，表示A 和 B的逻辑等价关系。

1.4 命题的等值演算与推理

基本等价式

（1）双重否定律 $\neg \neg \iff A$
（2）幂等律 $A\wedge A\iff A,A\vee A\iff A$
（3）交换律 $A\wedge B\iff B\wedge A,A\vee B\iff B\vee A$
（4）结合律
$A\wedge (B\wedge C)\iff (A\wedge B)\wedge C$,
$A\vee (B\vee C)\iff (A\vee B)\vee C$
$A\leftrightarrow (B\leftrightarrow C)\iff (A\leftrightarrow B)\leftrightarrow C$
（5）分配律
$A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$
$A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$
$A\to (B\to C)\iff (A\to B)\to (A\to C)$
（6）德摩根律 $\neg (A\wedge B)\iff \neg A\vee \neg B,\neg (A\vee B)\iff \neg A\wedge \neg B$
（7）吸收律 $A\wedge (A\vee B)\iff A,A\vee (A\wedge B)\iff A$
（8）零律 $A\vee 1\iff 1,A\wedge 0\iff 0$
（9）同一律 $A\wedge 1\iff A,A\vee 0\iff A$
（10）排中律 $A\vee \neg A\iff 1$
（11）矛盾律 $A\wedge \neg A\iff 0$
（12）蕴涵等值式 $A\to B\iff \neg A\vee B$
（13）等价等值式
$A\leftrightarrow B\iff (A\to B)\wedge (B\to A)$
$A\leftrightarrow B\iff (\neg A\vee B)\wedge (\neg B\vee A)$
$A\leftrightarrow B\iff (A\wedge B)\vee (\neg A\wedge \neg B)$
（14）假言易位 $A\to B\iff \neg B\to \neg A$
（15）等价否定等值式 $A\leftrightarrow B\iff \neg A\leftrightarrow \neg B$
（16）归谬论 $(A\to B)\wedge (A\to \neg B)\iff \neg A$

逻辑蕴涵重言式 logically implication

当命题公式$A\to B$为重言式，称$A$逻辑蕴涵$B$，记为$A\Rightarrow B$，需要注意重言蕴含$\Rightarrow$与普通蕴含$\to$的关系。

重言蕴涵推到

$\Rightarrow$是命题公式$A$和命题公式$B$的推理关系，$\to$是两个原子命题的联结关系。

归结法

归结法是计算机进行推理的方法

1.5 命题公式与真值表的关系

对任一依赖于命题变元 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​的命题公式$A$来说，可由 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​的真值根据命题公式$A$给出$A$的真值，从而建立起从 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​到$A$的真值表。
反之，若给定了由 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​到$A$的真值表，可以由下述方法，写出命题公式$A$对 p 1 , p 2 , p 3 , p 4 … p n p_1,p_2,p_3,p_4…p_n p1​,p2​,p3​,p4​…pn​的逻辑表达式。

由T列来写

由F列来写

1.6 联结词的完备集

参考：
【离散数学】数理逻辑 第一章 命题逻辑(4) 联结词的完备集

完备集

对偶式基本概念

1.7 范式

范式定义与生成步骤

主析取及主合取范式

主析取范式：

设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

  若干个极小项的析取（并集）。

主合取范式：

设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

若干个极大项的合取（交集）。

极大项，极小项: