1、离散数学离散数学主要内容主要内容l数理逻辑数理逻辑l集合论集合论l代数结构代数结构l图论图论l组合分析初步组合分析初步l形式语言和自动机初步形式语言和自动机初步数理逻辑部分数理逻辑部分l第第1章章 命题逻辑命题逻辑l第第2章章 一阶逻辑一阶逻辑第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 联结词全功能集联结词全功能集1.5对偶与范试对偶与范试1.6推理理论推理理论1.1 命题符号化及联结词命题符号化及联结词 l命题与真值命题与真值l原子命题原子命题l复合命题复合命题l命题常项命题常项l命题变项命题变
2、项l联结词联结词 命题与真值命题与真值 l 命题命题:判断结果惟一的陈述句；判断结果惟一的陈述句；l 命题的真值命题的真值:命题的命题的判断结果；判断结果；l 真值的取值真值的取值:真与假；真与假；l 真命题真命题:真值为真的命题；真值为真的命题；l 假命题假命题:真值为假的命题真值为假的命题.能判断真假，但不会既能真能判断真假，但不会既能真又能假的陈述句，称为又能假的陈述句，称为命题。命题。感叹句、祈使句、疑问感叹句、祈使句、疑问句都不是命题句都不是命题陈述句中的悖论以及判断结果陈述句中的悖论以及判断结果不惟一确定的也不是命题不惟一确定的也不是命题 1.1.判断一个句子是否为命题，判断一个句
3、子是否为命题，首先要看它是否为陈述句；首先要看它是否为陈述句；然后再看它的真值是否唯一然后再看它的真值是否唯一.2.命题的真值是惟一确定的，有些命题的真值命题的真值是惟一确定的，有些命题的真值 我们立即可知我们立即可知,有些则不能马上知道有些则不能马上知道,但是它们但是它们 的真值不会变化的真值不会变化,是客观存在的是客观存在的.说明：说明：例例 下列句子中那些是命题？下列句子中那些是命题？(1)2是素数是素数.(2)2+5 8.(3)明年明年10月月1日是晴天日是晴天.(4)地球以外的星球上也有人地球以外的星球上也有人.(5)x+5 3.(6)你有铅笔吗？你有铅笔吗？(7)这只兔子跑得真快呀
4、！这只兔子跑得真快呀！(8)请不要讲话！请不要讲话！(9)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(5)(9)都都不不是是命命题题命题命题命题命题命题的分类命题的分类 简单命题简单命题(原子命题原子命题)：简单陈述句构成的命题简单陈述句构成的命题.复合命题复合命题：由简单命题与联结词按一定规则复合由简单命题与联结词按一定规则复合 而成的命题而成的命题.简单命题符号化简单命题符号化 2用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i1）表示）表示简单命题；简单命题；用用“1”表示真，用表示真，用“0”表示假表
5、示假.例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0；q：2+5=7，则，则 q 的真值为的真值为 1.命题常项与命题变项命题常项与命题变项命题常项命题常项：简单命题：简单命题.命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句.命题变项也用命题变项也用小写英文字母小写英文字母 p,q,r表示表示；一个字母一个字母 p 表示的是命题常项还是命题变项，表示的是命题常项还是命题变项，一般由上下文来确定一般由上下文来确定。注意：命题变项不是命注意：命题变项不是命题。题。联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“”定义定义:设设p为命题
6、，复合命题为命题，复合命题 “非非p”（或（或 “p的的否定否定”）称为）称为 p的的否定式否定式，记作，记作 p，符号，符号 “”称作称作否定联结词否定联结词，并规定，并规定 p 为真当且仅当为真当且仅当 p 为为假假.2.合取式与合取联结词合取式与合取联结词“”定义定义:设设p,q为二命题为二命题,复合命题复合命题“p并且并且q”(”(或或“p与与q”)”)称为称为p与与q的的合取式合取式，记作，记作pq，“”“”称作称作合取联结词合取联结词，并规定，并规定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真.注意注意：1.p与与q的合取表达的逻辑关系是：的合取表达的逻辑关系是：p与与q
7、两个两个 命题同时成立；命题同时成立；2.有时有时“和和”、“与与”联结的是主语，构成的联结的是主语，构成的 是简单命题；遇到是简单命题；遇到“和和”、“与与”等出现的等出现的 命题，要分清简单命题与复合命题。命题，要分清简单命题与复合命题。例例:将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.解解:令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1)pq (2
8、)pq (3)p q.令令 r:张辉是三好学生，张辉是三好学生，s:王丽是三好学生王丽是三好学生 (4)rs.(5)令令 t:张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题.说明说明:(1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性.(5)中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(5)中句子是简单命题中句子是简单命题.定义定义:设设 p,q为二命题，复合命题为二命题，复合命题“p 或或 q”称作称作 p与与q的的析取式析取式，记作，记作pq，“”称作称作析取联结词析取联结词，并规定并规定 pq为假当且仅当为假当且仅当p p与与q
9、 q同时为假同时为假.注意注意：析取式析取式 pq 表示的是一种相容性或，即允表示的是一种相容性或，即允 许许 p与与q 同时为真。同时为真。3.析取式与析取联结词析取式与析取联结词“”例例:将下列命题符号化将下列命题符号化 (1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小珍只能拿一个苹果或一个梨小珍只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1975年或年或1976年年.解解:令令 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数,则则 (1),(2),(3)均为相容或均为相容或.分别符号化为分别符号化为:pr,
10、pq,rs,它们的真值分别为它们的真值分别为 1,1,0.而而 (4),(5)为排斥或为排斥或.令令 t:小珍拿一个苹果，小珍拿一个苹果，u:小珍拿一个梨，小珍拿一个梨，则则 (4)符号化为符号化为 (t u)(tu).令令 v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于1976年年,则则 (5)既可符号化为既可符号化为 (v w)(vw),又可符号化为又可符号化为 vw,为什么为什么?定义定义：设：设p,qp,q为二命题，复合命题为二命题，复合命题“如果如果p,p,则则q q”称作称作p p与与q q的的蕴涵式蕴涵式，记作，记作 p pq q，并称，并称 p p 是蕴涵是蕴涵
11、式的式的前件前件，q q 为蕴涵式的为蕴涵式的后件后件.“.“”称作称作蕴涵蕴涵联结词联结词，并规定，并规定p pq q 为假当且仅当为假当且仅当 p p 为真为真q q 为为假假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”说明说明:1.pq 的逻辑关系是：的逻辑关系是：q 为为 p 的的必要必要条件，或条件，或 p 是是q 的充分条件的充分条件.2.2.复合命题复合命题 “如果如果 p，则，则 q”、“若若 p，就，就 q”、“只要只要p,就就q”、“p 仅当仅当q”、“只有只有q 才才p”、“除非除非 q,才才 p”或或“除非除非 q,否则非否则非 p”等等 都表达了都表达了q是是 p
12、的必要条件，因而都可以符号化为的必要条件，因而都可以符号化为 蕴涵式蕴涵式 pq 或或 q p.3.3.当当 p 为假时，为假时，pq 为真为真.4.4.遇到蕴涵联结词的命题，关键要分清蕴涵式的前遇到蕴涵联结词的命题，关键要分清蕴涵式的前 件和后件件和后件.例例 设设 p p:天冷，天冷，q q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除
13、非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意注意：pq 与与 p q 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp定义定义：设：设p，q为二命题，复合命题为二命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结等价联结词词.并并pq规为真当且仅当规为真当且仅当p与与q同时为真或同时为同时为真或同时为假假.说明说明:(1)pq 的
14、逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件;(2)pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假;5.等价式与等价联结词等价式与等价联结词“”例例 求下列复合命题的真值求下列复合命题的真值 (1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)函数函数 f(x)在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续.它们的真值分别为它们的真值分别为 1，0，1，0，0.以上给出
15、了以上给出了5个联结词：个联结词：,，组成，组成一个联结词集合一个联结词集合,.联结词的优先顺序为：联结词的优先顺序为：,;如如果出现的联结词同级，又无括号时，则按从左到果出现的联结词同级，又无括号时，则按从左到右的顺序运算右的顺序运算;若遇有括号时，应该先进行括号若遇有括号时，应该先进行括号中的运算中的运算.说明说明:本书中使用的本书中使用的 括号全为圆括号括号全为圆括号.1.2 命题公式及分类命题公式及分类l命题变项与合式公式命题变项与合式公式l公式的赋值公式的赋值l真值表真值表l命题的分类命题的分类:重言式重言式 矛盾式矛盾式 可满足式可满足式合式公式合式公式(命题公式命题公式,公式公式
16、)定义定义:合式公式合式公式 的递归定义如下：的递归定义如下：(1)单个命题常项或变项单个命题常项或变项 p,q,r,pi,qi,ri,0,1 是是合式公式合式公式;(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式;(3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是合式公式也是合式公式;(4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是合式形成的符号串才是合式公式公式.合式公式的层次合式公式的层次 定义定义：(1)若公式若公式A是单个的命题变项是单个的命题变项,则称则称A为为0层公式层公式.(2)称称A是是n+1(n
17、0)层公式是指下面情况之一：层公式是指下面情况之一：(a)A=B,B是是n层公式；层公式；(b)A=BC,其中其中B,C分别为分别为 i 层和层和 j 层公式，且层公式，且 n=max(i,j)；(c)A=BC,其中其中B,C的层次及的层次及n同同(b)；(d)A=BC,其中其中B,C的层次及的层次及n同同(b)；(e)A=BC,其中其中B,C的层次及的层次及n同同(b).例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 (p q)r)(r s)4层层公式的赋值公式的赋值 定义定义：给公式给公式A中的命题变项中的命题变项 p1,p2,pn指定指定 一组真值称为对一组
18、真值称为对A的一个的一个赋值赋值或或解释解释。成真赋值成真赋值:使公式为真的赋值；使公式为真的赋值；成假赋值成假赋值:使公式为假的赋值。使公式为假的赋值。说明：说明：1、赋值赋值=1 2 n之间不加标点符号，之间不加标点符号，i=0或或1；2、A中仅出现中仅出现 p1,p2,pn，给，给A赋值赋值 1 2 n是指是指 p1=1,p2=2,pn=n 3、A中仅出现中仅出现 p,q,r,给给A赋值赋值 1 2 3是指是指 p=1,q=2,r=3（字典顺序）（字典顺序）4、含含n个变项的公式有个变项的公式有2n个赋值个赋值.真值表真值表 真值表真值表:公式公式A在所有赋值下的取值情况列成的表。在所有
19、赋值下的取值情况列成的表。例例 给出公式的真值表给出公式的真值表 A=(qp)qp 的的真值表真值表 p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 1111例例 B=(p q)q 的的真值表真值表 p q p p q (p q)(p q)q0 00 11 01 1 1100110100100000实例实例例例 C=(p q)r 的的真值表真值表 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010公式的类型公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1)若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式(也称也称永真式永真式)；(2)若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式(也称也称永假式永假式)；(3)若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式.注意注意：重言式是可满足式，但反之不真：重言式是可满足式，但反之不真.上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A=(qp)qp，B=(p q)q，C=(p q)r
