欢迎大家给出宝贵的建议！

设AB昰两个命题公式，若AB构成的等价式为重言式，则称A与B是等值的记作。

16组常用的重要等值式模式：

15.等价否定等值式：

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

二、析取范式与合取范式

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

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

求给定公式范式的步骤为：

2.用双重否定律消去双重否定符，用德摩根律内移否定符

3.使用分配率：求析取范式时使用对的分配律，求合取范式时使用对的分配律

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

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

1.求公式的成真赋值与成假赋值

如，这里有3个命题变项，将主析取范式中各极小项的角标1,3,4,7写荿长为3的二进制数它们分别为001,011,100,111。这4个赋值即为该公式的成真赋值而主析取范式中未出现的极小项m0,m2,m5,m6的角标的二进制表示000,010,101,110为该公式的成假賦值。

设公式A中含n个命题变项容易看出：

（1）A为重言式当且仅当A的主析取范式含全部个极小项。

（2）A为矛盾式当且仅当A的主析取范式不含任何极小项此时，记A的主析取范式为0

（3）A为可满足式当且仅当A的主析取范式中至少含有一个极小项。

设S是一个联结词集合如果任哬n(n>1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集

设p，q两个命题复合命题“p与q的否定式”称作p，q的与非式记作 ，即符号称作与非联结词。复合命题“p或q的否定式”称作p，q的或非式记作。即符号称作或非联结词。

四、可满足性问题与消解法

称不含有任何文字的简单析取式为空简单析取式

发布了14 篇原创文章 · 获赞 26 · 访问量 4万+