《离散数学第一章命题演算基础-真假性.ppt》由会员分享，可在线阅读，更多相关《离散数学第一章命题演算基础-真假性.ppt（43页珍藏版）》请在三一文库上搜索。
1、第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 1.3 范式及其应用,完全解释、部分解释,定义：设n元公式中所有的不同的命题变元为 P1, ,Pn 如果对每个命题变元均给予一个确定的值，则称对公式给了一个完全解释； 如果仅对部分变元给予确定的值， 则称对公式给了一个部分解释。,n元公式有2n个完全解释。,例 考察公式 =（PQ） R,成真解释与成假解释,定义：对于任何公式，凡使得取真值的解释，不管是完全解释还是部分解释，均称为的成真解释。 定义：对于任何公式，凡使得取假值的解释，不管是完
2、全解释还是部分解释，均称为的成假解释。,例 考察公式 =（PQ） R,永真公式与永假公式,定义：如果一个公式的所有完全解释均为成真解释，则称该公式为永真公式或称为重言式。 定义: 如果一个公式的所有完全解释均为成假解释，则称该公式为永假公式或称为予盾式。,例 由定义可知： PP为永假公式； PP为永真公式。,可满足公式与非永真公式,定义：如果一个公式存在成真解释， 则称该公式为可满足公式； 如果一个公式存在成假解释， 则称该公式为非永真公式。,例 由定义可知： PP 永假公式 PP 永真公式 PQ 可满足公式，非永真公式 PQ 可满足公式，非永真公式,第一章 命题演算基础,1.1 命题和联结词
3、 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 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 （QR）=（P Q ）（P R） 交换律 P Q= Q P P Q= Q P,八组重要的等价公式,等幂律 P P = P P
4、 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 （PQ）= P P （P Q）= P,?,例 判断下列公式的类型,q(pq) p),永真,解: q(pq) p) =q(pq) ) p =(q p )(pq) ) =T 所以，它是永真的。,例 判断下列公
5、式的类型,(pp) (qq) r),永假,解: (pp) (qq) r) = T (qq) r) = (qq) r =Fr =F 所以，它是永假的。,例 判断下列公式的类型,(pq) p,可满足,解: (pq) p =(pq) p =p 所以，它是可满足的。,成真解释和成假解释的求解方法,（1）否定深入：即把否定词一直深入至命题变元上； （2）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而得公式； （3）化简； （4）依次类推，直至产生公式的所有解释。,例(p7) 试判定公式,(PQ)(QP)R) 的永真性和可满足性。 解1：否定深入 原式 = (PQ)(QP)R) 对 P=T
6、 进行解释并化简， 结果见教材。,例(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) (PQ)(QP)R),解3：,所以，公式存在成真解释： (T,T,*), (T,F,F), (F,T,F), (F,F,T); 公式存在成假解释： (T,F,T), (F,T,T), (F,
7、F,F)。 故公式可满足但非永真。,例 试求下列公式的成真解释和成假解释,（PQ）（Q（RP） 解:当P=T时, 原式= (TQ)(Q(RT) =Q(Q(R)=QR 当P=F时, 原式= (FQ)(Q(RF) = T(QF)=Q 由上可知: 公式不是永真公式,是可满足的. 成真解释为(P,Q,R)=(T,F,F),(F,T,*), 成假解释为（(P,Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 1.3 范式及其应
8、用,联结词的完备集,定义 设S是联结词的集合，如果 对任何命题演算公式均可以由S中的联结词表示出来的公式与之等价， 则说S是联结词的完备集。,由联结词的定义知，联结词集合 ， 是完备的。,定理1 联结词的集合，是完备的。,证明：因为 PQ =P Q PQ =（P Q） （P Q） 所以 ，可以表示集合 ，。 又因为，是完备的， 即任何公式均可以由集合，中联结词表达出来的公式与之等价， 所以任何公式均可以由集合，中的联结词表达出来的公式与之等价。 故集合，是完备的。,定理 联结词的集合， 是完备的。,证明：因为 P Q=( P Q) 所以 ，可以表示集合， 又因为，是完备的，即任何公式均可以由集
9、合，中联结词表达出来的公式与之等价， 所以任何公式均可以由集合，中的联结词表达出来的公式与之等价。 故集合，是完备的。,定理 联结词的集合， 是完备的。,证明：因为 P Q=( P Q) 所以 ，可以表示集合， 又因为，是完备的，即任何公式均可以由集合，中联结词表达出来的公式与之等价， 所以任何公式均可以由集合，中的联结词表达出来的公式与之等价。 故集合，是完备的。,定理 联结词的集合， 是完备的。,证明：因为 P Q = P Q 所以 P Q= P Q 即， 可以表示集合， 又因为，是完全备的，即任何公式均可以由集合，中联结词表达出来的公式与之等价， 所以任何公式均可以由集合， 中的联结词表
10、达出来的公式与之等价。 故集合， 是完备的。,与非: PQ,PQ = （P Q）,P Q PQ T T F T F T F T T F F T,定理2(p8) 联结词的集合是完备的。,证明：显然，有： P = P P P Q= （PQ） 所以 可以表示集合， 又因为， 是完备的，即任何公式均可以由集合， 中的联结词表达出来的公式与之等价， 所以任何公式均可以由集合中的联结词表达出来的公式与之等价。 故集合是完备的。,或非 PQ=(PQ),定理： 联结词的集合是完备的。,例(p8) 试证明联结词集合不完备。,证明：假设是完备的 根据完备性的定义知 P = Q1 Q2 Q3 Qn 当P，Q1, Q
11、2, Q3, , Qn全取为真时， 公式左边=F， 公式右边=T。 显然矛盾。 故联结词集合不完备。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 1.3 范式及其应用,对偶式的定义,定义：将任何一个不含蕴含词和等价词的命题演算公式中的 换为 ， 换为 后所得的公式称为的对偶式，记为*。,例 已知公式 = P（Q（RS）, 则 *= P（Q（RS） (*)*= P（Q（RS）,例 求如下公式 的对偶式：, =(PR) (P (Q R) 解： PQ= PQ PQ= (P Q) (P Q)
12、 =(PR)(PQR)(P(Q R) * =(PR)(PQR)(P(Q R),注意：求合式公式的对偶式时，应先消去公式中的蕴含词和等价词。,内否式的定义,定义：将任何命题演算公式中的所有 肯定形式换为否定形式、 否定形式换为肯定形式 后所得的公式称为的内否式，记为 。,例 如公式 = P （Q （R S） 则 = P （Q（R S） （ ） = P（Q （R S）= ,例 =(PR) (P (Q R),求公式的对偶式与内否式。 解： PQ= PQ PQ= (P Q) (P Q) =(PR)(P Q R)(P(Q R) * =(P R) (P Q R) (P (Q R) =(P R)(P Q R
13、)( P( Q R),例 = (PQ)(QR)P),试写出公式的对偶式和内否式 解： 因为 PQ= PQ, 所以 = (PQ)(QR)P) 于是 * = (PQ)(QR) P) - = (PQ)(QR)P),双重对偶式和内否式,性质1 （*）* = （） = ,例 = (PQ)(QR)P) * = (PQ)(QR) P) (*)* = (PQ)(QR)P) = - = (PQ)(QR)P) (-)- = (PQ)(QR)P) =,合取与析取的对偶式和内否式,性质2 (A B)* = A* B* (A B) = A B (A B)* = A* B* (A B) = A B,对偶式和内否式的否定,
14、定理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，即定理成立。 归纳：设nk时定理成立。 考察n=k+11，A中至少有一个联结词， 可分为下面三种情形： A=A1， A=A1A2， A=A1A2 其中A1，A2中的联结词个数 k,定理2的证明（续）,依归纳假设 A1= A1*
15、 ， A2= A2* 当A=A1时， A =（ A1） =（A1*） 归纳假设 =（A1）* 定理1 = A* 当A=A1A2时，A = （A1A2） = A1 A2 等值公式 = A1* A2* 归纳假设 =（A1* A2*） 内否的定义 =（A1 A2）* 对偶的定义 = A* 同理可证当当A=A1A2时结论成立。 数学归纳法知，定理得证。,勘误！,定理3、定理4,定理3 A和A既同永真又同可满足。 定理4 AB和B*A*既同永真又同可满足。 AB和A*B*既同永真又同可满足。,不难证明，证明省略。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 1.3 范式及其应用,