命题逻辑基本概念精.ppt

《命题逻辑基本概念精.ppt》由会员分享，可在线阅读，更多相关《命题逻辑基本概念精.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、命题逻辑基本概念第1页，本讲稿共31页本课程是现代数学的一个重要分支，是计本课程是现代数学的一个重要分支，是计算机科学基础理论的核心课程算机科学基础理论的核心课程。研究的对象是离散数据结构及相互关系。研究的对象是离散数据结构及相互关系。主要内容：数理逻辑、集合论及代数、图主要内容：数理逻辑、集合论及代数、图论和组合数学等论和组合数学等。第2页，本讲稿共31页离散数学与数学离散数学与数学连续型、离散型、随机型连续型、离散型、随机型离散数学与计算机科学离散数学与计算机科学数据结构、算法与软件理论、人工智能、数据挖掘、信数据结构、算法与软件理论、人工智能、数据挖掘、信息安全、息安全、.离散数学与我离

2、散数学与我第3页，本讲稿共31页数理逻辑数理逻辑关于逻辑的故事：关于逻辑的故事：1.上帝能否造出一块自己搬不动的石头？上帝能否造出一块自己搬不动的石头？2.理发师悖论理发师悖论3.集合论悖论集合论悖论4.第4页，本讲稿共31页什么是逻辑？什么是逻辑？研究人的思维形式和规律的学科。由研究研究人的思维形式和规律的学科。由研究对象和方法的差异可分为：对象和方法的差异可分为：1.形式逻辑形式逻辑2.数理逻辑数理逻辑3.思辨逻辑思辨逻辑第5页，本讲稿共31页什么是数理逻辑？什么是数理逻辑？字面含义：数学理论的逻辑。逻辑是研究字面含义：数学理论的逻辑。逻辑是研究演绎（推理）规律的学科。演绎（推理）规律的学

3、科。广义理解：用数学方法研究演绎规律的学广义理解：用数学方法研究演绎规律的学科。科。狭义理解：用数学方法研究数学中演绎规狭义理解：用数学方法研究数学中演绎规律和数学基础的学科。律和数学基础的学科。我们只介绍命题逻辑和一阶逻辑我们只介绍命题逻辑和一阶逻辑第6页，本讲稿共31页第一章第一章命题逻辑命题逻辑1.11.1命题与联结词命题与联结词命题与联结词命题与联结词第7页，本讲稿共31页称能判断真假而不是可真可假的陈述句为称能判断真假而不是可真可假的陈述句为命命题题。作为命题的陈述句所表达得的判断结果称为作为命题的陈述句所表达得的判断结果称为命题的命题的真值真值。真值只取两个：真值只取两个：真与假真

4、与假(T,F)。真值为真的命题称为真值为真的命题称为真命题真命题。真值为假的命题称为真值为假的命题称为假命题假命题。q感叹句、疑问句、祈使句都不能称为命题。感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不是命题。判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题陈述句中的悖论不是命题。说明说明第8页，本讲稿共31页(1)4是素数。(2)(3)x大于y。(4)充分大的偶数等于两个素数之和。(5)今天是星期二。(6)(7)请不要吸烟！(8)这朵花真美丽啊！(9)我正在说假话。例例例例 判断下列句子是否为命题。判断下列句子是否为命题。判断下列句子是否为命题。判断下列句子

5、是否为命题。(1)(1)是，假命题是，假命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况而定。是，真值根据具体情况而定。(6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，悖论不是，悖论第9页，本讲稿共31页r：充分大的偶数等于两充分大的偶数等于两个素数之和个素数之和。s：今天是星期二今天是星期二。p：4 4是素数。是素数。q：命题和真值的符号化用小写英文字母用小写英文字母p,q,r,pi,qi,ri 表示命题

6、表示命题用用“1”表示真，用表示真，用“0”表示假表示假不能被分解成更简单的陈述句，称这样的命题不能被分解成更简单的陈述句，称这样的命题为为简单简单命题或原子命题命题或原子命题。由简单陈述句通过联结词而成的陈述句，称这样的命由简单陈述句通过联结词而成的陈述句，称这样的命题为题为复合命题复合命题。第10页，本讲稿共31页 命题常元命题常元命题常元命题常元我们把表示具体命题及表示常命题的我们把表示具体命题及表示常命题的p，q，r，s等与等与1，0统称为统称为命题常元命题常元命题常元命题常元。命题变元命题变元命题变元命题变元是以是以“真、假真、假”或或“1，0”为取值范围的变元，它未指为取值范围的变

7、元，它未指出符号所表示的具体命题，可以代表任意命题。出符号所表示的具体命题，可以代表任意命题。指派指派当命题变元用一个特定命题取代时，该命题变元才能有确当命题变元用一个特定命题取代时，该命题变元才能有确定的真值，从而成为一个命题。称对命题变元进行指派。定的真值，从而成为一个命题。称对命题变元进行指派。第11页，本讲稿共31页数理逻辑研究方法的主要特征是将论述或推数理逻辑研究方法的主要特征是将论述或推理中的理中的各种要素都符号化各种要素都符号化。即构造各种符号。即构造各种符号语言来代替自然语言。语言来代替自然语言。将联结词（将联结词（connective）符号化，消除其二义）符号化，消除其二义性

8、，对其进行严格定义。性，对其进行严格定义。例如：例如：他学过英语或法语他学过英语或法语。鱼香肉丝或西红柿炒鸡蛋，加一碗汤。鱼香肉丝或西红柿炒鸡蛋，加一碗汤。第12页，本讲稿共31页定义定义1.1否定(NOT)设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作p，符号称作否定联结词，并规定p为真当且仅当p为假。例如：p：哈尔滨是一个大城市。p：哈尔滨是一个不大城市。p：哈尔滨不是一个大城市。pp1001第13页，本讲稿共31页定义定义定义定义1.21.2合取合取(AND)(AND)设p,q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词，

9、并规定pq为真当且仅当p与q同时为真（遇假则假）。使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性。描述合取式的灵活性与多样性。自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一面一面”等联结词都可以符号化为等联结词都可以符号化为。2)2)分清简单命题与复合命题。分清简单命题与复合命题。不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词。pqpq1 11 11 11 10 00 00 01 10 00 000 0第14页，本讲稿共31页例例将下列命题符号化(1)吴颖既用功又聪明。(2)吴颖不仅用

10、功而且聪明。(3)吴颖虽然聪明，但不用功。(4)张辉与王丽都是三好学生。(5)张辉与王丽是同学。p:p:吴颖用功。吴颖用功。q:q:吴颖聪明。吴颖聪明。r:r:张辉是三好学生张辉是三好学生。s:s:王丽是三好学生王丽是三好学生。t:t:张辉与王丽是同学张辉与王丽是同学。(1)pq(1)pq(2)pq(2)pq(3)qp(3)qp(4)rs(4)rs(5)t(5)t解题要点：解题要点：正确理解命题含义。正确理解命题含义。找出原子命题并符号化。找出原子命题并符号化。选择恰当的联结词。选择恰当的联结词。第15页，本讲稿共31页合取举例p：我们去看电影。q：房间里有十张桌子。pq：我们去看电影并且房间

11、里有十张桌子。在数理逻辑中，关心的只是复合命题与构成复合命题在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容并不关心各语句的具体内容(与语义无关与语义无关)。说明说明第16页，本讲稿共31页定义定义1.3析取(OR)设p，q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假（遇真为真）。自然语言中的自然语言中的“或或”具有二义性，用它联结的命题有具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称时

12、具有相容性，有时具有排斥性，对应的联结词分别称为相容或为相容或和排斥或排斥或(排异或排异或)。说明说明pqpq1 11 11 11 10 01 10 01 11 10 000 0第17页，本讲稿共31页例例 将下列命题符号化将下列命题符号化(1)张晓静爱唱歌或爱听音乐。张晓静爱唱歌或爱听音乐。(2)张晓静只能挑选张晓静只能挑选202或或203房间。房间。(3)张晓静是江西人或安徽人。张晓静是江西人或安徽人。(4)他昨天做了二十或三十道习题。他昨天做了二十或三十道习题。(1)(1)设设 p p：张晓静爱唱歌，：张晓静爱唱歌，q q：张晓静爱听音乐。：张晓静爱听音乐。相容或，符号化为相容或，符号化

13、为 p pq q(2)(2)设设t t：张晓静挑选：张晓静挑选202202房间，房间，u u：张晓静挑选：张晓静挑选203203房间。房间。排斥或，符号化为：排斥或，符号化为：(t tu u)()(t tu u)(3)(3)设设r r：张晓静是江西人，：张晓静是江西人，s s：张晓静是安徽人。：张晓静是安徽人。排斥或，符号化为：排斥或，符号化为：r rs s。(排斥或排斥或联结的两个命题事实上不可能同时为真联结的两个命题事实上不可能同时为真)或符号化为：或符号化为：(rs)(rs)(rs)(rs)(4)(4)原子命题，因为原子命题，因为“或或”只表示了习题的近似数目。只表示了习题的近似数目。第

14、18页，本讲稿共31页定义定义定义定义1.41.4蕴涵蕴涵设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词,并规定pq为假当且仅当p为真q为假。说明说明pq的逻辑关系表示的逻辑关系表示q是是p的必要条件。的必要条件。q是是p的必要条件有许多不同的叙述方式的必要条件有许多不同的叙述方式只要只要p，就，就q因为因为p，所以，所以q p仅当仅当q 只有只有q才才p 除非除非q才才p 除非除非q，否则非，否则非ppqp q1 11 11 11 10 00 00 01 11 10 001 1第19页，本讲稿共31页例例 将下列

15、命题符号化，并指出其真值将下列命题符号化，并指出其真值(1)如果3+36，则雪是白的。(2)如果3+36，则雪是白的。(3)如果3+36，则雪不是白的。(4)如果3+36，则雪不是白的。解：令解：令p p：3+33+36 6，p p的真值为的真值为1 1。q q：雪是白色的，：雪是白色的，q q的真值也为的真值也为1 1。（1）pq 1 （2）pq 1（3）pq 0 （4）pq 1第20页，本讲稿共31页以下命题中出现的a是一个给定的正整数：(5)只要a能被4整除，则a一定能被2整除。(6)a能被4整除，仅当a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否则a不

16、能被4整除。(9)只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。解：解：令令r r：a a能被能被4 4整除整除 s s：a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题均叙述的是五个命题均叙述的是a a能被能被2 2整除是整除是a a能被能被4 4整除的必要条件，因整除的必要条件，因而都符号化为而都符号化为r rs s。其真值为。其真值为1 1。在在(10)(10)中，将中，将a a能被能被4 4整除看成了整除看成了a a能被能被2 2整除的必要条件，因而应符号化整除的必要条件，因而应符号化为为s sr r。a a值不定时，真值未知。值不定时，

17、真值未知。第21页，本讲稿共31页关于蕴含的进一步说明关于蕴含的进一步说明作为一种规定，当作为一种规定，当p为假时，无论为假时，无论q是真是假，是真是假，pq均为均为真。也就是说，只有真。也就是说，只有p为真为真q为假这一种情况使得复合为假这一种情况使得复合命题命题pq为假。为假。例：如果例：如果x5，则，则x2。(1)x=6x=6如果如果6565，则则6262。(2)(2)x=3x=3 如果如果3535，则则3232。(3)x=1(3)x=1 如果如果1515，则则1212。例：如果我有车，那么我去接你例：如果我有车，那么我去接你常出现的错误，没有分清充分条件与必要条件。常出现的错误，没有分

18、清充分条件与必要条件。第22页，本讲稿共31页定义定义定义定义1.51.5等价等价等价等价设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词，并规定pq为真当且仅当p与q同时为真或同时为假。说明说明“当且仅当当且仅当”（if and only if）p pq q的的逻辑逻辑关系关系为为p p与与q q互互为为充分必要条件。充分必要条件。(pq)(qp)(pq)(qp)与与p pq q的的逻辑逻辑关系完全一致。关系完全一致。pqp q1 11 11 11 10 00 00 01 10 00 001 1第23页，本讲稿共31页例例 将下列命题符号化，并讨论它们的

19、真值将下列命题符号化，并讨论它们的真值(1)是无理数当且仅当加拿大位于亚洲。(2)2+35的充要条件是是无理数。(3)若两圆A，B的面积相等，则它们的半径相等；反之亦然。(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。(1)(1)设设 p p：是无理数，是无理数，q q：加拿大位于亚洲。：加拿大位于亚洲。符号化为符号化为 p pq q，真值为，真值为0 0。(2)(2)设设 p p：2+32+35 5，q q：是无理数。是无理数。符号化为符号化为 p pq q，真值为，真值为1 1。(3)(3)设设 p p：两圆：两圆A A，B B的面积相等，的面积相等，q q：两圆：两圆

20、A A，B B的半径相等。的半径相等。符号化为符号化为 p pq q，真值为，真值为1 1。(4)(4)设设 p p：王小红心情愉快，：王小红心情愉快，q q：王小红唱歌。：王小红唱歌。符号化为符号化为 p pq q，真值由具体情况而定。，真值由具体情况而定。第24页，本讲稿共31页关于基本联结词的说明关于基本联结词的说明,，称为一个联结词集。，称为一个联结词集。由联结词集由联结词集,中的一个联结词联结一个或两个中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它原子命题组成的复合命题是最简单的复合命题，可以称它们为们为基本的复合命题基本的复合命题。基本复合命题的真值

21、见下表：基本复合命题的真值见下表：第25页，本讲稿共31页多次使用联结词集中的联结词，可以组成更为复杂的复合多次使用联结词集中的联结词，可以组成更为复杂的复合命题。命题。求复杂复合命题的真值时，除依据上表外，还要规定联结求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。词的优先顺序，将括号也算在内。本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：()，对于同一优先级的联结词，先出现者先运算。，对于同一优先级的联结词，先出现者先运算。第26页，本讲稿共31页例例:令令p：北京比天津人口多。：北京比天津人口多。q：2+24.r：乌鸦是白色的。：乌鸦是白色的。求

22、下列复合命题的真值：求下列复合命题的真值：(1)(p q)(p q)r(2)(q r)(pr)(3)(p r)(p r)解：解：p p、q q、r r的真值分别为的真值分别为1 1、1 1、0 0(1)1(1)1(2)1(2)1(3)0(3)0我们关心的是复合命题中命题之间的真值关系，而不我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。关心命题的内容。说明说明第27页，本讲稿共31页例题：命题符号化例题：命题符号化(1)我和他既是兄弟又是同学我和他既是兄弟又是同学p：我和他是兄弟，：我和他是兄弟，q：我和他是同学。：我和他是同学。故命题可符号化为：故命题可符号化为：p q。(2)

23、张三或李四都可以做这件事。张三或李四都可以做这件事。p：张三可以做这件事。：张三可以做这件事。q：李四可以做这件事。：李四可以做这件事。故命题可符号化为：故命题可符号化为：p q。(3)仅当我有时间且天不下雨，我将去镇上。仅当我有时间且天不下雨，我将去镇上。对于对于“仅当仅当”，实质上是，实质上是“当当”的逆命题。的逆命题。“当当A则则B”是是AB，而，而“仅当仅当A则则B”是是BA。p：我有时间。：我有时间。q：天不下雨。：天不下雨。r：我将去镇上。：我将去镇上。故命题可符号化为：故命题可符号化为：r(p q)。第28页，本讲稿共31页(4)(4)张刚总是在图书馆看书，除非图书馆不开门或张刚

24、生病。张刚总是在图书馆看书，除非图书馆不开门或张刚生病。p：张刚在图书馆看书，：张刚在图书馆看书，q：图书馆不开门，：图书馆不开门，r：张刚生病。：张刚生病。故命题可符号化为：故命题可符号化为：(q r)p。(5)风雨无阻，我去上学。风雨无阻，我去上学。可理解为可理解为“不管是否刮风、是否下雨，我都去上学不管是否刮风、是否下雨，我都去上学”。p：天刮风，：天刮风，q：天下雨，：天下雨，r：我去上学。：我去上学。故命题可符号化为：故命题可符号化为：(p qr)(p qr)(p qr)(p qr)或或(p q r)(p q r)(p q r)(p q r)理解为理解为“四种情况必居其一四种情况必居

25、其一,而每种情况下我都去上学而每种情况下我都去上学”第29页，本讲稿共31页命题符号化的要点命题符号化的要点要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。要要选选用用恰恰当当的的联联结结词词，尤尤其其要要善善于于识识别别自自然然语言中的联结词（有时它们被省略）。语言中的联结词（有时它们被省略）。否定词的位置要放准确。否定词的位置要放准确。需需要要的的括括号号不不能能省省略略，而而可可以以省省略略的的括括号号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。要注意的是要注意的是,语句的形式化未必是唯一的。语句的形式化未必是唯一的。第30页，本讲稿共31页课后作业：课后作业：P.32-331.3,1.5，1.6（1）（）（3）第31页，本讲稿共31页