离散数学第一章命题演算基础-真假性.ppt
《离散数学第一章命题演算基础-真假性.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 范式及其应
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第一章 命题演算 基础 假性
链接地址:https://www.31doc.com/p-3406926.html