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

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 (Assoc

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

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

4、义 祈使句、疑问句、感叹句不具有真假意义 （3）能判断出真假。 将来某个时候能判断出真假也行,两者必居其一且只居其一 二值逻辑,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 命题符号

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

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

7、今天下雨。 Q：今天不下雨。（此时Q既是P） PQ：今天下雨与今天不下雨。 PQ的真值为F。 命题联结词“合取”也可以将若干个命题联结在一起。 “合取”是一个二元运算。,15,1.1 命题符号化 2.联接词,注意，并非所有的“和”、“与”、“并且”均可用“”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“”表示。 练习：P：一个世纪是一百年。 Q：4是偶数。 写出PQ并确定其真值。,16,1.1 命题符号化 2.联接词,析取: PQ为假当且仅当P和Q的真值均为假。 例：P: 李红学英语。 Q: 李红学日语。

8、PQ: 李红学英语或者学日语。,相当于汉语中两者可同时为真的“或”,P Q,PQ,0 0,0,0 1,1,1 0,1,1 1,1,并非所有的“或”可用“”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。 析取“”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里 P：他可能是100米赛跑的冠军。 Q：他可能是400米赛跑的冠军。 PQ：他可能是100米或400米赛跑的冠军。,17,1.1 命题符号化 2.联接词,还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三十道习题。这里的“或”字只表示了习题的近

9、似数目，不能用联结词“”表达。 练习：P：雪是黑的。 Q：4是偶数。 写出PQ并确定其真值。,18,1.1 命题符号化 2.联接词,蕴涵: PQ为假当且仅当P为真、Q为假。 例：P: 天晴。 Q: 我骑自行车上班。 PQ: 如果天晴，则我骑自行车上班。,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：我得到这本

10、小说，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的真值为F，PQ的真值为T。,19,1.1 命题符号化 2.联接词,在自然语言中，“如果”与“那么”之间常常是有因果联系的，否则就没有意义，但对条件命题PQ来说，只要P、Q能够分别确定真值，PQ即成为命题。此外，自然语言中对“如果、则”这样的语句，当前提为假时，结论不管真假，这个语句的意义，往往无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都

11、取为T。,在数学上和有些逻辑学的书籍中，“若P则Q”亦可叫作P蕴含Q，而本书在条件命题中将避免使用“蕴含”一词，因为在以后将另外定义“蕴含”这个概念。 命题联结词“”亦可记作“ ”。,20,1.1 命题符号化 2.联接词,蕴涵 P Q,P 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,

12、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.联接词,分析找出 简单命题,用大写字母 表示简单命题,用联接词联接命题符号,例：符号化命题：如果我上街并且我不累，我就去书店看看。 简单命题：我上街 我累 我去书店看看,解 令 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的代入实例。 例：