离散数学对偶和范式.ppt

* 从A的主析取范式求其主合取范式的步骤 (a)求出A的主析取范式中设有包含的小项。(b) 求出与(a)中小项的下标相同的大项。(c) 做(b)中大项之合取，即为A的主合取范式。例如，(p?q)?q?m1?m3，则(p?q)?q?M0?M2。 第二十三页，共三十五页，2022年，8月28日 * 求公式的主范式 例 求公式 A=(p??q)?r的主析取范式与主合 取范式. (1) 求主析取范式 (p??q)?r ? (p?q)?r , （析取范式） ① (p?q) ? (p?q)?(?r?r) ? (p?q??r)?(p?q?r) ? m6?m7 , ② 第二十四页，共三十五页，2022年，8月28日 * 求公式的主范式(续) r ?(?p?p)?(?q?q)?r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5?m7 ③ ②, ③代入①并排序，得 (p??q)?r ? m1?m3?m5? m6?m7（主析取范式） 第二十五页，共三十五页，2022年，8月28日 关于离散数学对偶和范式 第一页，共三十五页，2022年，8月28日 * 对偶式和对偶原理 定义 在仅含有联结词?, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*. 从定义不难看出，(A*)* 还原成A 显然，A也是A*的对偶式。可见A与A*互为对偶式。 第二页，共三十五页，2022年，8月28日 * 对偶式和对偶原理 定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和 A*中的全部命题变项，将A和A*写成n元函数形式， 则 (1) ? A(p1,p2,…,pn) ? A* (? p1, ? p2,…, ? pn) (2) A(? p1, ? p2,…, ? pn) ? ? A* (p1,p2,…,pn) (1)表明，公式A的否定等价于其命题变元否定的对偶式； (2)表明，命题变元否定的公式等价于对偶式之否定。 第三页，共三十五页，2022年，8月28日 * 对偶式和对偶原理 定理（对偶原理）设A，B为两个命题公式， 若A ? B，则A* ? B*. 有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方便。 第四页，共三十五页，2022年，8月28日 * 判定问题 真值表 等值演算 范式 第五页，共三十五页，2022年，8月28日 * 析取范式与合取范式 文字:命题变项及其否定的总称 如 p, ?q 简单析取式:有限个文字构成的析取式 如 p, ?q, p??q, p?q?r, … 简单合取式:有限个文字构成的合取式 如 p, ?q, p??q, p?q?r, … 注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如p，?q等。 第六页，共三十五页，2022年，8月28日 * 析取范式与合取范式 定理： 简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。 定理： 简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。 第七页，共三十五页，2022年，8月28日 * 析取范式与合取范式 简单析取式:有限个文字构成的析取式 如 p, ?q, p??q, p?q?r, … 简单合取式:有限个文字构成的合取式 如 p, ?q, p??q, p?q?r, … 析取范式:由有限个简单合取式组成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1?A2???Ar , 其中A1,A2,?,Ar是简单析取式 第八页，共三十五页，2022年，8月28日 * 析取范式与合取范式(续) 范式:析取范式与合取范式的总称? 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 形如 p??q?r, ?p?q??r 的公式既是析取范式， 又是合取范式 (为什么?) 第九页，共三十五页，2022年，8月28日 * 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式A的范式的步骤： (1) 消去A中的?, ?（若存在）（消去公式中除?、?和?以外公式中出现的所有联结词