资源描述：
《离散-2-2-命题逻辑(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、主要内容：§1.4范式合取范式基本和求合取范式主合取范式极大项求主合取范式的方法主合取范式的性质析取范式、主析取范式（自学、讨论）合取范式与析取范式的联系1.-吴扬扬制-§1.4范式1.合取范式(1)基本和定义：基本和可归纳定义如下：（1）命题变元或命题变元的否定是基本和；（2）若A、B是基本和，则A∨B也是基本和.定理1.4.1:一个基本和是永真式iff它同时含有某个变元及其否定。当且仅当证明(必要性)设基本和A是永真式，但不同时包含一个变元及其否定，现对A中不带否定符号的变元指派0，带否定符号的变元指派1，则A
2、为0，与A是永真式矛盾。(充分性）设A是基本和，且含有Pi和┐Pi,运用交换律和结合律可得：A(Pi┐Pi)BTBT∴A是永真式.2§1.4范式1.合取范式(2)例:求┐(P→Q)(Q∨R)的合取范式。解：原式┐(┐P∨Q)(Q∨R)（蕴涵等值式）(┐(┐P∨Q)→(Q∨R))∧((Q∨R)→┐(┐P∨Q))（等价等值式）((┐P∨Q)∨(Q∨R))∧(┐(Q∨R)∨┐(┐P∨Q))（蕴涵等值、双重否定）(┐P∨Q∨R)∧((┐Q∧┐R)∨(P∧┐Q))（等幂律、德·摩根律）(┐P∨Q∨R
3、)∧┐Q∧(┐R∨P)（分配律）----合取范式(((┐P∨R)∧┐Q))∨(Q∧┐Q))∧(┐R∨P)（交换律、分配律）(┐P∨R)∧┐Q∧(┐R∨P)（补余律、同一律）--------合取范式»基本恒等式合取范式合取范式可归纳定义如下：（1）基本和是合取范式；（2）若A,B是合取范式，则A∧B也是合取范式。若一个合取范式与给定公式等价，则称该范式为给定公式的合取范式。3§1.4范式2.主合取范式（1）极大项：n个变元的极大项是N个变元的极大项有2n主合取范式归纳定义：（1）极大项是主合取范式；（2）若A、B
4、是主合取范式，则A∧B是主合取范式。求主合取范式方法:化归方法真值表PQR000001010011100101110111极大项P∨Q∨RP∨Q∨┐RP∨┐Q∨RP∨┐Q∨┐R┐P∨Q∨R┐P∨Q∨┐R┐P∨┐Q∨R┐P∨┐Q∨┐RM0M1M2M3M4M5M6M7只有一个解释使其为F包含n个变元的基本和，每个变元仅出现一次4.-吴扬扬制-例:求┐(P→Q)(Q∨R)的主合取范式。解：原式┐(┐P∨Q)(Q∨R)蕴涵等值(┐(┐P∨Q)→(Q∨R))∧((Q∨R)→┐(┐P∨Q))等价等值式((┐P∨Q)∨
5、(Q∨R))∧(┐(Q∨R)∨┐(┐P∨Q))蕴涵等值、双重否定(┐P∨Q∨R)∧((┐Q∧┐R)∨(P∧┐Q))等幂律、德·摩根律(┐P∨Q∨R)∧┐Q∧(┐R∨P)----合取范式（1）分配律(((┐P∨R)∧┐Q))∨(Q∧┐Q))∧(┐R∨P)(┐P∨R)∧┐Q∧(┐R∨P)----合取范式（2）补余律、同一律(┐P∨Q∨R)∧（┐Q∨F∨F)∧((┐R∨P)∨F)(┐P∨Q∨R)∧(┐Q∨(P∧┐P)∨(R∧┐R))∧((┐R∨P)∨(Q∧┐Q)(┐P∨Q∨R)∧(┐Q∨P∨R)∧(┐Q∨┐
6、P∨R)∧(┐Q∨P∨┐R)∧(┐Q∨┐P∨┐R))∧(┐R∨P∨Q))∧(┐R∨P∨┐Q)(┐P∨Q∨R)∧(┐Q∨P∨R)∧(┐Q∨┐P∨R)∧(┐Q∨P∨┐R)∧(┐Q∨┐P∨┐R))∧(┐R∨P∨Q)真值表法»5.-吴扬扬制-利用真值表求主合取范式：在公式A的真值表中，使A为0的指派所对应的极大项的合取式就是A的主合取范式。例:求┐(P→Q)(Q∨R)的主合取范式。§1.4范式2.主合取范式（2）PQR000001010011100101110111P→Q11110011┐(P→Q）00001100Q∨
7、R01110111┐(P→Q)(Q∨R)10000100P∨Q∨┐RP∨┐Q∨RP∨┐Q∨┐R┐P∨Q∨R┐P∨┐Q∨R┐P∨┐Q∨┐RM1M2M3M4M6M7┐(P→Q)(Q∨R)的主合取范式为：∏（1,2,3,4,6,7)主析取范式»«主合取范式6.-吴扬扬制-§1.4范式2.主合取范式（3）主合取范式的性质：唯一性一个公式为永假式的充分必要条件是其主合取范式包含所有极大项。3.析取范式(自学讨论P21定义1.4.8-P22例1.4.7）基本积及其性质析取范式的一般形式、求析取范式的基本步骤4.主析取范式极
8、小项的一般形式及其性质主析取范式的一般形式、化归方法、真值表法主析取范式性质以┐(P→Q)(Q∨R)为例7.-吴扬扬制-§1.4范式5.主合取范式与主析取范式的联系如果公式A的主析取范式为：∑(i1,…,it)其中：ip∈{0,1,…,2n-1},则A的主合取范式为：∏（j1,…,js)其中：jp∈{0,1,…,2n-1}-{i1,…,it}例：┐(P→Q
