2-命题逻辑_ou.ppt
《2-命题逻辑_ou.ppt》由会员分享,可在线阅读,更多相关《2-命题逻辑_ou.ppt(144页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第二章第二章 命题逻辑命题逻辑 数理逻辑数理逻辑v数理逻辑是用数学的方法研究思维规律的一门数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号,简洁地表达出学科。由于它使用了一套符号,简洁地表达出各种推理的逻辑关系,因此,数理逻辑一般又各种推理的逻辑关系,因此,数理逻辑一般又称为符号逻辑。称为符号逻辑。v数理逻辑和计算机的发展有着密切的联系,它数理逻辑和计算机的发展有着密切的联系,它为机器证明、自动程序设计、计算机辅助设计为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。等计算机应用和理论研究提供必要的理论基础。v古典数理逻辑:命题逻辑和谓词逻辑古
2、典数理逻辑:命题逻辑和谓词逻辑是计算是计算机科学很重要的数学基础。机科学很重要的数学基础。v现代数理逻辑:逻辑演算、证明论、公理集合现代数理逻辑:逻辑演算、证明论、公理集合论、递归论和模型论论、递归论和模型论 。数理逻辑的创始人数理逻辑的创始人-莱布尼茨莱布尼茨(Leibniz,Gottfried Wilhelm)1646.7.1-1716.11.14 德国数学家、物理学家、哲学家等,德国数学家、物理学家、哲学家等,一个举世罕见的科学天才。研究领域涉一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、学、历史
3、学、语言学、生物学以及外交、神学等诸多方面神学等诸多方面.出生于德国东部莱比锡的一个书香之出生于德国东部莱比锡的一个书香之家,父亲是莱比锡大学的道德哲学教授,家,父亲是莱比锡大学的道德哲学教授,母亲出生在一个教授家庭。莱布尼兹的母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅父亲在他年仅6 6岁时便去世了,给他留岁时便去世了,给他留下了丰富的藏书。下了丰富的藏书。v1515岁时,进了莱比锡大学学习法律,一进校便跟上了岁时,进了莱比锡大学学习法律,一进校便跟上了大学二年级标准的人文学科的课程,还广泛阅读了培大学二年级标准的人文学科的课程,还广泛阅读了培根、开普勒、伽利略等人的著作,并对他们的著述进
4、根、开普勒、伽利略等人的著作,并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的行深入的思考和评价。在听了教授讲授欧几里德的几何原本几何原本的课程后,莱布尼兹对数学产生了浓厚的课程后,莱布尼兹对数学产生了浓厚的兴趣。的兴趣。1717岁时他在耶拿大学学习了短时期的数学,岁时他在耶拿大学学习了短时期的数学,并获得了哲学硕士学位并获得了哲学硕士学位 。v2626岁设计出世界第一台乘法器,被认为是现代机器数岁设计出世界第一台乘法器,被认为是现代机器数学的先驱者。学的先驱者。v Leibniz(1646Leibniz(164617161716年年)之梦:有一天所有的知识,之梦:有一天所有的知识
5、,包括精神和无形的真理,能够通过通用的代数演算放包括精神和无形的真理,能够通过通用的代数演算放入一个单一的演绎系统。入一个单一的演绎系统。v16931693年,发现了机械能的能量守恒定律。年,发现了机械能的能量守恒定律。v与牛顿并称为微积分的创立者。与牛顿并称为微积分的创立者。v系统阐述了二进制记数法,并把它和中国的八卦联系系统阐述了二进制记数法,并把它和中国的八卦联系起来。起来。第二章第二章 命题逻辑命题逻辑2.1 命题以及逻辑联结词命题以及逻辑联结词 2.2 命题公式命题公式 2.3 命题公式的等价关系和蕴涵关系命题公式的等价关系和蕴涵关系 2.4 范式范式 2.5 命题逻辑在二值逻辑器件
6、和语句逻辑中的应用 2.1 命题以及逻辑联结词命题以及逻辑联结词 1 命题命题 v所谓命题是指一句有真假意义的话。所谓命题是指一句有真假意义的话。v例如:上海是中国最大的城市例如:上海是中国最大的城市今天是星期二今天是星期二所有素数都是奇数所有素数都是奇数1+1=2v命题用大写英文字母命题用大写英文字母P,Q,P1,P2,表示。表示。下列句子中不是命下列句子中不是命题题的有的有()vA.我不会解答这道题。我不会解答这道题。vB.严禁吸烟。严禁吸烟。vC.我正在说谎。我正在说谎。vD.如果太阳从西方升起,你就可以长生不老。如果太阳从西方升起,你就可以长生不老。vE.别的星球上有生物。别的星球上有
7、生物。vF.几点了?几点了?vG.1960年长春春城电影院放映了国产故事片年长春春城电影院放映了国产故事片“白毛女白毛女”。vH.1+101=110vI.全体起立!全体起立!vJ.这个教室好大呀这个教室好大呀!v如果一个命题是真的,就说它的真值如果一个命题是真的,就说它的真值是是1;如果一个命题是假的,就说它的如果一个命题是假的,就说它的真值是真值是0。v也用也用“1”代表一个抽象的真命题,代表一个抽象的真命题,用用“0”代表一个抽象的假命题。代表一个抽象的假命题。2 逻辑联结词逻辑联结词 定义定义2.1.1v设设P是一个命题,命题是一个命题,命题“P是不对的是不对的”称称为为P的否定,记以的
8、否定,记以 P,读作读作非非P。真值规定:真值规定:P是真的当且仅当是真的当且仅当P是假的。是假的。v例例.P:吉大是中国最大的大学。吉大是中国最大的大学。P:吉大不是中国最大的大学。吉大不是中国最大的大学。Q:张三是好人张三是好人 Q:张三不是好人张三不是好人定义定义2.1.2v设设P,Q是两个命题,命题是两个命题,命题“P或者或者Q”称称为为P,Q的析取,记以的析取,记以P Q,读作读作P或或Q。真值规定:真值规定:P Q是真的当且仅当是真的当且仅当P,Q中至中至少有一个是真的。少有一个是真的。v例例.P:今天下雨,今天下雨,Q:今天刮风,今天刮风,P Q:今天下雨或者刮风。今天下雨或者刮
9、风。定义定义2.1.3v设设P,Q是两个命题,命题是两个命题,命题“P并且并且Q”称为称为P,Q的合取,记以的合取,记以P Q,读作读作P且且Q。真值规定:真值规定:P Q是真的当且仅当是真的当且仅当P和和Q都是真的。都是真的。v例例.P:2 2=5,Q:雪是黑的,雪是黑的,P Q:2 2=5并且雪是黑的。并且雪是黑的。注意:注意:自然语言中的自然语言中的“或者或者”一词有两种用法:一词有两种用法:v1)“张三或者李四考了张三或者李四考了90分分”,表示两者表示两者可以同时成立。这是可以同时成立。这是“可兼或可兼或”。v按照联结词按照联结词“”的定义,当的定义,当P,Q都为都为真时,真时,P
10、Q也为真,因此,也为真,因此,“”所表示所表示的的“或或”是是“可兼或可兼或”。v2)“我明天到北京出差或者到广州去度假我明天到北京出差或者到广州去度假”,表示的是二者只能居其一,不会同时,表示的是二者只能居其一,不会同时成立。这是成立。这是“不可兼或不可兼或”。v“不可兼或不可兼或”不可以用不可以用 来表示来表示.表示为:表示为:(P Q)(P Q)异或异或判断:判断:(1)今天晚上我在家中看戏或去剧场看戏。)今天晚上我在家中看戏或去剧场看戏。(2)他可能是)他可能是100米或米或400米冠军。米冠军。(3)我第一节课上数学课或上英语课。)我第一节课上数学课或上英语课。(4)李梅是三好学生或
11、优秀团员。)李梅是三好学生或优秀团员。(5)张三生于)张三生于1987年或年或1988年。年。(6)老王或小李有一个去上海出差。)老王或小李有一个去上海出差。(7)李明是软件学院的学生,他住在)李明是软件学院的学生,他住在312室或室或 313室。室。定义定义2.1.4v设设P,Q是两个命题,命题是两个命题,命题“如果如果P,则则Q”称为称为P蕴涵蕴涵Q,记以记以PQ。真值规定:真值规定:PQ是假的当且仅当是假的当且仅当P是真的是真的而而Q是假的。是假的。v例例.P:f(x)是可微的,是可微的,Q:f(x)是连续的,是连续的,PQ:若若f(x)是可微的,则是可微的,则f(x)是连续的。是连续的
12、。v由定义知,如果由定义知,如果P是假命题,则不管是假命题,则不管Q是是什么命题,命题什么命题,命题“如果如果P,则则Q”在命题逻在命题逻辑中都被认为是辑中都被认为是真命题真命题。与自然语言与自然语言不一样的地方不一样的地方v例例.P:2 2=5,Q:雪是黑的,雪是黑的,于是,命题于是,命题“如果如果2 2=5,则雪是黑的,则雪是黑的”是真命题。是真命题。定义定义2.1.5v设设P,Q是两个命题,命题是两个命题,命题“P当且仅当且仅当当Q”称为称为P等价等价Q,记以记以PQ。真值规定:真值规定:PQ是真的当且仅当是真的当且仅当P,Q或者都是真的,或者都是假的。或者都是真的,或者都是假的。v例如
13、,例如,P:a2+b2=a2,Q:b=0,PQ:a2+b2=a2当且仅当当且仅当b=0。例例2.1.1 v如果你走路时看书,那么你会成为近如果你走路时看书,那么你会成为近视眼。视眼。v令令P:你走路;你走路;Q:你看书;你看书;R:你你会成为近视眼。会成为近视眼。于是,上述语句可表示为(于是,上述语句可表示为(P Q)R。例例2.1.2 v除非他以书面或口头的方式正式通知除非他以书面或口头的方式正式通知我,否则我不参加明天的会议。我,否则我不参加明天的会议。v令令P:他书面通知我;他书面通知我;Q:他口头通他口头通知我;知我;R:我参加明天的会议。我参加明天的会议。于是,上述语句可表示为于是,
14、上述语句可表示为(P Q)R。例例2.1.3 v设设P,Q,R的意义如下:的意义如下:P:苹果是甜的;苹果是甜的;Q:苹果是红的;苹果是红的;R:我买苹果。我买苹果。试用日常语言复述下述复合命题:试用日常语言复述下述复合命题:(1)(P Q)R(2)(PQ)R v解:解:(1)如果苹果甜且红,那么我买如果苹果甜且红,那么我买;(2)我没买苹果,因为苹果不甜也不红我没买苹果,因为苹果不甜也不红.2.2 命题公式命题公式 1 公式公式 v我们用大写的英文字母我们用大写的英文字母P,Q,R,等代表一个抽象的命题,或称为等代表一个抽象的命题,或称为命命题符号题符号。v定义定义2.2.1 命题符号称为原
15、子。命题符号称为原子。v例如例如,Q,S,等都是原子。等都是原子。定义定义2.2.2 命题公式命题公式v命题逻辑中的公式,是如下定义的一个符命题逻辑中的公式,是如下定义的一个符号串:号串:(1)原子是公式;原子是公式;(2)0、1是公式;是公式;(3)若若G,H是公式,则是公式,则(G),(G H),(G H),(GH),(GH)是是公式;公式;(4)所有公式都是有限次使用所有公式都是有限次使用(1),(2),(3)得到的符号串。得到的符号串。(1)命题与命题符号的区别:命题与命题符号的区别:命题本身是有真假意义的一句话,但命题符号本身不具有真假意义。命题本身是有真假意义的一句话,但命题符号本
16、身不具有真假意义。命题不是命题公式中的语法单位,而命题符号是命题公式中的语法单位。命题不是命题公式中的语法单位,而命题符号是命题公式中的语法单位。(2)命题公式是由命题符号、命题公式是由命题符号、0、1、逻辑联结词、圆括号按照规定组成的有限、逻辑联结词、圆括号按照规定组成的有限长度符号串。长度符号串。(3)由于命题符号是抽象的,所以命题公式也是抽象的,本身不具有真假意义。由于命题符号是抽象的,所以命题公式也是抽象的,本身不具有真假意义。关于命题、命题符号和命题公式关于命题、命题符号和命题公式规定:1.公式公式(G)的括号可以省略,写成的括号可以省略,写成 G。2.整个公式的最外层括号可以省略。
17、整个公式的最外层括号可以省略。3.五种逻辑联结词的优先级按如下次序五种逻辑联结词的优先级按如下次序递增:递增:,v例如,我们写符号串例如,我们写符号串P Q RQS R就意味着是如下公式:就意味着是如下公式:(P(Q R)(Q(S)R)2 解释解释 v定义定义2.2.3 设设G是命题公式,是命题公式,A1,An是出现在是出现在G中的所有原子。中的所有原子。指定指定A1,An的一组真值,则这组真值称为的一组真值,则这组真值称为G的一个解释。的一个解释。v设设G是公式,是公式,I是是G的一个解释,显然,的一个解释,显然,G在在I下有真值,通常记为下有真值,通常记为TI(G)。例例 vG=P Q,设
18、解释设解释I,I如下:如下:I:I:则则TI(G)=1,TI(G)=0 v注意:该例子中写成注意:该例子中写成G=1或或G=0是错是错误的!误的!P Q 1 1 P Q 1 0 定义定义2.2.4 v公式公式G在其所有可能的解释下所取真在其所有可能的解释下所取真值的表,称为值的表,称为G的的真值表真值表。v显然,有显然,有n个不同原子的公式,共有个不同原子的公式,共有2n个解释。个解释。v例:例:G=(P Q)R,其真值表如下:其真值表如下:PQRG00010011010101111001101111001111v 练习:请画出练习:请画出 P,P Q,P Q,PQ,PQ的真值表。的真值表。v
19、若公式若公式G中出现的所有原子为中出现的所有原子为A1,An,有时我们用有时我们用m1,mn表示表示G的一个解释的一个解释I,其中其中 v例例.公式公式G=(P Q)R的真值表中第的真值表中第二个解释就可以记为二个解释就可以记为 P,Q,R 定义定义2.2.5 v公式公式G称为称为恒真的恒真的(或有效的或有效的),如果,如果G在它的所有解释下都是真的;在它的所有解释下都是真的;v公式公式G称为称为恒假的恒假的(或不可满足的或不可满足的),如果如果G在它的所有解释下都是假的;在它的所有解释下都是假的;v公式公式G称为称为可满足的可满足的,如果它不是恒,如果它不是恒假的。假的。v考虑考虑G1=(P
20、Q)P,G2=(P Q)P,G3=P P。从真值表可以看出从真值表可以看出G1对所有解释具有对所有解释具有“真真”值,公式值,公式G3对所有解释具有对所有解释具有“假假”值,值,而而G2具有具有“真真”和和“假假”值。值。PQ G1 PQ G2 PG30010000001101010101100111111v练习:用真值表判断公式练习:用真值表判断公式(PQ)(Q R)(PR)的)的类型类型vG是恒真的是恒真的 iff G是恒假的。是恒假的。vG是可满足的是可满足的 iff 至少有一个解释至少有一个解释I,使使G在在I下为真。下为真。v若若G是恒真的,则是恒真的,则G是可满足的;是可满足的;反
21、反之不对。之不对。v如果公式如果公式G在解释在解释I下是真的,则称下是真的,则称I满足满足G;如果如果G在解释在解释I下是假的,则下是假的,则称称I弄假弄假G。v练习:求满足公式(练习:求满足公式(P Q)P Q的的解释和弄假它的解释。解释和弄假它的解释。v在逻辑研究和计算机推理以及决策判断中,在逻辑研究和计算机推理以及决策判断中,人们对于所研究的命题,最关心的莫过于人们对于所研究的命题,最关心的莫过于“真真”、“假假”问题,所以恒真公式在数理逻问题,所以恒真公式在数理逻辑研究中占有特殊且重要的地位。辑研究中占有特殊且重要的地位。3 判定问题判定问题v能否给出一个能否给出一个可行方法可行方法,
22、对任意的公式,对任意的公式,判定其是否是恒真公式。判定其是否是恒真公式。v因为一个命题公式的原子数目有限因为一个命题公式的原子数目有限(n),从,从而解释的数目是有限的而解释的数目是有限的(2n),所以命题逻辑,所以命题逻辑的判定问题是可解的的判定问题是可解的(可判定的,可计算的可判定的,可计算的).v结论结论:命题公式的恒真,恒假性命题公式的恒真,恒假性是可判定的是可判定的.作业作业:习题习题2.1-3,习题习题2.2-1、3、42.3 命题公式的等价关系命题公式的等价关系和蕴涵关系和蕴涵关系 1 公式的等价公式的等价 v定义定义2.3.1 称公式称公式G,H是等价的,记是等价的,记以以G=
23、H,如果如果G,H在其任意解释在其任意解释I下,下,其真值相同。其真值相同。v公式公式G,H等价等价 iff 公式公式GH恒真。恒真。v公式间的等价关系有自反性、对称性、公式间的等价关系有自反性、对称性、传递性。传递性。基本等价式基本等价式 1)(GH)=(GH)(HG);2)(GH)=(G H);3)G G=G,G G=G;(等幂等幂律律)4)G H=H G,G H=H G;(交换交换律律)5)G(H S)=(G H)S,G(H S)=(G H)S;(结合结合律律)6)G(G H)=G,G(G H)=G;(吸收律吸收律)7)G(H S)=(G H)(G S),G(H S)=(G H)(G S
24、);(分配律分配律)8)G 0=G,G 1=G;(同一律同一律)9)G 0=0,G 1=1;(零一律零一律)10)(G H)=GH,(G H)=GH。(De Morgan律律)(互补律:(互补律:G G=1;G G=0 双重否定律:双重否定律:G=G)上述等价式可用真值表验证。上述等价式可用真值表验证。证明命题公式恒真或恒假的两个方法证明命题公式恒真或恒假的两个方法 v方法一方法一.真值表方法。真值表方法。即列出公式的真值表,若表中对应公式所即列出公式的真值表,若表中对应公式所在列的每一取值全为在列的每一取值全为1,这说明该公式在,这说明该公式在它的所有解释下都是真,因此是恒真的;它的所有解释
25、下都是真,因此是恒真的;若表中对应公式所在列的每一取值全为若表中对应公式所在列的每一取值全为0,这说明该公式在它的所有解释下都为假,这说明该公式在它的所有解释下都为假,因此是恒假的。因此是恒假的。v方法二方法二.以基本等价式为基础,通过反复对一以基本等价式为基础,通过反复对一个公式的等价代换,使之最后转化为一个恒真个公式的等价代换,使之最后转化为一个恒真式或恒假式,从而实现公式恒真或恒假的证明。式或恒假式,从而实现公式恒真或恒假的证明。例例.(PQ)(Q R)(PR)=(P Q)(Q R)(P R)=(P Q)(Q R)(P R)=(P Q)(Q P R)(R P R)=(P Q)(Q P R
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 命题逻辑 _ou
限制150内