离散数学第一章

1.公式类型

1）重言式

也是永真式，公式真值恒为1。

2）矛盾式

永假式，真值恒为0。

3）可满足式

不是矛盾式的就都是可满足式。重言式一定是可满足式。

2.成真赋值与成假赋值

也叫成真指派与成假指派。
一组原子的取值（真值指派）使得公式为真：成真指派（赋值）
一组原子的取值（真值指派）使得公式为假：成假指派（赋值）

3.等价式

也叫等值式，即任意的分量指派情况下，公式的值都相同，则等价。
可用真值表、等值演算法判断。

4.析取范式与合取范式

有限个命题变量（及其非命题）的析取称为析取式。
有限个命题变量（及其非命题）的合取称为合取式。

有限个合取式的析取称为析取范式。
有限个析取式的合取称为合取范式。
合取范式与析取范式仍不唯一。

析取范式与合取范式中只能包含非、且、或。
任意公式都存在等值的析取范式与合取范式。

极小项：（小项、布尔合取）包含n个命题变元的合取式，且每个命题变元或其非命题变元出现且仅出现一次（p出现则非p不出现、非p出现则p不出现），且出现的次序与下标次序（或字母的字典序）一致。

eg：三个命题变元，对应的小项就有八个小项。

极大项：（大项、布尔析取）包含n个命题变元的析取式，且每个命题变元或其非命题变元出现且仅出现一次（p出现则非p不出现、非p出现则p不出现），且出现的次序与下标次序（或字母的字典序）一致。

eg：三个命题变元，对应也有八个大项，需要注意的是用的是成假赋值。

主合取范式：合取范式中每个析取式都是大项，则称为主合取范式。
主析取范式：析取范式中每个合取项都是小项，则称为主析取范式

求主析取范式与主合取范式：真值表法与等值演算法。

eg：真值表举例：

要注意例子中求主析取范式中用的是小项，而求主合取范式用的是求主析取范式所剩下的项所对应的成假赋值的大项。

eg：等值演算：核心方法是抽出一个永真式，在进行等值演算
eg2：再举一个例子