离散数学课件

离散数学离散数学1离散数学课件离散数学是计算机科学的核心理论课程，是计算机专业的专业基础课。第一部分数理逻辑第二部分集合与关系代数第三部分图论离散数学课件离散数学是计算机科学的核心理论课程，是计算机专业2第一部分数理逻辑第一章命题逻辑基本概念第二章命题逻辑等值演算第三章命题逻辑推理理论第四章一阶逻辑基本概念第五章一阶逻辑等值演算与推理第一部分数理逻辑第一章命题逻辑基本概念3第一章命题逻辑基本概念1。1命题与联结词命题：能判断真假的陈述句。命题真值：作为命题的陈述句所表达的判断结果。第一章命题逻辑基本概念1。1命题与联结词4例1。判断下列句子是否为命题。（1）4是素数（2）是无理数（3）x大于y。

（4）月球上有冰。

（5）2000年元旦是晴天。

（6）

大于吗？

（7）请不要吸烟！（8）这朵花真美丽啊！（9）我正在说假话。例1。判断下列句子是否为命题。5例1.2将下面这段话中所出现的原子命题符号化，并指出其真值，然后写出这段陈述。3是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数解p:是无理数。q:2是素数。r:2是偶数。s:3是素数。t:4是素数。例1.2将下面这段话中所出现的原子命题符号化，并指出其真值，6定义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.1设p为命题，复合命题“非p”称为p的否定式，7例1.3将下列命题符号化（1）吴影既用功又聪明。（2）吴影不仅用功而且聪明。（3）吴影虽然聪明，但不用功。（4）张辉与王丽都是三好学生。（5）张辉与王丽是同学例1.4将下列命题符号化（1）张晓静爱唱歌或爱听音乐。（2）张晓静是江西人或安徽人。（3）张晓静只能挑选202或203房间。例1.3将下列命题符号化例1.4将下列命题符号化8定义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整除。定义1.4设p，q为两命题，复合命题“如果p则q”称为p与9（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为假。（9）只有a能被2整除，a才能被4整除。定义1.5设p，10例1.6将下列命题符号化，并指出下列命题的真值（1）是无理数当且仅当加拿大位于亚洲。（2）2+3=5的充要条件是是无理数。（3）若两圆01，02的面积相等，则它们半径相等，反之亦然。（4）当小王心情愉快时就唱歌，反之当她唱歌时就心情愉快。例1.6将下列命题符号化，并指出下列命题的真值11基本复合命题的真值Pqppqpqpqpq0001101111000001011111011001基本复合命题的真值Pqppqpqpq12例1.7令P：北京比天津的人口多。q：2+2=4r：乌鸦是白色的。求下列复合命题的真值(1)((Pq)(pq))r(2)(qr)(pr)(3)(Pr)((pr)例1.7131.2命题公式及赋值定义1.6（1）单个命题变项是合式公式，称为原子命题公式。（2）若A是合式公式，则（A）也是合式公式。（3）若A，B是合式公式有则（AB），（AB），（AB），（AB）也是合式公式。（4）只有有限次应用（1）~（3）形成的符号串才是合式公式。1.2命题公式及赋值定义1.6（1）单个命题变项是合式公式，14定义1.7(1)若A是单个命题变项，则A是0层公式。（2）称A是n+1(n0)层公式:(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)。(3)若公式A的层次为k，则称A是k层公式。定义1.7(1)若A是单个命题变项，则A是0层公式。15定义1.8设p1,p2…pn是出现在公式A中的全部命题变项，给p1,p2…pn各指定一个真值，称为对A的一个赋值。若指定的一组值使A的真值为1，则称这组值为A的成真赋值。若使A的真值为0，则称这组值为A的成假赋值。定义1.9将命题公式A在所有赋值下取值情况列成表，称为A的真值表。定义1.8设p1,p2…pn是出现在公式A中的全部命题16例1.8求下列公式的真值表，并求成真赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr定义1.10设A为一命题公式（1）若A在它的各种赋值下取值均为真，则称A是重言式或永真式。（2）若A在它的各种赋值下取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A是可满足式。例1.8求下列公式的真值表，并求成真赋值。定义1.10设A为17例1.9下列公式都有两个命题变项p,q，它们中哪些具有相同的真值表？(1)pq(2)pq(3)(pq)(4)(pq)(qp)(5)qp例1.9下列公式都有两个命题变项p,q，它们中哪些具有相同18例1.10下列公式中哪些具有相同的真值表？(1)pq(2)qr(3)(pq)((pr)p)）(4)(qr)(pp)例1.10下列公式中哪些具有相同的真值表？19第二章命题逻辑等值演算2.1等值式定义2.1设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B等值，记为AB。第二章命题逻辑等值演算2.1等值式定义2.1设A,B是20例2.1判断下面两个公式是否等值：(pq),pq例2.2判断下面各组公式是否等值：（1）p(qr)与(pq)r（2）(pq)r与(pq)r例2.1判断下面两个公式是否等值：例2.2判断下面各组公式是21置换规则：设（A）是含公式A的命题公式，（B）是用公式B置换了（A）中所有的A以后得到的命题公式，若BA，则（B）（A）。

例2.3用等值演算法验证等值式(pq)r(pr)(qr)例2.4证明(pq)r与p(qr)不等值置换规则：设（A）是含公式A的命题公式，（B）是用22例2.5用等值演算法判断下列公式的类型(1)(pq)pq(2)(p(pq))r(3)P(((pq)p)q)例2.6在一次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。例2.5用等值演算法判断下列公式的类型例2.6在一次研讨232.2析取范式与合取范式定义2.2命题变项及其否定统称作文字，仅由有限个文字构成的析取式称作简单析取式仅由有限个文字构成的合取式称作简单合取式定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。2.2析取范式与合取范式定义2.2命题变项及其否定统称作24定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。（2）由有限个简单析取式构成的合取式称为合取范式。（3）析取范式与合取范式统称为范式。.定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。25定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式。（2）一个合取范式是重言式当且仅当它的每个简单析取式是重言式。定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合26定理2.3（范式存在定理）任一命题公式都存在与之等值的析取范式与合取范式例2.7求下面公式的析取范式与合取范式(pq)r定理2.3（范式存在定理）任一命题公式都存在与之等值的析取范27定义2.3在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上，称这样的简单合取式为极小项定义2.3在含有n个命题变项的简单合取式中，若每个命题变项28定理2.4设mi与Mi是命题变项p1,p2…pn形成的极小和极大项，则mi

Mi,Mimi定理2.5任何命题公式都存在与之等值的主析取范式与主合取范式，且是唯一的。定理2.4设mi与Mi是命题变项p1,p2…pn形成的极小和29例2.8求例2.7中公式的主析取范式与主合取范式例2.9求命题公式pq的主析取范式与主合取范式例2.8求例2.7中公式的主析取范式与主合取范式30例2.10用公式的主析取范式判断公式的类型（1）（pq）q（2）p（pq）（3）（pq）r例2.10用公式的主析取范式判断公式的类型31例2.11判断下面公式是否等值：（1）p与(pq)(pq)（2）(pq)r与(pq)r例2.11判断下面公式是否等值：32例2.12某科研所要从3名科研骨干A，B，C中挑选1-2人出国进修。由于工作需要，选派时要满足以下条件：（1）若A去，则C同去。（2）若B取，则C不能去。（3）若C不去，则A或B可以去问应如何选派？例2.12某科研所要从3名科研骨干A，B，C中挑选1-233例2.13由公式的主析取范式求主合取范式（1）Am1m2(A中含命题变项p,q)(2)Bm1m2m3(B中含命题变项p,q,r)例2.13由公式的主析取范式求主合取范式342.3联结词的完备集定义2.6称F：{0，1}n{0，1}为n元真值函数。定义2.7设S是一个联结词集合，如果任何n元真值函数都可由仅含S中的联结词构成的公式表示，则称S是联结词完备集。2.3联结词的完备集定义2.6称F：{0，1}n{035定理2.6S={，，}是联结词完备集。推论以下联结词集都是完备的。（1）S1={，，，}（2）S2={，，，，}（3）S3={，}（4）S4={，，}（5）S5={，}定理2.6S={，，}是联结词完备集。36定义2.8pq(pq)pq(pq)定理2.7{

},{

}都是联结词完备集定义2.8pq(pq)pq37第三章命题逻辑的推理理论3.1推理的形式结构第三章命题逻辑的推理理论3.1推理的形式结构38定义3.1设A1，A2…An,B都是命题公式，若对于A1，A2…An,B中命题变项的任一组赋值，或者A1A2

…An为假，或者A1A2

…An为真时，B为真，则称由前提A1，A2…An推出B的推理有效或是正确的，并称B是有效的结论。定义3.1设A1，A2…An,B都是命题公式，若对于A1，A39例3.1判断下列推理是否正确：(1){p,pq}ᅡq(2){p,qp}ᅡq定理3.1命题公式A1，A2，…An推B的推理正确当且仅当A1A2

…An

B

为重言式。例3.1判断下列推理是否正确：40例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判断下列推理是否正确：413.2自然推理系统定义3.2一个形式系统I由下面四个部分组成：（1）非空的字母表集，记作A（I）。（2）A（I）中符号构成的公式集，记作E（I）。（3）E（I）中一些特殊的公式组成的公理集，记作AX（I）。（4）推理规则集，记作R（I）。3.2自然推理系统定义3.2一个形式系统I由下面四个部分42定义3.3自然推理系统P定义如下：1。字母表（1）命题变项符号：p，q，r，…pi,qi,ri…（2）联结词符号：，，，，。（3）号与逗号（），。2。合式公式。定义3.3自然推理系统P定义如下：433。推理规则（1）前提引入规则（2）结论引入规则（3）置换规则（4）假言推理规则（5）附加规则

3。推理规则44（6）化简规则（7）拒取式规则（8）假言三段论规则（9）析取三段论规则（10）构造性二难推理规则（6）化简规则45（10）破坏性二难（11）合取引入规则例3.3在自然推理系统中构造下面推理的证明（1）前提：pq,qr,ps,s

结论：r(pq)（10）破坏性二难例3.3在自然推理系统中构造下面推理的46例3.4在自然推理系统P中构造下面推理的证明若数a是实数，则它不是有理数就是无理数，若a不能表成分数，则它不是有理数。a是实数且它不能表成分数，所以a是无理数。例3.4在自然推理系统P中构造下面推理的证明47例3.5在自然推理系统P中构造下面推理的证明如果小张和小王去看电影，则小李也去看电影，小赵不去看电影或小张去看电影，小王去看电影，所以当小赵去看电影时小李也去。例3.5在自然推理系统P中构造下面推理的证明48例3.6在自然推理系统P中构造下面推理的证明如果小张守第一垒且小李向B队投球，则A队将取胜。或者A队未取胜，或者A队成为联赛第一名。A队没有成为联赛第一名。小张守第一垒，因此小李没向B队投球。例3.6在自然推理系统P中构造下面推理的证明49第四章一阶逻辑基本概念4.1一阶逻辑命题符号化1。个体词指研究对象中可以独立存在的具体的或抽象的客体2。谓词用来刻划个体词性质及个体词之间相互关系的词第四章一阶逻辑基本概念4.1一阶逻辑命题符号化50例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值：（1）只有2是素数，4才是素数。（2）如果5大于4，则4大于6。例4.2在个体域分别为(a),(b)条件时，将下列命题符号化(1)凡人都呼吸。(2)有的人用左手写字。例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的51量词：表示个体常项或变项之间数量关系的词1。全称量词2。存在量词（a）个体域D1为人类集合（b）个体域D2为全总个体域量词：表示个体常项或变项之间数量关系的词52例4.3在个体域限制为(a),(b)条件时，将下列命题符号化（1）对于任意的x,均有x2-3x+2=(x-1)(x-2)（2）存在x，使得x+5=3其中:(a)个体域D1=N（N为自然数集合）(b)个体域D2=R(R为实数集合）例4.3在个体域限制为(a),(b)条件时，将下列命题符53例4.4将下列命题符号化，并讨论它们的真值.(1)所有的人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必是亚洲人。。例4.4将下列命题符号化，并讨论它们的真值.。54例4.5将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的二只兔子例4.5将下列命题符号化554.2一阶逻辑公式及解释定义4.1一阶语言的字母表定义如下（1）个体常项：a,b,c,…,ai,bi,ci…,i1（2）个体变项：x,y,z,…,xi,yi,zi,…,i1（3）函数符号：f,g,h,…fi,gi,hi…,i1（4）谓词符号：F，G，H，…,Fi，Gi，Hi…，i14.2一阶逻辑公式及解释定义4.1一阶语言的字母表定义如下56（5）量词符号：，（6）联结词符号：，，，，（7）括号和逗号，（，），定义4.2P的项定义如下（1）个体常项和个体变项是项。（2）若（x1,x2,…,xn)是任意n元函数，t1,t2,,…,tn是任意的n个项，则(t1,t2,…,tn)是项（5）量词符号：，57（3）所有的项都是有限次使用规则（1）、（2）得到。定义4.3设R（x1,x2,…,xn)是P的任意n元谓词，t1,t2,,…,tn是任意的n个项，则称R（t1,t2,…,tn）是P的原子公式。（3）所有的项都是有限次使用规则（1）、（2）得到。58定义4.4P的合式公式定义如下（1）原子公式是合式公式。（2）若A是合式公式，则A是合式公式。（3）若A、B是合式公式AB、AB、AB、AB是合式公式。（4）若A是合式公式，则xA、xA也是合式公式。（5）只有有限次使用（1）~（4）构成的符号串才是合式公式。的。定义4.4P的合式公式定义如下的。59定义4.5在公式xA和xA中，称x为指导变元，A为相应量词辖域。在xA和xA的辖域中，x的所有出现都称为約束出现，A中不是約束出现的其它变项均称为自由出现定义4.5在公式xA和xA中，称x为指导变元，A为相应量60例4.6指出下列公式中的指导变元，各量词的辖域，自由出现和約束出现的个体变项：（1）x(F(x,y)G(x,z))（2）x(F(x)G(y))y(H(x)L(x,y,z))例4.6指出下列公式中的指导变元，各量词的辖域，自由出现和約61定义4.6设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式简称闭式。例4.7将下列两个公式中的变项指定为常项使其成为命题（1）x(F(x)G(x))（2）xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y))定义4.6设A是任意的公式，若A中不含自由出现的个体变项，62定义4.7P的解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素的集合(c)DI中一些特定函数的集合(d)DI中特定谓词的集合定义4.7P的解释I由下面4部分组成：63例4.8给定解释I如下个体域D=Na=0f(x,y)=x+y,g(x,y)=x•yF(x,y)为x=y在I下，下列哪些公式为真？哪些公式为假？哪些公式真值不能确定？例4.8给定解释I如下64（1）F(f(x,y),g(x,y))（2）F(f(x,a),y)F(g(x,y),z)（3）F(g(x,y),g(y,z))（4）xF(g(x,y),z)（5）xF(g(x,a),x)F(x,y)（6）xF(g(x,a),x)（1）F(f(x,y),g(x,y))65（7）xy(F(f(x,a),y)F(f(y,a),x))（8）xyzF(f(x,y),z)（9）xF(f(x,x),g(x,x))（7）xy(F(f(x,a),y)F(f(y,a),66定理4.1封闭的公式在任何解释下都变成命题。定义4.8设A为一公式，若A在任何解释下均为真，则称A为永真式。若A在任何解释下均为假则称A为矛盾式。若至少存在一个解释使A为真则称A是可满足式。定理4.1封闭的公式在任何解释下都变成命题。定义4.867定义4.9设A。是含命题变项p1、p2、…、pn的命题公式，A1、A2、…An是n个谓词公式,用Ai(1in)处处代替A。中的Pi，所得公式A称为A。的代换实例。定义4.9设A。是含命题变项p1、p2、…、pn的命题68定理4.2重言式的代换实例是永真式，矛盾式的代换实例是矛盾式。例4.9判断下列公式中哪些是永真式，哪些是矛盾式？(1)x(F(x)G(x))(2)x(F(x)G(x))(3)xF(x)(xyG(x、y)xF(X))(4)(xF(x)yG(y))yG(y)定理4.2重言式的代换实例是永真式，矛盾式的代换实例是矛盾式69例4.10判断下列公式的类型（1）xF(x)xF(x)（2）xyF(x、y)xyF(x、y)（3）x(F(x)G(x))yG(y)例4.10判断下列公式的类型70第五章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则定义5.1设A、B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B等值。记为AB第五章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则定711.置换规则设（A）是含公式A的公式，（B）是用公式B取代（A）中所有的A之后的公式，若AB，则（A）（B）2.换名规则设A为一个公式，将A中某量词辖域中某約束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现的某个体变项符号，公式中其余部分不变，设所得公式为A'，则A

A‘。3.代替规则设A为一个公式，将A中某自由出现的个体变项的所有出现用A中未曾出现的某个体变项符号代替，公式A中其余部分不变，设所得公式为A'，则A

A'。1.置换规则2.换名规则3.代替规则72例5.1将下面公式化成与之等值的公式，使其没有既是約束出现又是自由出现的个体变项。（1）xF(x、y、z)yG(x、y、z)（2）x(F(x、y)yG(x、y、z))例5.2证明（1）x(A(x)B(x))不等值于xA(x)xB(x)（2）x(A(x)B(x))不等值于xA(x)xB(x)例5.1将下面公式化成与之等值的公式，使其没有既是約束出现又73例5.3设个体域为D={a,b,c}，将下面公式的量词消去(1)x(F(x)G(x))(2)x(F(x)yG(y))(3)xyF(x、y)例5.3设个体域为D={a,b,c}，将下面公式的量74例5.4给定解释I如下（1）个体域D={2、3}（2）D中特定元素a=2（3）D中特定函数f(x):f(2)=3、f(3)=2（4）D上的特定谓词G（x、y)为：G（2、2）=G（2、3）=G（3、2）=1，G（3、3）=0L（2、2）=L（3、3）=1、L（2、3）=L（3、2）=0F（x）为F（2）=0、F（3）=1在I下求下列各式的真值(1)x(F(x)G(x、a))(2)x(F(f(x))G(x、f(x)))(3)xyL(x、y)(4)xyL(x、y)例5.4给定解释I如下75例5.5证明下列各等值式。（1）x(M(x)F(x))x(Mx)F(x))（2）x(F(x)G(x))x(F(x)G(x))（3）xy(F(x)G(y)H(x、y))xy(F(x)G(y)H(x、y)（4）xy(F(x)G(y)L(x、y))xy(F(x)G(y)L(x、y))5.2一阶逻辑前束泛式例5.5证明下列各等值式。5.2一阶逻辑前束泛式76定义5.2设A为一阶逻