左孝凌离散数学1.3命题公式与翻译1.4真值表与等价公式.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/3,#,1,离散数学,(,Discrete Mathematics,),1.3.1,命题公式,1.3.2,复合命题符号化,(,翻译,),第1页,2,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,1.3.1,合式公式,(Well-formed formula)(wff),定义,1.3.1,:,原子公式,单个,命题变元,和,命题常量,称为,原子公式,。,第2页,3,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,定义,1.3.2,：合式公式,(1),原子公式,是,合式公式,(wff),。,（,2,）若,A,，,B,是合式公式，则（,A,），,(A,B),，,(A,B),，,(A,B),，,(A,B),也是合式公式。,（,3,）,当且仅当,有限次地应用,(1)(2),所得到包含,原子公式、,联结词和括号符号串是合式公式。,第3页,4,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,例,1,：,指出,(P(P,Q),是否是命题公式,(wff),，假如是，则详细说明。,解：,P,是,wff,由,(1),Q,是,wff,由,(1),P,Q,是,wff,由,(2),(P(P,Q),由,(2),(PQ,）,(Q,),，,(PQ,，,(PQ,）,Q,），,PQ,S,(P,W,)Q,),不是合式公式。,第4页,联结词优先级：,、,。,则：,PQR,是合式公式,等价于,Wff,：,（,（,PQ,）,R,）,命题公式外层括号能够省略,等价于,Wff,：（,PQ,）,R,不等价于,Wff,：,P,（,QR,）,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,第5页,6,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,1.3.2,复合命题符号化,(,翻译,),自然语言语句用,Wff,形式化,要准确,确定原子命题,，并将其,形式化,。,要选取恰当联结词，尤其要善于,识别自然语言中联结词,（有时它们被省略），,否定词位置,要放准确。,必要,时能够,进行改述,，即改变原来叙述方式，,但要确保表示意思一致,。,需要,括号不能省略,，而能够省略括号，,在需要提升公式可读性时亦可不省略。,要注意语句形式化,未必是唯一,。,第6页,能够把本命题表示为：,(P,Q,）。,解,P,：上海到北京,14,次列车是下午五点半开。,Q,：上海到北京,14,次列车是下午六点开。,在本例中，,汉语“或”是不可兼或,，而,逻辑联结词是“可兼或”,，所以不能直接对两命题析取。结构如表,1-3.1,所表示。,PQ,原命题,P,Q,(P,Q),T,T,F,T,F,T,F,T,F,T,F,T,T,F,T,F,F,F,T,F,表,1-3.1,例题,2,上海到北京,14,次列车是下午五点半或六点开。,第7页,解,这个命题意义，亦可了解为：,假如你不努力则你将失败。,若设,P,：你努力。,Q,：你失败。,本例可表示为：,PQ,例题,5,除非你努力，不然你将失败。,第8页,解 这个命题意义是：,可兼或,若设,P,：张三能够做这事。,Q,：李四能够做这事。,本例可表示为：,P,Q,例题,6,张三或李四都能够做这件事。,第9页,10,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,1),我今天进城，除非下雨。,1-3.(7),2),仅当你走我将留下。,1-3.(7),3),假如早晨不下雨，我去看电影，不然就在家里,读书或看报。,1-3.(7),4),一个人起初说：“占据空间、有质量而且不停改变叫做物质”；以后他改说，“占据空间有质量叫做物质，而物质是不停改变。”问他前后主张差异在什么地方，试以命题形式进行分析,。,1-3.(6),练习,1,第10页,11,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,我今天进城，除非下雨。,1-3.(7),P,：,我今天进城。,Q:,天下雨。,QP,2),仅当你走我将留下。,1-3.7),P:,你走。,Q:,我留下。,QP,3),假如早晨不下雨，我去看电影，不然就在家里,读书或看报。,1-3.(7),P:,早晨下雨。,Q:,我去看电影。,R:,我在家里读,或,看报。,(PQ),(PR),）,（,要么看电影要么留在家里，排斥或,）,解答,第11页,12,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,5),一个人起初说：“占据空间、有质量而且不停改变叫做物质”；以后他改说，“占据空间有质量叫做物质，而物质是不停改变。”问他前后主张差异在什么地方，试以命题形式进行分析。,1-3.(6),P:,它占据空间,Q:,它有质量,R:,它不停改变,S:,它是物质,这个人起初主张：,(PQR),S,以后主张：,(,（,PQ,）,S)(SR),解答,第12页,练习,2,（小李不在图书馆），（他要么找老师去了），（要么就是因为身体不适，回宿舍去了）。,命题符号化是很主要，一定要掌握好，在命题推理中经常最先碰到就是符号化一个问题，处理不好，等于说推理首要前提没有了。,解,设,P,：小李在图书馆。,Q,：小李找老师。,R,：小李身体不适。,S,：小李回宿舍。,则命题符号化为：（,P,）,（,(Q (RS),）,（小李不是,而是,）,（要么,要么,排斥或）,第13页,14,第一章 命题逻辑,（,Propositional Logic,）,1.3,命题公式与翻译,小结,：本节介绍了命题公式概念及复合命题符号化,.,重点是了解命题公式递归定义,掌握复合命题符号化方法,.,作业：,p12(5),第14页,15,离散数学,(,Discrete Mathematics,),1.4.1,真值表,(Truth Table),1.4.2,等价公式,(,Propositional Equivalences),第15页,16,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,定义,1.4.2(,真值表,),在命题公式,A,中,对于命题变元每一组赋值,和由它们所确定,命题公式,A,真值列成表,，称做命题公式,A真值表,。,考虑：,含有,n,个命题变元,公式共有,多少组不一样赋值,？,2,n,第16页,17,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,对公式,A,结构真值表详细步骤为：,（,1,）找出公式中全部命题变元,P,1,P,2,P,n,（,2,）按从小到大次序列出对命题变元,P,1,P,2,P,n,全部,2,n,组赋值。,（,3,）对应各组赋值计算出公式,A,真值，并将其列在对应赋值后面。,第17页,18,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,1.,给出,(P,Q),(P,Q),真值表：P,Q,P,Q,(P,Q),P,Q,(P,Q),(P,Q),0,0,0,1,1,0,1,1,第18页,19,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,1.,给出,(P,Q),(P,Q),真值表：,P,Q,P,Q,(P,Q),P,Q,(P,Q),(P,Q),0,0,0,1,1,0,1,1,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,第19页,20,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,2,：结构公式,(P,Q)R,真值表。,P,Q,R,P,Q,(P,Q)R,0,00,0,0,1,0,1,0,0,1,1,1,0,0,1,0,1,1,1,0,1,1,1,第20页,21,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,2,：结构公式,(P,Q)R,真值表。,P,Q,R,P,Q,(P,Q)R,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,第21页,22,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,练习,1,：结构公式,(P,Q),(,Q,P,）,真值表P,Q,P,Q,P,Q,Q,P,(,P,Q,),(,Q,P,),0,0,0,1,1,0,1,1,第22页,23,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,练习,1,：结构公式,(P,Q),(,Q,P,）,真值表。,P,Q,P,Q,P,Q,Q,P,(,P,Q,),(,Q,P,),0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,0,1,1,1,0,0,1,1,1,第23页,24,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,P,Q,(,P,Q,),(,P,Q,),(,P,Q,),Q,0,0,0,1,1,0,1,1,练习,2,：结构公式,(P,Q,）,Q,真值表。,第24页,25,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,P,Q,(,P,Q,),(,P,Q,),(,P,Q,),Q,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,0,0,练习,2,：结构公式,(P,Q,）,Q,真值表。,第25页,永真公式 永假公式：,不论对其分量作怎样真值指派，其真值永为,T,，称为永真公式，记为,T,。,如例,1,不论对其分量作怎样真值指派，其真值永为,F,，称为永假公式，记为,F,。,如例,2,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,第26页,从真值表中能够看到，,有些命题公式,在分量不一样指派下，其对应真值与,另一命题公式完全相同,，如,PQ,与,PQ,对应真值相同，如表,1-4.5,所表示。,P,Q,PQ,PQ,T,T,T,T,T,F,F,F,F,T,T,T,F,F,T,T,表,1-4.5,我们说,PQ,和,PQ,是等价，这在以后推理中尤其有用。,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,1.4.2,等价公式,第27页,同理,(PQ)(PQ),与,P,Q,对应真值相同，如表,1-4.6,所表示。,表,1-4.6,P,Q,P,Q,(PQ)(PQ),T,T,T,T,T,F,F,F,F,T,F,F,F,F,T,T,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,1.4.2,等价公式,第28页,29,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,定义,1.4.3:,给定两个命题公式,A,和,B,设,P,1,P,2,P,n,为出现于,A,和,B,中全部原子变元,若给,P,1,P,2,P,n,任一组真值指派,A,和,B,真值都相同,则,称,A,和,B,是等价,.,记作,A,B,。,1.4.2,等价公式,第29页,30,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,1.,真值表法,2.,等值演算法,1.,真值表法,例,1.(P,Q),(P,Q),见真值表例题,1.,例,2.,证实,:P,Q,(PQ),(QP),P,Q,P,Q,QP,PQ,(PQ),(QP),0,0,0,1,1,0,1,1,证实公式等价方法：,第30页,31,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,1.,真值表法,2.,等值演算法,1.,真值表法,例,1.(P,Q),(P,Q),见真值表例题,1.,例,2.,证实,:P,Q,(PQ),(QP),P,Q,P,Q,QP,PQ,(PQ),(QP),0,0,1,1,1,1,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,1,1,1,所以：,P,Q,(PQ),(QP),(PQ)(PQ),试用等值演算方法证实,另外，,P,Q,(PQ)(Q P),第31页,32,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,2.,等值演算法,(Equivalent Caculation),（利用,P15,表,1-4.8),主要等价式,(,补充,):,11.,蕴涵等值式,:,P,Q,P,Q,Q,P,Q,P,（假言易位）,12.,等价,等值式,P,Q,(PQ),(QP),(PQ)(Q P),(PQ)(PQ),13.,假言易位,:,P,Q,Q,P,14.,等价否定等值式,:,P,Q,P,Q,15.,归谬论,:,(,P,Q,),(,P,Q),P,第32页,对合律,P,P,1,幂等律,PP,P,，,PP,P,2,结合律,(PQ,）,R,P,（,QR,）,(PQ,）,R,P,（,QR,）,3,交换律,PQ,QP,PQ,QP,4,分配律,P,（,QR,）,（,PQ,）（,PR,）,P,（,QR,）,（,PQ,）（,PR,）,5,吸收律,P,（,PQ,）,P,P,（,PQ,）,P,6,德摩根律,(PQ),PQ,(PQ),PQ,7,同一律,PF,P,，,P,T,P,8,零律,P,T,T,，,P,F,F,9,否定律,PP,T,，,PP,F,10,表,1-4.8,命题定律,任何数,与,0,相或,还是,任何数,任何数,与,1,相与,为,1,任何数,与,1,相与,还是,任何数,与,0,相与,为,0,第33页,例题,6,验证吸收律,P,（,PQ,）,P,P,（,PQ,）,P,证实 列出真值表,表,1-4.9,P,Q,PQ,P,（,PQ,）,PQ,P,（,PQ,）,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,F,F,F,F,由表,1-4.9,可知吸收律成立。,练习,18,页（,4,）,第34页,35,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,等值演算中使用一条主要规则：,置换规则。,定义,1.4.4,子公式：,假如,X,是,wff A,一部分,且,X,本身也是,wff,，则称,X,是,A,子公式。,比如,P,(P,Q),为,Q,(,P,(P,Q),子公式。,定理,1.4.1,置换定理：,设,X,是,wff A,子公式，若,X,Y,，则若将,A,中,X,用,Y,来置换，所得公式,B,与,A,等价，即,A,B,。,定义,1.4.5,等值演算：,依据已知等价公式,推演出另外一些等价公式过程称为,等值演算,.,第35页,36,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,1,：证实,Q,（,P,（,P,Q,）,QP,证,:Q,（,P,（,P,Q,）,QP,P(,吸收律,),例,2,：证实（,P,Q,）,Q,P,Q,证：,(P,Q),Q,(P,Q),(,Q,Q),(,P,Q),T,P,Q,例,3,：证实（,PQ,）（,Q,R,）,P,Q,R,证：（,PQ,）（,Q,R,）,（,P,Q,）（,Q,R,）,(,P,Q),（,Q,R,）,（,P,Q,）,（,Q,R,）,（,P,Q,R,）,（,Q,Q,R,）,(,P,Q,R),(,Q,Q,),R),(,P,Q,R),(T,R),(,P,Q,R),T,P,Q,R),第36页,37,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,例,4,：验证,P,(,Q,R),(,P,Q,)R,证,:,右,(,P,Q,),R,（蕴含等值）,P,Q,R,（德摩根律）,P,(,Q,R),（结合律）,P,(,Q,R),（蕴含等值）,P,(,Q,R),（蕴含等值）,第37页,例,5,：,依据真值表方法“排斥或”可表示为,(P,Q),证实：,(P,Q),(,P,Q)(,Q,P,),证,:,(,P,Q,),（,（,PQ,）,（,Q,P,）,）,（,（,P,Q,）,（,Q,P,）,）,（,（,P,Q,）,）,（,（,Q,P,）,）,（,P,Q,）,（,P,Q,）,练：,1.(,P,Q,),(,P,R),P,(,Q,R),2.(,P,Q,),(,P,Q,),(,P,Q,),(,P,Q,),第38页,39,第一章 命题逻辑,（,Propositional Logic,）,1.4,真值表与等价公式,等值演算,在计算机硬件设计中,在开关理论和电子元器件中都占有主要地位,.,小结,:,本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了惯用主要等价公式（,24,个）。,重点掌握用真值表法验证公式等价性和等值演算法推演两个公式等价。,作业：,P19,（,7,）,.,预习,:1.5,1.6,思索题：,第39页,