1-3 命题逻辑 离散数学 教学课件.pptVIP

由p, q, r三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真 赋值 名称 公式 成假 赋值 名称 ?p ??q ??r ?p ??q ? r ?p ? q ??r ?p ? q ? r p ??q ? ?r p ??q ? r p ?q ??r p ?q ? r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p ? q ? r p ? q ??r p ? ?q ? r p ? ?q ??r ?p ? q ? r ?p ? q ??r ?p ? ?q ? r ?p ? ?q ??r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 M1 M2 M3 M4 M5 M6 M7 主合取范式 主合取范式 由极大项构成的合取范式 如，n=3, 命题变项为p, q, r 时，主合取范式: (p?q??r)?(?p?q??r) ? M1?M5 定理 任何命题公式都存在着与之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法 1. 求A的合取范式A′； 2. 若A′的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式： B ? B ? 0 ? B ? (pi ? ? pi ) ? (B ? pi) ? (B ? ? pi) 3. 将重复出现的命题变项、重言式及重复出现的极大项都“消去”。 4. 将极大项按由小到大的顺序排列，并用 ? 表示之，如 M1 ? M2 ? M6 用 ?(1,2,6) 表示。 用等价演算法求主合取范式的步骤 求公式(p??q)?r 的主合取范式 解1: 原式? ?(? p ? ? q) ?r , ? (p?q) ? r ? (p?r)?(q?r) 合取范式① p?r? (p?r)?(q ? ?q ) ?(p?r ?q)?( p? ?q ?r) ? M000 ? M010 ② q?r ?(q?r)?(p? ? p ) ?(p?r ? q)?(? p? q ?r) ? M000 ? M100 ③ ②, ③代入①并排序，得主合取范式： 原式?M0 ? M2 ? M4? ?(0,2,4) 解2: (p??q)?r ? (? p ? ? q) ?r , ? (p?q) ? r ? (p?r)?(q?r) (合取范式) ? M0x0 ? Mx00 ? M000 ? M010 ? M000 ? M100 ? M0 ? M2 ? M4 ? ?(0,2,4) 求公式(p??q)?r 的主合取范式 ? (p?q)?r （析取范式） ? m11x ? mxx1 ? (m110 ? m111)?(m001 ? m011 ? m101 ? m111) ? ?(1,3,5,6,7) 极小项mi与极大项Mi的关系—— ?mi ? Mi ?Mi ? mi 由主析取范式求主合取范式举例 已知命题公式A含3个命题变项，其成真赋值为000、010、100、110，求主析取范式和主合取范式 解：主析取范式为：m0 ? m2 ? m4 ? m6 因为成假赋值为：111、101、011、001 所以， 主合取范式为 M1 ? M3 ? M5 ? M7 作业3 P34: 12 P35: 13 P35: 15 * 判断命题公式类别的方法 真值表法 等价代换法 化成标准型（主析取范式和主合取范式）的方法 * 公式类别：重言式、矛盾式和可满足式 * 公式类别：重言式、矛盾式和可满足式 * 任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式。 例如，A = ? P ?(P ?Q) ?(P ? ? Q ?R) ， A为析取范式 则A的对偶式A* = ? P ? (P ? Q) ? (P ? ? Q ?