离散-1-1-命题逻辑.ppt

《离散-1-1-命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散-1-1-命题逻辑.ppt（26页珍藏版）》请在三一办公上搜索。

1、1,离 散 数 学,林昌龙华侨大学计算机学院,2,教材与参考资料,教材：离散数学 刘玉珍、刘咏梅编，武汉大学出版社参考资料：离散数学耿素云、屈婉玲、张立昂编，清华大学出版社离散数学朱一清编著，电子工业出版社Discrete Mathematical Structures Bernard Kolman,Fobert C.Busby and Sharon Ross 著 Prentice Hall出版社,3,目的、意义和要求,IEEE(Institute of Electrical and Electronics Engineers)美国电气和电子工程师协会 ACM(Association for

2、Computing Machinery)美国计算机协会Computing curricula 2001 computer science,4,目的、意义和要求,研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学要求：内容：1-7 章、8-10简介、11章作业：按时交、课后复习（概念、定理）,5,离散数学的构成,数理逻辑,集 合 论,图 论,代数系统,命题逻辑,谓词逻辑,集合,关系,图的基本概念,几个特殊图,代数系统的基本概念,特殊代数系统,离散数学,函数,图的连通性,代数系统的同态与同构,6,主要内容：,1.1 命题

3、符号化基本概念命题联接词1.2 合式公式命题语言的字母表合式公式可归纳定义公式的代入实例,7,第一篇 数理逻辑第一章 命题逻辑,数理逻辑是用数学方法研究形式推理的一门学科命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析,在计算机科学中的应用：软件、硬件设计,符号化,研究公式间的关系,推导、演算,8,1.1 命题符号化 1.基本概念,命题：具有唯一真/假值的陈述句。T/1真 F/0假,（1）命题必须是一个完整的句子，包括用数学式子代表的语句。（2）所给的语句具有真假意义。一般只有陈述句才具有真假意义祈使句、疑问句、感叹句不具有真假意义（3）能判断出真假。将来某个时

4、候能判断出真假也行,两者必居其一且只居其一二值逻辑,9,1.1 命题符号化 1.基本概念,命题：具有唯一真/假值的陈述句。T/1真 F/0假,例：,中国的首都在北京。雪是白色的。1+1=10 建国大业里面有很多大腕。贾君鹏，你妈妈喊你回家吃饭。立正！你喜欢网络游戏吗？今天的天气真热！,10,1.1 命题符号化 1.基本概念,命题：具有唯一真/假值的陈述句。T/1真 F/0假,例：,哥德巴赫猜想是正确的。牛鬼蛇神是存在的。x+y 3 我正在说谎。本命题是假的。,11,1.1 命题符号化 1.基本概念,命题：具有唯一真/假值的陈述句。T/1真 F/0假,简单命题：若命题是一个简单的陈述句。复合命题

5、：由简单命题通过“非”、“或”、“与”、“蕴含”、“等值”等命题联结词而组成。例：李红既学英语又学日语。你只有刻苦学习，才能取得好成绩。,12,否定词（）：P为真当且仅当P的真值为假。例：P:中国的首都在北京。P:中国的首都不在北京。,1.1 命题符号化 2.联接词,是不是简单命题？,P,P,0,1,1,0,合取:PQ为真当且仅当P和Q的真值均为真。例：P:李红学英语。Q:李红学日语。PQ:李红学英语并且学日语。,相当于汉语的“与”、“并且”,P Q,PQ,0 0,0,0 1,0,1 0,0,1 1,1,与自然语言不同：凡是命题均可联接。,13,1.1 命题符号化 2.联接词,合取的概念与自然

6、语言中的“与”意义相似，但并不完全相同。例如P：我们去看电影。Q：房间里有十张桌子。上述命题的合取为PQ：我们去看电影与房间里有十张桌子。在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P和Q的合取PQ来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，PQ的真值也必确定。,14,1.1 命题符号化 2.联接词,命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。P：今天下雨。Q：今天不下雨。（此时Q既是P）PQ：今天下雨与今天不下雨。PQ的真值为F。命题联结词“合取”也可以将若干个命题联结在一起。“合取”是一个二元运算。,1

7、5,1.1 命题符号化 2.联接词,注意，并非所有的“和”、“与”、“并且”均可用“”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“”表示。练习：P：一个世纪是一百年。Q：4是偶数。写出PQ并确定其真值。,16,1.1 命题符号化 2.联接词,析取:PQ为假当且仅当P和Q的真值均为假。例：P:李红学英语。Q:李红学日语。PQ:李红学英语或者学日语。,相当于汉语中两者可同时为真的“或”,P Q,PQ,0 0,0,0 1,1,1 0,1,1 1,1,并非所有的“或”可用“”表示。例如，“我向东行或向西行。”该语

8、句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。析取“”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里P：他可能是100米赛跑的冠军。Q：他可能是400米赛跑的冠军。PQ：他可能是100米或400米赛跑的冠军。,17,1.1 命题符号化 2.联接词,还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三十道习题。这里的“或”字只表示了习题的近似数目，不能用联结词“”表达。练习：P：雪是黑的。Q：4是偶数。写出PQ并确定其真值。,18,1.1 命题符号化 2.联接词,蕴涵:PQ为假当且仅当P为真、Q为假。例：P:天晴。Q:我骑自行车上班。P

9、Q:如果天晴，则我骑自行车上班。,P Q,PQ,0 0,1,0 1,1,1 0,0,1 1,1,例1 如果某动物为哺乳动物，则它必胎生。例2 如果我得到这本小说，那么我今夜就读完它。例3 如果雪是黑的，那么太阳从西方出。上述三个例子都可用条件命题PQ表达。在例1中，P：某动物为哺乳动物，Q：它必胎生。P的真值为T，Q的真值为T，PQ的真值为T。在例2中，P：我得到这本小说，Q：我今夜就读完它。P的真值为T，Q的真值为T，PQ的真值为T。如果P的真值为T，Q的真值为F，PQ的真值为F。如果P的真值为F，Q的真值为T，PQ的真值为T。在例3中，P：雪是黑的，Q：太阳从西方出。P的真值为F，Q的真值

10、为F，PQ的真值为T。,19,1.1 命题符号化 2.联接词,在自然语言中，“如果”与“那么”之间常常是有因果联系的，否则就没有意义，但对条件命题PQ来说，只要P、Q能够分别确定真值，PQ即成为命题。此外，自然语言中对“如果、则”这样的语句，当前提为假时，结论不管真假，这个语句的意义，往往无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T。,在数学上和有些逻辑学的书籍中，“若P则Q”亦可叫作P蕴含Q，而本书在条件命题中将避免使用“蕴含”一词，因为在以后将另外定义“蕴含”这个概念。命题联结词“”亦可记作“”。,20,1.1 命题符号化 2.联接词,蕴涵P Q,P

11、 Q,PQ,0 0,1,0 1,1,1 0,0,1 1,1,P是Q的充分条件。Q当P。Q是P的必要条件。P仅当Q。P除非Q。只有Q，才P。,21,1.1 命题符号化 2.联接词,等价:PQ为真当且仅当P和Q的真值相同。例：P:两个圆的面积相等。Q:两个圆的半径相等。PQ:两个圆的面积相等当且仅当两个圆的半径相等。,P Q,PQ,0 0,1,0 1,0,1 0,0,1 1,1,“P当且仅当Q”有两层含义：（1）P当Q；（2）P仅当Q等价联结词又可以称为双蕴含连接词,例 当且仅当你走，我留下。P：你走，Q：我留下。命题可以表示为：P Q,22,1.1 命题符号化 2.联接词,分析找出简单命题,用大

12、写字母表示简单命题,用联接词联接命题符号,例：符号化命题：如果我上街并且我不累，我就去书店看看。简单命题：我上街 我累 我去书店看看,解 令 P:我上街 Q:我累 R:我去书店看看 则可符号化为：（PQ)R,23,1.2 合式公式(1),1.命题语言的字母表：命题常元：T,F(或 0，1)命题变元：P1,P2,Pn联接词：，辅助符号：（，）*：上的符号串，包括空串 2.命题逻辑的合式公式可归纳定义如下：命题常元或命题变元是合式公式；若A,B是合式公式,则(A),(AB),(AB),(AB)和(AB)都是合式公式；有限次地使用,所得到的符号串才是合式公式。例：(（PQ)P)R子公式、真子公式,24,1.2 合式公式(2),3.公式的代入实例：,所得到的公式称为A的代入实例。例：（PQ)P，用PQ取代P，用PQ取代Q，(PQ)(PQ)(PQ)（同时取代）(PQ)Q)(PQ)(P(PQ)(PQ)(P(PQ)注意上面“同时取代”和“逐步取代”的不同,先取代P,再取代Q,25,作业：P4 1,2,P7 3(1),26,发明计算机的目的？计算机应用领域,信息、数据及其处理方法机器表示,现实世界,信息世界,机器世界,抽象表示,特点：处理各种各样 非连续数据,意义：,