《离散数学》课程教学课件（PPT讲稿）02b 析取范式和合取范式

析取范式与合取范式

析取范式与合取范式 析取范式与合取范式

析取范式与合取范式基本概念文字：命题变项及其否定的总称如 p, -p简单析取式：有限个文字构成的析取式如 p,-q,pv-q,pvqvr,...简单合取式有限个文字构成的合取式p,,pa-q,paqar,.…

1 析取范式与合取范式 基本概念 ◆文字: 命题变项及其否定的总称 如 p, p ◆简单析取式: 有限个文字构成的析取式 如 p, q, pq, pqr, . ◆简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr,

析取范式与合取范式析取范式：由有限个简单合取式组成的析取式如 p, pq, pV-q,(p-q)v(-pq-r)v(qr)合取范式：由有限个简单析取式组成的合取式如 p,pv-q,pq,(pvq)p(p-q-r)范式：析取范式与合取范式的总称2

2 析取范式与合取范式 ◆析取范式: 由有限个简单合取式组成的析取式 如 p, pq, pq, (pq)(pqr)(qr) ◆合取范式: 由有限个简单析取式组成的合取式 如 p, pq, pq, (pq)p(pqr) ◆范式: 析取范式与合取范式的总称

范式说明：单个文字既是简单析取式，又是简单合取式形如p^-qr，～pvqv-r的公式既是析取范式，又是合取范式一个简单合取式构一个简单析取式构成的析取范式成的合取范式三个简单析取式构三个简单合取式构成的合取范式成的析取范式3

3 范式 说明： ◆ 单个文字既是简单析取式，又是简单合取式 ◆ 形如 pqr, pqr 的公式既是析取范式，又是合取 范式 • 一个简单合取式构 成的析取范式 • 三个简单析取式构 成的合取范式 • 一个简单析取式构 成的合取范式 • 三个简单合取式构 成的析取范式

范式的性质定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式如pV-p(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式如一q4

4 范式的性质 定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某 个命题变项和它的否定式. 如 pp (2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题 变项和它的否定式. 如 qq

范式的性质定理2.2（1）一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.OVO(2)一个合取范式是重言式当且仅当它的每个简单析取式都1^1是重言式5

5 范式的性质 定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合 取式都是矛盾式. (2) 一个合取范式是重言式当且仅当它的每个简单析取式都 是重言式. 11 00

命题公式的范式定理2.3（范式存在定理）任何命题公式都存在与之等值的析取范式与合取范式6

6 命题公式的范式 定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式

命题公式的范式公式A的析取（合取）范式与A等值的析取(合取)范式求公式A的范式的步骤：(1)消去A中的→,（若存在）A→BAVB（蕴含等值式）AB)^(B→>A)-B-(A^B)-AV-B

7 命题公式的范式 公式A的析取(合取)范式⎯⎯与A等值的析取(合取)范式 求公式A的范式的步骤： (1) 消去A中的→, （若存在） A→BAB （蕴含等值式） AB(A→B)(B→A)(AB)(AB) (等价、蕴含等值式) (2) 否定联结词的内移或消去  A A (双重否定律) (AB)AB （德摩根律） (AB)AB

命题公式的范式(3)使用分配律求合取范式AV(BAC)(AVB)A(AVC求析取范式A^(BVC) (A^B)V(A^C不惟一公式范式的不足8

8 命题公式的范式 (3) 使用分配律 A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式 公式范式的不足⎯⎯不惟一

求公式的范式例题求下列公式的析取范式与合取范式(1) (p→-q)vr(2) (p→-q)→r解(1) (p→-q)v→r(消去→)(p-q)r(结合律)-pv-qv-r最后结果既是析取范式（由3个简单合取式组成的析取式），又是合取范式（由一个简单析取式组成的合取式）9

9 求公式的范式 例题 求下列公式的析取范式与合取范式 (1) (p→q)r (2) (p→q)→r 解 (1) (p→q)r  (pq)r （消去→）  pqr （结合律） 最后结果既是析取范式(由3个简单合取式组成的析取式)，又 是合取范式(由一个简单析取式组成的合取式)