离散数学课件第一章(第4讲).pptVIP

Ｐ∧Ｑ?（Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）∧（?Ｐ∨Ｑ）根据真值表，可直接写出各命题公式的主合取范式：Ｐ→Ｑ??Ｐ∨ＱＰ?Ｑ?（Ｐ∨?Ｑ）∧（?Ｐ∨Ｑ）讨论：（1）该命题公式的主合范式中大项的个数等于其真值表中真值为“Ｆ”的个数。（2）由真值表找大项的方法为：将表中值为“Ｆ”所对应的真值指派中，T对应变元的否定，F对应变元本身。（3）只要命题公式不是永真式，则一定可以写出与其等价的唯一的主合取范式。（4）可用主合取范式判定二个命题公式是否等价。（5）对应于有ｎ个变元的命题公式，则一定有：主析范式小项数＋主合范式大项数＝2n下面介绍不用真值表求一命题公式主合取范式的方法：（1）将命题公式化为与其等价的合取范式；（2）除去永真项，合并析取项中相同变元，变为最简合取式；例：Ｐ∨?Ｐ∨Ｑ为永真项，去掉。Ｐ∨Ｐ∨Ｑ?Ｐ∨Ｑ，合并析取项中相同变元。（3）对析取项补入没有出现的命题变元，即添加(析取)例如（Ｐ∧?P）的形式，并应用∨对∧的分配律展开公式。例：若命题公式有二个变元Ｐ、Ｑ，当合取范式中的某一项缺少变元时，利用“∨”对“∧”的分配律添项：即：Ｐ?Ｐ∨（Ｑ∧?Ｑ）?（Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）（4）合并相同的大项。例：求Ｐ∧（Ｐ→Ｑ）∨Ｑ的主合取范式解：原式?Ｐ∧（?Ｐ∨Ｑ）∨Ｑ?（Ｐ∧?Ｐ）∨（Ｐ∧Ｑ）∨Ｑ?（Ｐ∧Ｑ）∨Ｑ?（Ｐ∨Ｑ）∧（Ｑ∨Ｑ）?（Ｐ∨Ｑ）∧Ｑ----合并析取项中相同变元，化为最简合取范式?（Ｐ∨Ｑ）∧(Ｑ∨（?Ｐ∧Ｐ）)----添项?（Ｐ∨Ｑ）∧（?Ｐ∨Ｑ）∧（Ｐ∨Ｑ）?（Ｐ∨Ｑ）∧（?Ｐ∨Ｑ）----合并相同大项4．主析(合)取范式的编码表示为了能够用编码的形式表达主析(合)取范式，作如下规定：小项和大项中的各命题变元的出现位置必须安排一固定次序。（１）小项的编码对于有ｎ个变元的命题公式，则最多可有2n个小项，用mi表示小项，用m0∨m1…∨m2n-1来表示主析取范式。P∧Q∧R1117m7P∧Q∧?R1106m6P∧?Q∧R1015m5P∧?Q∧?R1004m4?P∧Q∧R0113m3?P∧Q∧?R0102m2?P∧?Q∧R0011m1?P∧?Q∧?R0000m0小项表示二进制数十进制数m(i)十下面表格列出三个变元，且Ｐ、Ｑ、Ｒ的位置已固定，小项表达如下：对主析取范式编码的方法：(1)将小项中的变元按照固定次序排列；(2)用二进制表示出其对应的小项，将小项中变元的肯定用1表示，变元的否定用0表示；(3)将二进制转变为十进制，用mi表示小项；(4)将mi表示的各小项，用析取符号连接，得到编码表示的主析取范式；(5)取各小项下标的十进制数字，按照顺序置于?符号后，可进一步简化编码表示主析取范式。解：原式?（Ｐ∧Ｑ∧Ｒ）∨（Ｐ∧Ｑ∧?Ｒ）∨（?Ｐ∧?Ｑ∧Ｒ）∨（?Ｐ∧Ｑ∧Ｒ）?m(111)∨m(110)∨m(001)∨m(011)?m7∨m6∨m1∨m3??m1,m3,m6,m7??1,3,6,7例：求（Ｐ∧Ｑ）∨（?Ｐ∧Ｒ）的主析取范式的编码表达式：（设小项按照Ｐ、Ｑ、Ｒ次序固定）（2）大项的编码对于有ｎ个变元的命题公式，则最多可有2n个大项，用Mi表示大项，用M0∨M1…∨M2n-1来表示主合取范式。?P∨?Q∨?R1117M7?P∨?Q∨R1106M6?P∨Q∨?R1015M5?P∨Q∨R1004M4P∨?Q∨?R0113M3P∨?Q∨R0102M2P∨Q∨?R0011M1P∨Q∨R0000M0大项表示二进制数十进制数M(i)十下面表格列出三个变元，且Ｐ、Ｑ、Ｒ