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

第一章 命题演算基础 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 PQR TTTT TTFF TT*不能确定 F*T 成真解释与成假解释 定义：对于任何公式，凡使得取真值的解释，不管是 完全解释还是部分解释，均称为的成真解释。 定义：对于任何公式，凡使得取假值的解释，不管是 完全解释还是部分解释，均称为的成假解释。 例 考察公式 =（PQ） R PQR TTTT1个成真解释 TTFF1个成假解释 TT*不能确定1个成真解释 1个成假解释 F*T4个成真解释 永真公式与永假公式 定义：如果一个公式的所有完全解释均为成真解释，则 称该公式为永真公式或称为重言式。 定义: 如果一个公式的所有完全解释均为成假解释，则 称该公式为永假公式或称为予盾式。 例 由定义可知： PP为永假公式； PP为永真公式。 可满足公式与非永真公式 定义：如果一个公式存在成真解释， 则称该公式为可满足公式； 如果一个公式存在成假解释， 则称该公式为非永真公式。 例 由定义可知： PP 永假公式 PP 永真公式 PQ 可满足公式，非永真公式 PQ 可满足公式，非永真公式 第一章 命题演算基础 1.1 命题和联结词 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 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 所以，它是永真的。 例 判断下列公式的类型 (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 进行解释并化简， 结果见教材。 例(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,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（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 范式及其应用 联结词的完备集 定义 设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 即， 可以表示集合， 又因为，是完全备的，即任何公式均可 以由集合，中联结词表达出来的公式与之 等价， 所以任何公式均可以由集合， 中的联 结词表达出来的公式与之等价。 故集合， 是完备的。 与非: 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) 定理： 联结词的集合是完备的。 P Q PQ T T F T F F F T F F F T 例(p8) 试证明联结词集合不完备。 证明：假设是完备的 根据完备性的定义知 P = Q1 Q2 Q3 Qn 当P，Q1, Q2, 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) =(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)( 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 对偶式和内否式的否定 定理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* ， A2= A2* 当A=A1时， A =（ A1） =（A1*） 归纳假设 =（A1）* 定理1 = A* 当A=A1A2时，A = （A1A2） = A1 A2 等值公式 = A1* A2* 归纳假设