离散数学第1.5陈瑜 1.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 主要内容: 析取范式、合取范式、主析取（主合取）范式、极小项、极大项等的定义 求主析取范式和主合取范式的方法 1）真值表法 2）等价变换法 实例分析 1.5 命题公式的范式表示： 一个命题公式可有无穷多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也不能解决。 要解决判定问题，可用范式(公式的标准型)。 范式——全名叫规范型式normal form,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。 1.5 命题公式的范式表示： 一个命题公式可有无穷多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也不能解决。 要解决判定问题，可用范式(公式的标准型)。 范式——全名叫规范型式normal form,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。 例5.1 1）Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语 、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 例5.1 1） Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短语、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 结论： 从上述定义和例子可以得出如下关系： 结论： 从上述定义和例子可以得出如下关系： 结论： 从上述定义和例子可以得出如下关系： 结论： 从上述定义和例子可以得出如下关系： 定理1.6 （范式存在定理）任何命题公式都存在与之等价的合取范式与析取范式。证明： （略p14) 求一个命题公式的与之等价的析取范式和合取范式，其步骤如下： 求一个命题公式的与之等价的析取范式和合取范式，其步骤如下： 求一个命题公式的与之等价的析取范式和合取范式，其步骤如下： 范式的求取（化归）过程： （1）消除式中联结词→, ? P→Q ? ～P∨Q E2 P ? Q ? （P→Q）∧（Q→P） E1 （2）利用德?摩根定律将联结词～直接移到各命题变元之前并简化 E19 : ～～ P ? P E23: ～（P∨Q） ? ～ P∧～Q E24: ～（P∧Q） ? ～P∨～Q 范式的求取（化归）过程： （1）消除式中联结词→, ? P→Q ? ～P∨Q E2 P ? Q ? （P→Q）∧（Q→P） E1 （2）利用德?摩根定律将联结词～直接移到各命题变元之前并简化 E19 : ～～ P ? P E23: ～（P∨Q） ? ～ P∧～Q E24: ～（P∧Q） ? ～P∨～Q (3）利用分配律、结合律、交换律等，将公式化成合取（析取）范式。 例4.2 求（P∧（Q→R））→S的合取范式 解：（P∧（