东南大学离散数学课件.pptVIP

2.2 析取范式和合取范式 把命题公式化归为一种标准的形式，称此标准形式为范式。 以有限次步骤来判定命题公式是否为永真式、永假式，或者可满足的，或者二个命题公式等价等这一类的问题，统称为判定问题。 讨论范式和主范式的目的之一就是为了进行判定。 2.2 析取范式和合取范式 定义: 命题变元及其否定统称为文字。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称作简单合取式。 例：设p、q为二个命题变元 p，q，p∨p，q∨q，?p∨q， ?q∨ ?p，p∨q，p∨ ?q 称为简单析取式 q，p∧p，q∧q， ?p∧q， ?q∧ ?p，p∧q，p∧ ?q 称为简单合取式。 2.2 析取范式和合取范式 定理: 1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式。 2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式。 2.2 析取范式和合取范式 定义2.3： 1)由有限个简单合取式构成的析取式称为析取范式。 2)由有限个简单析取式构成的合取式称为合取范式。 3)析取范式与合取范式统称为范式。 例： p∧q ∧r 既是析取范式又是合取范式。 2.2 析取范式和合取范式 定理： 1)一个析取范式是永假式当且仅当它的每个简单合取式都是永假式。 例：p??p ?(p∧?p)∨(?p∧p) ?Ｆ　永假式 2)一个合取范式是永真式当且仅当它的每个简单析取式都是永真式。 例：(p?p)?(?p∨p)∧(p∨?p)?Ｔ 2.2 析取范式和合取范式 定理(范式存在定理)： 任意命题公式都存在着与之等值的析取范式与合取范式。 方法： 利用等值公式：化去“→”、“?”联结词，把命题公式变为与其等值的用{?，∧，∨}表达的公式。 例: p→q??p∨q， p?q?(p∧q)∨(?p∧?q) ?(?p∨q)∧(p∨?q) 2.2 析取范式和合取范式 将“?”深入到原子命题变元前，并使变元前最多只有一个“?”词。 例：?(?p∨?q)?? ?p∧ ? ?q ?p∧q 利用“∧”对“∨”的分配，将公式化成为析取范式。 除去永假项得最简析取范式。 2.2 析取范式和合取范式 例：求(p → q)∧(p∧q)的析取范式： 解：原式 (1)化去→词 ?(?p∨q)∧(p∧q) (2)“∧”对“∨”分配，化为析取范式 ?(?p∧p∧q)∨(q∧p∧q) (3)最简析取范式 ?p∧q 　 2.2 析取范式和合取范式 求一个命题公式的合取范式的方法和求析取范式的方法雷同： 第(１)、(２)步相同； 第(３)利用“∨”对“∧”的分配就行； 第(４)去掉永真项。 2.2 析取范式和合取范式 例：求((p∨q) → r) → p的最简合取范式和最简析取范式。 解：1. 求最简析取范式 原式? (?(p∨q)∨r) → p ? ?(?(p∨q)∨r)∨p ? (? ?(p∨q)∧? r)∨p ?(p∨q)∧? r∨p ?(p ∧? r)∨(q∧? r)∨p ? p∨(p ∧? r)∨(q∧? r) ? p∨(q∧? r) 吸收律 2.2 析取范式和合取范式 2. 求最简合取范式 原式? (?(p∨q)∨r) → p ? ?(?(p∨q)∨r)∨p ? (? ?(p∨q)∧? r)∨p ?(p∨q)∧? r∨p ?(p∨q ∨p)∧(? r∨p) ? (p∨q)∧(? r∨p) 2.2 析取范式和合取范式 讨论： 一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等值的。 2.2 析取范式和合取范式 定义：在含有n个命题变元的简单合取式(简单析取式)中，若每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变元或它的否定式出现在从左算起的第i位上(若无角标则按字典顺序排列)，称这样简单合取式(简单析取式)为极小项(极大项)。 说明： （a）各命题变元的位置安排一固定次序； （b）对极小（大）项安排一个次序。 　对于有ｎ个变元的命题公式，则最多可有2n个极小（大）项。 2.2 析取范式和合取范式 对一个命题变元，极小项有21=2个， 即：p、?p。 对二个命题变元，极小项有22=4个， 即：p∧q、?p∧q、p∧ ?q、 ?p∧ ?q。 对三个命题变元，极小项有23=8个， 即：p∧q∧r、p∧q∧?r、p∧?q