四川大学离散数学课件2-命题公式的蕴含
- 格式:ppt
- 大小:170.00 KB
- 文档页数:19
离散数学数理逻辑命题逻辑第三节命题公式的等值式蕴含式定义设命题公式A,B,若A↔B是重言式,称A和B等值,逻辑等价。
记为A⇔B,称为等值式,逻辑等价式注:⇔不是联结词,是公式关系符号,A⇔B不表示一个公式定理1)若A⇔B,则对A↔B的任何解释,A,B有相同的值2)A⇔A3)若A⇔B,则B⇔A 4) 若A⇔B,B⇔C,则A⇔C等值关系是等价关系可用真值表法求得一些所含命题变元不多的简单基本的等值式,后利用基本等值式推导出众多的较为复杂的等值式。
这种方法称为推导法或等值演算法交换律E1A∧B⇔B∧A A∨B⇔B∨A结合律E2(A∧B)∧C⇔A∧(B∧C)(A∨B)∨C⇔A∨(B∨C)分配律E3A∧(B∨C)⇔(A∧B)∨(A∧C)A∨(B∧C)⇔(A∨B)∧(A∨C)同一律E4A∧1⇔A A∨0⇔A互否律E5A∧﹁A⇔0A∨﹁A⇔1双重否定律E6﹁(﹁A)⇔A幂律E7A∧A⇔A A∨A⇔A常元律E8A∧0⇔0A∨1⇔1吸收律E9A∧(A∨B)⇔A A∨(A∧B)⇔A德.摩根律E10﹁(A∧B)⇔﹁A∨﹁B﹁(A∨B)⇔﹁A∧﹁B联结词化规律A→B⇔﹁A∨B A↔B⇔(A→B)∧(B→A)其他A→(B→C)⇔(A→B)→(A→C)⇔(A∧B)→C A→B⇔﹁B→﹁A交换律E1A∧B⇔B∧A A∨B⇔B∨A结合律E2(A∧B)∧C⇔A∧(B∧C)(A∨B)∨C⇔A∨(B∨C)分配律E3A∧(B∨C)⇔(A∧B)∨(A∧C)A∨(B∧C)⇔(A∨B)∧(A∨C)同一律E4A∧1⇔A A∨0⇔A互否律E5A∧﹁A⇔0A∨﹁A⇔1双重否定律E6﹁(﹁A)⇔A幂律E7A∧A⇔A A∨A⇔A常元律E8A∧0⇔0A∨1⇔1吸收律E9A∧(A∨B)⇔A A∨(A∧B)⇔A 德.摩根律E10﹁(A∧B)⇔﹁A∨﹁B﹁(A∨B)⇔﹁A∧﹁B联结词化规律E11A→B⇔﹁A∨BA↔B⇔(A→B)∧(B→A)其他E12A→(B→C)⇔(A→B)→(A→C)⇔(A∧B)→CA→B⇔﹁B→﹁A例证明下列等值关系(P→Q)∧(R→Q)⇔(P∨R)→Q(P∧Q∧A→C)∧(A→P∨Q∨C)⇔(A∧(P↔Q))→C定义仅含联结词﹁,∧, ∨的命题公式称限性公式。
离散数学蕴含的意思在离散数学中,蕴含关系(通常用→表示)有着特定的含义。
蕴含式p→q可以理解为:如果p成立,那么q一定成立;或者说p是q的充分条件。
从逻辑值的角度来看,当p为真而q为假时,p→q才为假,其余情况(p为假或者p和q都为真)下,p→q都为真。
这就像是一种承诺,如果前提p满足了,结果q就必须兑现,不然这个蕴含关系就不成立。
关于可衍生注释:我们可以进一步思考这种逻辑关系在实际中的体现。
例如在程序设计中的条件语句,就常常会用到蕴含关系的思想。
如果某个条件(p)满足,就执行特定的代码块(q)。
这有助于我们更好地理解程序的控制流程和逻辑架构。
赏析:蕴含关系的美妙之处在于它简洁地概括了一种因果联系。
它像是一座桥梁,将不同的命题连接起来,让我们能够从一个已知的事实(p)推断出另一个相关的事实(q)。
这种逻辑上的连贯性为解决复杂的逻辑问题提供了基础框架,使得我们能够层层推理,就像搭建积木一样构建起庞大的逻辑体系。
由于离散数学是众多数学家智慧的结晶,很难归结于某一个作者。
它是经过长期的发展和众多学者的研究逐步完善的学科内容。
例子1:我和小明在讨论离散数学的作业。
我对他说:“你看这蕴含关系啊,就好像是我们生活中的约定。
比如说,如果明天不下雨(p),那我们就去打篮球(q)。
要是明天真的没下雨,我们却没去打球,那这个约定就相当于违背了,也就是p→q为假。
但要是明天下雨了(p为假),不管我们打没打球,这个约定从逻辑上来说都还是合理的,因为前提没达成嘛,这就对应着p为假时p→q为真。
离散数学里的蕴含关系是不是很有趣?就像生活中的这些小约定一样,有着内在的逻辑呢!”小明挠挠头说:“还真是这么回事儿,以前觉得很抽象,现在感觉挺接地气的呢。
”例子2:老师在课堂上讲离散数学的蕴含关系。
他问大家:“同学们,假如我告诉你们‘如果考试成绩优秀(p),就会得到奖励(q)’,这就是一个蕴含关系。
你们想想,如果真的有人考得很好,可是我却没给奖励,这时候这个蕴含关系就不成立了对吧?但要是有人没考好(p为假),我不管有没有给奖励,从逻辑上讲这个说法都是对的。
本节小结:要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。
P Q P∧Q P∨Q P→Q P↔QF F F F T TF T F T T FT F F T F FT T T T T T1-5. 重言(永真)蕴涵式有些重言(永真)式,如(P∧(P→Q))→Q,公式中间是“→”联结词,是很重要的,称之为重言蕴涵式。
1.定义:如果公式A→B是重言式,则称A重言(永真)蕴涵B,记作A⇒B。
上式可以写成(P∧(P→Q))⇒Q注意符号“⇒”不是联结词,它是表示公式间的“永真蕴涵”关系,也可以看成是“推导”关系。
即A⇒B可以理解成由A可推出B,即由A为真,可以推出B也为真。
2.重言(永真)蕴涵式A⇒B的证明方法方法1.列真值表。
(即列A→B的真值表)这里就不再举例了。
下面讨论另外两种方法。
A B A→B F F T F T T T F F T T T先看一看A→B的真值表,如果A→B为永真式,则真值表的第三组指派不会出现。
于是有下面两种证明方法(解释法)。
方法2.假设前件为真,推出后件也为真。
例如求证:P ∧(P→Q)⇒Q证明:设前件P ∧(P→Q) 为真,则P、(P→Q)均真,所以Q为T。
∴P ∧(P→Q) ⇒Q方法3.假设后件为假,推出前件也为假。
例如求证:P ∧(P→Q)⇒Q证明:假设后件Q为F。
1.如P为F,则前件P ∧(P→Q)为F2.如P为T,则(P→Q)为F,所以前件P ∧(P→Q)为假。
∴P ∧(P→Q)⇒Q蕴涵式的直观意义设P:天下雨。
Q:马路湿。
则P∧(P→Q)⇒Q表示:如果天下雨,则马路湿;现在天下雨,所以,马路一定是湿的。
(Q∧(P→Q)⇒P?⌝Q∧(P→Q)⇒⌝P?)论证以下推理的正确性。
⏹P:x是偶数Q:x2是偶数⏹如果x是偶数,则x2是偶数;x是偶数,所以x2是偶数。
⏹如果x是偶数,则x2是偶数;x2是偶数,所以x是偶数。
⏹如果x是偶数,则x2是偶数;x不是偶数,所以x2不是偶数。