对偶及范式.docVIP

第四讲 对偶及范式 对偶的定义： 将命题公式中的∧换成 ∨，∨换成∧，T和F互相替代，所得公式即为公式A的对偶式，记作 A* 例如:（（p∨q））））(p∧q）, (p∧q）德·摩律B的对偶式，如果A?B ，那么A*?B*。也就是说，一对等价公式的对偶式也等价。 范式 在提出范式之前，要先提出两个概念：简单合取式和简单析取式。 简单合取式：用∧连接各个命题变项或其否定所形成的命题公式就是简单合取式。 比如 p∧q, p∧q∧┓r， p∧┓p∧┓r 都是简单合取式。 简单析取式：用∨连接各个命题变项或其否定所形成的命题公式就是简单析取式。 比如 p∨q, p∨q∨┓r， p∨┓p∨┓r 都是简单析取式。 需要注意的是： p，┓p即是简单合取式，又是简单析取式。 给出两个显而易见的定理： 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定， 如p∧┓p∧┓r 一个简单析取式是重言式当且仅当它同时含有某个命题变项及其否定， 如p∨┓p∨┓r 范式的定义： 由有限个简单合取式构成的析取式称为析取范式。 如 （p∧q）∨（p∧┓p∧┓r）a,b,c……），那么称这样的简单合取式为极小项。 比如p∧q∧┓r , p∧q。 极大项： 在一个简单析取式中，如果每个命题变项和它的否定仅出现一个，并且必须出现一个，并且命题变项或其否定是按固定的顺序排列的，那么称这样的简单析取式为极大项。 比如p∨q∨┓r , p∨q。 在提出了极小项和极大项之后，我们可以在命题公式，命题变项的真值和二进制表示之间建立一个对应关系。如下表所示。 其中，公式为真时，p,q,r的赋值称为成真赋值。 公式为假时，p,q,r的赋值称为成假赋值。 Mi ，mi的脚标i表示赋值列中的三个数值所组成的二进制所对应的十进制数。 由表所知：┓mi ? Mi 极小项 极大项 公式 成真赋值 名称 公式 成假赋值 名称 ┓p∧┓q∧┓r 0 0 0 m1 p∨q∨r 0 0 0 M1 ┓p∧┓q∧r 0 0 1 m2 p∨q∨┓r 0 0 1 M2 ┓p∧q∧┓r 0 1 0 m3 p∨┓q∨r 0 1 0 M3 ┓p∧q∧r 0 1 1 m4 p∨┓q∨┓r 0 1 1 M4 p∧┓q∧┓r 1 0 0 m5 ┓p∨q∨r 1 0 0 M5 p∧┓q∧r 1 0 1 m6 ┓p∨q∨┓r 1 0 1 M6 p∧q∧┓r 1 1 0 m7 ┓p∨┓q∨r 1 1 0 M7 p∧q∧r 1 1 1 m8 ┓p∨┓q∨┓r 1 1 1 M8 主范式的定义： 由n个命题变项构成的析取范式中所有的简单合取式都是极小项，称为主析取范式。 由n个命题变项构成的合取范式中所有的简单析取式都是极大项，称为主合取范式。 任何命题公式都存在着与之等价的主析取范式和主合取范式。 通过一道例题来介绍主析取范式和主合取范式的求法： 例：求 （（p∨q）→r）→p 的主析取范式和主合取范式 （（p∨q）→r）→p ?（┓（p∨q）∨r）→p ? ┓（ ┓（p∨q）∨r）∨p ?（p∨q）∧┓r∨p ?（p∨q）∧（┓r∨p） 下一步非常关键：前一个括号内缺少r，所以 析取一个(r∧┓r)，后一个括号也是 同样，如果是（p∧q），就合取一个(r∨┓r)； ? （（p∨q）∨(r∧┓r)）∧(（┓r∨p）∨(q∧┓q)) ?（p∨q∨r）∧（p∨q∨┓r）∧（p∨┓r∨q）∧（p∨┓r∨┓q） ?（p∨q∨r）∧（p∨q∨┓r）∧（p∨┓r∨┓q） ?M000∧M001∧M011 ?m010∨m100∨m101∨m110∨m111 主析取范式和主合取范式的简记式中的角标是互补的，知其一即可求另一个。 另一种求法是画真值表。 主范式的作用如下： 1. 求公式的成真赋值与成假赋值 2. 判断公式的类型。 A为重言式当且仅当它的主析取范式含全部2n个极小项。 A为矛盾式当且仅当它的主析取范式不含极小项。 A为可满足式当且仅当它的主析取范式至少含有一个极小项。 3 判断两公式是否等价。 求出两公式的主析取范式，若相同，则等价；否则，不等价。