1、Discrete Mathematics 西南科技大学 计算机科学与技术学院第一章 命题逻辑 1.4 范式及用途 Discrete Mathematics 西南科技大学 计算机科学与技术学院引言q 给定一个命题公式，如何判断它的类型 是重言式、矛盾式、还是可满足式？q 目前已经给出了两种方法，即 真值表法 和 逻辑等价演算法 。q 还有第三种方法，这就是把命题公式化成一种统一的、标准的公式 范式 。Discrete Mathematics 西南科技大学 计算机科学与技术学院给定命题变元 p,q，则 p， q， p， q， p q， p q， p q， p q等都是简单析取式，而p， q， p，
2、 q， p q， p q， p q， p q 都等都是简单合取式。 1.简单析取式和简单合取式定义 仅由有限个命题变元或其否定构成的析取式称为 简单析取式 。仅由有限个命题变元或其否定构成的合取式称为 简单合取式 。Discrete Mathematics 西南科技大学 计算机科学与技术学院2.析取范式和合取范式定 义 (1)仅 由有限个 简单 合取式 构成的 析取式 称 为析取范式 ；(2)仅由有限个 简单析取式 构成的 合取式 称为合取范式 。u显然任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式。Discrete Mathematics 西南科技大学 计算机科学与技术学院例
3、如 ： A=(p q r) (p q) (p q) 则 A为析取范式 。A的对偶式为： A*=(p q r) (p q) (p q) 显然， A*为合取范式。u 对任何给定的命题公式，都能求出与之等价的析取范式与合取范式。Discrete Mathematics 西南科技大学 计算机科学与技术学院定理 (范式存在定理 ) 任一命题公式都存在着与之等价的析取范式和合取范式。下述分析给出了任何命题公式范式存在性的证明，这证明同时也是求其范式的 具体步骤 ，即(1).消去对 、 、 来说冗余的联结词。即用基本的逻辑恒等式及置换规则将 、 联结词消去，所用的逻辑恒等式是 pq p q p q (p q
4、) (p q)Discrete Mathematics 西南科技大学 计算机科学与技术学院(2).否定号消去或内移若遇有 p或 (p q)， (p q) 等形式，利用双重否定律和德 .摩根律可将否定号消去或内移，即 p p ；(p q) p q ；(p q) p q。 Discrete Mathematics 西南科技大学 计算机科学与技术学院(3).利用分配律 若是求析取范式，应该利用 “ ”对 “ ”的分配律；若是求合取范式，应该利用 “ ”对 “ ”的分配律。 任给一个命题公式 A， 经过以上三步演算，可得到一个与 A逻辑等价的析取范式或合取范式。u 值得注意的是， 任何命题公式的析取范
5、式和合取范式都不是唯一的，我们把其中运算符最少的称为 最简析取 (合取 )范式 。 Discrete Mathematics 西南科技大学 计算机科学与技术学院例 1 求下面命题公式的合取范式和析取范式。解 (1)求合取范式 至此，求出了原公式的合取范式。 但上式可再化简，得 ： (p q) (r p)， 该式也是原公式的合取范式（最简），这说明与某个命题公式等价的合取范式是不唯一的。 Discrete Mathematics 西南科技大学 计算机科学与技术学院(2)求析取范式最后结果为原公式的析取范式，利用交换律和吸收律得 ，也是原公式的析取范式，由此可见，与命题公式等值的析取范式也是不唯一的。
