离散数学1.1-2

1、1离散数学离散数学张波张波E-mail：手机：手机公室：行政楼办公室：行政楼B2122主要内容主要内容n数理逻辑（又称符号逻辑）数理逻辑（又称符号逻辑）n集合论集合论n代数结构代数结构n图论图论n组合分析初步组合分析初步n形式语言和自动机初步形式语言和自动机初步3数理逻辑部分数理逻辑部分n第第1章章 命题逻辑命题逻辑n第第2章章 一阶逻辑一阶逻辑4第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 对偶与范式对偶与范式1.5 推理理论推理理论51.1 命题符号化及联结词命题符号化

2、及联结词 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 6命题与真值命题与真值 命题命题: 判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值: 判断的结果判断的结果真值的取值真值的取值: 真与假真与假真命题真命题: 真值为真的命题真值为真的命题假命题假命题: 真值为假的命题真值为假的命题注意注意: 1.感叹句、祈使句、疑问句都不是命题；感叹句、祈使句、疑问句都不是命题； 2.陈述句中的悖论不是命题；陈述句中的悖论不是命题； 3.判断结果不惟一确定的不是命题判断结果不惟一确定的不是命题7 例例 下列句子中那些是命题？下列

3、句子中那些是命题？ (1) 是无理数是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你今天偷菜了吗？你今天偷菜了吗？ (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) 诚湖内不许滑冰！诚湖内不许滑冰！ (7) 我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题28例例 下列句子中那些是命题？下列句子中那些是命题？ (8)明年明年10月月1日是晴天日是晴天. (9) 地球外的星球上也有人地球外的星球上也有人.（10）111100. （8）、（）、（9）的真值虽然现在还不

4、知道，但它）的真值虽然现在还不知道，但它的真值是唯一的，因而是命题。的真值是唯一的，因而是命题。（10）在二进制中为真，在十进制中为假，需）在二进制中为真，在十进制中为假，需根据上下文才能确定其真值，因而不是命题。根据上下文才能确定其真值，因而不是命题。9命题的分类命题的分类 1. 1.简单命题简单命题( (原子命题原子命题) ) 简单构成的命题简单构成的命题 (不能分解成更简单的陈述句不能分解成更简单的陈述句) 简单命题的真值是确定的，又称为简单命题的真值是确定的，又称为命题常项命题常项或或命题常元命题常元 2.2.复合命题复合命题 由简单命题与联结词按一定规则复合而成的命题由简单命题与联结

5、词按一定规则复合而成的命题 3.3.命题变项（命题变元）命题变项（命题变元） 真值不确定的陈述句，如真值不确定的陈述句，如:x+35:x+35 注意：命题变元注意：命题变元不是不是命题！命题！10简单命题符号化简单命题符号化 2用小写英文字母用小写英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示简单命题简单命题用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为 0 q：2 + 5 = 7，则，则 q 的真值为的真值为 1命题变项：命题变项：也用小写英文字母也用小写英文字母 p, q, r, , ,

6、pi, ,qi, ,ri (i1）表示）表示11联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“ ” 定义定义 设设p为命题，复合命题为命题，复合命题 “ “非非p”（或（或 “ “p的否定的否定”）称称 为为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词 p 为真当且仅当为真当且仅当p为假为假2.合取式与合取联结词合取式与合取联结词“” 定义定义 设设p, ,q为二命题为二命题, ,复合命题复合命题“p并且并且q”(”(或或“p与与q”)”)称称 为为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词，并规，并规

7、定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与多样性 分清简单命题与复合命题分清简单命题与复合命题 12 例例 将下列命题符号化将下列命题符号化. (1) 王晓既用功又聪明王晓既用功又聪明. (2) 王晓不仅聪明，而且用功王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与王丽是同学张辉与王丽是同学.解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) q p.13 例例 令令

8、r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (4) rs. (5) 令令 t : 张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 .说明说明: (1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性. (5) 中中“与与”不是联结词的含义，因而不是联结词的含义，因而(5)中句子中句子是是 简单命题简单命题.又如：李文与李武是兄弟。又如：李文与李武是兄弟。14联结词与复合命题联结词与复合命题 定义定义 设设 p,q为二命题，复合命题为二命题，复合命题“p或或q”称作称作p与与q 的的析取式析取式，记作，记作pq，称作称作析取联结词析

9、取联结词，并规，并规 定定pq为假当且仅当为假当且仅当p与与q同时为假同时为假.例例 将下列命题符号化将下列命题符号化 (1) 2或或4是素数是素数. (2) 2或或3是素数是素数. (3) 4或或6是素数是素数. (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. (5) 王晓红生于王晓红生于1989年或年或1990年年. 3.析取式与析取联结词析取式与析取联结词“”15解解 令令 p:2是素数是素数, q:3是素数是素数, r:4是素数是素数, s:6是素数是素数, , 则则 (1), (2), (3) 均为均为相容或相容或（允许（允许同时为真同时为真）. . 分别符号化为

10、分别符号化为: : pr , pq, rs, 它们的真值分别为它们的真值分别为 1, 1, 0. 而而 (4), (5) 为为排斥或排斥或（不相容或）（不相容或）. 令令 t :小元元拿一个苹果，小元元拿一个苹果，u:小元元拿一个梨，小元元拿一个梨， 则则 (4) 符号化为符号化为 (t u) ( tu). 令令v :王晓红生于王晓红生于1975年年, ,w: :王晓红生于王晓红生于1976年年, ,则则 (5) 既可符号化为既可符号化为 (v w)( vw), 又可又可符号化为符号化为 vw , 为什么为什么? 16例例 （7）小王现在在宿舍或图书馆里）小王现在在宿舍或图书馆里. 令令v :

11、小王在宿舍小王在宿舍, ,w: :小王在图书馆小王在图书馆 则则 (7) 符号化为符号化为 vw例例 （6 6）选小王或小李中的一人当班长）选小王或小李中的一人当班长. . 解解 令令 t :小王当班长，小王当班长，u:小李当班长小李当班长 则则 (6) 符号化为符号化为 (t u) ( tu).17 定义定义 设设 p,q为二命题，复合命题为二命题，复合命题 “如果如果p,则则q” 称作称作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称p是蕴涵式的是蕴涵式的前件前件，q为蕴涵式的为蕴涵式的后件后件. 称称作作蕴涵联结词蕴涵联结词，并规定，并规定，pq为假当且仅为假当且仅当当 p 为真为

12、真 q 为假为假. 注意：注意：1. p与与q不一定有内在联系不一定有内在联系 2. 前件前件p为假时，为假时， pq为真为真4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”18pq 的逻辑关系：的逻辑关系： p为为 q 的充分条件，的充分条件，q 为为 p 的必要条件的必要条件“如果如果 p，则，则 q ” 的不同表述法很多：的不同表述法很多： 若若 p，就，就 q 只要只要 p，就，就 q p 仅当仅当 q 只有只有 q 才才 p 除非除非 q, 才才 p 或或 除非除非 q, 否则非否则非 p，常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件19 例例 设设 p p: :天冷

13、，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意

14、： pq 与与 q p 等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp20定义定义 设设p，q为二命题，复合命题为二命题，复合命题 “p当且仅当当且仅当q”称称作作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结词等价联结词.并并pq规为真当且仅当规为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.说明说明: (1) pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件 (2) pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假 (3) p q与与(p q) (q p)等值等值5.等价式与等价联结词等价式与等价联结词“”21例例 求

15、下列复合命题的真值求下列复合命题的真值 (1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数. (3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. (4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲. (5) 2 + 2 4 当且仅当当且仅当3不是奇数不是奇数. （6）两圆面积相等当且仅当它们的半径）两圆面积相等当且仅当它们的半径相等相等. 它们的真值分别为它们的真值分别为 1，0，1，0，1, 122复合命题符号化：复合命题符号化：第一步：分析出各简单命题，并将它们符号化第一步：分析出各简

16、单命题，并将它们符号化第二步：使用合适的连接词，把简单命题逐个联结起来第二步：使用合适的连接词，把简单命题逐个联结起来例例 1. 小王是小王是500米速滑冠军或米速滑冠军或1000米速滑冠军米速滑冠军 2. 小王现在在宿舍或在图书馆里小王现在在宿舍或在图书馆里 3. 选小王或小李中的一人当班长选小王或小李中的一人当班长 4. 如果我上街，我就去书店看看，除非我很累如果我上街，我就去书店看看，除非我很累 r （pq ） 或或 （ r p)p) q 5. 小王是计算机系学生，他生于小王是计算机系学生，他生于1990年或年或1991 年，他是三好学生年，他是三好学生23联结词与复合命题联结词与复合命

17、题以上给出了以上给出了5个联结词：个联结词： , , , , ，组成，组成一个联结词集合一个联结词集合 , , , , ， 联结词的优先顺序为：联结词的优先顺序为： , , , , ; 如果出如果出现的联结词同级，又无括号时，则按从左到右现的联结词同级，又无括号时，则按从左到右的字典顺序运算的字典顺序运算; 若遇有括号时，应该先进行括若遇有括号时，应该先进行括号中的运算号中的运算. 注意注意: : 本书中使用的本书中使用的 括号全为圆括号括号全为圆括号. 241.2 命题公式及分类命题公式及分类命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题公式的分类命题公式的分类 重

18、言式重言式 矛盾式矛盾式 可满足式可满足式25命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题, ,真值确定的陈述句真值确定的陈述句命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义 合式公式合式公式 (命题公式命题公式, 公式公式) 递归定义如下：递归定义如下：(1) 单个命题常项或变项单个命题常项或变项 p,q,r,pi ,qi ,ri ,0,1 是是合式公式合式公式(2) 若若A是合式公式，则是合式公式，则 ( A)也是合式公式也是合式公式(3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是合式公式也

19、是合式公式(4) 只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是形成的符号串才是合式公式合式公式26合式公式的层次合式公式的层次 定义定义 (1) 若公式若公式A是单个的命题变项或命题常项（包括是单个的命题变项或命题常项（包括0，1）, 则称则称A为为0层公式层公式.(2) 称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一： (a) A= B, B是是n层公式；层公式； (b) A=B C, 其中其中B,C分别为分别为i层和层和j层公式，且层公式，且 n=max(i, j)； (c) A=B C, 其中其中B,C的层次及的层次及n同同(b)； (d) A=B

20、C, 其中其中B,C的层次及的层次及n同同(b)； (e) A=BC, 其中其中B,C的层次及的层次及n同同(b). 27合式公式的层次合式公式的层次 例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 ( p q) r)( r s) 4层层28公式的赋值公式的赋值 定义定义 给公式给公式A中的命题变项中的命题变项 p1, p2, , pn，给给p1, p2, , pn各指定一个真值（各指定一个真值（0或或1），称为对），称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值: 使公式为真的赋值使公式为真的赋值成假赋值成假赋值: 使公式为假的赋值使公式为假的赋值说明说明： 赋值赋值 = 1 2 n之间不加标点符号，之间不加标点符号， i=0或或1. A中仅出现中仅出现 p1, p2, , pn，给，给A赋值赋值 1 2 n是是指指 p1= 1, p2= 2, , pn= n A中仅出现中仅出现 p, q, r, , 给给A赋值赋值 1 2 3是指是指p= 1,q= 2 , r= 3 含含n个变项的公式有个变项的公式有2n个赋值个赋值.29真值表真值表 真值表真值表: 公式公式A在所有赋值下的取值情况列成的表在所有赋值下的取值情况列成的表 （1）列出所有命题变项，列出所有可能赋值）列出所有命题变项，列出所