《命题逻辑基本概念课件.ppt》由会员分享，可在线阅读，更多相关《命题逻辑基本概念课件.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1第第1 1章章 命题逻辑基本概念命题逻辑基本概念离散数学离散数学 2第一次课程说明第一次课程说明第一次课程说明第一次课程说明q本书的主要内容本书的主要内容数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论 3第一次课程说明第一次课程说明第一次课程说明第一次课程说明q数理逻辑数理逻辑:数理逻辑是研究推理逻辑规则的一个数学分支，它采数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性进而讨论推理体系的一致性、可靠性和完备（全）性等。数理逻辑的研究内容是两个演
2、算加四论，具体为等。数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算、集合论、模型论、递归论和证命题演算、谓词演算、集合论、模型论、递归论和证明论。数理逻辑是形式逻辑与数学相结合的产物。但明论。数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究的是各学科（包括数学）共同遵从的一数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。般性的逻辑规律，而各门学科只研究自身的具体规律。q本章是后续各章的准备或前提本章是后续各章的准备或前提 41.1 命题与联结词q数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理。q推理的推理的前提前提和和结
3、论结论都是都是表达判断表达判断的的陈述句陈述句。q表达判断的陈述句构成了推理的表达判断的陈述句构成了推理的基本单位基本单位。51.1 1.1 命题与联结词命题与联结词q称非真即假的陈述句为称非真即假的陈述句为命题命题（proposition）。q作为命题的陈述句所表达得的判断结果称为命题的作为命题的陈述句所表达得的判断结果称为命题的真值真值。q真值只取两个：真值只取两个：真与假真与假。q真值为真的命题称为真值为真的命题称为真命题真命题。q真值为假的命题称为真值为假的命题称为假命题假命题。q感叹句、疑问句、祈使句都不能称为命题。感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不
4、是命题。判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题陈述句中的悖论不是命题。说明说明 6(1)(1)4 4是素数。是素数。(2)(2)(3)(3)x x大于大于y y。(4)(4)充分大的偶数等于两个素充分大的偶数等于两个素数之和。数之和。(5)(5)今天是星期二。今天是星期二。(6)(6)(7)(7)请不要吸烟！请不要吸烟！(8)(8)这朵花真美丽啊！这朵花真美丽啊！(9)(9)我正在说假话。我正在说假话。例例1.11.1 判断下列句子是否为命题。判断下列句子是否为命题。(1)(1)是，假命题是，假命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定
5、的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况是，真值根据具体情况而定。而定。(6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，悖论不是，悖论 7命题和真值的符号化命题和真值的符号化q用小写英文字母p,q,r,pi,qi,ri 表示命题q用“1”表示真，用“0”表示假 r：充分大的偶数等于两充分大的偶数等于两个素数之和个素数之和。s：今天是星期二今天是星期二。p：4 4是素数。是素数。q：q不能被分解成更简单的陈述句，称这样的命不能被分解成更简单的陈述句，称这样的命题为题为简单命题简
6、单命题或或原子命题原子命题。q由简单陈述句通过联结词而成的陈述句，称由简单陈述句通过联结词而成的陈述句，称这样的命题为这样的命题为复合命题复合命题。8例例1.21.2将下面这段陈述中所出现的原子命题符号化，并指出它将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。们的真值，然后再写出这段陈述。是是有有理理数数是是不不对对的的；2 2是是偶偶素素数数；2 2或或4 4是是素素数数；如如果果2 2是素数，则是素数，则3 3也是素数；也是素数；2 2是素数当且仅当是素数当且仅当3 3也是素数。也是素数。p：是有理数是有理数q：2 2是素数；是素数；r：2 2是偶数是偶数s
7、 s：3 3是素数；是素数；t：4 4是素数是素数0111 10非非p；q并且并且(与与)r；q或或t t；如果如果q，则则s；q当且仅当当且仅当s。9例例例例1.21.21.21.2的讨论的讨论的讨论的讨论q半形式化形式半形式化形式q数理逻辑研究方法的主要特征是将论述或推理中的数理逻辑研究方法的主要特征是将论述或推理中的各种要素各种要素都符号化都符号化。即构造各种符号语言来代替自然语言。即构造各种符号语言来代替自然语言。为达到这。为达到这一目的一目的,引入形式化语言引入形式化语言.q形式化语言形式化语言：完全由符号所构成的语言。完全由符号所构成的语言。q将联结词（将联结词（connectiv
8、e）符号化，消除其二义）符号化，消除其二义性，对其进行严格定义。性，对其进行严格定义。q例如：例如：他他是是100100米或米或400400米赛跑的冠军。米赛跑的冠军。鱼香肉丝或锅包肉，加一碗汤。鱼香肉丝或锅包肉，加一碗汤。10定义1.1 否定否定(negation)q设设p为命题，复合命题为命题，复合命题“非非p”(”(或或“p的否定的否定”)”)称为称为p的否定式的否定式,记作记作p，符号符号称作称作否定联结词否定联结词，并规定，并规定p为真当且仅当为真当且仅当p为假为假。例如例如：p：哈尔滨哈尔滨是一个大城市是一个大城市。p：哈尔滨是一个不大城市。哈尔滨是一个不大城市。p：哈尔滨不是一个
9、大城市。哈尔滨不是一个大城市。pp1001 11定义定义1.21.2 合取合取合取合取(conjunctionconjunction)q设设p,qp,q为二命题，复合命题为二命题，复合命题“p p并且并且q”(q”(或或“p p与与q”)q”)称为称为p p与与q q的的合取式合取式，记作，记作pqpq，称称作作合取联结词合取联结词，并规定，并规定pqpq为为真当且仅当真当且仅当p p与与q q同时为真同时为真。使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性。描述合取式的灵活性与多样性。自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、
10、“虽然虽然但是但是”、“一面一面一面一面”等联结词都等联结词都可以符号化为可以符号化为。2)2)分清简单命题与复合命题。分清简单命题与复合命题。不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词。pqpq1 1 1 11 11 10 00 00 01 10 00 000 0 12例1.3 将下列命题符号化将下列命题符号化(1)(1)吴颖既用功又聪明。吴颖既用功又聪明。(2)(2)吴颖不仅用功而且聪明。吴颖不仅用功而且聪明。(3)(3)吴颖虽然聪明，但不用功。吴颖虽然聪明，但不用功。(4)(4)张辉与王丽都是三好学生。张辉与王丽都是三好学生。(5)(5)张辉与王丽是同学。张辉与王丽是同
11、学。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解题要点：解题要点：正确理解命题含义。正确理解命题含义。找出原子命题并符号化。找出原子命题并符号化。选择恰当的联结词。选择恰当的联结词。13合取举例合取举例qp：我们去看电影。我们去看电影。q：房间里有十张桌子。房间里有十张桌子。pq：我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。在数理逻辑中，关
12、心的只是复合命题与构成复合在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容辑关系，并不关心各语句的具体内容。说明说明 14定义1.3 析取析取(disjunction)q设设p p，q q为二命题，复合命题为二命题，复合命题“p p或或q q”称作称作p p与与q q的的析取式析取式，记作，记作p pq q，称作称作析取联结词析取联结词，并，并规定规定p pq q为假当且仅当为假当且仅当p p与与q q同同时为假时为假。自然语言中的自然语言中的“或或”具有二义性，用它联结的命具有二义性
13、，用它联结的命题有时具有相容性，有时具有排斥性，对应的联题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或结词分别称为相容或和排斥或排斥或(排异或排异或)。说明说明pqpq1 1 1 11 11 10 01 10 01 11 10 000 0 15例例1.4 1.4 将下列命题符号化将下列命题符号化 (1)(1)张晓静爱唱歌或爱听音乐。张晓静爱唱歌或爱听音乐。(2)(2)张晓静只能挑选张晓静只能挑选202202或或203203房间。房间。(3)(3)张晓静是江西人或安徽人。张晓静是江西人或安徽人。(4)(4)他昨天做了二十或三十道习题。他昨天做了二十或三十道习题。(1)(1)设设 p
14、 p：张晓静爱唱歌，张晓静爱唱歌，q q：张晓静爱听音乐。张晓静爱听音乐。相容或，符号化为相容或，符号化为 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
15、)(4)原子命题，因为原子命题，因为“或或”只表示了习题的近似数目只表示了习题的近似数目。16定义定义1.41.4 蕴涵蕴涵蕴涵蕴涵(implicationimplication)q设设p p，q q为二命题，复合命题为二命题，复合命题“如果如果p p，则则q q”称作称作p p与与q q的的蕴涵式蕴涵式，记作，记作p pq q，并称并称p p是蕴涵式的是蕴涵式的前件前件，q q为蕴涵式的为蕴涵式的后件后件，称作称作蕴涵联结词蕴涵联结词,并规定并规定p pq q为假当且仅当为假当且仅当p p为真为真q q为假为假。说明说明qpq的逻辑关系表示的逻辑关系表示q是是p的必要条件。的必要条件。qq是
16、是p的必要条件有许多不同的叙述方式的必要条件有许多不同的叙述方式只要只要p，就就q因为因为p，所以所以qp仅当仅当q只有只有q才才p除非除非q才才p除非除非q，否则非否则非ppqp q1 1 1 11 11 10 00 00 01 11 10 001 1 17例例例例1.5 1.5 1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 (1)(1)如果如果3+33+36 6，则雪是白的。，则雪是白的。(2)(2)如果如果3+363+36，则雪是白的。，则雪是白的。(3)(3)如果如果3+33+36 6，则雪不是
17、白的。，则雪不是白的。(4)(4)如果如果3+363+36，则雪不是白的。，则雪不是白的。解：令解：令p p：3+33+36 6，p p的真值为的真值为1 1。q q：雪是白色的，雪是白色的，q q的真值也为的真值也为1 1。(1)pq(2)(2)pq(3)pq(4)(4)pq1101 18例例例例1.5 1.5 1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 以下命题中出现的以下命题中出现的a a是一个给定的正整数：是一个给定的正整数：(5)(5)只要只要a a能被能被4 4整除，则整除，则a a一定能
18、被一定能被2 2整除。整除。(6)(6)a a能被能被4 4整除，仅当整除，仅当a a能被能被2 2整除。整除。(7)(7)除非除非a a能被能被2 2整除，整除，a a才能被才能被4 4整除。整除。(8)(8)除非除非a a能被能被2 2整除，否则整除，否则a a不能被不能被4 4整除。整除。(9)(9)只有只有a a能被能被2 2整除，整除，a a才能被才能被4 4整除。整除。(10)(10)只有只有a a能被能被4 4整除，整除，a a才能被才能被2 2整除。整除。解：解：令令r r：a a能被能被4 4整除整除 s s：a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题
19、均叙述的是五个命题均叙述的是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值不定时，真值未知。值不定时，真值未知。19关于蕴含的进一步说明关于蕴含的进一步说明q作为一种规定，当作为一种规定，当p p为假时，无论为假时，无论q q是真是假，是真是假，p pq q均为真。均为真。也就是说，只有也就是说，只有p p为真为真q q为
20、假这一种情况使得复合命题为假这一种情况使得复合命题p pq q为假。称为为假。称为实质蕴含实质蕴含。q例：如果例：如果x5x5，则则x2x2。(1)(1)x=6x=6如果如果6565，则则6262。(2)(2)x=3x=3 如果如果3535，则则3232。(3)(3)x=1 x=1 如果如果1515，则则1212。q例：如果我有车，那么我去接你例：如果我有车，那么我去接你 q常出现的错误，没有分清充分条件与必要条件。常出现的错误，没有分清充分条件与必要条件。20定义定义1.51.5 等价等价等价等价(two-way-implicationtwo-way-implication)q设设p p，q
21、 q为二命题，复合命题为二命题，复合命题“p p当且仅当当且仅当q q”称作称作p p与与q q的的等价式等价式，记作记作p pq q，称作称作等价联结词等价联结词，并规定并规定p pq q为真当且仅当为真当且仅当p p与与q q同同时为真或同时为假时为真或同时为假。说明说明q“当且仅当当且仅当”（if and only if）qp pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件。互为充分必要条件。q(pq)(qp)pq)(qp)与与p pq q的逻辑关系完全一致。的逻辑关系完全一致。pqp q1 1 1 11 11 10 00 00 01 10 00 001 1 21例例例
22、例1.6 1.6 1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值 (1)(1)是无理数当且仅当加拿大位于亚洲。是无理数当且仅当加拿大位于亚洲。(2)(2)2+32+35 5的充要条件是的充要条件是是无理数。是无理数。(3)(3)若两圆若两圆A A，B B的面积相等，则它们的半径相等；反之亦然。的面积相等，则它们的半径相等；反之亦然。(4)(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。(1)(1)设设 p p：
23、是无理数是无理数，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：两圆两圆A A，B B的半径相等的半径相等。符号化为符号化为 p pq q，真值为真值为1 1。(4)(4)设设 p p：王小红心情愉快王小红心情愉快，q q：王小红唱歌王小红唱歌。符号化为符号化为 p pq q，真值由具体情况而定。真值由具体情况而定。22关于基本联结词的说明关于基本联结
24、词的说明q,，称为一个联结词集。，称为一个联结词集。q由联结词集由联结词集,中的一个联结词联结一个或中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以两个原子命题组成的复合命题是最简单的复合命题，可以称它们为称它们为基本的复合命题基本的复合命题。q基本复合命题的真值见下表：基本复合命题的真值见下表：23关于基本联结词的说明关于基本联结词的说明q多次使用联结词集中的联结词，可以组成更为复杂的复合多次使用联结词集中的联结词，可以组成更为复杂的复合命题。命题。q求复杂复合命题的真值时，除依据上表外，还要规定联结求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将
25、括号也算在内。词的优先顺序，将括号也算在内。q本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：()()，对于同一优先级的联结词，先出现者先运算。，对于同一优先级的联结词，先出现者先运算。24例例1.71.7令令 p p：北京比天津人口多。北京比天津人口多。q q：2+22+24.4.r r：乌鸦是白色的。乌鸦是白色的。求下列复合命题的真值：求下列复合命题的真值：(1)(1)(pq)(pq)r pq)(pq)r(2)(qr)(pr)(2)(qr)(pr)(3)(pr)(3)(pr)(pr)(pr)解：解：p p、q q、r r的真值分别为的真值分别为1 1、1 1、0 0 (1)1(1)1(2)1(2)1(3)0(3)0我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。说明说明