离散笔记【第二章】

等值式

设A,B是两个命题的公式，若A,B构成的等价式 $A\leftrightarrow B$ 为重言式，则称A与B是等价的，记作 $A\Leftrightarrow B$ 。

16组常用的重要等值式模式：
1.双重否定律

$A\Leftrightarrow \neg\neg A$

2.幂等律

$A\Leftrightarrow A\vee A，A\Leftrightarrow A\wedge A$

3.交换律
4.结合律
5.分配律
6.德摩根律
7.吸收律
8.零律
9.同一律
10.排中律
11.矛盾律
12.蕴含等值式
13.等价等值式
14.假言易位
15.等价否定等值式
16.归谬论

等值演算：由已知的等值式推演出另外一些等值式的过程称作等值式演算

置换规则：设F(A)是含公式A的命题公式，F(B)是用公式B置换F(A)中所有A的出现后得到的命题公式。

命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式，仅由有限个文字构成的合取式称作简单合取式。

一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式
一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式

由有限个简单合取式的析取构成的命题公式称作析取范式。由有限个简单析取式的合取构成的命题公式称作合取范式。

任一命题公式都存在与之等值的析取范式与合取范式。

在含n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按照下标从小到大或按照字典序顺序排列，陈这样的简单合取式（简单析取式）为极小项（极大项）。

所有简单合取式（简单析取式）都是极小项（极大项）的析取范式（合取范式）称为主析取范式（主和取范式）

$F:{\{0,1\}}^n\rightarrow \{0,1\}$ 为n元正值函数。