离散数学(第四版)讲义1

1、引言discrete math.离散数学研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。(辞海)计算机科学、信息科学、数字化科学的数学基础离散数学的内容：数理逻辑(mathematics logic) 集合论(sets)代数结构(algebra structure) 图论(graph theory) 组合论(combination) 线性代数(linear algebra) 概率论(probability theory)与高等数学的区别教学内容：数理逻辑(mathematics logic) 集合论(se代数结构(algebra structure)图论(graph theo

2、ry)离散数学的由来与发展：一、古老历史：计数：自然数发展：图论：konigsberg七桥问题二、年青新生： 计算机：二进制运算离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程离散数学的后继课程：数据结构、编译技术、 算法分析与设计、人工智能、 数据库离散数学课程的学习方法：强调：逻辑性、抽象性；注重：概念、方法与应用参考教材：1、离散数学（耿素云，屈婉玲，北大版）2、离散数学（方世昌，西安电子科大版）3、离散数学结构（第三版、影印版）（bernard kolman> robert c.busby> sharon ross,清华版）4、离散数学提要与范例

3、（阮传概、卢友清，北京广播学院版）第一章命题逻辑（proposition logic）1、命题符号化及联结词2、命题公式及分类3、等值演算4、联结词全功能集5、对偶与范式6、推理理论逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科一 一套符号体系+ 组规则数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：逻辑演算、公理化集合论、递归论、模型论、证明论1、命题符号化及联结词命题（proposition）： 一个有确定真或假意义的语句。example 1下列句子都是命题：1. 华盛顿是美国的首都。2. 多伦多是加拿大的首都。3. 1+1=2。4. 2+2=3。命题1

4、和3是真命题，2和4是假命题。example 2考虑如下句子：1. 现在几点了？2. 认真阅读一下。3. x+l=24. x+y=z.句子1和2不是命题，因为它们都不是陈述句。句子3和4不是命题，由于x, y和z的值不确定，使得它们的真值 都不唯一。命题的语句形式：陈述句非命题语句：疑问句、命令句、感叹句、非命题陈述句：悖论语句(真值不唯一)命题的符号表示：大小写英文字母：p、q、r命题真值(truth values)的表示：真：t、1假：f、0命题语句真值确定的几点说明：1、时间性2、区域性3、标准性命题真值间的关系表示：真值表(truth table)definition 1.设p为任一命

5、题,复合命题“非p”(或“p的否定”)称为p的否定式。 记作一1 p o 1为否定联结词。真值表见table 1 o (let p be a proposition. the statementait is not the case that p. " is another proposition, calledthe negation of p. the negation of p is denoted by p. the proposition p is read anot p")p的否定table 1tabkl：否定命题的真值表p*p1001example 3设p表示

6、“今天是星期五”，则p表示“今天不是星期五”。显然，当p的真值为0时，卩的真值为1。definition 2.设p，q为两命题，复合命题“p并且q”(或“p和q”)称作p与q的 合取式。记作paqo a为合取联结词。真值表见table 2o (letp andq he propositions. the proposition "p and q9" denoted by p fq, is the proposition that is true when both p and q are true and is false otherwise. the propositio

7、n p/q is called the conjunction of p and q.)p和q的合取table 2table2：两个命题的合取的真值表pqp a q000010100111example 4用p表示命题“今天是星期五”，q表示命题“今天下雨”，则命题p 与q的合取式是什么？解答：p与q的合取式paq是“今天是星期五，而且今天下雨。”如果是星 期五，又下雨，则该命题为真；如果是除星期五外的任意一天，或者虽是 星期五但没下雨，则该命题为假。definition 3设p，q为两命题，复合命题“p或q”称作p与q的析取式。记作p vqo v 为析取联结词。真值表见 table 3。(l

8、et p and q be propositions. the proposition f,p or q," denoted by p/q9is the proposition that is false when p and q are both false and true otherwise. the proposition pvq is called the disjunction of p and q.)p和q的析取table 3table3：两个命题的析取的真值表pqp v q000011101111example 5还是以example 4为例，命题p与q的析取式是什么

9、？ 解答：p与q的析取式pvq是“今天是星期五或今天下雨。”只有今天既不 是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨 t （包括下雨的星期五），则该命题就为真。definition 4设p, q为两命题，复合命题“如果p,则q”称作p与q的蕴含式。记 作pf q。称p为蕴含式的前件(hypothesis), q为蕴含式的后件 (conclusion)o f称作蕴含联结词。真值表见table 4。(let p and q be propositions. the implication p fq is the proposition that is false when p

10、 is true and q is false and true otherwise.)如果p,则q单条件，蕴涵p：前提 q：结论table 4table4：蕴含式p f q的真值表pqp f q0 010 111 001 11example 6用p表示命题“天下雨”，用q表示命题“我骑自行车上班”，将下列命 题符号化：（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。解答：（1）中，p是q的充分条件，因而符号化为p->q；（2）中，p是q的必要条件，因而符号化为qfpodefinition 5.设p，q为两命题，复合命题“p当且仅当q”称作p与q的等价式。 记作p

11、<>q, 称作等价联结词。真值表见table 5。(let p and q be propositions the biconditional poq is the proposition that is true when p and q have the same truth values and is false otherwise.)p当且仅当q双条件，等价table5：等价式p r q的真值表pqpsq00i010100111example 7将下一命题符号化：“只有(仅当)你是计算机科学系的学生(c)或者你不是新生，你 才可以通过校园网上internet (a)。”解答

12、：a f (ev )example 8将下一命题符号化：“如果你身高小于4英尺(r),你就不能乘坐过山车(q),除非你超 过了 16 岁(s)o ”解答：(1) (ra' s)-*1 q.如果你身高小于4英尺，而且你不超过16岁，那么你就不能乘 坐过山车。(2) «l(r -1 q).如果你不超过16岁，那么当你身高小于4英尺时，你就不能乘 坐过山车。example 9“说离散数学是枯燥无味的或毫无价值的，那是不对的。”p：离散数学是有味道的；q：离散数学是有价值的；解答： 符号化为： p v « q)2、命题公式及分类p、q、r称为原子命题(atomic prop

13、osition)o原子命题或加上逻辑联结词组成的表达式成为复合命题(compositional proposition) o从命题常量 到 命题变量(propositional variable)命题公式：1. 原子命题是命题公式；2. 设p是命题公式，则p也是命题公式；3. 设 p、q 是命题公式，贝ij （paq）、（p/q）、（p-q）、（p-q）也 是命题公式；4. 有限次地使用1、2、3所得到的也是命题公式。proposition formulas, well-formed formulas（wff）命题公式的运算规则：逻辑联接词的优先级：、a. v、一、-命题公式的表达式的运算规律

14、：同代数表达式命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代入（或指派），得到一 个公式对应的真值。性质1：如果一个命题公式有n个互异的命题变量，则命题公式对应的真 值有2"种可能分布。example 10求下列命题公式的真值表：（1） p a （q v-r）.table6:pa (qv-r）的真值表pqrirq v-rp a (q v-r)0 0 01100 0 10000 1 01100 1 10101 0 01111 0 10001 1 01111 1 1011求下列命题公式的真值表：（2） （ pa （pfq） fqtable7: (pa(pr) fq的真值表p

15、qpf qpa(pq)(p/(pf q)l q00101011011000111111求下列命题公式的真值表：（3） -1 （pfq） a q .table8: « ( pq ) a q 的真值表pqpf qfpq)i(p->q)aq00100011001001011100永真式(tautology)：公式中的命题变量无论怎样代入，公式对应 的真值恒为1。永假式(contradiction)：公式中的命题变量无论怎样代入，公式 对应的真值恒为oo可满足式(satisfaction)：公式中的命题变量无论怎样代入，公式 对应的真值总有一种情况为lo一般命题公式(contingen

16、cy)：既不是永真公式也不是永假公式。性质2：(1) 设p是永真命题公式，则p的否定公式是永假命题公式；(2) 设p是永假命题公式，则p的否定公式是永真命题公式；(3) 设 p、q 是永真命题公式，则(paq)、(pvq)、(pf q)、(p q) 也是永真命题公式。小结1. 命题的概念：定义、逻辑值、符号化表示2. 从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表4.命题公式的分类：永真公式、永假公式、可满足公式、一般公式3、等值演算 propositional equivalencesdefinition 6.设

17、a, b为两命题公式，若等价式a-b是重言式，则称a与b是等 值的。记作aob。(the propositions a and b are called logically equivalent if ab is a tautology. the notation a denotes that a and b are logically equivalent.) 逻辑等值，或逻辑等价example 11证明一 ( pvq )与一'p/是等值的。(这个等值关系是德摩根(de morgan)定律之一。德摩根是十九世纪 中叶的英国数学家。)解答：真值表见table 90因为对于p和q所有可能

18、的组合，(pv q)和paq的真值都相同，所以这两个命题是等值的。table 9pqpvq*(pvq)pq>pa>q0001111011010010100101110000example 12证明pfq与p vq是等值的。解答：真值表见table 10o因为对于p和q所有可能的组合，p-q 和pvq的真值都相同，所以这两个命题是等值的。table 10tablelo: pf q 与pvq 的真值表pqpfqppvq00111011111000011101example 13证明pv(qar)与(pvq)a(pvr)是等值的。(分配律)解答：真值表见table 11。因为对于p、q和

19、i所有可能的组合，p v(qar)和(pvq)a(pvr)的真值都相同，所以这两个命题是等值的。tabic 11tablell: pv(qar)与(pvq)a(pvr)的真值表p q rqarpv(qar)pvqpvr(pvq)a(pvr)0 0 0000000 0 1000100 1 0001000 1 1111111 0 0011111 0 1011111 1 0011111 1 111111下面给出24个重要的等值式(祥见p9)：双重否定律、等幕律、交 换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、 矛盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。根据已

20、知的等值式，推演出另外一些等值式的过程称为等值演算。在进行等值演算时，往往用到置换规则。example 14证明 (pv('paq)与一p/ q 是等值的。-(p v(->paq)< rp/ -(-'paq) o rp a-'(-,p)v -»q q rp/(pvq ) <=>(ip ap)v(-ipa -iq) ofvgp/xiq) <>(-ipa-iq)vf o -p aqexample 15证明(paq) f (pvq)是重言式。(paq)(pvq)o -(paq)v(pvq)o (-pv-.q)v(pvq)o 卜pv

21、p) v(-qvq)o tvt ot判断命题公式逻辑等价的方法：1. 真值表2. 命题公式的演算基本等值定理；公式的代入不变性(置换规则)；等值关系的传递性。命题公式逻辑等价关系的应用:1、判定是否逻辑等价(等值)；2、判断是否为永真公式或永假公式；3、命题公式的化简。4、联结词全功能集definition 7.设p,q为两命题，复合命题“p,q之中恰有一个成立”称为p与q的排 斥或或异或。记作p q, 称作排斥或或异或联结词。真值表见table 12o (let p and q be propositions. the exclusive or of p and q, denoted by

22、p q9is the proposition that is true when exactly one of p and q is true and is false otherwise.)p和q的异或table 12table12：异或pq的真值表pqpq00i01i100111p q o(p/i q)v(ipaq)definition 8.设p,q为两命题，复合命题“p与q的否定”称为p与q的与非式。记 作ptq，匸称作与非联结词。真值表见table 13。(let p and q be propositions. the and not of p and q, denoted by p

23、q9 is the proposition that is false when p and q are both true and true otherwise.)p和q的与非table 13table13：与非式ptq的真值表pqptq001011101110ptqo -1 (paq)definition 9-设p,q为两命题，复合命题“p或q的否定”称为p与q的或非式。记 作pjq, /称作或非联结词。真值表见table 14。let p and q be propositions. the or not of p and q, denoted by plq, is the propos

24、ition that is true when p and q are both false and false otherwise.)p和q的或非table 14table14：与非式p/q的真值表pqpjq001010100110p/q <=>>( pvq)逻辑联结词集是功能完备集(functionally complete set)：任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来的 公式。逻辑联结词集是极小功能完备集：是功能完备集并且没有冗余联结词。例1： 1、a> v> 、ax v> t、/是功能完备的，但不是极小功 能完备的。例2： a&g

25、t; t 是极小功能完备的。例3： >、v > 是极小功能完备的。5、对偶与范式definition 10.命题公式p的对偶公式(dual)：将p中的析取联结词换成合取联结词，合取联结词换成析取联结词，1换成0, 0换成1 (如果存在的话)。 记为p*.对偶原理(duality principle)：设p, q是两命题公式，如果poq,则p*oq*。例：a： (p a-i q)v qb： p v q这里，aob,分析是否a*ob*。命题公式的标准化范式小项(small item)/合取式(conjunctive form):若干个原子命题或其否 定的合取。大项(large item

26、)/析取式(disjunctive form):若干个原子命题或其否定 的析取。析取范式(disjunctive normal form)：若干个小项的析取。 合取范式(conjunctive normal form)：若干个大项的合取。定理1：任意一个命题公式都存在与之等价的合取范式和析取范式。(范式 存在定理)定理的证明思路：1、消去对、!、v来说冗余的联结词；2、将否定联结词移到命题变量的前面；3、消除多余的否定联结词；4、利用分配律化成合取范式和析取范式。令a(a】、a2n .n aj是包含有n个变量的公式, 极小项(extremal):小项中恰包含n个变量或其否定。 极大项(extr

27、emal):大项中恰包含n个变量或其否定。主析取范式(unique disjunctive normal form):若干个极小项的 析取。主合取范式(unique conjunctive normal form):若干个极大项的 合取。以三个命题变项p,q,i为例，可形成28个极小项，每个极小项对应 一个二进制数，也对应一个十进制数，二进制数是该极小项的成真赋值， 十进制数可做该极小项抽象表示法的角码。对应情况如下：ipaiqa>r0000,记作m()；»pa iqar0011,记作»paqa f0102,记作m2；«paqaroil3,记作n>3；

28、pa>qa>r1004,记作m<4；pa-qar1015,记作血5；paqa »rno6,记作ni6；paqar1117,记作m7。主析取范式：如nij vm2 vm5可用工(1,2,5 )表示。以三个命题变项p,q,i为例，可形成23=8个极大项，每个极大项对应 一个二进制数，也对应一个十进制数，二进制数是该极大项的成假赋值， 十进制数可做该极大项抽象表示法的角码。对应情况如下：pvqvr0000,记作mo；pvqv ir0011,记作mi；pv qvr0102,记作m2；pv iqv foil3,记作m3；«pvqvr1004,记作m4；>pvq

29、v >r1015,记作m5；pv >qvr1106,记作me；ip v iqv >r1117,记作m7。主合取范式：如mo/ m3 a m6可用n( 0,3,6)表示。example 16求paqvr的主析取范式和主合取范式：解：(p/q )vr o(p aq) a( rv -> r)v(r a(p v -«p)o(p aq ar) v (p aq ->ar)v(p ar) v (-> p ar)«(paqar)v(paq-iar)v(par)a(q-ivq)v(-!par) a(q-)vq) <=>(paqar)v(paq-

30、!ar)v(paqar)v(p-iaqar)v(1 paqar)v(1 p-iaqar) <=>(paqar)v(paq-iar)v(p-iaqar)v(-i paqar)v(-i p-iaqar) <>m7v m6v m5v m3v niio 口 1,3,5,6,7 )(主析取范式) omu am2 am4»ii( 0,2,4)(主合取范式)例6张先生手中有代号为a、b、c、d、e的五种股票，根据当前 股市情况及张先生本人的经济需求，需要有若干个股票抛出，但又必须满 足如下复杂的要求：(1) 若a抛出，则b也抛出；一(2) b和c要留一种股票且只能留一种；b

31、0c(3) c和d要么全抛，要么都不抛；cd(4) d和e两种股票中必然有一种或两种要抛出；dv-ie(5) 若e抛出，则a、b也抛出。一 eaa 'b上述五种条件全部满足，问有几种合理的方案供张先生选择。 解答：留abe或cd (将题意置换成主析取范式)。小结1、命题公式的等价演算2、命题公式的标准化描述表达、分类、判定、应用6、推理理论数理逻辑的主要任务是借助于数学的方法来研究推理的逻辑。推理是从前题推出结论的思维过程，前提是已知的命题公式，结论是从前题出发应用推理规则推出的命题 公式。definition 11.若a!aa2a.aak->b为重言式，则称从aba2,ak推出

32、结论b的 推理正确，记作aiaaaa-aabo b是a|,a2,ak的逻辑结论或有 效结论。称a!aa2a.aak->b为推理的形式结构。判断推理是否正确的方法有以下几种：(1) 真值表法；(2) 等值演算法；(3) 主析取范式法。(即判断a!aa2a.aak->b是否为重言式)example 17判断下列推理是否正确：如果天气凉快，小王就不去游泳，天气凉快, 所以小王没去游泳。判断下列推理是否正确：如果天气凉快，小王就不去游泳，天气凉快, 所以小王没去游泳。在这里，设p：天气凉快；q：小王去游泳。前提：pfq, p。结论：q。推理的形式结构：(pf >q )/p)f q。下

33、面分别用三种方法来判断该蕴含式是否为重言式。(1)真值表法table 15tablcl5： (p* q) ap)-* (*)的真值表pqfpf-iq(p-iq)ap(*)0011010i01011011111i0001真值表的最后一列全为1,因而c)是重言式，所以推理正确。(2) 等值演算法(p->-.q)ap)-q<=>(-ipv -iq)ap)*q oi(ip v iq)ap)v «q o1('p v ,q)v 'pv 'q<=>1(>pv >q)v ('p v >q) ol该蕴含式是重言式，所以推理正确。(3) 主析取范式法(pf-iq)/p)f iq o(-ip v »q)/p)fq<=>1(pv q)ap)v >q<=>-(-«p v «q)v -«p v -q<=>(paq)v(-«pa(qv -'q)v(->qa(pv ->p)o(p aq)v(paq)v(-ipa 'q) v(iqap)v( a ip) <=>(paq)v('paq)v('pa 'q)v(pa q)<