离散数学第一章命题演算基础-真假性.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 P Q R T T T T T T F F T T * 不能确定 F * * T 成真解释与成假解释 定义：对于任何公式 ，凡使得 取真值的解释，不管 是完全解释还是部分解释，均称为 的成真解释。 定义：对于任何公式 ，凡使得 取假值的解释，不管 是完全解释还是部分解释，均称为 的成假解释。 例 考察公式 =（ PQ） R P Q R T T T T 1个成真解释 T T F F 1个成假解释 T T * 不能确定 1个成真解释 1个成假解释 F * * T 4个成真解释 永真公式与永假公式 定义：如果一个公式的所有完全解释均为成真解释，则 称该公式为永真公式或称为重言式。 定义 : 如果一个公式的所有完全解释均为成假解释，则 称该公式为永假公式或称为予盾式。 例 由定义可知： 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 (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) 试判定公式 (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=QP C=BR AC (T,T,T) F T F T (T,T,F) F F F T (T,F,T) T T F F (T,F,F) T T T T (F,T,T) T T F F (F,T,F) T T T T (F,F,T) T F T T (F,F,F) T F 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 范式及其应用 联结词的完备集 定义 设 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=(P Q) 定理： 联结词的集合 是完备的。 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, 所以 = (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，即定理成立。 归纳：设 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* 归纳假设 =（ 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 范式及其应用