离散数学第一章命题演算基础-真假性.ppt

第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用完全解释、部分解释完全解释、部分解释定义：设定义：设n元公式元公式 中所有的不同的命题变元为中所有的不同的命题变元为 P1,Pn 如果对每个命题变元均给予一个确定的值，如果对每个命题变元均给予一个确定的值，则称对公式则称对公式 给了一个给了一个完全解释完全解释；如果仅对部分变元给予确定的值，如果仅对部分变元给予确定的值，则称对公式则称对公式 给了一个给了一个部分解释部分解释。n元公式元公式 有有2n个完全解释。个完全解释。例 考察公式考察公式 =（P Q）R PQR TTTTTTFFTT*不能确定F*T成真解释与成假解释定义：对于任何公式定义：对于任何公式，凡使得，凡使得 取真值的解释，不管是取真值的解释，不管是完全解释还是部分解释，均称为完全解释还是部分解释，均称为 的成真解释。的成真解释。定义：对于任何公式定义：对于任何公式，凡使得，凡使得 取假值的解释，不管是取假值的解释，不管是完全解释还是部分解释，均称为完全解释还是部分解释，均称为 的成假解释。的成假解释。例 考察公式考察公式 =（P Q）R PQR TTTT1个成真解释TTFF1个成假解释TT*不能确定1个成真解释1个成假解释F*T4个成真解释永真公式与永假公式永真公式与永假公式定义：如果一个公式的所有完全解释均为成真解释，则定义：如果一个公式的所有完全解释均为成真解释，则称该公式为永真公式或称为重言式。称该公式为永真公式或称为重言式。定义定义:如果一个公式的所有完全解释均为成假解释，则如果一个公式的所有完全解释均为成假解释，则称该公式为永假公式或称为予盾式。称该公式为永假公式或称为予盾式。例例 由定义可知：由定义可知：PP为永假公式；为永假公式；PP为永真公式。为永真公式。可满足公式与非永真公式可满足公式与非永真公式定义：如果一个公式存在成真解释，定义：如果一个公式存在成真解释，则称该公式为则称该公式为可满足公式可满足公式；如果一个公式存在成假解释，如果一个公式存在成假解释，则称该公式为则称该公式为非永真公式非永真公式。例例 由定义可知：由定义可知：PP 永假公式永假公式 PP 永真公式永真公式 P Q 可满足公式，非永真公式可满足公式，非永真公式 P Q 可满足公式，非永真公式可满足公式，非永真公式第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用逻辑等价逻辑等价定义：给定两个公式定义：给定两个公式 和和，设设P1，P2，Pn为为 和和 的所有命题变元，的所有命题变元，那么那么 和和 有有2n个解释。个解释。如果对每个解释，如果对每个解释，和和 永取相同的真假值，永取相同的真假值，则称则称 和和 是是逻辑等价逻辑等价的，记为的，记为=。八组重要的等价公式 双重否定律双重否定律 P=P结合律结合律 （P Q）R=P （Q R）（P Q）R=P （Q R）分配律分配律 P （Q R）=（P Q）（P R）P （Q R）=（P Q）（P R）交换律交换律 P Q=Q P P Q=Q P八组重要的等价公式等幂律等幂律 P P=P P P=P P P=T P P=T等值公式等值公式 P Q=P Q P Q=（PQ）（Q P）=（P Q）（P Q）=（P Q）（P Q）（P Q）=PQ （P Q）=PQ八组重要的等价公式 部份解释部份解释 P T=P P F=F P T=T P F=P T P=P F P=T P T=T P F=P T P=P F P=P 吸收律吸收律 P （P Q）=P P （P Q）=P?例 判断下列公式的类型 q (p q)p)永真解解:q (p q)p)=q(p q)p =(q p)(p q)=T 所以，它是永真的所以，它是永真的。例 判断下列公式的类型(p p)(q q)r)永假解解:(p p)(q q)r)=T(q q)r)=(q q)r =F r =F 所以，它是永假的。所以，它是永假的。例 判断下列公式的类型判断下列公式的类型 (pq)p可满足解解:(pq)p =(p q)p =p 所以，它是可满足的。所以，它是可满足的。成真解释和成假解释的求解方法（1）否定深入：即把否定词一直深入至命题变）否定深入：即把否定词一直深入至命题变元上；元上；（2）部分解释：选定某个出现次数最多的变元）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而对它作真或假的两种解释从而得公式；得公式；（3）化简；）化简；（4）依次类推，直至产生公式的所有解释。）依次类推，直至产生公式的所有解释。例(p7)试判定公式(P Q)(QP)R)的永真性和可满足性。的永真性和可满足性。解解1：否定深入：否定深入 原式原式=(P Q)(QP)R)对对 P=T 进行解释并化简，进行解释并化简，结果见教材。结果见教材。例(p7)(PQ)(QP)R)解解2：在否定深入的基础上对在否定深入的基础上对P=F进行解释并化简。进行解释并化简。原式原式=（FQ）（QF）R）=（QF）R =Q R Q=T 时，时，原式原式=TR=R，于是于是 R=T 时，原式时，原式=F R=F 时，原式时，原式=T 因此，公式存在成真解释因此，公式存在成真解释 （P，Q，R）=（F，T，F）；公式存在成假解释公式存在成假解释 （P，Q，R）=（F，T，T）。）。故公式可满足但非永真。故公式可满足但非永真。例(p7)(P Q)(QP)R)解解3：所以，公式存在成真解释：所以，公式存在成真解释：(T,T,*),(T,F,F),(F,T,F),(F,F,T);公式存在成假解释：公式存在成假解释：(T,F,T),(F,T,T),(F,F,F)。故公式可满足但非永真。故公式可满足但非永真。(P,Q,R)A=(PQ)B=QPC=BRAC(T,T,T)FTFT(T,T,F)FFFT(T,F,T)TTFF(T,F,F)TTTT(F,T,T)TTFF(F,T,F)TTTT(F,F,T)TFTT(F,F,F)TFFF例例 试求下列公式的成真解释和成假解释试求下列公式的成真解释和成假解释 （PQ）（Q（R P）解解:当当P=T时时,原式原式=(TQ)(Q(R T)=Q(Q(R)=QR 当当P=F时时,原式原式=(FQ)(Q(R F)=T(Q F)=Q由上可知由上可知:公式不是永真公式公式不是永真公式,是可满足的是可满足的.成真解释为成真解释为(P,Q,R)=(T,F,F),(F,T,*),成假解释为（成假解释为（(P,Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用联结词的完备集 定义定义 设设S是联结词的集合，如果是联结词的集合，如果 对任何命题演算公式均可以由对任何命题演算公式均可以由S中的联中的联结词表示出来的公式与之等价结词表示出来的公式与之等价，则说则说S是联结词的完备集。是联结词的完备集。由联结词的定义知，联结词集合由联结词的定义知，联结词集合 ，是完备的。是完备的。定理1 联结词的集合联结词的集合，是完备的。是完备的。证明：因为证明：因为 PQ=P Q PQ=（P Q）（P Q）所以所以 ，可以表示集合可以表示集合，。又因为又因为，是完备的，是完备的，即任何公式即任何公式 均可以由集合均可以由集合，中中联结词表达出来的公式与之等价，联结词表达出来的公式与之等价，所以任何公式所以任何公式 均可以由集合均可以由集合，中的联中的联结词表达出来的公式与之等价。结词表达出来的公式与之等价。故集合故集合，是完备的。是完备的。定理定理 联结词的集合联结词的集合，是完备的。是完备的。证明：因为证明：因为 P Q=(P Q)所以所以 ，可以表示集合可以表示集合，又因为又因为，是完备的，即任何公式是完备的，即任何公式 均均可以由集合可以由集合，中联结词表达出来的公中联结词表达出来的公式与之等价，式与之等价，所以任何公式所以任何公式 均可以由集合均可以由集合，中的联结中的联结词表达出来的公式与之等价。词表达出来的公式与之等价。故集合故集合，是完备的。是完备的。定理定理 联结词的集合联结词的集合，是完备的。是完备的。证明：因为证明：因为 P Q=(P Q)所以所以 ，可以表示集合可以表示集合，又因为又因为，是完备的，即任何公式是完备的，即任何公式 均均可以由集合可以由集合，中联结词表达出来的公中联结词表达出来的公式与之等价，式与之等价，所以任何公式所以任何公式 均可以由集合均可以由集合，中的联中的联结词表达出来的公式与之等价。结词表达出来的公式与之等价。故集合故集合，是完备的。是完备的。定理定理 联结词的集合联结词的集合，是完备的。是完备的。证明：因为证明：因为 P Q=P Q 所以所以 P Q=P Q 即即，可以表示集合可以表示集合，又因为又因为，是完全备的，即任何公式是完全备的，即任何公式 均可均可以由集合以由集合，中联结词表达出来的公式与之中联结词表达出来的公式与之等价，等价，所以任何公式所以任何公式 均可以由集合均可以由集合，中的联中的联结词表达出来的公式与之等价。结词表达出来的公式与之等价。故集合故集合，是完备的。是完备的。与非与非:P Q P Q=（P Q）P Q P Q T T FT F TF T TF F T定理定理2(p8)联结词的集合联结词的集合是完备的。是完备的。证明：显然，有：证明：显然，有：P=P P P Q=（P Q）所以所以 可以表示集合可以表示集合，又因为又因为，是完备的，即任何公式是完备的，即任何公式 均可均可以由集合以由集合，中的联结词表达出来的公式中的联结词表达出来的公式与之等价，与之等价，所以任何公式所以任何公式 均可以由集合均可以由集合 中的联结词中的联结词表达出来的公式与之等价。表达出来的公式与之等价。故集合故集合 是完备的。是完备的。或非或非 PQ=(PQ)定理：定理：联结词的集合联结词的集合是完备的。是完备的。P Q PQ T T FT F FF T FF F T例例(p8)试证明联结词集合试证明联结词集合 不完备。不完备。证明：假设证明：假设 是完备的是完备的 根据完备性的定义知根据完备性的定义知 P=Q1 Q2 Q3 Qn 当当P，Q1,Q2,Q3,Qn全取为真时，全取为真时，公式左边公式左边=F，公式右边公式右边=T。显然矛盾。显然矛盾。故联结词集合故联结词集合 不完备。不完备。第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式 1.3 1.3 范式及其应用范式及其应用对偶式对偶式的定义 定义：将任何一个不含蕴含词和等价词的命题演算公定义：将任何一个不含蕴含词和等价词的命题演算公式式 中的中的 换为换为 ，换为换为 后所得的公式称为后所得的公式称为 的的对偶式对偶式，记为，记为*。例例 已知公式已知公式 =P（Q（RS）,则则 *=P（Q（RS）(*)*=P（Q（RS）例 求如下公式求如下公式 的对偶式：的对偶式：=(PR)(P(Q R)解：解：PQ=P Q PQ=(P Q)(P Q)=(P R)(P QR)(P(Q R)*=(P R)(P QR)(P(Q R)注意：求合式公式的对偶式时，应先消去公式中的蕴含词和等注意：求合式公式的对偶式时，应先消去公式中的蕴含词和等价词。价词。内否式的定义定义：将任何命题演算公式定义：将任何命题演算公式 中的所有中的所有肯定形式换为否定形式、肯定形式换为否定形式、否定形式换为肯定形式否定形式换为肯定形式后所得的公式称为后所得的公式称为 的的内否式内否式，记为，记为 。例例 如公式如公式 =P （Q （R S）则则 =P （Q（R S）（）=P（Q （R S）=例 =(PR)(P(Q R)求公式求公式 的对偶式与内否式。的对偶式与内否式。解：解：PQ=P Q PQ=(P Q)(P Q)=(P R)(P Q R)(P(Q R)*=(P R)(P Q R)(P(Q R)=(P R)(P Q R)(P(Q R)例 =(PQ)(QR)P)试写出公式试写出公式 的对偶式和内否式的对偶式和内否式解：解：因为因为 PQ=P Q,所以所以 =(P Q)(Q R)P)于是于是 *=(P Q)(Q R)P)-=(P Q)(Q R)P)双重对偶式和内否式双重对偶式和内否式性质性质1 （*）*=（）=例例 =(P Q)(Q R)P)*=(P Q)(Q R)P)(*)*=(P Q)(Q R)P)=-=(P Q)(Q R)P)(-)-=(P Q)(Q R)P)=合取与析取的对偶式和内否式合取与析取的对偶式和内否式性质2 (A B)*=A*B*(A B)=A B (A B)*=A*B*(A B)=A B 对偶式和内否式的否定对偶式和内否式的否定定理定理1(p9)（A*）=（A）*（A）=（A）证明可以模仿定理2的证明进行，省略约定在讨论对偶式和内否式的定理时，命题约定在讨论对偶式和内否式的定理时，命题公式中仅含有公式中仅含有，和和 三个联结词，即三个联结词，即应先应先消去公式中的蕴含词和等价词消去公式中的蕴含词和等价词。定理定理2(p9)A=A*证明：对公式证明：对公式A中出现的联结词的个数中出现的联结词的个数n进行归纳证明进行归纳证明 奠基：当奠基：当n=0时时 A中无联结词，便有中无联结词，便有 A=P，从而有从而有 A=P，且且A*=P，所以所以A*=P=A，即定理成立。，即定理成立。归纳：设归纳：设n k时定理成立。时定理成立。考察考察n=k+1 1，A中至少有一个联结词，中至少有一个联结词，可分为下面三种情形：可分为下面三种情形：A=A1，A=A1 A2，A=A1 A2 其中其中A1，A2中的联结词个数中的联结词个数 k 定理2的证明（续）依归纳假设依归纳假设 A1=A1*，A2=A2*当当A=A1时，时，A=（A1）=（A1*）归纳假设归纳假设 =（A1）*定理定理1 =A*当当A=A1 A2时，时，A=（A1 A2）=A1 A2 等值公式等值公式 =A1*A2*归纳假设归纳假设 =（A1*A2*）内否的定义内否的定义 =（A1 A2）*对偶的定义对偶的定义 =A*同理可证当当同理可证当当A=A1 A2时结论成立。时结论成立。数学归纳法知，定理得证。数学归纳法知，定理得证。勘误！定理定理3、定理、定理4定理定理3 A和和A既同永真又同可满足。既同永真又同可满足。定理定理4 AB和和B*A*既同永真又同可满足。既同永真又同可满足。AB和和A*B*既同永真又同可满足。既同永真又同可满足。不难证明，证明省略。不难证明，证明省略。第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式 1.3 1.3 范式及其应用范式及其应用