离散数学第一章命题演算基础-命题和联结词.ppt

1、离散数学,数理逻辑 集合论 图论 代数,逻辑学:研究推理的科学,早期创始人 亚里士多德(公元前384322) 柏拉图(公元前429348), 首先把逻辑学的思想方法引入几何学 苏格拉底（前470前399年）,亚里士多德（Aristotole，公元前384-322）,亚里士多德有170多部著作，留传于世的仅47种。他的科学著作构成当时的科学知识百科全书。,世界古代史上最伟大的哲学家、科学家和教育家。他创立了形式逻辑学，丰富和发展了哲学的各个分支学科。,孔子（前551-479）,中国春秋末期伟大的思想家和教育家，儒家学派的创始人。 孔子被尊为圣人，无法超越，后代的人们只有沿袭与膜拜。,学而不思则罔

2、 思而不学则殆,数理逻辑数学化的逻辑学,在17世纪莱布尼兹（Leibniz）已经提出仿数学的方法发展逻辑的思想。 1930年，Godel完全性定理的证明完善了数理逻辑基础，建立了逻辑演算，成为现代科学特别是计算机科学不可缺少的基础理论之一。,数理逻辑发展史中的代表人物,德国G.W. Leibniz (1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。 英国G. Boole (1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。 德国G. Frege (1848-1925)在1879年建立了第一个谓词演算系统。 英国B. Russell (1872-197

3、0)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。 奥地利K. Godel (1906-1978)在1931年提出Godel不完全性定理。 英国Alan M. Turing (1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机一种理想的计算机。,数理逻辑的学习,“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。” Edsger. W. Dijkstra 1972年Turing奖获得者

4、(1930-2002),带权图的最短通路算法,A. M. Turing Award,姚期智,Dijkstra,Leslie Valiant, Harvard University,Valiants greatest single contribution may be his 1984 paper A Theory of the Learnable, which laid the foundations of computational learning theory. He introduced a general framework as well as concrete computat

5、ional models for studying the learning process, including the famous probably approximately correct (PAC) model of machine learning. This has developed into a vibrant research area and has had enormous influence on machine learning, artificial intelligence, and many areas of computing practice, such

6、 as natural language processing, handwriting recognition, and computer vision.,Professor of Computer Science and Applied Mathematics School of Engineering and Applied Sciences,目录（数理逻辑）,第一章 命题演算基础 （6学时） 第二章 命题演算的推理理论（4学时） 第三章 谓词演算基础（5学时） 第四章 谓词演算的推理理论（5学时） 第五章 递归函数论（4学时）,第一章 命题演算基础,1.1 命题和联结词 1.1.1 命

7、题 1.1.2 联结词 1.1.3 合式公式 1.2 真假性 1.3 范式及其应用,(一) 命题定义,定义1： 凡是可以判断真假的陈述句称为命题。,命题可以判断真假的陈述句,非经典逻辑 不接受 排中律,例：下列句子都是命题吗？,雪是白的。 雪是黑的。 好大的雪啊！ 8大于12。 1+101=110。 ,例：下列句子都是命题吗？,上海世博会开幕时天晴 21世纪末，人类将住在月球 大于2的偶数可表示成两个素数之和（哥德巴赫猜想） XB 如果x大于3，则x2大于9。 ,例：下列句子都是命题吗？,8大于12吗？ 请勿吸烟。 姚明很帅。 南京很美。 我正在说谎 。 ,这种自指谓的语句往往会产生自相矛盾的

8、结论，即所谓的悖论,具体命题的真假问题,在数理逻辑的学习中， 不能去纠缠各种具体命题的真假问题， 而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句,公説公有理 婆説婆有理,带联结词的命题,今晚我看书。 今晚我玩网络游戏。 今晚我不看书。 今晚我不玩网络游戏。 今晚我不看书， 我玩网络游戏。 今晚我看书，或者我玩网络游戏。,否定,并且,或者,(二) 原子命题和复合命题,原子命题不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。 复合命题由原子命题利用联结词构成的命题,复合命题例子,下列命题都是复合命题，其中红字为逻辑联结词： （1）雪

9、不是白的（并非雪是白的） （2）今晚我看书或者去看电影。 （3）如果天气好，那么我去接你。 （4）偶数a是质数，当且仅当a=2（a是常数）。 （5） 2是偶数且3也是偶数。 （6）你去了学校，我去了工厂。 （省略了逻辑联结词“且”）,(三)命题变元,定义2：如果当P表示任意命题时，P称为命题变元。,字母P表示,命题具体的、特定的命题，有确定的真值,命题变元任意命题，没有确定的真值,第一章 命题演算基础,1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式 1.2 真假性 1.3 范式及其应用,五种常用的联结词,否定词 合取词 析取词 蕴含词 等价词 ,P， 非P,设

10、P是一个命题。显然，如下这句话也是命题： “P是不对的” 称之为P的否定。,P P T F F T,日常语句中有： 非， 不，并非， ,真值表,否定词的例子,例 P：上海是中国的城市。 P：上海不是中国的城市。 例 P：雪是黑色的。 P：雪不是黑色的。,否定联结词使用的原则,将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。,例 P: 这些都是学生。 P：这些不都是学生 这些都不是学生,阿契贝难题,例 下述两命题都是真命题： A: “本句是六字句” B: “本句不是六字句”,看似矛盾的根本原因，在于两个命题的前提条件是否统一的问题。,PQ， P合取Q,设P，Q是两

11、个命题。显然，如下这句话也是命题： “P并且Q” 称之为P和Q的合取。,日常语句中有： 且，与，,合取词的例子,P: 225 Q：雪是白的。 PQ：225并且雪是白的。,P:今天刮风。 Q：今天下雨。 PQ：今天刮风并且今天下雨。,PQ， P析取Q,设P,Q是两个命题。显然，如下这句话也是命题： “P或者Q” 称之为P和Q的析取。,P Q P Q T T T T F T F T T F F F,日常语言中有： 或，,析取词的例子,P: 225 Q：雪是白的。 PQ：225或者雪是白的。,P:今天刮风。 Q：今天下雨。 PQ ：今天刮风或者今天下雨。,可兼的“或”,P Q PQ T T T T

12、F T F T T F F F,他会英语或法语。 今天刮风或者今天下雨。,不可兼的“或”,P Q PQ (P Q)(PQ) T T T F T F T T F T T T F F F F,人固有一死，或重于泰山，或轻于鸿毛。 今天晚上我去看电影，或去看球赛。,异或 XOR,PQ, P蕴含Q,设P,Q是两个命题。显然，如下这句话也是命题： “如果P则Q” 称之为P蕴含Q 。,日常语言中有： 如果则, 只要就，,P Q P Q T T T T F F F T T F F T,蕴含词的例子,P：236 Q：(23)+1=6+2 PQ: 如果236，则（23）16+2,P: 天气不好 Q：我去接你 P

13、Q: 如果天气不好，那么我去接你。,注1. 前件为假时，命题为真,如果蕴含前件P是假命题，那么不管Q是什么命题，命题 “如果P则Q” 在逻辑中都被认为是真命题。 例： 如果张三能及格，那太阳从西边升起。,注2. 前件、后件可以毫不相关,在日常语言中“如果则”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。 例： P：235 Q：雪是黑色的 PQ：如果235，则雪是黑色的,注3. 充分条件、必要条件,pq为真命题的逻辑关系是： p是q的充分条件， q是p的必要条件。 “q是p的必要条件”的叙述方式还有： p仅当q（仅当q，则p） 只有q才p

14、只要p就q 除非q，否则非p（非p，除非q）,蕴含词的例子,用表示下列命题： （1）只要天下雨，我就回家。 （2）只有天下雨，我才回家。 （3）除非天下雨，否则我不回家。 （4）仅当天下雨，我才回家。 解 设p：天下雨。 q：我回家。 则（1）符号化为 pq。 （2）符号化为 qp，或： pq （3）符号化为 qp，或： pq （4）符号化为 qp，或： pq,PQ， P等价于Q,设P，Q是两个命题。显然，如下这句话也是命题： “P当且仅当Q” 称之为P等价于Q。,P Q P Q T T T T F F F T F F F T,日常语言中有： 当且仅当，,等价词的例子,P: 224 Q：雪是白

15、色的。 P Q：224当且仅当雪是白色的。,P: 225 Q：雪是黑色的。 P Q：225当且仅当雪是黑色。,等价词的例子,三角形ABC为等腰三角形当且仅当三角形ABC有两条边相等。,非复合命题的例子,（1）Tom和John是兄弟。 （2）如果x0， 则 x20。 （3）如果两个三角形全等，则它们的面积相等。 （4）一个三角形为等腰三角形当且仅当三角形有两条边相等。,未指定,注4. 充要条件,p q为真命题的逻辑关系是： p是q的充分条件， p是q的必要条件。,中学数学选修2-1：四种命题,中学数学选修2-1：充分、必要,真值函项,定义：以真假为定义域并以真假为值域的函数 称为真值函项。,需要

16、集合与映射的知识才能够讲透!,T, F,T, F,T, F,(T, T), (T,F),(F,T), (F,F),一元联结词的真值表,一元联结词有一个命题变项P，它取真和假两种，可定义四个不同的一元联结词f0，f1，f2，f3，或称为真值函项。 其真假关系可用下图表示：,P f0(P) f1(P) f2(P) f3(P) T T T F F F T F T F,永真,恒等,否定P,永假,二元联结词,P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 T T T F T T T F F F T T T T F F F F T F T

17、 T F T T F T T F F T F T F F F F T T T T F T T F T F T F F F T F F F F T T T T F T T F T F F F F F T F,f2为 蕴含,f4为 析取,f8为 等价,f11为合取,三元联结词共有多少个？,28,第一章 命题演算基础,1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式 1.2 真假性 1.3 范式及其应用,合式公式(Well formed formulae),合式公式为如下定义的式子，简称为公式： 任何命题变元均是公式； 如果P为公式，则P为公式； 如果为P，Q为公式，

18、则 PQ, PQ, PQ, PQ 为公式； 当且仅当经过有限次使用、所组成的符号串才是公式，否则不为公式 。,n 元公式,若公式中有n个不同的命题变元， 就说为n 元公式。,例 一个3元公式： （PQ）R）（PQ）,命题符号化,将复合命题符号化的步骤是 分析出简单命题，符号化 用联结词联结简单命题,提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。,例1(p5) 将下列各命题符号化: 只有努力学习、认真复习，才能取得好成绩。,解：令P表示“努力学习”； Q表示“认真复习”； R表示“取得好成绩”。 则原句译为 R（PQ）,该语句能不能译为（PQ） R？,例4(p5)已知三个命题： P：今晚我在家上网；Q：今晚我去球场看足球比赛；R：今晚我在家上网或去球场看足球比赛。试问PQ和R是否表达同一命题？请用真值表说明之。,R=(PQ)(PQ),不可兼 或,例 将下列语句形式化，并表示为命题公式：,（1）狗急跳墙。 令 p：狗急了， q