离散数学教学课件01-命题逻辑-1.6~1.7.pptVIP

第一章 命题逻辑Propositional Logic 第六节 范式 第六节 范式 问题 对一个命题公式，除了真值表以外，怎样才能判定其类型？ 已知一个公式为真和为假的所有赋值，能否写出该公式的表达式？ 如何能找出命题公式的标准形式，使我们仅根据这种标准形式就能判断两个公式是否等值？ 范式 一、简单合取式与简单析取式 1. 简单合取式 定义：在一个公式里，仅由命题变元及其否定构成的合取式，叫做简单合取式（或基本积，质合取式）其中，每个命题变元或其否定，成为合取项。 例如：P，? Q，P ∧ Q，P ∧ Q ∧ ? Q 简单合取式 定理：简单合取式为矛盾式的充要条件是： 它同时含有某个命题变元及其否定 证明：1）充分性：对于任意命题变元P， P ∧ ? P为F 若P ∧ ? P在简单合取式中出现，它必为永假式 2）必要性：设某简单合取式为永假式，但它并不同时包含任何命题变元及其否定 若对各不带否定的命题变元赋值T，对带否定的命题变元赋值F，则该简单合取式的值为T，与假设矛盾。证毕 简单析取式 2. 简单析取式 定义：在一个公式里，仅由命题变元及其否定构成的析取式，叫做简单析取式（或基本和，质析取式）其中，每个命题变元或其否定，成为析取项。 例如：P，? Q，P ∨ Q，P ∨ Q ∨ ? Q 定理：简单析取式为重言式的充要条件是： 它同时含有某个命题变元及其否定 范式 二、析取范式与合取范式 1. 析取范式 定义：给定的命题公式若能表示为与之等价的简单合取式的析取，即 A ? ∨ Ai， Ai为简单合取式。则称该简单合取式的析取为给定公式的析取范式。例如：(P ∧ Q) ∨ (P ∧ ? Q) ∨ ? Q 定理： 一个析取范式为矛盾式，当且仅当它的 每个简单合取式都是矛盾式。 （证明略） 合取范式 2.合取范式 定义：给定的命题公式若能表示为与之等价的简单析取式的合取，即 A ? ∧ Ai， Ai为简单析取式。则称该简单析取式的合取为给定公式的合取范式。 例如：(P ∨ Q) ∧ (P ∨ ? Q) ∧ ? Q 定理：一个合取范式为重言式，当且仅当它的 每个简单析取式都是重言式。 定理：任何一个命题公式，都可以表示成为析取范式和合取范式。 求范式的方法 求范式的方法： 利用命题定律，消去公式中除? 、∧、∨以外的所有联结词 使用德·摩根律以及双否定律(? ? A ? A)将公式中出现的联结词 ? 都移到命题变元前 利用结合律、分配律等，将公式化为析取或合取范式 范式 例1.33： 求P ∧ (P ? Q)的析取范式与合取范式 解： P ∧ (P ? Q) ? P ∧ (? P ∨ Q) 合取范式 ? (P ∧? P) ∨ (P ∧Q) 析取范式 ? P ∧ Q 既是析取范式，也是合取范式 范式 例1.34 求证：Q ∨ P∧? Q ∨ ? P∧? Q是永真式 证明：Q ∨ P∧? Q ∨ ? P∧? Q ? Q ∨ (P ∨ ? P)∧? Q ? (Q ∨ P ∨ ? P)∧ (Q ∨ ? Q) 在这个合取范式中，每个简单析取式都是重言式， 因此，该公式为重言式。 范式 例1.35 求：? (P ∨ Q) ? (P∧Q)的析取范式与合取范式 解： ? (P ∨ Q) ? (P∧Q) ?(? (P ∨ Q) ? (P∧Q)) ∧ ((P∧Q) ?? (P ∨ Q)) ? (P ∨ Q ∨ (P∧Q)) ∧ (? (P∧Q) ∨ ? (P ∨ Q)) ? (P ∨ Q ) ∧ (? P ∨ ? Q ∨ (? P ∧ ? Q ) ) ? (P ∨ Q ) ∧ (? P ∨ ? Q) 合取范式 ? (P ∧? P ) ∨ (Q ∧? P ) ∨ (P ∧? Q ) ∨ (Q ∧? Q) 析取范式 范式 例1.36 求公式 (P ? Q ) ? P 的判定问题 解： (P ? Q ) ? P ? ? (? P ∨ Q ) ∨ P ? (P ∧ ? Q ) ∨ P ? P 根据该合取范式可知，该公式不是重言式 根据该析取范式可知，该公式不是矛盾式 因此该公式是偶然式 范式 回到本节开始所提到的问题： 对一个命题公式，除了真值表以外，怎样才能判定其类型？ 已知一个公式为真和为假的所有赋值，能否写出该公式的表达式？ 如何能找出命题公式的标准形式，使我们仅根据这种标准形式就能判断两个公式是否等值？ 主范式 三、主析取范式 定义：在含有n个命题变元P1，P2，…，Pn简单合取式中，若每一个Pi和? Pi恰好有一个出现一次，而且正好出现在左起第i个变元的位置上（若无下标，按字典顺序）则