上堂课的内容重点与难点.ppt
《上堂课的内容重点与难点.ppt》由会员分享,可在线阅读,更多相关《上堂课的内容重点与难点.ppt(48页珍藏版)》请在三一文库上搜索。
1、1/48,上堂课的内容、重点与难点,联结词的使用 等价公式 成真解释与成假解释,真值函项的理解 蕴含词的正确使用 等价公式的理解与运用,命题 联结词 合式公式 解释 逻辑等价 真假性,2/48,1.2.3 联结词的完备集,定义 设S是联结词的集合,如果 对任何命题演算公式均可以由S中的联结词表示出来的公式与之等价, 则称S是联结词的完备集。,由联结词的定义知,联结词集合 , 是完备的。,3/48,定理1 联结词的集合,是完备的。,思路: 去蕴含词与等价词 PQ = P Q PQ = (P Q) (P Q),4/48,定理 联结词的集合, 是完备的。,思路: 在去蕴含词与等价词的基础上, PQ
2、=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,公
3、式右边=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) (
4、) = 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= A
5、1* , A2= A2* 。 对于上述三种情形,可以分别证明结论成立: A =A*。 由数学归纳法知,定理得证。,14/48,1.3 范式及其应用,合取式,析取式,析取范式,合取范式,主析取范式,主合取范式,主范式 范式 真假性,唯一 两者有关联 不唯一,成真解释,成假解释,对于完全解释, 合(析)取式 =极小(大)项,15/48,合取式、析取式,定义1 命题变元、或者命题变元的否定、或由它们利用合取词组成的合式公式称为合取式。 定义2 命题变元、或者命题变元的否定、或由它们利用析取词组成的合式公式称为析取式。 例 显然, P,P,PQ,PQR 均为合取式; P,P,PQ,PQR 均为析取式。
6、,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) 均为合
7、取范式。,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。 根据解释和范式的关系知: 对应于
8、成真解释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)重复使
9、用分配律: 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)
10、=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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上堂 内容 重点 难点
链接地址:https://www.31doc.com/p-2631868.html