离散数学PPT课件

离散数学离散数学课件离散数学是计算机科学的核心理论课程，是计算机专业的专业基础课。第一部分数理逻辑第二部分集合与关系代数第三部分图论第一部分数理逻辑第一章命题逻辑基本概念第二章命题逻辑等值演算第三章命题逻辑推理理论第四章一阶逻辑基本概念第五章一阶逻辑等值演算与推理第一章命题逻辑基本概念1。1命题与联结词命题：能判断真假的陈述句。命题真值：作为命题的陈述句所表达的判断结果。例1。判断下列句子是否为命题。（1）4是素数（2）是无理数（3）x大于y。（4）月球上有冰。（5）2000年元旦是晴天。（6）大于吗？（7）请不要吸烟！（8）这朵花真美丽啊！（9）我正在说假话。25例1.2将下面这段话中所出现的原子命题符号化，并指出其真值，然后写出这段陈述。3是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数2解p:是无理数。q:2是素数。r:2是偶数。s:3是素数。t:4是素数。定义1.1设p为命题，复合命题“非p”称为p的否定式，记作p。p为真当且仅当p为假。定义1.2设p，q为两命题，复合命题“p并且q”称为p与q的合取式，记作“pq”。pq为真当且仅当p，q同时为真。定义1.3设p，q为两命题，复合命题“p或q”称为p与q的析取式，记作“pq”。pq为假当且仅当p，q同时为假。例1.3将下列命题符号化（1）吴影既用功又聪明。（2）吴影不仅用功而且聪明。（3）吴影虽然聪明，但不用功。（4）张辉与王丽都是三好学生。（5）张辉与王丽是同学例1.4将下列命题符号化（1）张晓静爱唱歌或爱听音乐。（2）张晓静是江西人或安徽人。（3）张晓静只能挑选202或203房间。定义1.4设p，q为两命题，复合命题“如果p则q”称为p与q的蕴涵式，记作“pq”。pq为假当且仅当p为真，q为假。例1.5将下列命题符号化，并指出下列命题的真值（1）如果3+3=6，则雪是白色的。（2）如果3+36，则雪是白色的。（3）如果3+3=6，则雪不是白色的。（4）如果3+36，则雪不是白色的。（5）只要a能被4整除，则a能被2整除。（6）a能被4整除，仅当a能被2整除。（7）除非a能被2整除，a才能被4整除。（8）除非a能被2整除，否则a不能被4整除。（9）只有a能被2整除，a才能被4整除。（10）只有a能被4整除，a才能被2整除。定义1.5设p，q为两命题，复合命题“p当且仅当q”称为p与q的等价式，记作“pq”。pq为真当且仅当p，q同为真，或p，q为假。例1.6将下列命题符号化，并指出下列命题的真值（1）是无理数当且仅当加拿大位于亚洲。（2）2+3=5的充要条件是是无理数。（3）若两圆01，02的面积相等，则它们半径相等，反之亦然。（4）当小王心情愉快时就唱歌，反之当她唱歌时就心情愉快。33基本复合命题的真值Pqppqpqpqpq0001101111000001011111011001例1.7令P：北京比天津的人口多。q：2+2=4r：乌鸦是白色的。求下列复合命题的真值(1)((Pq)(pq))r(2)(qr)(pr)(3)(Pr)((pr)1.2命题公式及赋值定义1.6（1）单个命题变项是合式公式，称为原子命题公式。（2）若A是合式公式，则（A）也是合式公式。（3）若A，B是合式公式有则（AB），（AB），（AB），（AB）也是合式公式。（4）只有有限次应用（1）~（3）形成的符号串才是合式公式。定义1.7(1)若A是单个命题变项，则A是0层公式。（2）称A是n+1(n0)层公式:(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C，其中B，C的层次及n同（b)；(e)A=BC，其中B，C的层次及n同（b)。(3)若公式A的层次为k，则称A是k层公式。定义1.8设p1,p2…pn是出现在公式A中的全部命题变项，给p1,p2…pn各指定一个真值，称为对A的一个赋值。若指定的一组值使A的真值为1，则称这组值为A的成真赋值。若使A的真值为0，则称这组值为A的成假赋值。定义1.9将命题公式A在所有赋值下取值情况列成表，称为A的真值表。例1.8求下列公式的真值表，并求成真赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr定义1.10设A为一命题公式（1）若A在它的各种赋值下取值均为真，则称A是重言式或永真式。（2）若A在它的各种赋值下取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A是可满足式。例1.9下列公式都有两个命题变项p,q，它们中哪些具有相同的真值表？(1)pq(2)pq(3)(pq)(4)(pq)(qp)(5)qp例1.10下列公式中哪些具有相同的真值表？(1)pq(2)qr(3)(pq)((pr)p)）(4)(qr)(pp)第二章命题逻辑等值演算2.1等值式定义2.1设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B等值，记为AB。例2.1判断下面两个公式是否等值：(pq),pq例2.2判断下面各组公式是否等值：（1）p(qr)与(pq)r（2）(pq)r与(pq)r置换规则：设（A）是含公式A的命题公式，（B）是用公式B置换了（A）中所有的A以后得到的命题公式，若BA，则（B）（A）。例2.3用等值演算法验证等值式(pq)r(pr)(qr)例2.4证明(pq)r与p(qr)不等值例2.5用等值演算法判断下列公式的类型(1)(pq)pq(2)(p(pq))r(3)P(((pq)p)q)例2.6在一次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。2.2析取范式与合取范式定义2.2命题变项及其否定统称作文字，仅由有限个文字构成的析取式称作简单析取式仅由有限个文字构成的合取式称作简单合取式定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。（2）由有限个简单析取式构成的合取式称为合取范式。（3）析取范式与合取范式统称为范式。.定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式。（2）一个合取范式是重言式当且仅当它的每个简单析取式是重言式。定理2.3（范式存在定理）任一命题公式都存在与之等值的析取范式与合取范式例2.7求下面公式的析取范式与合取范式(pq)r定义2.3在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上，称这样的简单合取式为极小项定理2.4设mi与Mi是命题变项p1,p2…pn形成的极小和极大项，则miMi,Mimi定理2.5任何命题公式都存在与之等值的主析取范式与主合取范式，且是唯一的。例2.8求例2.7中公式的主析取范式与主合取范式例2.9求命题公式pq的主析取范式与主合取范式例2.10用公式的主析取范式判断公式的类型（1）（pq）q（2）p（pq）（3）（pq）r例2.11判断下面公式是否等值：（1）p与(pq)(pq)（2）(pq)r与(pq)r例2.12某科研所要从3名科研骨干A，B，C中挑选1-2人出国进修。由于工作需要，选派时要满足以下条件：（1）若A去，则C同去。（2）若B取，则C不能去。（3）若C不去，则A或B可以去问应如何选派？例2.13由公式的主析取范式求主合取范式（1）Am1m2(A中含命题变项p,q)(2)Bm1m2m3(B中含命题变项p,q,r)2.3联结词的完备集定义2.6称F：{0，1}n{0，1}为n元真值函数。定义2.7设S是一个联结词集合，如果任何n元真值函数都可由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理2.6S={，，}是联结词完备集。推论以下联结词集都是完备的。（1）S1={，，，}（2）S2={，，，，}（3）S3={，}（4）S4={，，}（5）S5={，}定义2.8pq(pq)pq(pq)定理2.7{},{}都是联结词完备集第三章命题逻辑的推理理论3.1推理的形式结构定义3.1设A1，A2…An,B都是命题公式，若对于A1，A2…An,B中命题变项的任一组赋值，或者A1A2…An为假，或者A1A2…An为真时，B为真，则称由前提A1，A2…An推出B的推理有效或是正确的，并称B是有效的结论。例3.1判断下列推理是否正确：(1){p,pq}ᅡq(2){p,qp}ᅡq定理3.1命题公式A1，A2，…An推B的推理正确当且仅当A1A2…AnB为重言式。例3.2判断下列推理是否正确：（1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。（2）若a能被4整除，则a能被2整除。a能被2整除，所以a能被4整除。（3）下午马芳或去看电影或去游泳。她没去看电影，所以去游泳了。（4）若气温超过30。C，则王小燕必去游泳。若她去游泳，她就不去看电影了，所以王小燕没去看电影，下午气温超过了30。C。3.2自然推理系统定义3.2一个形式系统I由下面四个部分组成：（1）非空的字母表集，记作A（I）。（2）A（I）中符号构成的公式集，记作E（I）。（3）E（I）中一些特殊的公式组成的公理集，记作AX（I）。（4）推理规则集，记作R（I）。定义3.3自然推理系统P定义如下：1。字母表（1）命题变项符号：p，q，r，…pi,qi,ri…（2）联结词符号：，，，，。（3）号与逗号（），。2。合式公式。3。推理规则（1）前提引入规则（2）结论引入规则（3）置换规则（4）假言推理规则（5）附加规则（6）化简规则（7）拒取式规则（8）假言三段论规则（9）析取三段论规则（10）构造性二难推理规则（10）破坏性二难（11）合取引入规则例3.3在自然推理系统中构造下面推理的证明（1）前提：pq,qr,ps,s结论：r(pq)例3.4在自然推理系统P中构造下面推理的证明若数a是实数，则它不是有理数就是无理数，若a不能表成分数，则它不是有理数。a是实数且它不能表成分数，所以a是无理数。例3.5在自然推理系统P中构造下面推理的证明如果小张和小王去看电影，则小李也去看电影，小赵不去看电影或小张去看电影，小王去看电影，所以当小赵去看电影时小李也去。例3.6在自然推理系统P中构造下面推理的证明如果小张守第一垒且小李向B队投球，则A队将取胜。或者A队未取胜，或者A队成为联赛第一名。A队没有成为联赛第一名。小张守第一垒，因此小李没向B队投球。第四章一阶逻辑基本概念4.1一阶逻辑命题符号化1。个体词指研究对象中可以独立存在的具体的或抽象的客体2。谓词用来刻划个体词性质及个体词之间相互关系的词例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值：（1）只有2是素数，4才是素数。（2）如果5大于4，则4大于6。例4.2在个体域分别为(a),(b)条件时，将下列命题符号化(1)凡人都呼吸。(2)有的人用左手写字。量词：表示个体常项或变项之间数量关系的词1。全称量词2。存在量词（a）个体域D1为人类集合（b）个体域D2为全总个体域例4.3在个体域限制为(a),(b)条件时，将下列命题符号化（1）对于任意的x,均有x2-3x+2=(x-1)(x-2)（2）存在x，使得x+5=3其中:(a)个体