《离散数学第五版第二章(耿素云、屈婉玲、张立昂编著)》由会员分享，可在线阅读，更多相关《离散数学第五版第二章(耿素云、屈婉玲、张立昂编著)（54页珍藏版）》请在金锄头文库上搜索。
1、离散数学,著名的“苏格拉底三段论”： 凡是人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,如何判定该推理是否是正确的？,前提 p:凡是人都是要死的。 q:苏格拉底是人。,结论 r:苏格拉底是要死的。,推理无效,一阶逻辑的研究内容：,将简单命题再细分，分析出个体词、谓词和量词，从 而达到表达出个体与总体的内在联系和数量关系，这就是一 阶逻辑所研究的内容，一阶逻辑又称为一阶谓词或谓词逻辑。,第二章 一阶逻辑基本概念,2.1 一阶逻辑的基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式 2.4 一阶逻辑推理理论,2.1一阶逻辑的基本概念,（1）个体词是指所研究对象中可以独立存在
2、的具体或 抽象的客体。,个体词,例如：张明，中国，精神，计算机。,（2）个体常项是指表示具体或者特定的客体的个体词 称作个体常项，通常用a，b，c表示。,例如：6大于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是实数 宇宙间一切事物的集合（全总个体域）。,2.1一阶逻辑的基本概念,谓词,（1）谓词是用来刻画个体词
3、性质及个体之间相互关系 的词。当与一个个体相关时，它刻画了个体的性 质；当与两个或两个以上个体相关时，则刻画了 个体之间的关系。,是无理数 x是有理数。 小王与小李同岁。 x与y具有关系L,2.1一阶逻辑的基本概念,例如：x大于y。,（2）谓词常项是指表示具体性质或关系的谓词称为谓词 常项，通常用F，G，H，表示。,（3）谓词变项是表示抽象的或泛指的性质或关系的谓词 称为谓词变项，常用F，G，H，表示。,注：n元谓词并不是命题。,（4）n元谓词P（x1，x2，xn）表示含有n（n0） 个命题变项：当n=1时，P（x1）表示x1具有性质 P；当n1时，表示x1，x2xn具有关系P。,2.1一阶逻
4、辑的基本概念,注：命题可以表示成0元谓词，命题是特殊的谓词。,（5） 0元谓词表示不含有个体变项的谓词。,例如：F（a），G（a，b）。,例1：将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的 真值。,只有2是素数，4才是素数。,如果5大于4，则4大于6。,如果张明比李民高，李民比赵亮高，则张明比赵亮高。,2.1一阶逻辑的基本概念,量词,（1）量词是表示个体常项或变项之间数量关系的词。,（2）全称量词是表示日常用语中“一切的”、“所有 的”、“每一个”、“任意的”、“凡是”、 “都”等词，可符号化为，并用x，y等表示 个体域中的所有个体，用xF(x)，yG(y)表示 个体域中的所有个体都有
5、性质F和都有性质G。,（3）存在量词是表示日常用语中“存在”、“有一 个”、“有的”、“至少有一个”等词，可符号 化为，并用x，y表示个体域中有的个体， 用xF(x),yG(y)表示个体域中有的个体有 性质F和有的有性质G 。,2.1一阶逻辑的基本概念,例2：在个体域分别限制（a）和（b）条件时，将下面两个命题 符号化：,凡人都呼吸。,有的人用左手写字。,其中：（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
6、(x) F(x) 2）x(M(x)G(x),同一命题，在不同的域中命题符号化的形式也不同！,2.1一阶逻辑的基本概念,例3：在个体域分别限制（a）和（b）条件时，将下面两个命题 符号化：,对于任意的x，均有x*x3x+2=(x-1)(x-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=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）
7、真命题 2）xG（x） 真命题,同一命题，在不同域中的真值可能不同。,2.1一阶逻辑的基本概念,例4：将下列命题符号化，并讨论真值：,凡是偶数均能被2整除。,存在着偶素数。,（4）说明：本书中，讨论命题符号化时，若没有指 明个体域，就采用全总个体域。,没有不犯错误的人。,在北京工作的人未必都是北京人。,一切人都不一样高。,每个自然数都有后继数。,2.1一阶逻辑的基本概念,分析命题中表示性质和关系的谓词，分别符号化为一元和n（n=2）元谓词。,根据命题的实际意义选用全称量词或存在量词。,（5）注意：,一般来说，多个量词出现时，它们的顺序不能随意调换。,有些命题的符号化形式不仅一种。,在引入特性谓
8、词后，使用全称量词与存在量词符号化的形式是不同的。,个体域为有限集D=a1,a2,an，则： xA（x）=A(a1)A(a2)A(an) xA（x）=A(a1)A(a2)A(an),2.1一阶逻辑的基本概念,例5：将下列命题符号化，并讨论真值：,一切人都不一样高。,每个自然数都有后继数。,有的自然数无先驱数。,第二章 一阶逻辑基本概念,2.1 一阶逻辑的基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式 2.4 一阶逻辑推理理论,2.2一阶逻辑合式公式及解释,一阶语言的字母表（定义2.1）,一、一阶语言,(1)个体常项：a,b,c,(2)个体变项：x,y,z,(3)函数符号：f,
9、g,h,(5)量词符号：，,(6)连接词符号：，,(4)谓词符号：F，G，H，,(7)括号与逗号：（，），,2.2一阶逻辑合式公式及解释,一阶语言的项（定义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),2.2一阶逻辑合式公式及解释,一阶语言的原子公式（定义2.3
10、）,设R（x1,x2,xn）是任意的n元谓词，t1,t2,tn 是一阶语言的任意n个项，则称R(t1,t2,tn)是一阶 语言的原子公式。,例如：F（x）,G(y),H(x,y),L(x,y),2.2一阶逻辑合式公式及解释,一阶语言的合式公式（定义2.4）,(1)原子公式是合式公式,(2)若A是合式公式，则(A)是合式公式。,(3)若A，B是合式公式，则(AB),(AB),(AB),(AB) 也是合式公式。,(4)若A是合式公式，则xA，xA也是合式公式。,(5)只有有限次地使用（1）（4）构成的符号串才是合 式公式。,2.2一阶逻辑合式公式及解释,指导变元、辖域、约束出现、自由出现（定义2.
11、5）,二、与合式公式相关的概念,在公式xA和xA中，称x为指导变元，A为相应量词的 辖域。在x和x的辖域中，x的所有出现均为约束出 现，A中不是约束出现的其它变项均称为自由出现。,2.2一阶逻辑合式公式及解释,例1：指出下列各公式中的指导变项、量词的辖域、个体变项的 自由出现和约束出现。,x(F(x)yH(x,y),xF(x)G(x,y),xy(R(x,y)L(y,z)xH(x,y),x(F(x,y)G(x,z),x(F(x)G(y)y(H(x)L(x,y,z),2.2一阶逻辑合式公式及解释,封闭的公式（定义2.6）,设A是任意的公式，若A中不含自由出现的个体变项，则 称A为封闭的公式，简称闭
12、式。,例如：x(F(x)G(x),xy(F(x)G(x,y) 闭式 x(F(x)G(x,y),xyL(x,y,z) 不是闭式,换名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，该成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变。,代替规则 对某个自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。,2.2一阶逻辑合式公式及解释,定义2.7,三、解释,（a）非空个体域DI,封闭公式在任何解释下都变成命题, 的解释I由下面4部分组成：,（b）DI中一些特定元素的集合,（c）DI上特定函数集合,（d）DI上特定谓词集合,2.2一阶逻辑合式公式及
13、解释,F(f(x,a),y)F(g(x,y),z),F(g(x,y),g(y,z),F(f(x,y),g(x,y),xF(g(x,a),x)F(x,y),xF(g(x,a),x),xyzF(f(x,y),z),xy(F(f(x,a),y)F(f(y,a),x),xF(f(x,x),g(x,x),xF(g(x,y),z),2.2一阶逻辑合式公式及解释,说明,（2）在解释的公式A中的个体变项均取值于DI,（6）被解释的公式不一定全部包含解释中的四个部分,（1）在解释的定义中引进了几个元语言符号， 如：,（3）若A中含个体常项，就解释成,（4） 为第i个n元函数,（5） 为第i个n元谓词,2.2一阶
14、逻辑合式公式及解释,定义2.8,三、公式的类型,设A为一公式，若A在任何解释下均为真，则称A为永真式 （或称逻辑有效式）。若A在任何解释下均为假，则称A为 矛盾式（或永假式）。若至少存在一个解释使A为真，则 称A是可满足式。,如何判断公式的类型？,在一阶逻辑中，由于公式的复杂性和解释的多样性，到 目前为止，没有找到一种可行的方法来判断公式的类型。,2.2一阶逻辑合式公式及解释,代换实例（定义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(
15、y)都是pq的代换实例，而 x(F(x)G(x)不是pq的代换实例。,重言式的代换实例都是永真式，矛盾式的代换实例都是 矛盾式。,2.2一阶逻辑合式公式及解释,例3：判断下列公式哪些是永真式，哪些是矛盾式：,x(F(x)G(x),xF(x)(xyG(x,y)xF(x),x(F(x)G(x),xF(x)(xF(x)yG(y),(xF(x)yG(y)yG(y),可以根据命题公式重言式的代换实例来判断公式的类型！,2.2一阶逻辑合式公式及解释,例4：判断下列公式的类型：,xF(x)xF(x),xyF(x,y)xyF(x,y),x(F(x)G(x)yG(y),通过构造一些特殊的解释，来判断公式的类型！,第二章 一阶逻辑基本概念,2.1 一阶逻辑的基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式 2.4 一阶逻辑推理理论,2.3 一阶逻辑等值式,将下面命题符号化： 没有不犯错误的人。,(1)x(F(x)G(x),(2)x(F(x)G(x),在一阶逻辑中，有些命题可以有不同的符号化形式！,2.3 一阶逻辑等值式,等值式（定义2.10）,一、一阶逻辑等值式,设A，B是一阶逻辑中任意两个公式，若AB是永真式， 则称A与B是等值的。记作AB，成AB是等值式。,一阶逻辑中的几个基本的等值式,
