[学习总结]JackieLee.ppt

2) 求析取式 ((P ? Q)?R)?P ? ? (? (P ? Q) ? R) ?P ? ? ( (?P ? ? Q) ? R) ?P ? (? (?P ? ? Q) ? ? R) ?P ( ? ) ( ? ) ( ? ) ( ? ) ? ((? ?P ? ? ? Q) ? ? R) ?P ( ? ) ? (? (P ? Q) ? R)?P ? ((P ? Q) ? ? R) ?P ? (P ? ? R ) ? (Q ? ? R) ?P ? P ? ( Q ? ? R ) ( ? ) ( ? ) ( 吸收律 ) 值得注意的是，任何命题公式析取范式或合取范式不唯一，因而不能作为命题公式的标准形式。为此，我们进一步引入“ 主取析范式”、“ 主合取范式”的概念。它们是用极小项极大项来定义的。 极小项：含有n个命题变元的简单合取式, 极大项：含有n个命题变元的简单析取式， 且具有形式： ? ? ? 且具有形式： ? ? ? 注1. 其中 指Pi或? Pi，1? i ? n 注2. 极小项，极大项中必含有n–1个联结词(?或?) 注3. 一定位于第i个位置，顺序不能乱。 注4. 任意两个极小项的合取为矛盾式； 任意两个极大项的析取为重言式。 定 理 3 主析取范式：与命题公式A对应的析取范式中的简单合取式全是极小项， 主合取范式：与命题公式A等值的合取范式中的简单析取式全是极大项， 任何命题公式的主析取范式和主合取范式一定存在，而且唯一。 特别地约定，永假式A的主合取式为0。 特别地约定，永真式A的主合取范式为1。 例1.8 求命题公式A＝? (P?Q)?(P?Q)的主析取范式和主合取范式 求命题公式的主析取范式和主合取范式的两个基本方法：真值表法和等值演算 解题思想 解：本例采用真值表法 (1) 先构造A的真值表 P Q ? (P?Q) (P?Q) P?Q A 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 (2) 根据成真赋值写出对应 极小项，并排序；根据成假赋值定出对应的极大项, 并全部排序 成真赋值 0 1，1 0， 成假赋值 0 0，1 1， 对应的极小项m1 = ? P?Q m2= P? ? Q ; 对应的极大项M0 = P?Q M3= ? P ? ? Q ; (3) 按(2)中约定的顺序写主析取范式和主合取范式: 主析取式：m1 ? m2 主合取范式：M0 ? M3 例1.9 求公式A＝((P?R)?Q)?(Q?P)的主析取范式和主合取范式 解法一：用真值表法 例1.4 列命题公式(P?(P?Q))?Q的真值表 P Q P?Q P?(P?Q) ((P?(P?Q))?Q 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 1 小结 1. 什么是命题？ 2. 如何符号化？(五种联结词) 3. 如何分析命题公式的真值(真值表的列法) 重言式或永真式： 矛盾式或永假式：命题公式A在各种赋值下取值均为假。 可 满 足 式：命题公式A至少存在一组赋值为成真赋值。 若A在各种赋值下取值恒为真, 则A为重言式。 设A是一个命题公式， 四、命题公式的类型 §1.3 等 值 演 算 等值公式 用真值表可以验证公式等值 设A，B为二命题公式， 若等价式A?B是重言式，则A与B等值。 记作：A?B 等值关系是自反的、对称的、传递的，即为等价关系。 一、等值演算的概念 等值演算：按一定方法寻找某个复合命题公式的等值式的过程。 二、常用的重要等值公式表： 1、A??? A 双重否定律 2、A?A?A 3、A?A?A 等幂律 4、A?B?B?A 5、A?B ?B?A 交换律 6、(A?B)? C? 7、(A?B)?C ? 结合律 8、A?(B ? C ) ? 9、A?(B ? C ) ? 分配律 10、? (A?B) ? 11、 ? (A?B) ? 德 ·摩根律 A?(B?C) A?(B?C) (A?B) ?( A?C) (A?B) ? (A?C) ? A?? B ? A?? B 12、 A?(A?B) ? A 13、 A?(A?B) ? A 吸收律 * 14、 A?1 ? 1 15、 A?0 ? 0 零律 16、 A?0 ? A 17、 A?1 ? A 同一律 19、 A?? A ? 0 矛盾律 20、 A?B? ? A?B 蕴涵等值式 * 假言易位 等价否定等值式 归谬论 * 21、 A?B?(A?B)?(B?A ) 等价等值式 22、 A?B??B?? A 23、 A?B??