1、离散数学离散数学第第1页页著名“苏格拉底三段论”：凡是人都是要死。苏格拉底是人。所以苏格拉底是要死。怎样判定该推理是否是正确？前提 p:凡是人都是要死。q:苏格拉底是人。结论 r:苏格拉底是要死。推理无效推理无效第第2页页一阶逻辑研究内容：将简单命题再细分，分析出个体词、谓词和量词个体词、谓词和量词，从而到达表示出个体与总体内在联络和数量关系个体与总体内在联络和数量关系，这就是一阶逻辑所研究内容，一阶逻辑又称为一阶谓词一阶谓词或谓词逻辑谓词逻辑。第第3页页第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式2.4 一阶逻辑推理理论
2、第第4页页2.1一一阶逻辑基本概念基本概念（1）个体词个体词是指所研究对象中能够独立存在详细或 抽象客体。1.个体词比如：张明，中国，精神，计算机。（2）个体常项个体常项是指表示详细或者特定客体个体词 称作个体常项，通惯用a，b，c表示。比如：6大于5。第第5页页2.1一一阶逻辑基本概念基本概念比如：x大于y。（3）个体变项个体变项是指表示抽象或者泛指客体个体词 称作个体常项，通惯用x，y，z表示。（4）个体域个体域是指个体变项取值范围为个体域（或称论域）。个体域能够是有穷集合，也能够是无穷集合。比如：1,2,3,4、a,b,c,d,e、自然数集合N0,1,2,3，实数集合Rx|x是实数宇宙间
3、一切事物集合（全总个体域）。第第6页页2.1一一阶逻辑基本概念基本概念2.谓词（1）谓词谓词是用来刻画个体词性质及个体之间相互关系词。当与一个个体相关时，它刻画了个体性质；当与两个或两个以上个体相关时，则刻画了个体之间关系。1)是无理数2)x是有理数。3)小王与小李同岁。4)x与y具相关系L第第7页页2.1一一阶逻辑基本概念基本概念比如：x大于y。（2）谓词常项谓词常项是指表示详细性质或关系谓词称为谓词常项，通惯用F，G，H，表示。（3）谓词变项谓词变项是表示抽象或泛指性质或关系谓词称为谓词变项，惯用F，G，H，表示。注：n元谓词并不是命题。（4）n n元谓词元谓词P P（x x1 1，x x
4、2 2，x xn n）表示含有n（n0）个命题变项：当n=1时，P（x1）表示x1含有性质P；当n1时，表示x1，x2xn具相关系P。第第8页页2.1一一阶逻辑基本概念基本概念注：命题能够表示成0元谓词，命题是特殊谓词。（5）0 0元谓词元谓词表示不含有个体变项谓词。比如：F（a），G（a，b）。例1：将以下命题在一阶逻辑中用0元谓词符号化，并讨论它们 真值。1)只有2是素数，4才是素数。2)假如5大于4，则4大于6。3)假如张明比李民高，李民比赵亮高，则张明比赵亮高。第第9页页2.1一一阶逻辑基本概念基本概念3.量词（1）量词量词是表示个体常项或变项之间数量关系词。（2）全称量词全称量词是表
5、示日惯用语中“一切”、“全部”、“每一个”、“任意”、“凡是”、“都”等词，可符号化为，并用x，y等表示个体域中全部个体，用xF(x)，yG(y)表示个体域中全部个体都有性质F和都有性质G。（3）存在量词存在量词是表示日惯用语中“存在”、“有一个”、“有”、“最少有一个”等词，可符号化为，并用x，y表示个体域中有个体，用xF(x),yG(y)表示个体域中有个体有 性质F和有有性质G。第第10页页2.1一一阶逻辑基本概念基本概念例2：在个体域分别限制（a）和（b）条件时，将下面两个命题 符号化：1)凡人都呼吸。2)有人用左手写字。其中：（a）个体域D1为人类集合。（b）个体域D2为全总个体域。（
6、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)同一命题，在不一样域中命题符号化形式也不一样！第第11页页2.1一一阶逻辑基本概念基本概念例3：在个体域分别限制（a）和（b）条件时，将下面两个命题 符号化：1)对于任意x，都有x*x3x+2=(x-1)(x-2)。2)存在x，使得x+5=3。其中：（a）个体域D1=N(N为自然数集合)。（b）个体域D2=R(R为实数集合)。（a）：令F（x）：x*x3x+2=(x-1)(x-2)。G（x）：x+5=
7、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）真命题同一命题，在不一样域中真值可能不一样。第第12页页2.1一一阶逻辑基本概念基本概念例4：将以下命题符号化，并讨论真值：1)凡是偶数均能被2整除。2)存在着偶素数。（4）说明：说明：本书中，讨论命题符号化时，若没有指明个体域，就采取全总个体域。3)没有不犯错误人。4)在北京工作人未必都是北京人。5)一切人都不一样高。6)每个自然数都有后继数。第第13页页2.1一一阶逻辑基本概念基本概念1)分析命题中表示性质和关系谓词，分别符号化为一元
8、和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)第第14页页2.1一一阶逻辑基本概念基本概念例5：将以下命题符号化，并讨论真值：1)一切人都不一样高。2)每个自然数都有后继数。3)有自然数无先驱数。第第15页页第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑基本概念2.2 一阶逻
9、辑合式公式及解释2.3 一阶逻辑等值式2.4 一阶逻辑推理理论第第16页页2.2一一阶逻辑合式公式及解合式公式及解释1.一阶语言字母表（定义2.1）一、一阶语言(1)个体常项：a,b,c,(2)个体变项：x,y,z,(3)函数符号：f,g,h,(5)量词符号：，(6)连接词符号：，(4)谓词符号：F，G，H，(7)括号与逗号：（，），第第17页页2.2一一阶逻辑合式公式及解合式公式及解释2.一阶语言项（定义2.2）(1)个体常项和个体变项是项(2)若（x1,x2,xn）是任意n元函数，t1,t2,，tn是任意n个项，则（t1,t2,tn）是项。(3)全部项都是有限次使用（1）,（2）得到。比如
10、：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)第第18页页2.2一一阶逻辑合式公式及解合式公式及解释3.一阶语言原子公式（定义2.3）设R（x1,x2,xn）是任意n元谓词，t1,t2,tn是一阶语言任意n个项，则称R(t1,t2,tn)是一阶语言原子公式。比如：F（x）,G(y),H(x,y),L(x,y)第第19页页2.2一一阶逻辑合式公式及解合式公式及解释4.一阶语言合式公式（定义2.4）(1)原子公式是合式公式(2)若A是合式公式，则(A)是合式公式。(3)若A，
11、B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式。(4)若A是合式公式，则xA，xA也是合式公式。(5)只有有限次地使用（1）（4）组成符号串才是合 式公式。第第20页页2.2一一阶逻辑合式公式及解合式公式及解释1.指导变元、辖域、约束出现、自由出现（定义2.5）二、与合式公式相关概念在公式xA和xA中，称x为指导变元指导变元，A为对应量词辖域辖域。在x和x辖域中，x全部出现均为约束出约束出现现，A中不是约束出现其它变项均称为自由出现自由出现。第第21页页2.2一一阶逻辑合式公式及解合式公式及解释例1：指出以下各公式中指导变项、量词辖域、个体变项 自由出现和约束出现。2)x(
12、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)第第22页页2.2一一阶逻辑合式公式及解合式公式及解释2.封闭公式（定义2.6）设A是任意公式，若A中不含自由出现个体变项，则称A为封闭公式封闭公式，简称闭式闭式。比如：x(F(x)G(x),xy(F(x)G(x,y)闭式 x(F(x)G(x,y),xyL(x,y,z)不是闭式换名规则换名规则 将量词辖域中出现某个约束出现个体变项及对应指导变项，该成另一个辖域中未曾出现过个体变项符号，公式中其余部分不变。代替规则代替
13、规则 对某个自由出现个体变项用与原公式中全部个体变项符号不一样变项符号去代替，且处处代替。第第23页页2.2一一阶逻辑合式公式及解合式公式及解释1.定义2.7三、解释（a）非空个体域DI封闭公式在任何解释下都变成命题 解释I由下面4部分组成：（b）DI中一些特定元素集合（c）DI上特定函数集合（d）DI上特定谓词集合第第24页页2.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
14、(f(x,a),y)F(f(y,a),x)9)xF(f(x,x),g(x,x)4)xF(g(x,y),z)第第25页页2.2一一阶逻辑合式公式及解合式公式及解释2.说明（2）在解释公式A中个体变项均取值于DI（6）被解释公式不一定全部包含解释中四个部分（1）在解释定义中引进了几个元语言符号，如：（3）若A中含个体常项，就解释成（4）为第i个n元函数（5）为第i个n元谓词第第26页页2.2一一阶逻辑合式公式及解合式公式及解释1.定义2.8三、公式类型设A为一公式，若A在任何解释下均为真，则称A为永真式（或称逻辑有效式）。若A在任何解释下均为假，则称A为矛盾式（或永假式）。若最少存在一个解释使A为
15、真，则称A是可满足式。2.怎样判断公式类型？在一阶逻辑中，因为公式复杂性和解释多样性，到当前为止，没有找到一个可行方法来判断公式类型。第第27页页2.2一一阶逻辑合式公式及解合式公式及解释3.代换实例（定义2.9）设A0是含命题变项p1,p2,pn命题公式，A1,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代换实例。重言式代换实例都是永真式，矛盾式代换实例都是矛盾式。第第28页页2.2一一阶逻辑合式公式及解合式公式及解释例3：判断以下公式哪些是永真式，哪
16、些是矛盾式：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)能够依据命题公式重言式代换实例来判断公式类型！第第29页页2.2一一阶逻辑合式公式及解合式公式及解释例4：判断以下公式类型：1)xF(x)xF(x)2)xyF(x,y)xyF(x,y)3)x(F(x)G(x)yG(y)经过结构一些特殊解释，来判断公式类型！第第30页页第二章第二章 一一阶逻辑基本概念基本概念2.1 一阶逻辑基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式2.4 一阶逻辑推理理论第第31页页2.3
17、 一一阶逻辑等等值式式将下面命题符号化：没有不犯错误人。(1)x(F(x)G(x)(2)x(F(x)G(x)在一阶逻辑中，有些命题能够有不一样符号化形式！第第32页页2.3 一一阶逻辑等等值式式1.等值式（定义2.10）一、一阶逻辑等值式设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值。记作AB，成AB是等值式。等值式。2.一阶逻辑中几个基本等值式(1)命题逻辑中16组等值式比如：xF(x)xF(x)F(x)G(x)F(x)G(x)第第33页页2.3 一一阶逻辑等等值式式(2)一阶逻辑中4组特殊等值式1)消去量词等值式设个体域为有限集Da1，a2，an，则有 xA(x)A(a
18、1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)2)量词否定等值式设A(x)为任意含自由出现个体变项x公式，则 xA(x)xA(x)xA(x)xA(x)第第34页页2.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)第第35页页2.3 一一阶逻辑等等值式式4)量词分配等值式设A(x)，B(x)
19、为任意含自由出现个体变项x公式，则 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)第第36页页2.3 一一阶逻辑等等值式式1.置换规则二、一阶逻辑置换规则设(A)是含公式A公式，(B)是公式B取代(A)中全部A之后公式，若AB，则(A)(B)。2.换名规则设A为一公式，将A中某量词辖域中某约束变项全部出现及对应指导变元，改成该量词辖域中未曾出现过某个变项符号，公式中其余部分不变，所得公式A，则AA。第第37页页2.3 一一阶逻辑等等值式式3.代替规则设A为一公式，将A中某个自由出现个体变项全部出现用A中未曾出现过个体变项符号代替，A中其余部分不变，所得公式为A
20、，则AA。第第38页页2.3 一一阶逻辑等等值式式例1：将以下公式化成与之等值公式，使其没有既是约束出现又是自由出现个体变项。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)利用置换规则、换名规则、代替规则消除既是约束出现又是自由出现个体变元！第第39页页2.3 一一阶逻辑等等值式式例2：证实：2)x(A(x)B(x)xA(x)xB(x)1)x(A(x)B(x)xA(x)xB(x)利用结构解释方法来证实两个谓词公式不等值！第第40页页2.3 一一阶逻辑等等值式式例3
21、：设个体域为Da，b，c将下面各公式中量词消去：2)x(F(x)yG(y)1)x(F(x)G(x)首先，将量词辖域缩小。然后，层层脱去量词，全称量词用全部个体属性或关系合取表示，存在量词用全部个体属性或关系析取表示。3)xyF(x,y)第第41页页2.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下求以下
22、各式真值。1)x(F(x)G(x,a)2)x(F(f(x)G(x,f(x)3)xyL(x,y)4)yxL(x,y)量词次序不能随意调换！第第42页页2.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)利用一阶逻辑等值演算公式以及命题逻辑等值演算公式来证实两个公式是否等值！第第43页页2.3 一一阶逻辑等等值式式设A为一个一阶逻辑公式，若A含有以下形式Q1x1Q2x2Q
23、kxkB则称A为前束范式，其中Qi(1=iy。指出在推理系统F中，以xyF(x,y)(真命题)为前提，推出xF(x,c)(假命题)原因。xyF(x,y)yF(z,y)F(z,c)xF(x,c)第第52页页5.3一一阶逻辑推理理推理理论例2：在自然推理系统F中，结构下面推理证实：任何自然数都是整数，存在着自然数。所以存在着整数。个 体域为实数集合R。例3：在自然推理系统F中，结构下面推理证实。前提：x(F(x)G(x),x(F(x)H(x)结论：x(G(x)H(x)第第53页页5.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)第第54页页
