离散数学命题与联结词

1、1数理逻辑部分数理逻辑部分n第一章第一章 命题逻辑命题逻辑n第二章第二章 一阶逻辑一阶逻辑2第一章第一章 命题逻辑命题逻辑 逻辑逻辑：研究推理，关注推理的正确性：研究推理，关注推理的正确性数学上，数学上，证明定理；证明定理；计算机科学中，计算机科学中，证明程序实现了要求它完成的任务。证明程序实现了要求它完成的任务。逻辑重点研究逻辑重点研究命题之间的关系命题之间的关系，而不是一个具体命，而不是一个具体命题内容在自然语言中的意义题内容在自然语言中的意义. .3例如，例如，软工专业的学生都喜欢看宫廷剧软工专业的学生都喜欢看宫廷剧延禧攻略延禧攻略. .任何一个喜欢看任何一个喜欢看延禧攻略延禧攻略的学生

2、都是软工的学生都是软工17011701班的班的. .软工专业的学生都是软工软工专业的学生都是软工17011701班的班的. .真真真真真真从逻辑的角度从逻辑的角度从语义的角度从语义的角度假假41.1 1.1 命题与联结词命题与联结词1.2 1.2 命题公式与赋值命题公式与赋值1.3 1.3 等值演算等值演算1.4 1.4 析取范式与合取范式析取范式与合取范式1.5 1.5 命题逻辑的推理理论命题逻辑的推理理论本章内容本章内容51.1 1.1 命题与联结词命题与联结词 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 6命题与真值命题与

3、真值 命题命题: : 判断结果惟一的陈述句判断结果惟一的陈述句. .命题的真值命题的真值: : 判断的结果判断的结果. .真值的取值真值的取值: : 真与假真与假. .真命题真命题: : 真值为真的命题真值为真的命题. .假命题假命题: : 真值为假的命题真值为假的命题. . 感叹句、祈使句、疑问句都不是命题！感叹句、祈使句、疑问句都不是命题！陈述句中的陈述句中的悖论悖论 以及判断结果不惟一确定的也以及判断结果不惟一确定的也不是命题！不是命题！ 注意注意: 理发师悖论理发师悖论 7理发师悖论：理发师悖论： 在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将

4、为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。 8 例例1.1 1.1 下列句子中哪些是命题？下列句子中哪些是命题？ (1) (1) 是无理数是无理数. . (2) 2 + 5 (2) 2 + 5 8.8. (3) (3) x + 5 + 5 3.3. (4) (4) 你有铅

5、笔吗？你有铅笔吗？ (5) (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) (6) 请不要讲话！请不要讲话！ (7) (7) 我正在说谎话我正在说谎话. .真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(3)(7)(7)都不是命题都不是命题29命题的分类命题的分类 简单命题简单命题( (原子命题原子命题) )： 简单陈述句构成的命题简单陈述句构成的命题. . 复合命题复合命题： 由简单命题与联结词按一定规则复合由简单命题与联结词按一定规则复合 而成的命题而成的命题. . 10例如例如 p ： 是有理数，则是有理数，则 p 的真值为的真值

6、为 用小写英文字母用小写英文字母 p, q, r, , pi , qi , ri (i1）表表示简单命题，示简单命题，简单命题符号化简单命题符号化 2用用“1 1”表示真，用表示真，用“0 0”表示假表示假. .1 1q ：2 + 5 = 72 + 5 = 7，则，则 q 的真值为的真值为0 011联结词与复合命题联结词与复合命题 1.1.否定式与否定联结词否定式与否定联结词“ ”定义定义 设设p为命题，复合命题为命题，复合命题 “非非p”（或（或 “p的的否定否定”）称为）称为p的的否定式否定式，记作，记作 p，符号，符号 称称作作否定联结词否定联结词，并规定，并规定 p 为真当且仅当为真当

7、且仅当p为为假假. .例如：例如：p：1010是素数，则是素数，则 p：1010不是素数不是素数. .122. 2. 合取式与合取联结词合取式与合取联结词“” 定义定义 设设p, q为二命题为二命题, ,复合命题复合命题“p并且并且q ”( (或或“p与与q ”) )称为称为p与与q 的的合取式合取式，记作，记作pq，称称作作合取联结词合取联结词，并规定，并规定 pq为真当且仅当为真当且仅当p 与与 q 同时为真同时为真. .描述合取式的灵活性与多样性，描述合取式的灵活性与多样性， 分清简单命题与复合命题分清简单命题与复合命题. .注意注意:13 例例1.3 1.3 将下列命题符号化将下列命题

8、符号化. . (1) (1)丁楠丁楠既既聪明聪明又又用功用功. . (2) (2)丁楠丁楠不仅不仅聪明，聪明，而且而且用功用功. . (3) (3)丁楠丁楠虽然虽然聪明，聪明，但但不用功不用功. . (4) (4)丁楠丁楠不是不是不聪明，不聪明，而是而是不用功不用功. . (5) (5)凌道恒凌道恒与与鞠奕明都是三好学生鞠奕明都是三好学生. . (6) (6)凌道恒凌道恒与与鞠奕明是同学鞠奕明是同学. .解：令解：令 p ：丁楠聪明，：丁楠聪明，q ：丁楠用功，则：丁楠用功，则 (1) (1) pq (2)(2) pq (3)(3) p q (4)(4) ( )p( q). . 14 例例1.

9、3(1.3(续续) ) 令令 r : :凌道恒是三好学生，凌道恒是三好学生，s : :鞠奕明是三好学生鞠奕明是三好学生(5) (5) rs. .(6) (6) 令令t : :凌道恒与鞠奕明是同学，凌道恒与鞠奕明是同学，t 是简单命题是简单命题 . .( (1)1)(5)(5)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性. .(6)(6)中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(6)(6)中中句句子是简单命题子是简单命题. .说明说明15定义定义 设设p, q为二命题，复合命题为二命题，复合命题“p或或q”称作称作p与与q 的的析取式析取式，记作，记作

10、pq，称作称作析取联结析取联结词词，并规定，并规定pq为假当且仅当为假当且仅当p与与q同时为假同时为假. .例例1.41.4 将下列命题符号化将下列命题符号化: :(1) 2(1) 2或或4 4是素数；是素数；(2) 2(2) 2或或3 3是素数；是素数；(3) 4(3) 4或或6 6是素数；是素数；(4) (4) 小元元只能拿一个苹果或一个梨；小元元只能拿一个苹果或一个梨；(5) (5) 王晓红生于王晓红生于19891989年或年或19901990年年. . 3. 3. 析取式与析取联结词析取式与析取联结词“”16解：令解：令p :2:2是素数是素数, , q :3:3是素数是素数, , r

11、 :4:4是素数是素数, , s :6:6是素数是素数, ,则则(1),(2),(3)(1),(2),(3)均为均为相容或相容或. .分别符号化为分别符号化为: : pr, , pq, rs, , 它们的真值分别它们的真值分别为为 1, 1, 0.1, 1, 0.而而 (4), (5)(4), (5)为为排斥或排斥或. .令令 t : :小元元拿一个苹果，小元元拿一个苹果，u : :小元元拿一个梨，小元元拿一个梨，则则(4)(4)符号化为符号化为(t u) ( tu).令令v : :王晓红生于王晓红生于19891989年年, ,w : :王晓红生于王晓红生于19901990年年, ,则则(5)

12、(5)既可符号化为既可符号化为 ( (v w)()( vw), ), 又可符号又可符号化为化为 vw , , WhyWhy? ? 17定义定义 设设p, q为二命题，复合命题为二命题，复合命题“如果如果p, ,则则q”称作称作p与与q的的蕴涵式蕴涵式，记作，记作p q，并称，并称p是蕴涵是蕴涵式的式的前件前件，q为蕴涵式的为蕴涵式的后件后件. . 称作称作蕴涵联结蕴涵联结词词，并规定，并规定，p q为假当且仅当为假当且仅当p为真为真q为假为假. .4. 4. 蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”18p q 的逻辑关系：的逻辑关系：q 为为 p 的必要条件的必要条件“如果如果 p，则则 q”

13、的不同表述法很多：的不同表述法很多： 若若 p，就就 q 只要只要 p，就就 q p 仅当仅当 q 只有只有 q 才才 p 除非除非 q, , 才才 p 或或 除非除非 q, , 否则非否则非 p，当当p为假时，为假时，p q为真为真常出现的错误：常出现的错误：分不清充分条件与必要条件！分不清充分条件与必要条件！19例例1.5 1.5 设设 p : :天冷，天冷，q : :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) (1) 只要只要天冷，小王天冷，小王就就穿羽绒服穿羽绒服. .(2) (2) 因为因为天冷，天冷，所以所以小王穿羽绒服小王穿羽绒服. .(3) (3)

14、若若小王不穿羽绒服，小王不穿羽绒服，则则天不冷天不冷. .(4) (4) 只有只有天冷，小王天冷，小王才才穿羽绒服穿羽绒服. .(5) (5) 除非除非天冷，小王天冷，小王才才穿羽绒服穿羽绒服. .(6) (6) 除非除非小王穿羽绒服，小王穿羽绒服，否则否则天不冷天不冷. .(7) (7) 如果如果天不冷，天不冷，则则小王不穿羽绒服小王不穿羽绒服. .(8) (8) 小王穿羽绒服小王穿羽绒服仅当仅当天冷的时候天冷的时候. . 注意注意：p q 与与 qp 等值（真值相同）等值（真值相同） pqpq q qp ppqqp qp p qqp20定义定义 设设p，q为二命题，复合命题为二命题，复合命

15、题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联等价联结词结词. .并规定并规定pq为真当且仅当为真当且仅当p与与q同时为真或同时为真或同时为假同时为假. .5. 5. 等价式与等价联结词等价式与等价联结词“”说明说明: :(1) (1) p q 的逻辑关系的逻辑关系: :p与与q互为充分必要条件互为充分必要条件, ,(2) (2) p q为真当且仅当为真当且仅当p与与q同真或同假同真或同假. .21例例1.6 1.6 求下列复合命题的真值求下列复合命题的真值(1) 2+2(1) 2+24 4 当且仅当当且仅当 3+33+36.6.(2) 2+2(2)

16、 2+24 4 当且仅当当且仅当 3 3是偶数是偶数. .(3) 2+2(3) 2+24 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. .(4) 2+2(4) 2+24 4 当且仅当当且仅当 美国位于非洲美国位于非洲. .(5) (5) 函数函数 f( (x) )在在x0 0可导的充要条件是可导的充要条件是 它在它在x0 0连续连续. .1 10 01 10 00 022以上给出了以上给出了5 5个联结词：个联结词： , , , , , , , , ，组成，组成一个联结词集合一个联结词集合 , , , , , , , , ，联结词的联结词的优先顺序优先顺序为：为： , , , , ,

17、, , , ; ; 如果出现的联结词同级，又无括号时，则按如果出现的联结词同级，又无括号时，则按从左从左到右到右的顺序运算的顺序运算; ; 若遇有括号时，应该先进行括若遇有括号时，应该先进行括号中的运算号中的运算. .本书中使用的括号全为圆括号本书中使用的括号全为圆括号. .注意注意:23逻辑联结词真值表小结逻辑联结词真值表小结pqppqpqpqpq000111011100000111100111110024例例1.7 1.7 将下列命题符号化并求其真值将下列命题符号化并求其真值. .(1) (1) 如果如果3 3是合数，则是合数，则4 4是素数，并且如果是素数，并且如果4 4是素数，则是素数，则它不能被它不能被2 2整除；整除；(2)(2)如果如果 当且仅当当且仅当5 5