上堂课的内容重点与难点.ppt

1/48,上堂课的内容、重点与难点,联结词的使用 等价公式 成真解释与成假解释,真值函项的理解 蕴含词的正确使用 等价公式的理解与运用,命题 联结词 合式公式 解释 逻辑等价 真假性,2/48,1.2.3 联结词的完备集,定义 设S是联结词的集合，如果 对任何命题演算公式均可以由S中的联结词表示出来的公式与之等价， 则称S是联结词的完备集。,由联结词的定义知，联结词集合 ， 是完备的。,3/48,定理1 联结词的集合，是完备的。,思路: 去蕴含词与等价词 PQ = P Q PQ = (P Q) (P Q),4/48,定理 联结词的集合， 是完备的。,思路: 在去蕴含词与等价词的基础上, PQ =P Q PQ = (P Q) (P Q) 去析取词： P Q = (P Q),5/48,定理 联结词的集合， 是完备的。,思路: 去等价词、析取词、合取词： PQ = ( PQ) (PQ) PQ= PQ PQ = (PQ)=(P Q),6/48,定理 联结词的集合是完备的。,或非： PQ=(PQ),思路： 对于完备集， ，去否定词与析取词 P = P P P Q= (P Q),7/48,例 试证明联结词集合不完备。,证明： 对于任意公式P， P也是公式 。 假设是完备的。根据完备性的定义知， P = Q1 Q2 Q3 Qn 当P，Q1, Q2, Q3, , Qn全取为假时， 公式左边=T，公式右边=F。 显然矛盾。 故联结词集合不完备。,8/48,联结词的完备集,， ， ， ， ， ,PQ= (P Q) PQ= (P Q),哪个大？哪个小？,9/48,1.2.4 对偶式和内否式,定义 将任何一个不含蕴含词和等价词的命题演算公式中的 换为 ， 换为 后所得的公式称为的对偶式，记为*。,例 已知 = P (QR）,= P(QR) *= P (QR) (*)*= P (QR),则:,10/48,内否式的定义,定义 将任何命题演算公式中的所有 肯定形式换为否定形式、 否定形式换为肯定形式 后所得的公式称为的内否式，记为 。,例 已知 = P (QR),= P(QR) = P(Q R) () = P (Q R),则:,11/48,对偶式和内否式的性质,性质 (*)* = () = ,定理3(p9) (A*)=(A)* (A)=(A),定理4(p9) A =A*,12/48,定理4的证明：,证明思路是对公式A中出现的联结词的个数n进行归纳证明。 当n=0时， A中无联结词，便有 A=P， 从而有 A=P， A*=P ， 所以 A* = P= A， 即定理成立。,13/48,证明(续): 归纳假设：设nk时定理成立。 考察n=k+11，A中至少有一个联结词， 可分为下面三种情形： A=A1， A=A1A2， A=A1A2 其中A1，A2中的联结词个数 k 。 依归纳假设 A1= A1* ， A2= A2* 。 对于上述三种情形，可以分别证明结论成立： A =A*。 由数学归纳法知，定理得证。,14/48,1.3 范式及其应用,合取式,析取式,析取范式,合取范式,主析取范式,主合取范式,主范式 范式 真假性,唯一 两者有关联 不唯一,成真解释,成假解释,对于完全解释， 合(析)取式 =极小(大)项,15/48,合取式、析取式,定义1 命题变元、或者命题变元的否定、或由它们利用合取词组成的合式公式称为合取式。 定义2 命题变元、或者命题变元的否定、或由它们利用析取词组成的合式公式称为析取式。 例 显然， P，P，PQ，PQR 均为合取式； P，P，PQ，PQR 均为析取式。,16/48,(一) 解释与合取式、析取式之间的关系,定理1 任给一个成真解释有且仅有一个合取式与之对应； 任给一个成假解释有且仅有一个析取式与之对应。,例 成真解释(P,Q,R)= (T,F,T) 成假解释(P,Q,R)= (F,F,T),合取式PQR,析取式PQR =(PQR),17/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) 均为合取范式。,18/48,例: 考察公式 =PQ的析取范式,对应于两个合取式为 PQ, PQ 于是，有 = (PQ) (PQ),有两个成真解释： (T, T), (F, F),19/48,例: 考察公式 =PQ的合取范式,对应析取式为 PQ, PQ 于是，有： = (PQ) (PQ),成假解释 (T, F), (F, T),20/48,定理2 任何命题演算公式均可以化为合取范式，也可以化为析取范式。,证明： (1)设公式为永真公式 =PP (2)设公式为永假公式 =PP,证明(3)： 设公式既非永真又非永假。 设公式的成真解释为1，2，n， 成假解释为1，2，t。 根据解释和范式的关系知： 对应于成真解释1，2，n的合取式为 1，2，n 对应于成假解释1，2，t的析取式为 1，2，t 而公式 12n的成真解释为 1，2，n； 公式12t的成假解释为 1，2，t。 根据两个公式逻辑等价的定义知 =12n =12t 故公式既可表示为析取范式又可表示为合取范式。,22/48,(二) 析取范式和合取范式的求解方法,等价变换法利用等价公式进行变换，将范式变换出来。 解 释 法利用所有成真解释或成假解释，写出范式。,23/48,等价变换法,(1)去蕴含词与等价词： PQ =P Q PQ = (P Q) (P Q) (2)否定深入： (P Q)= PQ (P Q)= PQ， P = P (3)重复使用分配律： P (QR)=(P Q )(P R) P (QR)=(P Q )(P R),24/48,解释法,(1) 求所有成真解释、成假解释； (2) 写出成真解释对应的合取式、 成假解释对应的析取式； (3) 把所有的合取式用析取词联结起来就构成析取范式，把所有的析取式用合取词联结起来就构成合取范式。,25/48,例 求公式的范式 (PQ)(RQ)P),解： 原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式,26/48,解：P=T时, 原式=(TQ)(RQ)T)=QR P=F时, 原式=(FQ)(RQ)F)=F 所以有: 成真解释为：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 成假解释为：(P,Q,R)=(T,T,T), (F, ),例 求公式的范式 (PQ)(RQ)P),于是析取范式为: (PQR)(P Q R)(P Q R) 合取范式为： (P QR)P,27/48,范式不唯一性,例 求公式的范式 (PQ)(RQ)P),解1： 原式=(PQ)(PR) 析取范式 = P(QR) 合取范式 解2: 析取范式为: (PQR)(P Q R)(P Q R) 合取范式为： (P QR)P,28/48,1.3.2 主范式,定义5 对于n个命题变元P1，P2，Pn，公式 Q1Q2Qn 称为极小项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极小项有四个，它们分别为： PQ PQ PQ PQ,(一) 主析取范式,29/48,三个命题变元P、Q和R可构造8个极小项,把命题变元的否定形式看成0，肯定形式看成1，则每个极小项对应一个二进制数，也对应一个十进制数。它们对应如下： PQR 与000 或0对应，简记为 m0 PQR 与001 或1对应，简记为 m1 PQR 与010 或2对应，简记为 m2 PQR 与011 或3对应，简记为 m3 PQR 与100 或4对应，简记为 m4 PQR 与101 或5对应，简记为 m5 PQR 与110 或6对应，简记为 m6 PQR 与111 或7对应，简记为 m7,30/48,主析取范式,定义6 仅有极小项构成的析取范式称为主析取范式。 定理3 任何一个合式公式，均有惟一的一个主析取范式与该合式公式等价。,主析取范式就是 公式的所有完全成真解释对应的极小项的析取。,31/48,求主析取范式的两种方法,(1)解释法: 根据公式的所有完全成真解释，求出与这些成真解释对应的合取式，所有合取式的析取就为公式的主析取范式。 (2)等价变换法: 将析取范式中的每一个合取式用AA填满命题变元，然后用等价公式进行变换，消去相同部分，即得公式的主析取范式。,32/48,例 求公式的主析取范式 (PQ)(RQ)P),解： 原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 =(PQ(R R)(P (QQ)R) = (PQR) (PQ R)(P QR) =101100110=456,33/48,解：P=T时, 原式=(TQ)(RQ)T)=QR P=F时, 原式=(FQ)(RQ)F)=F 所以有: 成真解释为：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F),例 求公式的主析取范式 (PQ)(RQ)P),于是主析取范式为: (PQR)(P Q R)(P Q R) =101100110 =456,34/48,(二) 主合取范式,定义7 对于n个命变元P1，P2，Pn，公式 Q1Q2Qn 称为极大项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极大项有四个，它们分别为： PQ PQ PQ PQ,35/48,三个命题变元P、Q和R可构造8个极大项,把命题变元的否定形式看成1，肯定形式看成0，则每个极大项对应一个二进制数，也对应一个十进制数。它们对应如下： PQR 与000 或0对应，简记为 M0 PQR 与001 或1对应，简记为 M1 PQR 与010 或2对应，简记为 M2 PQR 与011 或3对应，简记为 M3 PQR 与100 或4对应，简记为 M4 PQR 与101 或5对应，简记为 M5 PQR 与110 或6对应，简记为 M6 PQR与111 或7对应，简记为 M7,36/48,主合取范式,定义8 仅有极大项构成的合取范式称为主合取范式。 定理4 任何一个合式公式，均有惟一的一个主合取范式与该合式公式等价。,主合取范式就是 公式的所有完全成假解释对应的极大项的合取。,37/48,求主合取范式的两种方法,(1)解释法 根据公式的所有完全成假解释，求出与这些成假解释对应的析取式，所有析取式的合取就为公式的主合取范式。 (2)等价变换法 将合取范式中的每一个析取式用AA填满命题变元，然后用等价公式进行变换，消去相同部份，即得公式的主合取范式。,38/48,例 求公式的主合取范式 (PQ)(RQ)P),解：原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式 =(P(QQ)(RR)(QR) (PP) =(PQR)(PQR) (PQR) (PQR) (PQR) =000001010011111=01237,39/48,解：P=T时, 原式=(TQ)(RQ)T)=QR P=F时, 原式=(FQ)(RQ)F)=F 所以有: 成假解释为：(P,Q,R)=(T,T,T), (F, ),例 求公式的主合取范式 (PQ)(RQ)P),于是 主合取范式= (PQR) (PQR) (PQR) (PQR)(PQR) =111011010001000 =01237,(F,TT),(F,T,F),(F,F,T),(F,F,F),40/48,主合取范式和主析取范式紧密相关,(PQ)(RQ)P)=456 =01237,(PR)(P (Q R) =257 =01346,(PR)(P (Q R) =1467= (1,4,6,7) = 0235= (0,2,3,5),41/48,主合取范式和主析取范式的唯一性,任何一个命题演算公式，具有唯一的主合取范式和主析取范式，因此如果两个公式具有相同的主析取范式或主合取范式，则称两公式逻辑等价。,42/48,1.3.3 范式的应用,你面前有两扇门，其中一扇门后有宝藏，一扇门后有吃人妖怪。 在这两扇门前面，有两个人，这两个人都知道哪扇门后有宝藏，哪扇门后有吃人妖怪，而这两个人呢，一个人只说真话，一个人只说假话。 你只能问这两个人每人一个问题。你怎么问才能找到宝藏？,苹果考题：宝藏在哪里?,43/48,问： 对”此门后是否有宝藏”问题, 你的同伴回答”是”吗？,令 P：被问人说真话； Q：被问人回答“是”； R：其同伴回答“是” ； S：此门后有宝藏。 根据题意可得真值表如图所示。 根据真值表知，主析取范式为： S=(PQ)(PQ) =(PP)Q =Q 因此被问人回答“是”时，此门后一定没有宝藏。,T T T (假话) F,T F F (假话) T,F T F (真话) F,F F T (真话) T,结论: 否定被问人的回答!,44/48,专家的论证正确吗?,在研讨会上，三位专家分别发言如下: 一位专家由此得