数理逻辑1.51.pptVIP

1.5 对偶与范式 对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 对偶式和对偶原理 定义 在仅含有联结词?, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A*. 从定义不难看出，(A*)* 还原成A 定理 设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，B为两个命题公式， 若A ? B，则A* ? B*. 析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 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等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 形如 p??q?r, ?p?q??r 的公式既是析取范式， 又是合取范式 (为什么?) 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式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) （?对?分配律） 这一步得到合取范式（由两个简单析取式构成） 极小项与极大项 定义 在含有n个命题变项的简单合取式(简单析取式)中， 若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1?i?n）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）. 说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称. mi与Mi的关系: ?mi ? Mi , ?Mi ? mi 极小项与极大项(续) 由p, q两个命题变项形成的极小项与极大项 由p, q, r三个命题变项形成的极小项与极大项 主析取范式与主合取范式 主析取范式: 由极小项构成的析取范式 主合取范式: 由极大项构成的合取范式 例如，n=3, 命题变项为p, q, r时， (?p??q?r)?(?p?q?r) ? m1?m3 是主析取范式 (p?q??r)?(?p?q??r) ? M1?M5 是主合取范式 A的主析取范式: 与A等值的主析取范式 A的主合取范式: 与A等值的主合取范式. 主析取范式与主合取范式(续) 定理 任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是惟一的. 用等值演算法求公式的主范式的步骤： (1) 先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若