1、等值式、基本等值式等值演算复合联结词 排斥或 与非式 或非式联结词全功能集1(AB)AB (AB)ABA(AB)A, A(AB)AABAB对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 23/481.2.4 对偶式定义 在仅含有联结词 , , 的命题公式 A中， 将 换成 , 换成 ，若 A中含有 0或 1，就将 0换成 1， 1换成 0，所得命题公式称为 A的 对偶式 ，记为 A*.例 已知 = P (QR）= P(QR) *= P (QR)(*)*= P (QR)则 :4定理 设 A和 A*互为对偶式， p1,p2, pn是出现在 A和 A*中的全部命题变项，将 A和 A*写
2、成 n元函数形式，则 (1) A(p1,p2, pn) A* ( p1, p2, pn)(2) A( p1, p2, pn) A* (p1,p2, pn) 定理（对偶原理） 设 A， B为两个命题公式，若 A B，则 A* B*.例 设 A*(P,Q,R)是 P (Q R)， 证明A*(P,Q,R)A(P,Q,R)证： 因 A*(P,Q,R)P( QR) ，代入 可 得A*(P,Q,R)P(Q R)。而 按 对 偶式的定 义 ，由 A*(P,Q,R)可写出 (P,Q,R)P( QR)故 (P,Q,R)(P( QR)P (QR) ( 德 摩根律 )P(Q R) (德 摩根律 ) A*(P,Q,R
3、)6/481.3 范式及其应用合取式 析取式析取范式 合取范式主析取范式 主合取范式主范式范式真假性唯一两者有关联不唯一成真解释 成假解释对于完全解释，合 (析 )取式=极小 (大 )项7/48合取式、析取式定义 1 命题变元、或者命题变元的否定、或由它们利用 合取词 组成的合式公式称为 （简单）合取式 。定义 2 命题变元、或者命题变元的否定、或由它们利用 析取词 组成的合式公式称为 （简单）析取式 。例 显然，P， P， PQ， PQR 均为合取式；P， P， PQ， PQR 均为析取式。8/48(一 ) 解释与合取式、析取式之间的关系 定理 1 任给一个 成真 解释有且仅有一个 合取式与
4、之对应； 任给一个 成假 解释有且仅有一个 析取式 与之对应。例 成真解释 (P,Q,R)= (1,0,1)成假解释 (P,Q,R)= (0,0,1)合取式 PQR析取式 PQR=(PQR)9/48析取范式、合取范式定义 3 形如 A1 A2 An的公式称为 析取范式 ，其中 Ai(i=1,2,n)为合取式。定义 4 形如 A1 A2 An的公式称为 合取范式 ，其中 Ai(i=1,2,n)为析取式。例 P， P， PQ， PQ ， (PQ)(SR) 均为析取范式。P， P， PQ， PQ ， (PQ)(SR) 均为合取范式。10/48例 : 考察公式 =PQ的 析取范式对应于两个合取式为 P Q, P Q于是，有= (P Q) (P Q)P Q P QT T TT F FF T FF F T有两个成真解释： (1, 1), (0, 0)
