离散数学第2章

第二章谓词逻辑1著名的苏格拉底三段论所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。凭着人们的直觉可知：由前提：“所有的人都是要死的”，“苏格拉底是人”，推出的结论：“苏格拉底是要死的”是有效结论，但在命题逻辑中无法对此给出证明。因为如果令P：所有的人都是要死的。

Q：苏格拉底是人。R：苏格拉底是要死的。那么应有但并不是永真式．原因何在？2著名的苏格拉底三段论原因在于：在命题逻辑中，由于把命题P，Q，R看做是三个不同的、没有联系的命题，不考虑其内在联系，而实际上Ｐ，Ｑ，Ｒ之间是有内在联系的。因此在命题逻辑中无法证明上述这个简单的三段论推理。解决问题的途径:对原子命题作进一步的分解。3§2.1.1谓词与个体考察以下2个原子命题：（1）李华是工程师。（2）何威是工程师。若对这两个原子命题进行内部结构分析，就会发现它们之间既有相异之处又有相同之处。相异之处：主语不同相同之处：谓语共享4§2.1.1谓词与个体这两个语句虽不同，但其共同部分“谓语”是不变的。将这个不变部分从这类命题中分离（抽象）出来进行研究并符号化。例如，可将“xx是工程师”形式化为：Ｇ(xx)或Ｇ(·)因而，需要引入一个符号表示“xx是工程师”，再引入一种方法表示主语，这样就能将“xx是工程师”这个命题的本质属性刻划出来。5§2.1.1谓词与个体又如，可将“xx是教师”形式化为：Ｔ(xx)或Ｔ(·)可将“３大于２”形式化为：Ｄ(３，２)或Ｄ(·，·)可将“点a介于点b和c之间”形式化为：Ｆ(a，b,c)或F(·，·

，·)6§2.1.1谓词与个体像Ｇ(·)，Ｔ(·)，Ｄ(·，·)，F(·，·

，·)这样的抽象形式，实际上就是上述几个语句中描述主语性质的谓语结构的抽象形式或描述主语所涉及对象之间的关系的抽象形式。这种“描述主语性质的谓语结构的抽象形式或描述主语所涉及对象之间的关系的抽象形式”就是谓词。语句中的主语称为个体。在原子命题中引进谓词和个体的概念，这种以命题中的谓词为基础的分析研究，称为谓词逻辑(或称谓词演算)。

7§2.1.1谓词与个体在谓词逻辑中，将原子命题分解为谓词与个体两部分。例如:张华是大学生，其中“是大学生”为谓词，“张华”为个体。个体是指可以独立存在的客体。它可以是抽象的，也可以是具体的。谓词是用来刻划个体的性质或关系的。通常用大写拉丁字母F,G,H等表示谓词，用小写拉丁字母a,b,c等表示个体。8§2.1.1谓词与个体由于单独的谓词是没有含义的，如“是大学生”，它必须与个体结合才能构成命题。例如，

T（a）：a是教师。

D（３，２）：３大于２。

C（武汉，北京，广州）：武汉位于北京和广州之间。习惯上将一个n元谓词与n个个体所构成的命题写为注意顺序9§2.1.1谓词与个体在一个谓词中，个体是可以变化的，如“是大学生”中个体是可以变化的，可以是“张华是大学生”也可以是“何勇是大学生”，等等。可设F(x)表示“x是大学生”

，a表示“张华”，b表示“何勇”

，则“张华是大学生”可表示为F(a)“何勇是大学生”可表示为F(b)10§2.1.1谓词与个体个体的变化范围，称为个体域。而以某一个个体域为变域的变元，称为个体变元。将宇宙间一切事物所组成的个体域称为全总个体域。11§2.1.1谓词与个体仅含一个个体的谓词，称为一元谓词。含有n个个体的谓词，称为n元谓词。一般地，一元谓词刻画了个体的性质，多元谓词刻画了个体之间的关系。注意：１．谓词不是命题，只有当确定的个体“填入”后，才成为命题。２．命题看做是0元谓词。12思考题：“张华是大学生”可表示为F(a)，是否是0元谓词？不带个体变项的谓词称为0元谓词，因为F(a)中，a是个体常元，所以上述命题是0元谓词！13§2.1.1谓词与个体例:这个人正在看那本红皮面的书。解:令F(x,y)表示“x正在看y”，G(x)表示“x是人”，H(y)表示“y是红皮面的”，U(y)表示“y是书”，a表示“这个”，b表示“那本”，则上式可表示为F(a,b)

∧G(a)∧H(b)∧U(b)14练习：小张是足球或篮球裁判。小张比小王年龄大。李平的妈妈是一名医生。15

§2.1.2量词“x能被2整除”可符号化为：

P(x)：x能被2整除。

P(4)：4能被2整除，这是个命题，且其真值为真。

P(5)：5能被2整除，这是个命题，且其真值为假。考虑下列命题的符号化形式：所有偶数都能被2整除。每个人都要呼吸。有些狗是聪明的。16§2.1.2量词全称量词记作“x”，其含意是：“所有的x”、“每一个x”、“凡是x”、“任意的x”等等。表示对个体域中的所有个体其谓词F(x)均为真。17

1．全称量词例如，对于下列命题（1）所有鱼都生活在水中。（2）每个人都要呼吸。（3）凡是狮子都是猫科动物。(4）任意的素数都是整数如果令F(x)：x是鱼W(x)：x生活在水中

M(x)：x是人H(x)：x要呼吸

L(x)：x是狮子C(x)：x是猫科动物

P(x)：x是素数I(x)：x是整数18注意事项：１．命题变元不是命题，但在全称量词的作用下，仅含变量x的命题变元成为命题，如上面的例4

它表示：任意的素数都是整数。显然，这是一个命题，且它的真值为真。因此，在全称量词的作用下，命题变元中的变量x不再起变量的作用，或者说全称量词“约束”了x的变量作用。19注意事项：２．命题的表示形式与个体域密切相关。例：每个人都要呼吸。（１）若个体域为人类集合，令F（x):x要呼吸，则可符号化为：（２）若个体域为全总个体域，令F（x):x要呼吸，Ｍ(x):x是人，则可符号化为：即要用“特性谓词”加以限制。当个体域采用全总个体域时，必须使用特性谓词。20注意事项：３．在全称量词作用下，命题中的特性谓词与命题变元之间必须采用条件联结词，而不能用合取。４．对于多元谓词，可以有多个全称量词，如

A(x,y)：x和y都是正数。

B(x,y)：xy>0。那么它表示：对于任意的x和y都是正数，则

xy>0。这是一个命题，它的真值为真。21§2.1.2量词存在量词记作“”，其含意是：“存在着x”、“有些x”等等。表示个体域中存在某些个体其谓词F(x)均为真。222．存在量词例：对于下列命题（1）有些老虎是白色的。（2）有些狗是聪明的。（3）存在着不是有理数的实数。如果令T(x)：x是老虎W(x)：x是白色的

D(x)：x是狗C(x)：x是聪明的

Q(x)：x是有理数R(x)：x是实数取个体域为全总个体域，则上述命题可表示为232．存在量词注意：１．在存在量词的作用下，x不再起变量的作用，存在量词也“约束”了x的变量作用。注意：２．在存在量词作用下，命题中的特性谓词与命题变元之间必须采用联结词合取，而不能用条件。注意：3．命题的表示形式与个体域密切相关。例：有些狗是聪明的。若个体域为所有狗的集合，则该命题表示为：

24例1设个体域为整数集合，请把下列命题符号化(1）任意整数或是奇数或是偶数。（2）凡是素数必是奇数。(3）并非所有整数都是素数。（4）并非所有素数都是偶数。解令E(x)：x是偶数O(x)：x是奇数P(x)：x是素数则上述命题符号化为25例2请把下列命题符号化（1）有些人是聪明的。（2）并不是每个人都聪明。（3）尽管有人聪明，但未必一切人都聪明。解令M(x)：x是人C(x)：x是聪明的由于题设中没有指明个体域，一般都采用全总个体域，上述命题符号化为26例3请把下列命题符号化（1）凡是实数不是大于零就是等于零或小于零。解令R(x)：x是实数G(x,0)：x大于零

D(x,0):x等于零S(x,0):x小于零或令R(x)：x是实数>(x,0)：x大于零

=(x,0):x等于零<(x,0):x小于零27【例】如果令A(x)：x是整数B(x)：x是偶数C(x)：x是奇数D(x，y)：x是能整除y请用日常语言叙述下列命题：（1）所有偶数都是整数。（2）有些整数是奇数。（3）所有能被2整除的数都是偶数。（4）有些奇数能被3整除。28练习：1.没有不犯错的人。2.对于所有的正实数x,y，都有x+y≥x。3.每个人都要参加一些课外活动。4.某些人对某些药物过敏。291.没有不犯错的人P(x)：x犯错S(x)：x是人302.对于所有的正实数x,y，都有x+y≥x。P(x，y)：x+y≥xS(x)：x是正实数313.每个人都要参加一些课外活动。P(x，y)：x都要参加yS(x)：x是人N（y）：y是课外活动324.某些人对某些药物过敏。P(x，y)：x对y过敏S(x)：x是人N（y）：y是药物33思考题：将下列命题符号化1.兔子比乌龟跑得快2.有的兔子比所有乌龟跑得快3.并不是所有兔子都比乌龟跑得快4.不存在跑的同样快的两只兔子34因为题目没有指明个体域，所以使用全总个体域。1.兔子比乌龟跑得快2.有的兔子比所有乌龟跑得快3.并不是所有兔子都比乌龟跑得快4.不存在跑的同样快的两只兔子F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得一样快35函数在谓词逻辑中，个体与个体间有一定的关系，这种关系称为函数。一元函数二元函数多元函数36函数例1:肖阳的爸爸上北京去了。解:F(x,y):x到y去了，f(x):x的爸爸，a:肖阳，b:北京则有F(f(a)，b)例2:谢世平和他父亲及祖父三人一起去看演出。解:F(x,y,z):x与y及z一起看演出，f(x):x的父亲，

a:谢世平，则有F(a,f(a),f(f(a)))37§2.1.3谓词逻辑公式（公式）谓词逻辑公式中所使用的符号有以下七种:(1)个体常量符:a,b,c,…(2)个体变量符:x,y,z…(3)函数符:f,g,h…(4)谓词符:F,G,H…(5)联结词符:(7)括号(,)(6)量词符:一个谓词逻辑公式中是由上述符号按一定规则所组成的符号串。38§2.1.3谓词逻辑公式（公式）定义(项)(1)个体常量符是项；(2)个体变量符是项；(3)设f是n元函数符，为项，则是项。定义(原子公式)(4)项由且仅由有限次使用(1)，(2)，(3)而得。设P是n元谓词符，为项，则是原子公式。39§2.1.3

谓词逻辑公式（公式）定义谓词公式由下述各条规定组成：（1）原子公式是谓词公式。（2）若A是谓词公式，则﹁A也是谓词公式。（3）若A和B是谓词公式，则A∨B，A∧B，A→B，也是谓词公式。（4）若A是谓词公式，x是A中出现的变量，则和也是谓词公式。（5）只有有限次应用规则（1），（2），（3），（4）所得到的公式是谓词公式。40§2.1.3

谓词公式（续）例如，下列各式是谓词公式。但下列各式

不是谓词公式。41练习：下列哪些是谓词公式：42解释下面的公式设个体域为N，a=0，f(x,y)=x+y;g(x,y)=xyF(x,y):x=y43设个体域为N，a=0，f(x,y)=x+y;g(x,y)=xyF(x,y):x=y44§2.1.4

自由变元和约束变元由于全称量词的作用，使得命题函数中的x不再起变元的作用，或者说，量词约束了x的变元作用，在这种情况下，称变量x为“约束出现”，并称x为约束变元。又如在这个谓词公式中，易见，x是约束元，但y不是约束元，称y是“自由出现”，并称y为自由变元。量词后括号中的内容称为量词的作用域或辖域。45例１在谓词公式中，量词的作用域或辖域为量词的作用域为，x和y都是约束变元。

46例2在谓词公式中，量词的作用域或辖域为所以x是约束变元，而y是自由变元；

量词的作用域为所以y是约束变元，但x是自由变元；而S(y）中的y是自由元。47练习：指出各量词的辖域48设个体域为D={a,b,c},消去下列谓词公式中的量词。∀xP(x)∧∃xQ(x)∀x(P(x)→∃yQ(y))∀x∃yR(x,y)∃y∀xR(x,y)=(P(a)∧P(b)∧P(c))∧(Q(a)∨Q(b)∨Q(c))=(P(a)→(Q(a)∨Q(b)∨Q(c)))∧(P(b)→(Q(a)∨Q(b)∨Q(c)))∧(P(c)→(Q(a)∨Q(b)∨Q(c)))=∀x(R(x,a)∨R(x,b)∨R(x,c))=(R(a,a)∨R(a,b)∨R(a,c))∧(R(b,a)∨R(b,b)∨R(b,c))∧(R(c,a)∨R(c,b)∨R(c,c))=∃y(R(a,y)∧R(b,y)∧R(c,y))=(R(a,a)∧R(b,a)∧R(c,a))∨(R(a,b)∧R(b,b)∧R(c,b))∨(R(a,c)∧R(b,c)∧R(c,c))49几点说明在谓词公式中，一个变元可以既是约束变元又是自由变元。注意到具有相同的逻辑含义为了避免由于变元的约束和自由同时出现而引起概念上的混乱，可对约束变元进行换名，使得一个变量在谓词公式中只呈一种形式（约束变元或自由变元）出现。

50几点说明例如：在这个谓词公式中，y既是约束元又是自由元，如果把中的约束元y换名为z，则谓词公式可改写成

于是可确定x，z是约束元，y是自由元。

51换名规则

在对约束元换名时，应遵循以下两种规则（约束元换名规则）：（1）对约束元（如x）换名时，更改的名称范围是（或）中的x以及量词作用域中所出现的所有x，在量词作用域外的部分不换名。（2）换名时一定要更改为作用域中没有出现的变量名称52例３对下列谓词公式中约束变元进行换名，使得一个变量在谓词公式中只呈一种形式（约束元或自由元）出现。

53例３解：在这个谓词公式中，x既是约束元又是自由元，y也是约束元又是自由元。若把约束元x换名为u，约束元y换名为v，经换名后，谓词公式可写成为于是可知，u，v是约束元，x，y是自由元。

54代入规则对于谓词公式中的自由变元，也可以更改，这种更改称为代入，代入时应对谓词公式中出现该自由变元的每一处都进行。这称为自由元代入规则．例如，可更改为

55例３（续）对下列谓词公式中自由元进行代入，使得一个变量在谓词公式中只呈一种形式（约束元或自由元）出现。

56例３（续）

解：在这个谓词公式中，x既是约束元又是自由元，y也既是约束元又是自由元。若把自由元x用u代入，自由元y用v代入，经代入后，谓词公式可写成为于是可知，x，y是约束元，u，v是自由元。57注意：对改名上面各式都是错误的！58练习：使用代入和换名规则变换式子：59§2.2谓词演算关系式

谓词公式G在个体域D上的一个指派，是对D(非空)和G中谓词变元、自由变元作如下指定：1.对每个n元谓词变元，指定一个定义在D上的谓词常元。2.对每个个体变元指定D中的一个个体。60§2.2谓词演算关系式G：任意的谓词公式E:论述域1.如果G对E上的所有解释I为真，则称：G在E上永真。若E为全总域，则称G永真。2.如果G对E上的所有解释I为假，则称：G在E上永假。若E为全总域，则称G永假。3.如果G对E上的所有解释I至少有1个为真，则称：G在E上可满足。若E为全总域，则称G可满足。61谓词公式的翻译与论域的关系一个谓词公式，个体变元的论域不同，谓词公式的真值随之不同。例：P(x):”x

吃草”，Q(x):”x是无性繁殖的”。论域：D1:全体动物,D2:兔子(a)求(∀x)P(x)在D1,D2上的真值。(b)求(∃x)Q(x)在D1,D2上的真值。X√√X蚯蚓是无性繁殖的62谓词关系式将命题公式推广为谓词公式：例如：命题公式将P和Q分别替换为：公式就可变为：63关系式由于量词的引入，谓词公式多了如下公式：存在的析取全称的合取64关系式全称的析取存在的合取65例：证明1.设左式为真，则存在一个x0,使得：A(x0)∨B(x0)⇔T也即：A(x0)⇔T或者B(x0)⇔T当A(x0)⇔T时，也就说明存在x，使得∃xA(x)为真当B(x0)⇔T时，也就说明存在x，使得∃xB(x)为真所以右式也为真，从而左式等价于右式66例：证明2.设右式为真，则有2种情况a:当∃xA(x)⇔T时，也就说明存在x满足谓词A,设其为x0则A(x0)⇔T所以左式也为真，从而左式等价于右式b:当∃xB(x)⇔T时，也就说明存在x满足谓词B,设其为x1则B(x1)⇔T也即A(x0)∨B(x0)⇔T或者A(x1)∨B(x1)⇔T所以从两个方向证明了左右两式等价67例：利用等价式证明证明68例证明69例：证明∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)假设取解释为：个体域N，A(x)表示x是奇数，B(x)表示x是偶数，则：∀x(A(x)∨B(x))表示：任意的自然数要么是奇数要么是偶数。∀xA(x)∨∀xB(x)表示：任意的自然数都是奇数或者是任意的自然数都是偶数。真命题！假命题！70练习：证明下列各式成立71727374多个量词间的关系多个量词出现在一个公式中，则量词出现的顺序将直接关系到命题的意义。例如：对于二元谓词，可出现8种情况：75多个量词间的关系例如P(x,y)表示x与y同姓。x的论述域是甲班同学，y的论述域是乙班同学。故：甲班与乙班所有同学都同姓。乙班与甲班所有同学都同姓。甲班与乙班有同学同姓。乙班与甲班有同学同姓。显然意义相同76多个量词间的关系但再看这两组：对于甲班所有同学，乙班都有同学与他们同姓。乙班有一个(些)同学，与甲班所有同学都同姓。甲班有一个(些)同学，与乙班所有同学都同姓。对于乙班所有同学，甲班都有同学与他们同姓。显然意义不同77思考题：分别给出下列公式为真的解释和为假的解释。(∃x)A(x)→A(a)(∀x)(∀y)(A(x,y)→A(y,x))1.设论域={a,b}①若A(a)=F,A(b)=T,则(∃x)A(x)=T(∃x)A(x)→A(a)=F②若A(a)=T,A(b)=F,则(∃x)A(x)=T(∃x)A(x)→A(a)=T2.设论域={1,2,3}①A(x,y)表示x>y则(2>1)→(1>2)为假，所以原式为假②A(x,y)表示x≠y则(∀x)(∀y)(A(x,y)→A(y,x))为真78甲使用量词辖域收缩与扩张等值式进行如下演算：乙说甲错了，乙说得对吗？为什么？乙说得对，甲错了！因为全称量词∀的指导变元是x，辖域F(x)→G(x,y),F(x)和G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。79对偶定义设A是命题公式，且A中仅有联结词﹁，∨，∧，量词，。在A中把∨，∧，F，T，，，分别换成∧，∨，T，F，，后所得的命题公式称为A的对偶公式。80对偶例：的对偶式：81练习：写出对偶式82§2.3前束范式定义:一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式。例：

xyz(¬Q(x,y)

R(z))(前束范式)83前束范式前束范式有如下形式：其中，，A为不含有量词的谓词公式。例如等都式前束范式。而(x)

P(x)∧(y)Q(y),(x)(P(x)(y)Q(x,y))不是前束范式．可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末84判断下面的谓词公式是否是前束范式？XX√X√85前束范式定理:

任何一个谓词公式均和一个前束范式等价。证明：①利用量词转换把¬深入到原子谓词公式前,②利用约束变元的改名规则，③利用量词辖域的扩张收缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。86前束范式例：

xP(x)R(x)yP(y)R(x)

y(P(y)R(x))例：把

xP(x)

xQ(x)

变成前束范式。

xP(x)

xQ(x)

¬

xP(x)

xQ(x)

x¬P(x)

xQ(x)

x(¬P(x)

Q(x))

87前束范式求解的一般步骤：1.运用基本等价公式，把各种联结词转换成基本联结词：¬、

和∧2.运用E1、E8、E9、E24、E25、E26等将公式中的¬深入到各谓词变元的前面。3.利用换名、代入规则，使所有的约束变元均不同名，且自由变元与约束变元也不同名。4.利用E1、E8扩大量词的作用域至整个公式。88前束范式例.

将公式((

x)P(x)∨(y)Q(y))

(x)R(x)化归为前束范式原式

¬((

x)P(x)∨(y)Q(y))∨(x)R(x)((x)¬P(x)∧(y)¬Q(y))∨(x)R(x)((x)¬P(x)∧(y)¬Q(y))∨(z)R(z)

(x)(y)(z)[(¬P(x)∧¬Q(y))∨R(z)]

量词前移89例求下列谓词公式的前束范式：1）2）解1）

换名规则代入规则90解

2）（改名规则）

德摩根定律提前换名91思考：以下两种解法正确吗？都是正确的！92前束范式1.由于采用换名规则，导致得到不同的但是等价的前束范式2.或者由于量词前移的顺序不同，可得到不同的并且都是等价的前束范式．例如，((

x)P(x)∨(y)Q(y))

(x)R(x)的前束范式有:(

x)(y)(z)[(¬P(x)∧¬Q(y))∨R(z)]和(

y)(x)(z)[(¬P(x)∧¬Q(y))∨R(z)]可见，前范式一般不是唯一的．93斯柯林范式前束范式的优点是全部量词集中在公式前面，其缺点是各量词的排列无一定规则。这样当把一个公式化归为前束范式时，其表达形式会显现多种情形，不便应用.1920年斯柯林(Skolem)对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前．按此规定得到的范式形式，称为斯柯林范式．显然，任一公式均可化为斯柯林范式．它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域．这给离散数学的研究提供了一定的方便．94练习：请将下列式子改写成前束范式：95原式⇔⇁∀xP(x)⋁∃xQ(x)⇔∃x⇁P(x)⋁∃xQ(x)⇔∃x(⇁P(x)⋁Q(x))96原式⇔⇁[⇁∀x∃yP(a,x,y)⋁∃x(⇁∀y

Q(y,b)→R(x))]⇔⇁[⇁∀x∃yP(a,x,y)⋁∃x(∀y

Q(y,b)⋁

R(x))]⇔∀x∃yP(a,x,y)⋀⇁∃x(∀y

Q(y,b)⋁

R(x))⇔∀x∃yP(a,x,y)⋀∀x(∃y⇁Q(y,b)⋀⇁R(x))⇔∀x[∃yP(a,x,y)⋀(∃y⇁Q(y,b)⋀⇁R(x))]⇔∀x[∃yP(a,x,y)⋀∃y(⇁Q(y,b)⋀⇁R(x))]⇔∀x[∃yP(a,x,y)⋀∃z(⇁Q(z,b)⋀⇁R(x))]⇔∀x∃y∃z(P(a,x,y)⋀

(⇁Q(z,b)⋀⇁R(x))]979899将下列命题符号化，要求公式为前束范式1.有的汽车比有的火车跑得快2.有的火车比所有汽车跑得快3.不是所有火车都比所有汽车跑得快4.有的飞机比有的汽车慢是不对的100F(x)：x是汽车，G(y):y是火车，I(z):z是飞机，H(x,y):x比y跑得快。1.有的汽车比有的火车跑得快∃x∃y（F(x)∧G(y)∧H(x,y))2.有的火车比所有汽车跑得快∃x∀y（F(x)∧（G(y)→H(x,y))）3.不是所有火车都比所有汽车跑得快⇁∀x∀y（（F(x)∧G(y)）→H(x,y)）错∃x∃y(F(x)∧G(y)∧⇁H(x,y))对1014.有的飞机比有的汽车慢是不对的⇁∃x∃z(F(x)∧I(z)∧L(x,z)）⇔∀x∀z(⇁(F(x)∧I(z)）∨⇁L(x,z)）∀x∀z(F(x)∧I(z)→⇁L(x,z)）F(x)：x是汽车，G(y):y是火车，I(z):z是飞机，L(x,y):x比y跑得慢。102§2.4一阶谓词演算的推理理论谓词演算是命题演算的进一步深化和发展，因此命题演算的推理理论在谓词演算中几乎可以完全照搬，只不过这时涉及的公式是谓词演算的公式罢了．在谓词演算中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词。因此正确理解和运用有关量词规则是推理理论中十分重要的关键所在.103A(y)：一般我们用A(x1,x2,…,xn)表示含有x1,x2,…,xn自由出现的公式，用△表示任意的量词（∀或∃）例如：△x1A(x1,x2,…,xn)表示含x2,…,xn自由出现的公式，记为：A(x2,…,xn)，而x1是约束元。所以如公式∀x(F(x,y)→G(x,z))可以记为：A(y,z),表示包含自由出现的个体变项y,z。若A是任意公式，不包含个体变项，则称闭式。104一阶谓词演算的推理理论1.有关量词消去和产生规则量词消去规则(1)全称指定规则(简称UI或US规则)有两种形式:(

x)A(x)⇒A(c)其中c为任意个体常元

(

x)A(x)⇒A(y)A(y)是对于y自由的谓词公式要正确理解该规则的成立条件，否则会导致错误推理．105(1)全称指定规则(简称UI或US规则)解释：如果“盒子里全是黑球”成立，那么从盒子中任取一球都是黑球。106一阶谓词演算的推理理论(2)存在指定规则(简称EI或ES规则)有两种形式:(

x)A(x)⇒

A(c)其中c为特定个体常元

(

x)A(x)⇒

A(y)成立充分条件是：c或y不在前提中或者居先推导公式中出现或自由出现107(2)存在指定规则(简称EI或ES规则)解释：如果“盒子里存在黑球”成立，那么在盒子中至少可以找到一球是黑球。108一阶谓词演算的推理理论量词产生规则:(3)存在量词引入规则(简称EG规则)有两种形式:

A(c)⇒(

x)A(x)其中c为特定个体常元

A(y)⇒(

x)A(x)成立充分条件：①取代c的个体变元x不在A(c)中出现；②若A(y)是推导行中的公式，且y是由于使用ES引入的，x不得为A(y)中出现过的个体变元．若不满足成立条件，可能导致错误结论．109(3)存在量词引入规则(简称EG规则)解释：如果“盒子里存在一个黑球”成立，那么“盒子中存在黑球”就成立。110一阶谓词演算的推理理论(4)全称量词推广规则(简称UG规则)

A(c)⇒(

x)A(x)

A(x)⇒(

y)A(y)成立条件：①前提A(x)对于x的任意取值都成立；②对于由于使用ES规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元，都不能使用本规则而成为指导变元，否则将产生错误推理．111规则使用说明：（1）在使用ES,US时一定要是前束范式（2）推导中连续使用US规则可用相同变元

xP(x)

P(y),

xQ(x)

Q(y),

（3）推导中既用ES，又用US，则必须先用ES，后用US方可取相同变元，反之不行。

xP(x)

P(y)

xQ(x)

Q(y)（4）推导中连续使用ES规则时，使用一次更改一个变元。112一阶谓词演算的推理理论2.谓词演算中推理实例

谓词演算的推理方法是命题演算推理方法的扩展，因此在谓词演算中利用的推理规则也是T规则P规则和CP规则，还有已知的等价式，蕴涵式以及有关量词的消去和产生规则．113一阶谓词演算的推理理论例：证明苏格拉底论证：所有人都是要死的，苏格拉底是人，因此，苏格拉底是要死的．114例1：证明

令M(x):x是人,D(x):x是要死的,s:苏格拉底,原题可符号化为：

x(M(x)D(x))M(s)D(s)(1)M(s)P(2)x(M(x)D(x))P(3)M(s)D(s)US(2)(4)D(s)I11(1)(3)所有人都是要死的，苏格拉底是人，因此，苏格拉底是要死的．115例2：证：

x(H(x)M(x)),xH(x)

xM(x)(1)

xH(x) P(2)H(c)ES(1)(3)

x(H(x)M(x)) P(4)H(c)M(c) US(3)(5)M(c) I11(2)(4)(6)xM(x) EG(5)116例3：证:

x(P(x)Q(x))xP(x)

xQ(x)(1)

xP(x) 引入前件

(2)

x(P(x)Q(x)) P(3)P(c)Q(c) ES(2)

(4)P(c) US(1)(5)Q(c) (3)(4)I11(6)

xQ(x) EG(5)注意：先ES,后US117例4：(反证法)

¬x(P(x)Q(x)),xP(x)¬xQ(x)(1)¬¬xQ(x) 假设前提

(2)

xQ(x) (1)E1(3)Q(c) US(2)(4)

xP(x) P

(5)P(c) US(4)(6)P(c)Q(c) I9(3)(5)(7)

x(P(x)Q(x)) UG(6)(注意:P、Q对于任意x成立)(8)¬x(P(x)Q(x)) P(9)x(P(x)Q(x))¬x(P(x)Q(x))T(10)F118练习：1.前提：

x(F(x)→G(x)),

x(F(x)

H(x))

结论：

x(G(x)

H(x))2.用反证法证明：

x(P(x)∨Q(x))∀xP(x)∨

xQ(x)1191.前提：

x(F(x)→G(x)),

x(F(x)

H(x))结论：x(G(x)

H(x))(1)

x(F(x)

H(x)) P(2)(F(c)

H(c))ES(1)(3)

x(F(x)→G(x)) P(4)F(c)G(c) US(3)(5)F(c) I1(2)(6)H(c) I2(2)(7)G(c)I11(4)(5)(8)G(c)∧H(c)I9(6)(7)(9)∃x(G(x)∧H(x))EG(8)1202.用反证法证明：

x(P(x)∨Q(x))∀xP(x)∨

xQ(x)(1)⇁(

∀xP(x)∨

xQ(x))P(2)∃X⇁P(x)∧∀x⇁Q(x)(1)E8(3)∃X⇁P(x)(2)I1(4)∀x⇁Q(x)(2)I1(5)⇁P(c)(3)Es(6)⇁Q(c)(4)Us(7)∀x(P(x)∨Q(x))P(8)P(c)∨Q(c)(7)Us(9)⇁P(c)∧⇁Q(c)(5)(6)I9(10)⇁(P(c)∨Q(c))(9)E9(11)(P(c)∨Q(c))∧⇁(P(c)∨Q(c))

(8)(10)I9(12)F

（10）能否变为：⇁∀x(P(x)∨Q(x))然后(11)∀x(P(x)∨Q(x))∧⇁∀x(P(x)∨Q(x))

从而等价于F不行！121练习：3.天鹅都会飞，而癞蛤蟆不会飞，所以癞蛤蟆不是天鹅。T(x):x是天鹅；L(x):x是癞蛤蟆；F(x):x会飞。前提：∀x(T(x)→F(x)),∀x(L(x)→⇁F(x))结论：∀x(L(x)→⇁T(x))122前提：∀x(T(x)→F(x)),∀x(L(x)→⇁F(x))

结论：∀x(L