离散数学1.5讲述.ppt

* 1.5 对偶与范式 对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 * 对偶式和对偶原理 定义1.17 在仅含有联结词?, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*. 从定义不难看出，(A*)* 还原成A 例 ?(p ∧q) 与?(p ∨ q) 0 与 1 (p ∨ q) ∨0与(p ∧ q) ∧ 1 * 定理1.2 设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) 例 A(p,q,r) ? p ∧(? q ∨ r) A* (p,q,r) ? p ∨ (? q ∧ r) （1） ? A(p,q,r) ? ?（ p ∧(? q ∨ r)） ? ? p ∨ (q ∧ ? r) A* (? p, ? q, ? r) ? ? p ∨ (q ∧ ? r) （2） A (? p, ? q, ? r) ? ? p ∧( q ∨ ? r) ? A* (p,q,r) ? ? （p ∨ (? q ∧ r)）? ? p ∧( q ∨ ? r) * 定理1.3（对偶原理）设A，B为两个命题公式， 若A ? B，则A* ? B*. 例 1. A ? 1（重言式），则A* ? 0（矛盾式） 2. A ? 0（矛盾式） ，则A* ? 1（重言式） 3. p ∨ (? p ∨ ( q ∧ ?q) ）?1 则 p ∧ (? p ∧ ( q ∨ ?q) ）?0 * 析取范式与合取范式 简单析取式:有限个命题变项及其否定构成的析取式 如 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是简单析取式 * 析取范式与合取范式 范式:析取范式与合取范式的总称? 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 1.单个命题变项及其否定既是简单析取式，又是简单合取式 2.形如 p??q?r, ?p?q??r 的公式既是析取范式,又是合取范式 . 3. 析取范式的对偶式为合取范式，合取范式的对偶式为析取范式. 4.一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式. 5.一个合取范式是重言式，当且仅当它的每个简单析取式都是重言式. * 命题公式的范式 定理 1.4 任何命题公式都存在着与之等值的析 取范式与合取范式. 求公式A的范式的步骤： (1) 消去A中的?, ?（若存在） (2) 否定联结词?的内移或消去 (3) 使用分配律 ?对?分配（析取范式） ?对?分配（合取范式） 注意：公式的范式存在，但不惟一 * 求公式的范式举例 例 求下列公式的析取范式与合取范式 (1) A=(p??q)??r 解 (p??q)??r ? (?p??q)??r （消去?） ? ?p??q??r （结合律） 这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式） * 求公式的范式举例 (2) B=(p??q)?r 解 (p??q)?r ? (?p??q)?r （消去第一个?） ? ?(?p??q)?r （消去第二个?） ? (p?q)?r （否定号内移——德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (p?q)?r ? (p?r)?(q?r) （?对?分配律） 这一步得到合取范式（由两个简单析取式构成） * 极小项与极大项 定义1.20 在含有n个命题变项的简单合取式(简单析取式) 中，若每个命题变项与其否定不同时存在，而二者之一出 现且仅出现一次