离散数学第一章总结

离散数学第一章

1.公式类型

1）重言式

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

2）矛盾式

永假式，真值恒为0。

3）可满足式

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

2.成真赋值与成假赋值

也叫成真指派与成假指派。

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

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

3.等价式

也叫等值式，即任意的分量指派情况下，公式的值都相同，则等价。

可用真值表、等值演算法判断。

4.析取范式与合取范式

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

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

有限个合取式的析取称为析取范式。

有限个析取式的合取称为合取范式。

合取范式与析取范式仍不唯一。

析取范式与合取范式中只能包含非、且、或。

任意公式都存在等值的析取范式与合取范式。

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

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

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

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

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

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

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

eg：真值表举例：

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

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

eg2：再举一个例子