《离散数学第五版第二章》由会员分享，可在线阅读，更多相关《离散数学第五版第二章（54页珍藏版）》请在金锄头文库上搜索。
1、1离散数学离散数学精选精选ppt2著名的“苏格拉底三段论”： 凡是人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。如何判定该推理是否是正确的？前提 p:凡是人都是要死的。q:苏格拉底是人。结论 r:苏格拉底是要死的。推理无效推理无效精选精选ppt3一阶逻辑的研究内容：将简单命题再细分，分析出个体个体词、谓词和量和量词，从而达到表达出个体与个体与总体的内在体的内在联系和数量关系系和数量关系，这就是一阶逻辑所研究的内容，一阶逻辑又称为一一阶谓词或谓词逻辑。精选精选ppt4第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑的基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式2.
2、4 一阶逻辑推理理论精选精选ppt52.1一一阶逻辑的基本概念的基本概念（1）个体个体词是指所研究对象中可以独立存在的具体或 抽象的客体。1.个体词例如：张明，中国，精神，计算机。（2）个体常个体常项是指表示具体或者特定的客体的个体词 称作个体常项，通常用a，b，c表示。例如：6大于5。精选精选ppt62.1一一阶逻辑的基本概念的基本概念例如：x大于y。（3）个体个体变项是指表示抽象或者泛指的客体的个体词 称作个体常项，通常用x，y，z表示。（4）个体域个体域是指个体变项的取值范围为个体域（或称论域）。个体域可以是有穷集合，也可以是无穷集合。例如：1,2,3,4、a,b,c,d,e、自然数集合
3、N0,1,2,3，实数集合Rx|x是实数宇宙间一切事物的集合（全总个体域）。精选精选ppt72.1一一阶逻辑的基本概念的基本概念2.谓词（1）谓词是用来刻画个体词性质及个体之间相互关系的词。当与一个个体相关时，它刻画了个体的性质；当与两个或两个以上个体相关时，则刻画了个体之间的关系。1) 是无理数2)x是有理数。3)小王与小李同岁。4)x与y具有关系L精选精选ppt82.1一一阶逻辑的基本概念的基本概念例如：x大于y。（2）谓词常常项是指表示具体性质或关系的谓词称为谓词常项，通常用F，G，H，表示。（3）谓词变项是表示抽象的或泛指的性质或关系的谓词称为谓词变项，常用F，G，H，表示。注：n元谓
4、词并不是命题。（4）n n元元谓词P P（x x1 1，x x2 2，x xn n）表示含有n（n0）个命题变项：当n=1时，P（x1）表示x1具有性质P；当n1时，表示x1，x2xn具有关系P。精选精选ppt92.1一一阶逻辑的基本概念的基本概念注：命题可以表示成0元谓词，命题是特殊的谓词。（5） 0 0元元谓词表示不含有个体变项的谓词。例如：F（a），G（a，b）。例1：将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的 真值。1)只有2是素数，4才是素数。2)如果5大于4，则4大于6。3)如果张明比李民高，李民比赵亮高，则张明比赵亮高。精选精选ppt102.1一一阶逻辑的基本概念的基本
5、概念3.量词（1）量量词是表示个体常项或变项之间数量关系的词。（2）全称量全称量词是表示日常用语中“一切的”、“所有的”、“每一个”、“任意的”、“凡是”、“都”等词，可符号化为，并用x，y等表示个体域中的所有个体，用xF(x)，yG(y)表示个体域中的所有个体都有性质F和都有性质G。（3）存在量存在量词是表示日常用语中“存在”、“有一个”、“有的”、“至少有一个”等词，可符号化为，并用x，y表示个体域中有的个体，用xF(x),yG(y)表示个体域中有的个体有性质F和有的有性质G 。精选精选ppt112.1一一阶逻辑的基本概念的基本概念例2：在个体域分别限制（a）和（b）条件时，将下面两个命题
6、 符号化：1)凡人都呼吸。2)有的人用左手写字。其中：（a）个体域D1为人类集合。 （b）个体域D2为全总个体域。（a）：令F（x）：x呼吸。G（x）：x用左手写字。1）xF（x）2）xG（x）（b）：令F（x）：x呼吸。G（x）：x用左手写字。M（x）：x是人。1）x(M(x) F(x)2）x(M(x)G(x)同一命题，在不同的域中命题符号化的形式也不同！精选精选ppt122.1一一阶逻辑的基本概念的基本概念例3：在个体域分别限制（a）和（b）条件时，将下面两个命题 符号化：1)对于任意的x，均有x*x3x+2=(x-1)(x-2)。2)存在x，使得x+5=3。其中：（a）个体域D1=N(N
7、为自然数集合)。 （b）个体域D2=R(R为实数集合)。（a）：令F（x）：x*x3x+2=(x-1)(x-2) 。G（x）：x+5=3。1）xF（x） 真命题2）xG（x） 假命题（b）：令F（x）：x*x3x+2=(x-1)(x-2) 。G（x）：x+5=3。1）xF（x） 真命题2）xG（x） 真命题同一命题，在不同域中的真值可能不同。精选精选ppt132.1一一阶逻辑的基本概念的基本概念例4：将下列命题符号化，并讨论真值：1)凡是偶数均能被2整除。2)存在着偶素数。（4）说明：明：本书中，讨论命题符号化时，若没有指明个体域，就采用全总个体域。3)没有不犯错误的人。4)在北京工作的人未必
8、都是北京人。5)一切人都不一样高。6)每个自然数都有后继数。精选精选ppt142.1一一阶逻辑的基本概念的基本概念1)分析命题中表示性质和关系的谓词，分别符号化为一元和n（n=2）元谓词。2)根据命题的实际意义选用全称量词或存在量词。（5）注意：注意：3)一般来说，多个量词出现时，它们的顺序不能随意调换。4)有些命题的符号化形式不仅一种。5)在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。6)个体域为有限集D=a1,a2,an，则：xA（x）=A(a1)A(a2)A(an)xA（x）=A(a1)A(a2)A(an)精选精选ppt152.1一一阶逻辑的基本概念的基本概念例5：将下列
9、命题符号化，并讨论真值：1)一切人都不一样高。2)每个自然数都有后继数。3)有的自然数无先驱数。精选精选ppt16第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑的基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式2.4 一阶逻辑推理理论精选精选ppt172.2一一阶逻辑合式公式及解合式公式及解释1.一阶语言的字母表（定义2.1）一、一阶语言(1)个体常项：a,b,c,(2)个体变项：x,y,z,(3)函数符号：f,g,h,(5)量词符号：，(6)连接词符号：，(4)谓词符号：F，G，H，(7)括号与逗号：（，），精选精选ppt182.2一一阶逻辑合式公式及解合式公式及解释2
10、.一阶语言的项（定义2.2）(1)个体常项和个体变项是项(2)若（x1,x2,xn）是任意的n元函数，t1,t2,， tn是任意的n个项，则（t1,t2,tn）是项。(3)所有的项都是有限次使用（1）,（2）得到的。例如：a,b,x,y,f(x,y)=x+y,g(x,y)=x-y,h(x,y)=x*y，f(a,g(x,y)=a+(x-y)g(h(x,y),f(a,b)=x*y-(a+b)精选精选ppt192.2一一阶逻辑合式公式及解合式公式及解释3.一阶语言的原子公式（定义2.3）设R（x1,x2,xn）是任意的n元谓词，t1,t2,tn是一阶语言的任意n个项，则称R(t1,t2,tn)是一阶
11、语言的原子公式。例如：F（x）,G(y),H(x,y),L(x,y)精选精选ppt202.2一一阶逻辑合式公式及解合式公式及解释4.一阶语言的合式公式（定义2.4）(1)原子公式是合式公式(2)若A是合式公式，则(A)是合式公式。(3)若A，B是合式公式，则(AB),(AB),(AB),(AB) 也是合式公式。(4)若A是合式公式，则xA，xA也是合式公式。(5)只有有限次地使用（1）（4）构成的符号串才是合 式公式。精选精选ppt212.2一一阶逻辑合式公式及解合式公式及解释1.指导变元、辖域、约束出现、自由出现（定义2.5）二、与合式公式相关的概念在公式xA和xA中，称x为指指导变元元，A
12、为相应量词的辖域域。在x和x的辖域中，x的所有出现均为约束出束出现，A中不是约束出现的其它变项均称为自由出自由出现。精选精选ppt222.2一一阶逻辑合式公式及解合式公式及解释例1：指出下列各公式中的指导变项、量词的辖域、个体变项的 自由出现和约束出现。2)x(F(x)yH(x,y)3)xF(x)G(x,y)4)xy(R(x,y)L(y,z)xH(x,y)1)x(F(x,y)G(x,z)5)x(F(x)G(y)y(H(x)L(x,y,z)精选精选ppt232.2一一阶逻辑合式公式及解合式公式及解释2.封闭的公式（定义2.6）设A是任意的公式，若A中不含自由出现的个体变项，则称A为封封闭的公式的
13、公式，简称闭式式。例如：x(F(x)G(x),xy(F(x)G(x,y) 闭式 x(F(x)G(x,y),xyL(x,y,z) 不是闭式换名名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，该成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变。代替代替规则 对某个自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。精选精选ppt242.2一一阶逻辑合式公式及解合式公式及解释1.定义2.7三、解释（a）非空个体域DI封闭公式在任何解释下都变成命题 的解释I由下面4部分组成：（b）DI中一些特定元素的集合（c）DI上特定函数集合（d）DI上特定谓
14、词集合精选精选ppt252.2一一阶逻辑合式公式及解合式公式及解释2)F(f(x,a),y)F(g(x,y),z)3)F(g(x,y),g(y,z)1)F(f(x,y),g(x,y)5)xF(g(x,a),x)F(x,y)6)xF(g(x,a),x)8)xyzF(f(x,y),z)7)xy(F(f(x,a),y)F(f(y,a),x)9)xF(f(x,x),g(x,x)4)xF(g(x,y),z)精选精选ppt262.2一一阶逻辑合式公式及解合式公式及解释2.说明（2）在解释的公式A中的个体变项均取值于DI（6）被解释的公式不一定全部包含解释中的四个部分（1）在解释的定义中引进了几个元语言符号
15、，如：（3）若A中含个体常项，就解释成（4） 为第i个n元函数（5） 为第i个n元谓词精选精选ppt272.2一一阶逻辑合式公式及解合式公式及解释1.定义2.8三、公式的类型设A为一公式，若A在任何解释下均为真，则称A为永真式（或称逻辑有效式）。若A在任何解释下均为假，则称A为矛盾式（或永假式）。若至少存在一个解释使A为真，则称A是可满足式。2.如何判断公式的类型？在一阶逻辑中，由于公式的复杂性和解释的多样性，到目前为止，没有找到一种可行的方法来判断公式的类型。精选精选ppt282.2一一阶逻辑合式公式及解合式公式及解释3.代换实例（定义2.9）设A0是含命题变项p1,p2,pn的命题公式，A
16、1,A2,An是n个谓词公式，用Ai（1=I=n）处处代替A0中的pi，所得公式A称为A0的代换实例。例如：F(x)G(x),xF(x)yG(y)都是pq的代换实例，而x(F(x)G(x)不是pq的代换实例。重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。精选精选ppt292.2一一阶逻辑合式公式及解合式公式及解释例3：判断下列公式哪些是永真式，哪些是矛盾式：2)x(F(x)G(x)3)xF(x)(xyG(x,y)xF(x)1)x(F(x)G(x)5)xF(x)(xF(x)yG(y)4)(xF(x)yG(y)yG(y)可以根据命题公式重言式的代换实例来判断公式的类型！精选精选ppt30
17、2.2一一阶逻辑合式公式及解合式公式及解释例4：判断下列公式的类型：1)xF(x)xF(x)2)xyF(x,y)xyF(x,y)3)x(F(x)G(x)yG(y)通过构造一些特殊的解释，来判断公式的类型！精选精选ppt31第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑的基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式2.4 一阶逻辑推理理论精选精选ppt322.3 一一阶逻辑等等值式式将下面命题符号化： 没有不犯错误的人。(1)x(F(x)G(x)(2)x(F(x)G(x)在一阶逻辑中，有些命题可以有不同的符号化形式！精选精选ppt332.3 一一阶逻辑等等值式式1.等值
18、式（定义2.10）一、一阶逻辑等值式设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记作AB，成AB是等等值式。式。2.一阶逻辑中的几个基本的等值式(1)命题逻辑中16组等值式例如：xF(x)xF(x) F(x)G(x)F(x)G(x)精选精选ppt342.3 一一阶逻辑等等值式式(2)一阶逻辑中的4组特殊的等值式1)消去量词等值式设个体域为有限集Da1，a2，an，则有 xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an)2)量词否定等值式设A(x)为任意的含自由出现个体变项x的公式，则 xA(x)xA(x) xA(x)xA(x)精选精选p
19、pt352.3 一一阶逻辑等等值式式3)量词辖域收缩与扩张等值式设A(x)为任意的含自由出现个体变项x的公式，B中不含x的出现，则 x(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)x(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)精选精选ppt362.3 一一阶逻辑等等值式式4)量词分配等值式设A(x)，B(x)为任意的含自由出现个体变项x的公式，则 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)精选精选ppt372.3 一一阶逻辑等等
20、值式式1.置换规则二、一阶逻辑置换规则设(A)是含公式A的公式，(B)是公式B取代(A)中的所有的A之后的公式，若AB，则(A)(B)。2.换名规则设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个变项符号，公式中其余部分不变，所得公式A，则AA。精选精选ppt382.3 一一阶逻辑等等值式式3.代替规则设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，所得公式为A，则AA。精选精选ppt392.3 一一阶逻辑等等值式式例1：将下列公式化成与之等值的公式，使其没有既是约束出现的又是自由出
21、现的个体变项。2)x(F(x,y)yG(x,y,z)3)xy(R(x,y)L(y,z)xH(x,y)1)xF(x,y,z)yG(x,y,z)4)x(F(x)G(y)y(H(x)L(x,y,z)利用置换规则、换名规则、代替规则消除既是约束出现又是自由出现的个体变元！精选精选ppt402.3 一一阶逻辑等等值式式例2：证明：2)x(A(x)B(x)xA(x)xB(x)1)x(A(x)B(x)xA(x)xB(x)利用构造解释的方法来证明两个谓词公式不等值！精选精选ppt412.3 一一阶逻辑等等值式式例3：设个体域为Da，b，c将下面各公式中的量词消去：2)x(F(x)yG(y)1)x(F(x)G(
22、x)首先，将量词的辖域缩小。然后，层层脱去量词，全称量词用所有个体属性或关系的合取表示，存在量词用所有个体属性或关系的析取表示。3)xyF(x,y)精选精选ppt422.3 一一阶逻辑等等值式式例4：给定解释I如下：b)D中的特定元素a2a)个体域D2，3c)D上的特定函数f(x)为：f(2)=3,f(3)=2d)D上的特定谓词G(x,y)为：G(2,2)=G(2,3)=G(3,2)=1,G(3,3)=0.L(x,y)为：L(2,2)=L(3,3)=L(3,2)=0.F(x)为：F(2)=0,F(3)=1.在I下求下列各式的真值。1)x(F(x)G(x,a)2)x(F(f(x)G(x,f(x)
23、3)xyL(x,y)4)yxL(x,y)量词的顺序不能随意调换！精选精选ppt432.3 一一阶逻辑等等值式式例5：证明下列各等值式1)x(M(x)F(x)x(M(x)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(x) H(x,y)4)xy(F(x)G(y)L(x,y)xy(F(x)G(x)L(x,y)利用一阶逻辑等值演算公式以及命题逻辑等值演算公式来证明两个公式是否等值！精选精选ppt442.3 一一阶逻辑等等值式式设A为一个一阶逻辑公式，若A具有如下形式Q1x1Q2x2QkxkB则称A为前束范式，其中Qi(1=iy。指出在推理系
24、统F中， 以xyF(x,y)(真命题)为前提，推出xF(x,c)(假命题)的 原因 。xyF(x,y)yF(z,y)F(z,c)xF(x,c)精选精选ppt535.3一一阶逻辑的推理理的推理理论例2：在自然推理系统F中，构造下面推理的证明： 任何自然数都是整数，存在着自然数。所以存在着整数。个 体域为实数集合R。例3：在自然推理系统F中，构造下面推理的证明。前提：x(F(x)G(x),x(F(x)H(x)结论：x(G(x)H(x)精选精选ppt545.3一一阶逻辑的推理理的推理理论例4：在自然推理系统F中，构造下面推理的证明： 不存在能表示成分数的无理数，有理数都能表示成分数。因 此，有理数都不是无理数。例5：在自然推理系统F中，构造下面推理的证明。(1)前提：xF(x),xF(x)y(F(y)G(y)R(y) 结论：xR(x)(2)前提：xF(x),x(F(x)(G(y)R(x) 结论：x(F(x)R(x)精选精选ppt
