第一节、等值式
定义：设A,B是两个命题公式，若A，B构成的等价式A $\leftrightarrow$ B为重言式，则称A与B是等值的，记作A$\Leftrightarrow$ B。
注：A$\Leftrightarrow$ 1,则A为重言式， A$\Leftrightarrow$ 0,则A为矛盾式
##判断两个公式等值的方法
真值表法
例如判断p$\to$(q$\to$r)和（p$\to$q)$\to$r是否相等
| p | q | r | p$\wedge$q | q$\to$r | p$\to$(q$\to$r) | (p$\to$q)$\to$r |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
由此可知两式是等值式。但是用真值表，工作量比较大。
利用已知等值式代换得到新的等值式
- (p$\wedge\rceil$q)$\vee$($\rceil$p$\wedge$q) $\Leftrightarrow$（p$\vee$q）$\wedge$$\rceil$(p$\wedge$q)
我们有这么一个结论
设A是含有命题变项$p_1,p_2,\cdots,p_n$的命题公式，$A_1,A_2,\cdots,A_n$是任意的命题公式。对每一个i，把$p_i$在A中的所有出现都替换成$A_i$所得的新公式记为B。那么如果A是重言式，则B也是重言式
- 根据$p\leftrightarrow\rceil\rceil$p是重言式和上面的结论知，对于任意的A，都有$A\leftrightarrow\rceil\rceil$A是重言式，即$A\Leftrightarrow\rceil\rceil$A
需要记忆的16组重要的等值式模式
- 双重否定律(双重否定表肯定)：
$\rceil\rceil$A$\Leftrightarrow$A- 等幂律(一件事情说两遍)：
A$\vee$A⟺A，A$\wedge$A⟺A- 交换律：
A$\vee$B⟺B$\vee$A，A$\wedge$B⟺B$\wedge$A- 结合律：
(A$\vee$B)$\vee$C⟺A$\vee$(B$\vee$C)
(A$\wedge$B)$\wedge$C⟺A$\wedge$(B$\wedge$C)- 分配律：
A$\vee$(B$\wedge$C)⟺(A$\vee$B)$\wedge$(A$\vee$C)
A$\wedge$(B$\vee$C)⟺(A$\wedge$B)$\vee$(A$\wedge$C)- 德摩根律(去括号要变号)：
$\rceil$(A$\vee$B)⟺$\rceil$A$\wedge\rceil$B
$\rceil$(A$\wedge$B)⟺$\rceil$A$\vee\rceil$B- 吸收律：
A$\vee$(A$\wedge$B)⟺A
A$\wedge$(A$\vee$B)⟺A- 零律：
A$\vee$1⟺1
A$\wedge$0⟺0- 同一律：
A$vee$0⟺A
A$\wedge$1⟺A- 排中律：
A$\vee\rceil$A⟺1- 矛盾律：
A$\wedge\rceil$A⟺0- 蕴含等值式：
A$\to$B⟺$\rceil$A$\vee$B- 等价等值式
A$\leftrightarrow$B⟺(A$\to$B)$\wedge$(B$\to$A)- 假言易位(逆否命题)
A$\to$B⟺$\rceil$B$\leftrightarrow\rceil$A- 等价否定等值式
A$\leftrightarrow$B⟺$\rceil$A$\to\rceil$B- 归谬论(前提AAA错误)：
(A$\leftrightarrow$B)$\wedge$(A$\leftrightarrow\rceil$B)⟺$\rceil$A
等值演算
等值演算：由已知的等值式推演出另外一些等值式的过程。
置换规则：设$\Phi(A)$是包含A的命题公式，$\Phi(B)$用B置换了$\Phi(A)$中的所有（或部分）A得到的公式，若A$\Leftrightarrow$B，则$\Phi$(A)$\Leftrightarrow\Phi$(B)
等值演算的用途：
证明等值式
例：验证p$\to$(q$\to$r)$\Leftrightarrow$（p$\to$q)$\to$r
右边$\Leftrightarrow\rceil$(p$\wedge$q)$\vee$r$\Leftrightarrow$($\rceil$p$\vee\rceil$q)$\vee$r$\Leftrightarrow\rceil$p$\vee$($\rceil$q$\vee$r)$\Leftrightarrow\rceil$p$\vee$(q$\to$r)$\Leftrightarrow$p$\to$(q$\to$r)
判断公式类型
例：判断公式(p$\to$q)$\wedge$p$\to$q
原式$\Leftrightarrow\rceil$((p$\to$q)$\wedge$p)$\vee$q
$\Leftrightarrow\rceil$(($\rceil$p$\vee$q)$\wedge$p)$\vee$q
$\Leftrightarrow\rceil$($\rceil$p$\vee$q)$\vee\rceil$p$\vee$q
$\Leftrightarrow$(p$\wedge\rceil$q)$\vee\rceil$p$\vee$q
$\Leftrightarrow$(p$\vee\rceil$q)$\wedge$($\rceil$p$\vee\rceil$q)$\vee$q
$\Leftrightarrow$1$\wedge$($\rceil$p$\vee\rceil$q)$\vee$q
$\Leftrightarrow$($\rceil$p$\vee\rceil$q)$\vee$q
$\Leftrightarrow\rceil$p$\vee(\rceil$q$\vee$q)
$\Leftrightarrow\rceil$p$\vee$1
$\Leftrightarrow$1
文字断案问题
具体分析看课件
第二节、析取范式与合取范式
基本铺垫
文字：命题变式及其否定式统称为文字。如$p$和$\rceil p$
简单析取式：仅有有限个文字组成的析取式。如$p \vee q$
简单合取式：仅有有限个文字组成的合取式。如$p \wedge q$
为方便起见，有时候用$A_i$表示一个简单析取/合取式
定理：一个简单析取式是重言式$\Leftrightarrow$它同时含有某个命题变项及其否定式；一个简单合取式是矛盾式$\Leftrightarrow$它同时含有某个命题变项及其否定式。
析取范式：由有限个简单合取式构成的析取式。
合取范式：由有限个简单析取式构成的合取式。
范式：析取范式与合取范式统称为范式。
注：一个简单合取式既是析取范式，又是合取范式；一个简单析取式既是合取范式，又是析取范式
定理：(1)一个析取范式是矛盾式$\Leftrightarrow$它的每个简单合取式都是矛盾式。(2)一个合取范式是重言式$\Leftrightarrow$它的每个简单析取式都是重言式。
定理: (范式存在定理)任一个命题公式都存在着与之等值的析取范式与合取范式。
步骤:
- 消去连接词$\to$、$\Leftrightarrow$
A $\to$B $\Leftrightarrow$($\rceil$ A $\vee$ B)
A$\leftrightarrow$B $\Leftrightarrow$( $\rceil$A $\vee$ B) $\wedge$ (A $\vee\rceil$ B) - 否定联接词的消去或内移。
- 利用分配律
定义:在含有n个命题变项的简单合（析）取式中，每个命题变项和它的否定不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字母顺序），称这样的简单合（析）取式为极小（大）项。
定理：(1)每个极小项，如$p_1$ $\wedge$ $p_2$ $\wedge$ $p_3$ $\wedge\cdots\wedge$ $p_n$,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作$m_i$。(2)每个极大项，如$p_1$ $\vee$ $p_2$ $\vee$ $p_3$ $\vee\cdots\vee$ $p_n$,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，就将所对应的极大项记作$M_i$。
定理:(极小项与极大项关系)设$m_i$和$M_i$是命题变项$p_1$,$p_2$,$\cdots$,$p_n$形成的极小项和极大项，则$\rceil$ $m_i$ $\Leftrightarrow$ $M_i$，$\rceil$ $M_i$ $\Leftrightarrow$ $m_i$
定义:设由n个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则且无重复出现，则称该析（合）取范式为主析（合）取范式。
定理:任何命题公式都存在着与之等值的主析取范式和主合取范式，并且（在不计极小（大）项的顺序的前提下）是唯一的。
结论:主析取范式的极小项的下标（对应的0，1符号串）恰为原命题公式的成真赋值，而主合取范式的极大项的下标（对应的0，1符号串）恰为原命题公式的成假赋值。它们二者是互“补”的
因此，当命题变项比较少时，可以求真值表法来求主范式
主析取范式的用途（主合取范式类似讨论）
- 求公式的成真/成假赋值：若公式A中含有n个命题变项，且A的主析取范式含s个极小项，则A有s个成真赋值，有$2^n$-s个成假赋值。
- 判断公式的类型：
- A为重言式$\Leftrightarrow$A的主析取范式含全部$2^n$个极小项。
- A为矛盾式$\Leftrightarrow$A的主析取范式不含任何极小项。
- A为满足式$\Leftrightarrow$A的主析取范式至少含1个极小项。
- 判断两个命题公式是否等值。设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式$M$、$N$。 若$M$=$N$ ，则A$\Leftrightarrow$B，否则A、B不等值
注：重言式不含极大项，其主合取范式记为1。矛盾式不含极小项，其主析取范式记为0。
第三节、连接词的完备集
定义：称F：{0,1}$^n$ $\to${0,1}为n元真值函数。这里{0,1}$^n$是长为n的0和1构成的所有字符串形式的集合
定义:设S是一个联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的命题公式表示，则称S是一个联结词完备集。
含有n个命题变项的公式的真值表(指最后一列)至多有$2^{2^n}$。
定理:S={$\rceil$,$\wedge$,$\vee$}是联接词的完备集
推论:以下联接词集都是完备集
- S={$\rceil$,$\wedge$,$\vee$,$\to$,$\leftrightarrow$}
- S={$\rceil$,$\wedge$,$\vee$,$\to$}
- S={$\rceil$,$\wedge$}
- S={$\rceil$,$\vee$}
- S={$\rceil$,$\to$}
定义: 设p和q是两个命题，复合命题“p与（或）q的否定式” 称为p，q的与非式（或非式），记作p$\uparrow$q（ p$\downarrow$q ），符号$\uparrow$（ $\downarrow$ ）称为与（或）非联结词。并规定p$\uparrow$q为真当且仅当p与q不同时为真（p$\downarrow$q为真当且仅当p与q同时为假。）
定理:{$\uparrow$}、{$\downarrow$}都是联接词的完备集
