离散数学PPT课件.ppt

,离 散 数 学,离散数学课件,离散数学是计算机科学的核心理论课程，是计算机专业的专业基础课。第一部分 数理逻辑第二部分 集合与关系代数第三部分 图论,第一部分数理逻辑,第一章 命题逻辑基本概念第二章 命题逻辑等值演算第三章 命题逻辑推理理论第四章 一阶逻辑基本概念第五章 一阶逻辑等值演算与推理,第一章 命题逻辑基本概念,1。1命题与联结词命题：能判断真假的陈述句。命题真值：作为命题的陈述句所表达的判断结果。,例1。判断下列句子是否为命题。（1）4是素数（2）是无理数（3）x大于y。（4）月球上有冰。（5）2000年元旦是晴天。（6）大于 吗？（7）请不要吸烟！（8）这朵花真美丽啊！（9）我正在说假话。,例1.2将下面这段话中所出现的原子命题符号化，并指出其真值，然后写出这段陈述。3 是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数,解 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的合取式，记作“pq”。pq为真当且仅当 p，q同时为真。,定义1.3 设p，q为两命题，复合命题“p或q”称为p与q的析取式，记作“pq”。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的蕴涵式，记作“pq”。p q为假当且仅当 p为真，q为假。,例1.5将下列命题符号化，并指出下列命题的真值（1）如果3+3=6，则雪是白色的。（2）如果3+36，则雪是白色的。（3）如果3+3=6，则雪不是白色的。（4）如果3+36，则雪不是白色的。（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的等价式，记作“pq”。p q为真当且仅当 p，q同为真，或p，q 为假。,例1.6将下列命题符号化，并指出下列命题的真值（1）是无理数当且仅当加拿大位于亚洲。（2）2+3=5的充要条件是 是无理数。（3）若两圆01，02的面积相等，则它们半径相等，反 之亦然。（4）当小王心情愉快时就唱歌，反之当她唱歌时就心 情愉快。,基本复合命题的真值,例1.7令 P：北京比天津的人口多。q：2+2=4 r：乌鸦是白色的。求下列复合命题的真值(1)(Pq)(p q)r(2)(q r)(p r)(3)(P r)(p r),1.2命题公式及赋值,定义1.6（1）单个命题变项是合式公式，称为原子命题公式。（2）若A是合式公式，则（A）也是合式公式。（3）若A，B是合式公式有 则（AB），（AB），（AB），（A B）也是合式公式。（4）只有有限次应用（1）（3）形成的符号串才是合式公式。,定义1.7(1)若A是单个命题变项，则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 C，其中B，C的层次及n同（b)；(e)A=B C，其中B，C的层次及n同（b)。(3)若公式A的层次为k，则称A是k层公式。,定义1.8 设p1,p2pn是出现在公式A中的全部命题变项，给p1,p2pn各指定一个真值，称为对A的一个赋值。若指定的一组值使A的真值为1，则称这组值为A的成真赋值。若使A的真值为0，则称这组值为A的成假赋值。,定义1.9将命题公式A在所有赋值下取值情况列成表，称为A的真值表。,例1.8求下列公式的真值表，并求成真赋值。(1)(pq)r(2)(pp)(qq)(3)(p q)q r,定义1.10设A为一命题公式（1）若A在它的各种赋值下取值均为真，则称A是重言式或永真式。（2）若A在它的各种赋值下取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A是可满足式。,例1.9 下列公式都有两个命题变项p,q，它们中哪些具有相同的真值表？(1)pq(2)pq(3)(pq)(4)(pq)(qp)(5)qp,例1.10 下列公式中哪些具有相同的真值表？(1)pq(2)qr(3)(pq)(pr)p)）(4)(qr)(pp),第二章 命题逻辑等值演算,2.1等值式,定义2.1设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B等值，记为AB。,例2.1判断下面两个公式是否等值：(pq),pq,例2.2判断下面各组公式是否等值：（1）p(qr)与(pq)r（2）(pq)r与(pq)r,置换规则：设（A）是含公式A的命题公式，（B）是用公式B置换了（A）中所有的A以后得到的命题公式，若BA，则（B）（A）。,例2.3 用等值演算法验证等值式(pq)r(pr)(qr),例2.4证明(pq)r 与 p(qr)不等值,例2.5 用等值演算法判断下列公式的类型(1)(pq)pq(2)(p(pq)r(3)P(pq)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求下面公式的析取范式与合取范式(pq)r,定义2.3 在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i 个命题变项或它的否定式出现在从左算起的第i 位上，称这样的简单合取式为极小项,定理2.4设mi与Mi是命题变项p1,p2pn形成的极小和极大项，则mi Mi,Mi mi,定理2.5任何命题公式都存在与之等值的主析取范式与主合取范式，且是唯一的。,例2.8求例2.7中公式的主析取范式与主合取范式例2.9求命题公式pq的主析取范式与主合取范式,例2.10用公式的主析取范式判断公式的类型（1）（pq）q（2）p（p q）（3）（p q）r,例2.11判断下面公式是否等值：（1）p与(pq)(pq)（2）(pq)r与(pq)r,例2.12 某科研所要从3名科研骨干A，B，C中挑选1-2人出国进修。由于工作需要，选派时要满足以下条件：（1）若A去，则C同去。（2）若B取，则C不能去。（3）若C不去，则A或B可以去 问应如何选派？,例2.13由公式的主析取范式求主合取范式（1）Am1m2(A中含命题变项p,q)(2)Bm1m2m 3(B中含命题变项p,q,r),2.3联结词的完备集,定义2.6称F：0，1n0，1为n元真值函数。,定义2.7设S是一个联结词集合，如果任何n元真值函数都可由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,定理2.6 S=，是联结词完备集。推论 以下联结词集都是完备的。（1）S1=，（2）S2=，（3）S3=，（4）S4=，（5）S5=，,定义2.8 pq(pq)pq(pq),定理2.7,都是联结词完备集,第三章命题逻辑的推理理论,3.1推理的形式结构,定义3.1设A1，A2An,B都是命题公式，若对于A1，A2An,B中命题变项的任一组赋值，或者A1A2An为假，或者A1A2An为真时，B为真，则称由前提A1，A2An推出B的推理有效或是正确的，并称B是有效的结论。,例3.1判断下列推理是否正确：(1)p,pqq(2)p,q p q定理3.1 命题公式A1，A2，An推B的推理正确当且仅当A1A2An 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）前提：pq,qr,ps,s 结论：r(pq),例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)个体域D1=N（N为自然数集合）(b)个体域D2=R(R为实数集合）,例4.4将下列命题符号化，并讨论它们的真值.(1)所有的人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必是亚洲人。,。,例4.5将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的二只兔子,4.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，i1,（5）量词符号：，（6）联结词符号：，（7）括号和逗号，（，），定义4.2 P的项定义如下（1）个体常项和个体变项是项。（2）若（x1,x2,xn)是任意n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项,（3）所有的项都是有限次使用规则（1）、（2）得到。定义4.3设R（x1,x2,xn)是P的任意n元谓词，t1,t2,tn是任意的n个项，则称R（t1,t2,tn）是P的原子公式。,定义4.4 P的合式公式定义如下（1）原子公式是合式公式。（2）若A是合式公式，则A是合式公式。（3）若A、B是合式公式AB、AB、AB、AB是合式公式。（4）若A是合式公式，则xA、xA也是合式公式。（5）只有有限次使用（1）（4）构成的符号串才是合式公式。,的。,定义4.5在公式xA和xA中，称x为指导变元，A为相应量词辖域。在xA和xA的辖域中，x的所有出现都称为約束出现，A中不是約束出现的其它变项均称为自由出现,例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 设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.7P的解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素的集合(c)DI中一些特定函数的集合(d)DI中特定谓词的集合,例4.8给定解释I如下个体域D=Na=0f(x,y)=x+y,g(x,y)=xyF(x,y)为x=y在I下，下列哪些公式为真？哪些公式为假？哪些公式真值不能确定？,（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),（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),定理4.1 封闭的公式在任何解释下都变成命题。,定义4.8 设A为一公式，若A在任何解释下均为真，则称A为永真式。若A在任何解释下均为假则称A为矛盾式。若至少存在一个解释使A为真则称A是可满足式。,定义4.9 设A。是含命题变项p1、p2、pn的命题公式，A1、A2、An是n个谓词公式,用Ai(1in)处处代替A。中的Pi，所得公式A称为A。的代换实例。,定理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.10判断下列公式的类型（1）xF(x)xF(x)（2）xyF(x、y)xyF(x、y)（3）x(F(x)G(x)yG(y),第五章一阶逻辑等值演算与推理,5.1一阶逻辑等值式与置换规则,定义5.1设A、B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B等值。记为AB,1.置换规则设（A）是含公式A的公式，（B）是用公式B取代（A）中所有的A之后的公式，若AB，则（A）（B）,2.换名规则 设A为一个公式，将A中某量词辖域中某約束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现的某个体变项符号，公式中其余部分不变，设所得公式为A，则A A。,3.代替规则 设A为一个公式，将A中某自由出现的个体变项的所有出现用A中未曾出现的某个体变项符号代替，公式A中其余部分不变，设所得公式为A，则A A。,例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.3 设个体域为D=a,b,c，将下面公式的量词消去(1)x(F(x)G(x)(2)x(F(x)yG(y)(3)xyF(x、y),例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.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.2 设A为一阶逻辑公式，若A具有如下行式：Q1 x1 Q2 x2 Qk xk B，则称A为前束泛式，其中Qi（1 ik)为或，B为不含量词的公式。,定理5.1一阶逻辑中任何公式都存在与之等值的前束泛式。,例5.6求下面公式的前束泛式（1）xF(x)xG(x)（2）xF(x)xG(x),例5.7求下面公式的前束泛式,填出每一步的依据（1）xF(x)xG(x)（3）xF(x)xG(x),例5.8 求下面公式的前束泛式(1)xF(x、y)yG(x、y)(2)(x1 F(x1、x2)x2 G(x2)x1 H(x1、x2、x3),5.2一阶逻辑的推理理论,定义5.3 自然推理系统F定义如下：1字母表 同一阶语言P的字母表2合式公式 同P的合式公式 3推理规则（1）前提引入规则（2）结论引入规则（3）置换规则（4）假言推理规则（5）附加规则（6）化简规则,（7）拒取式规则（8）假言三段论规则（9）析取三段论规则（10）构造性二难推理规则（11）合取引入规则（12）UI规则（13）UG规则（14）EG规则（15）EI规则,例5.9 设个体域为实数集合，F(x,y)为xy,指出在推理系统F中，以xyF(x,y)(真命题）为前提，推出xF(x,c)（假命题）的原因（1）xyF(x,y)前提引入（2）yF(z,y)UI规则（3）F(z,c)EI规则(4)x F(x,c)UG规则,例5.10在自然推理系统F中,构造下面推理的证明任何自然数都是整数，存在自然数，所以存在整数。个体域：实数集合R,例5.11在自然推理系统F中,构造下面推理的证明前提：x（F(x)G(x),x(F(x)H(x)结论:x(G(x)H(x),例5.12在自然推理系统F中,构造下面推理的证明不存在能表示分数的无理数，有理数都能表示分数，因此有理数都不是无理数,