-对偶与范式.ppt

讲授人：胡 盛 1-7 对偶与范式 第一章 数理逻辑 1-7 对偶与范式 * 本节 重点 合式公式化为主析取范式和主合取范式。 难点 对偶式和范式的作用 。 要求 掌握对偶、范式、小项、大项、合取范式、析取范式、主析取范式、主合取范式的概念； 熟练掌握将命题公式化为与其等价的主合取范式与主析取范式的方法。 第一章 数理逻辑 1-7 对偶与范式 * 序 命题公式常常含有｛?、∨、∧｝中的联结词 观察p15，1-4.8等价公式联结词符号的特征，找出规律。 如：分配律 P∨(Q∧R)?(P∨Q)∧(P∨R) P∧(Q∨R)?(P∧Q)∨(P∧R) 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶 定义：1-7.1 在给定的命题公式中，将联结词?换成?，将?换成?，若有特殊变元F和T亦互相取代，所得公式A*称为A的对偶公式。 显然，A也是A*的对偶式。 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶－举例 例题: 写出下列表达式的对偶式 ?(P?Q) ?(P ?? (Q ? ? S)) (P ? Q) ? R (P ? Q) ? T P ? Q P ? Q ??(P ? Q) ??(P ? Q) 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶－性质1 定理1-7.1：设A和A*是对偶式，P1, P2 ,…,Pn是出现在A和A*中的原子变元，则 ?A(P1, P2, …, Pn)?A*(?P1, ?P2, …, ?Pn) A(?P1, ?P2, …, ?Pn)??A*(P1, P2, …, Pn) 证明：由得·摩根定律 P∧Q??(?P∨?Q), P∨Q??(?P∧?Q) 故 ?A(P1, P2, …, Pn)?A*(?P1, ?P2, …, ?Pn) 同理 ?A*(P1, P2, …, Pn)?A(?P1, ?P2, …, ?Pn) 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶－性质1（验证） 例题3 设A*(S,W,R)是?S?(?W?R)证明 A*(?S,?W,?R)??A(S,W,R) 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶－性质1 定理1-7.2 设P1, P2, …, Pn是出现在公式A和B中的所有原子变元，如果A?B，则A*?B*。 证明：因为A?B，即 A(P1, P2, … Pn)?B(P1, P2, …, Pn)是一个重言式，故 A(?P1, ?P2, …, ?Pn)?B(?P1, ?P2, …, ?Pn)也是一个重言式。即 A(?P1, ?P2, … ?Pn)?B(?P1, ?P2, …, ?Pn) 由定理1-7.1得 ?A*(P1, P2, …, Pn)??B*(P1, P2, …, Pn) 因此 A*?B* 由定理1-5.3 第一章 数理逻辑 1-7 对偶与范式 * 1、对偶－举例 例题4 如果A(P,Q,R)是P↑(Q∧?(R↓P))，求它的对偶式。并求与A及A*等价，但仅包含联结词”∧”、“∨”、及“?”的公式。 第一章 数理逻辑 1-7 对偶与范式 * 2、范式－定义 定义1-7.2 一个命题公式称为合取范式，当且仅当它具有型式： A1∧A2∧…∧An, (n≥1) 其中A1, A2, …, An都是由命题变元或其否定所组成的析取式。 举例:(?p?S?Q)?(?P?S??R) 定义1-7.3一个命题公式称为析取范式，当且仅当它具有型式 A1∨A2∨…∨An, (n≥1) 其中A1, A2, …, An都是由命题变元或其否定所组成的合取式。 举例:P?(Q?R) 第一章 数理逻辑 1-7 对偶与范式 * 2、范式－求法 求析取范式或合取范式的步骤： 将公式中的联结词化归成∧, ∨, ?。 利用德·摩根律将否定符号?直接移到各个命题变元之前 利用分配律、结合律将公式归约为合取范式或析取范式。 第一章 数理逻辑 1-7 对偶与范式 * 1-7 对偶与范式 例题5：求(P∧(Q→R))→S的合取范式 例题6：求?(P∨Q)?(P∧Q)的析取范式 P∨(Q∧R) ?(P∨Q)∧(P∨R) ? (P∧P)∨(P∧R)∨(Q∧P)∨(Q∧R) 合取范式与析取范式形式不唯一。 第一章 数理逻辑 1-7 对偶与范式 * 2、范式－主范式（小项、大项） 定义1-7.4 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如：p∧Q 定义1-7.6 n个命题变元的析取式，称作布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如：P∨Q 第一章 数理逻辑 1-7 对偶与范式 * 2个变元所有可能组