福州大学：《离散数学》课程教学资源（教案讲义）第二章命题逻辑等值演算.doc_大学文库

29 离散数学教案编号：C202 课时安排： 2 学时教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch2 命题逻辑等值演算 § 2.2 析取范式与合取范式 § 2.3 联结词的完备集教学目的要求（分掌握、熟悉、了解三个层次）： 1.掌握析取范式与合取范式。 2．了解联结词的完备集教学重点、难点： 1）重点：析取范式与合取范式掌握等值式的概念 2）难点：联结词的完备集概念教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点？疑点）： *一、析取范式与合取范式（25 分钟） 1．合取范式一命题公式 A 称为合取范式，当且仅当它具有形式： A=A1∧A2∧.∧An 其中 Ai(i＝1,2,.,n)为命题变项或其否定所组成的析取式（称简单析取式）. 2．析取范式一命题公式 A 称为析取范式，当且仅当它具有形式： A＝A1∨A2∨.∨An 其中 Ai(i＝1,2,.,n) 为命题变项或其否定所组成的合取式（称简单合取式）. 3．范式性质 (1)一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式; (2)一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式. 范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式. 4．化归析取范式或合取范式的步骤 (1)联结词化归为  , ∧ , ∨ ； p → q  p∨q; p  q  ( p∨q)∧(p∨ q); (2)利用双重否定律和德•摩根律，否定号的消去或内移;   p  p ; (p∧q)  p∨ q (3)利用分配律，结合律 [注] 任何命题公式的析取范式和合取范式都不是唯一的. 二、主析取范式和主合取范式（35 分钟） 1．极小项——简单合取式在含 n 个命题变项的简单合取式中,若每个命题变项与其否定不同时存在,而二者之一必出现且仅出现

一次，且第ⅰ个命题变项或其否定出现在从左起的第1位上（若命题变项无角标则按字典顺序排序），这样的简单合取式称为极小项 ●3个命颗变项，8个极小面对应情况加下」 p-qA- -0, pA gAr 010- -2.记作m2: pA qAr 0113，记作m: DA-A-r -100- 一4.记作m4 PA 9A r —101 记作 pA qA-r 10 -6,记作ms pA qAr -111 一7.i记作m7 一般情况下，n个命愿变项共产生2”个极小项，分别记为m,m,m,” 每一个极小项当其真值指派与编码相同时，其真值为1，在其余真值指派情况下均为0。任意两个不同极小项的合取式永假。全体极小项的析取式永为真。 2.极大项 -简单析取式在含·个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而二者之一必出现且仅出现次，且第ⅰ个命愿变项或其否定出现在左起的第ⅰ位上（若命愿变项无角码，则按字典顺序排列，这样的简单析取式称为极大项 ·3个命题变项，8个极大项对应情况如下： 0000.记作0 PVqV-r 0011记作M pV-qVr 010 一2，记作 pV-qV-r -011 -3,记作M6 -pVqVr —100—4,记作M pVaV-r 一101-5，记作Ms pV- aVr 110 6.记作M -pV-q V-r 一111一7，记作M ·一般情况下，n个命题变项共产生2”个极大项，分别记为M,M,M” ·每一个极大项当其真值指派与编码相同时，其真值为0，在其余真值指派情况下均为1。任意两个不同极大项的析取式永真。全体极大项的合取式永为假。 3.定义：对给定的命题公式来讲，仅含有极小项（极大项）的析取（合取）的等价式称为给定命题公式生析取范式（主合取范式）：定理：在真值表中，一个公式的真值为1(0)的指派所对应的极小项（极大项）的析取（合取）即为此公式的主析取范式（主合取范式）。 [注]任一命题公式的主合取范式和主析取范式一定存在，且是唯一的. 4。极小项与极大项之间的关系设命题公式A中含n个命题变项 mi M Mi台mi ·设命题公式A中含n个命题变项，且设A的主析取范式中只含k个极小项m,m配，mk当且仅当A 30

30 一次, 且第 i 个命题变项或其否定出现在从左起的第 i 位上(若命题变项无角标,则按字典顺序排序), 这样的简单合取式称为极小项. ⚫ 3 个命题变项，8 个极小项对应情况如下：  p∧q∧r —— 000 —— 0, 记作 m0；  p∧q∧r ——001 —— 1, 记作 m1；  p∧ q∧r ——010 —— 2, 记作 m2；  p∧ q∧r ——011 —— 3, 记作 m3； p∧q∧r ——100 —— 4, 记作 m4； p∧ q∧ r ——101 —— 5, 记作 m5； p∧ q∧r ——110 —— 6, 记作 m6； p∧ q∧r —— 111 —— 7, 记作 m7. ⚫ 一般情况下,n 个命题变项共产生 2 n 个极小项,分别记为 m0 ,m1 ,.m2 n -1。 ⚫ 每一个极小项当其真值指派与编码相同时，其真值为 1，在其余真值指派情况下均为 0。任意两个不同极小项的合取式永假。全体极小项的析取式永为真。 2．极大项——简单析取式在含 n 个命题变项的简单析取式中,若每个命题变项与其否定不同时存在,而二者之一必出现且仅出现一次, 且第 i 个命题变项或其否定出现在左起的第 i 位上(若命题变项无角码,则按字典顺序排列), 这样的简单析取式称为极大项. ⚫ 3 个命题变项，8 个极大项对应情况如下： p∨q∨r ——000——0，记作 M0 p∨q∨r ——001——1，记作 M1 p∨q∨r ——010——2，记作 M2 p∨q∨r ——011——3，记作 M3 p∨q∨r ——100——4，记作 M4 p∨q∨r ——101——5，记作 M5 p∨q∨r ——110——6，记作 M6 p∨q ∨r ——111——7，记作 M7 ⚫ 一般情况下,n 个命题变项共产生 2 n 个极大项,分别记为 M0,M1,.M2 n -1 . ⚫ 每一个极大项当其真值指派与编码相同时，其真值为 0，在其余真值指派情况下均为 1。任意两个不同极大项的析取式永真。全体极大项的合取式永为假。 3. 定义：对给定的命题公式来讲，仅含有极小项（极大项）的析取（合取）的等价式称为给定命题公式的主析取范式（主合取范式）。定理：在真值表中，一个公式的真值为 1 （0）的指派所对应的极小项（极大项）的析取（合取），即为此公式的主析取范式（主合取范式）。 [注]任一命题公式的主合取范式和主析取范式一定存在,且是唯一的. 4．极小项与极大项之间的关系设命题公式 A 中含 n 个命题变项 ⚫  mi  Mi ；  Mi  mi 。 ⚫ 设命题公式 A 中含 n 个命题变项,且设 A 的主析取范式中只含 k 个极小项 mil,mi2,.,mik 当且仅当 A

福州大学：《离散数学》课程教学资源（教案讲义）第二章 命题逻辑等值演算

福州大学：《离散数学》课程教学资源（教案讲义）第二章命题逻辑等值演算