第2xx谓词逻辑
本章主要内容包括谓词逻辑的基本概念、谓词逻辑命题的符号化，谓词公式及其真值，谓词公式的前束范式，重言蕴含式与推理规则等。下面就此作一简要介绍。
一、谓词逻辑的基本概念及其符号化
个体是指可以独立存在的客观实体，它可以是具体的，也可以是抽象的。具体的特定个体称为个体常量；抽象的、泛指的或在一定范围内变化的个体称为个体变量，也称为个体变元；个体变量的取值范围称为个体域(或论域)；在命题中，表示一个个体性质、特征或多个个体之间关系的成份称为谓词；表示具体性质或关系的谓词称为谓词常量或常谓词，否则称为谓词变量。
一般用大写字母
F、G、H等表示谓词，而用X、Y、Z等表示谓词变量。表示一个个体性质的谓词称为一元谓词：
表示多个个体之间关系的谓词称为多元谓词。
在命题中除了个体和谓词外，有时还出现表示数量的词称为量词。我们讨论的量词有两个，即存在量词和全称量词。全称量词对应于汉语中的“每个”、“所有的”、“任意的”等，用符号“”表示。存在量词对应于汉语中的“有的”、“至少有一个”、“存在”等，用符号“”表示。
在个体域事先给定的情形下，我们只有将个体域中的每个具体的个体代入到F(x)中去确定其真假，才能断定xF(x)的真假。当每一个个体都使得F(x)=1时，就有xF(x)=l；否则xF(x)=0。对于F(x)，我们只要发现个体域中有(一个或多个)个体使得F(x)=1时，就有xF(x)=1；否则(即任何个体都使得F(x)=
O)xF(x)=0。
在用量词符号化命题时，首先强调的是个体域，同一命题在不同的个体域内可能有不同的符号化形式，同时也可能有不同的真值，因此必须先清楚个体域，不先确定所考虑的个体域就不能准确地表达原命题的意思。为了解决这一
问题，使得符号化表达式有确定的含义而不需事先考虑个体域，我们在符号化表达式中增加一个指出个体变量的变化范围的谓词，这样就可以不需事先考虑个体域而能够准确地把命题的意思表示出来。这样我们考虑含有量词的命题时，总是在由一切事物构成的总体个体域上考虑问题。
当符号化时，如果命题中含有全称量词，则把所增加的指出个体变化范围的谓词(称为特性谓词)作为前件，而命题中原有的谓词作为后件，构成一个蕴含式来表示命题的意思：
如果命题中含有存在量词，则用增加的特性谓词和原命题中的谓词构成的合取式表示命题的意思。
在对给定的自然语言形式的命题进行符号化时，若是为了确定命题的真值，一般约定在某个个体域上进行，否则一般在总体个体域上进行，要根据具体情况而定。若是在总体个体域上进行，则需按上面的说明加上特性谓词及相应的联结词来表示。二、谓词公式及其真值
定义：
设F和X分别为n元谓词和n元谓词变量，x
1，x
2， (x)
n是个体变量，则F(x
1，x
2， (x)
n)和X(x
1，x
2， (x)
n)都称为原子公式。
定义1谓词公式是指满足下列条件的公式：
(1)命题公式和原子公式是公式：
(2)若A是公式，则A也是公式：
(3)若A，B是公式，则(A∨B)，(A∧B)，(A→B)，(A?B)也是公式：
(4)若A是公式，x是个体变量，则(xA)和(xA)也是公式：
(5)只有有限次应用
(1)~
(4)得到的才是公式。
定义2紧跟在x或x后面并用圆括号括起来的公式，或者没有圆括号括着的一个原子公式，称为相应量词的作用域(或辖域)。
把x或为中的变量叫作相应量词的指导变量(或指导变元、作用变元等)；在量词作用域中出现的与指导变量相同的变量称为约束变量(或约束变元)；除约束变量外的一切变量称为自由变量(或自由变元)。
在谓词公式中，自由变量虽然有时也在量词的作用域中出现，但不受相应量词中指导变量的约束，故可把自由变量看作公式中的参数。另一方面，在谓词公式中，一个变量可以既是约束变量，也是自由变量，后面习题解析中有相应的习题。为了避免一个变量既是自由变量又是约束变量可能引起的混淆，可对约束变量改名，使得一个变量在一个公式中只呈现一种形式，即仅为自由变量或仅为约束变量。
根据定义，谓词公式是一个关于自由变量(个体和命题)、谓词变量的命题函数，其值随着这些变量的变化而变化。
定义3设A为一谓词公式，其中含有自由个体变量x
1，x
2， (x)
l，命题变量P
1，P
2，…，P
m，谓词公式X
1，X
2，…，X
n，则谓词公式A可表示成为A(x 1，x
2， (x)
l，P
1，P
2，…，P
m，X
1，X
2，…，X
n)。如果对码，x
1，x
2， (x)
l分别指定个体a
1，a
2，…，a
l，对P
1，P
2，…，P
m分别指定为真值1或0，对X
1，X
2，…，X
n分别指定常谓词F
1，F
2，…，F
n，则给公式A作了一组赋值。此时也称是对谓词公式的一个解释。当给定一组赋值后，公式的真值就惟一确定了。
定义4如果一谓词公式在任何赋值下均为真，则该公式称为重言式(或永真式、逻辑有效式)；如果任何赋值都使其为假，则该公式称为矛盾式(或永假式)；如果至少有一赋值使其为真，则说公式为可满足式。
有教材也出现了闭式的定义。闭式是指在任何赋值(或解释)下，命题的真值不真即假，不会发生真值不确定的情况，也就是说，闭式在任何赋值下均为命题。
设A，B是谓词公式，若A→B是重言式，则称为重言蕴含式。重言蕴含式A→B，也称A逻辑蕴含B，记作A B，此式称为逻辑蕴含式。若A?B是重言式，则称为重言等价式，并称A和B等值或逻辑等价，记作A B，此式称为等值式或逻辑等价式。
除了由上一章命题逻辑推广而来的谓词逻辑等值式外，还有许多谓词公式本身特有的等值式(主要与量词相关)，下面给出一些常见且重要的基本谓词公式等值式。
定理1设A(x)是一个含有个体变量x的谓词公式，B是一个不含自由变量x 的公式，则下面各等值式成立：
(1)xA(x)x A(x)
(2)xA(x)x A(x)
(3)xA(x)x A(x)
(4)xA(x)x A(x)
(5)x(A(x)∨B)(xA(x)∨B)
(6)x(A(x)∧B)(xA(x)∧B)
(7)x(A(x)∨B)(xA(x)∨B)
(8)x(A(x)∧B)(xA(x)∧B)
说明：
其中
(1)(2)
(3)(4)称为量词转换律，它说明量词外面的否定词可以移至量词的作用域内，作用域内的否定词也可以移至外面，全称量词和存在量词可以互换：
(5)
(6)(7)
(8)称为量词作用域的扩张与收缩，它说明了在量词作用域内，如果存在与量词约束无关的公式，在某些情况下，可把这些公式从作用域内移出，反之，亦可移入。
定理2设A(x)是一个含有个体变量x的谓词公式，B是一个不含自由变量x 的公式，则下面各等值式成立：
(9)x(B→A(x))(B→xA(x))
(10)x(A(x)→B)(xA(x)→B)
(11)x(B→A(x))(B→xA(x))
(12)x(A(x)→B)(xA(x)→B)
定理3设A(x)，B(x)都是含有个体变量x的谓词公式，则下面等值式成立：
(13)x(A(x)→B(x))(xA(x)→xB(x))
(14)x(A(x)∧B(x))(xA(x)∧xB(x))
(15)x(A(x)∨B(x))(xA(x)∨xB(x))
(16)xA(x)∨xB(x))x y(A(x)∨B(y))
(17)xA(x)∧xB(x))x y(A(x)∧B(y))
定理4设A(x，y)是含有个体变量x，y的谓词公式，则
(18)x yA(x，y)y xA(x，y)
(19)x yA(x，y)y xA(x，y)
三、谓词公式的前束式
定理5(约束变量改名规则)设A(x)是含有自由变量x而不含有变量y的谓词公式，A(y)是将A(x)中的自由变量x均改成y后得到的公式。则有：
xA(x)yA(y)；xA(x)yA(y)
改名规则为：
(1)对约束变量，可以改名。其更改的变量名称范围为量词中的指导变量以及该量词作用域中所有出现该变量的地方，公式的其余部分不变。
(2)改名时一定要更改为作用域中没有出现过的变量名称。
定理6(自由变量改名规则〉设x是A(x，z)中仅自由出现的个体变量，y不出现在A（x，z)中，则
A(x，z)A(y，z)，且
zA(x，z)zA(y，z)，zA(x，z)zA(y，z)
改名规则(也称为代入规则)为：
(1)谓词公式中的自由变量可以更改，更改时需对公式中出现该自由变量的每一处都进行更改。
(2)用以更改的变量与原公式中所有变量的名称不能相同。
定义5设B是一个不含量词的谓词公式，△
i为或。如果公式A△
1x
l△
2x
2…△
nx
nB，则△
1x
l△
2x
2…△
nx
nB称为公式A的前束范式。当n=0时，有A B，B也称为A的前束范式。
定理7 (前束范式存在定理)任意一个谓词公式A都存在与它等值的前束范式。
说明：
谓词公式的前束范式并不一定惟一，所以不能象命题公式的主范式那样直接用于解决问题，它只是将谓词公式形式的范围缩小了一点，能够给研究工作提供一定的方便。
四、重言蕴含式与推理规则
定理8设A(x)，B(x)均为含有自由变量，x的任意的谓词公式，则有
（20）xA(x)∨xB(x)x(A(x)∨B(x))
（21）x(A(x)∧B(x))xA(x)∧xB(x)
（22）x(A(x)→B(x))xA(x)→xB(x)
（23）x(A(x)→B(x))xA(x)→xB(x)
（24）x(A(x)?B(x))xA(x)?xB(x)
定理9设A(x)为含有自由变量x的任意的谓词公式，则有
(25)xA(x)A(x)
(26)A(x)xA(x)
(27)xA(x)xA(x)
定理10设A(x，y)为含有自由变量x，y的任意的谓词公式，则有
(28)x yA(x，y)y yA(x，y)
(29)x yA(x，y)y xA(x，y)
(30)x yA(x，y)x yA(x，y)
(31)x yA(x，y)xA(x，x)
(30)xA(x，x)x yA(x，y)
在推理过程中，上面给出的一些等值式和重言蕴含式可以作为推理依据使用，并分别将推理过程中使用的等值式和重言蕴含式分别称为E规则和I规则。除此之外，常用的一些推理规则还有：
(1)前提引入规则：
也称为P规则，即前提在推理过程中随时可引入使用。.
(2)结论引用规则：
也称为T规则，即在推理过程中产生的中间结论可以作为后面推理的前提使用。
(3)全称量词规定规则(US):
如果对个体域中的所有变量x，P(x)成立，则对个体域中的某个变量c，P(c)成立.
(4)全称量词推广规则(UG):
如果对个体域中的每个个体变量c，P(c)成立，则可得到结论xP(x)成立。
(5)存在量词规定规则(ES):
如果对个体域中的某个个体P(x)成立，则必有某个特定的个体c，P(c)成立。
(6)存在量词推广规则(EG):
如果对个体域中的某个个体c，P(c)成立，则在个体域中，必存在x，使得P(x)成立。
第二章谓词逻辑 1.什么叫做客体和客体变元？如何表示客体和客体变元？ 2.么叫做谓词？ 3.什么叫做论域？我们定义一个“最大”的论域叫做什么？ 4.填空题： 1．存在量词：记作( )，表示( )或者( )或者( )。 2．全称量词：记作( )，表示( )或者( )或者( )。 5.什么叫做量词的作用域？指出下面两个谓词公式中各个量词的作用域。 ?x(F(x,y)→?yP(y))∧Q(z)∧?xA(x) ?x?y?z(A(x,y)→B(x,y,z))∧C(t) 6.什么叫做约束变元？什么叫做自由变元？指出下面公式中哪些客体变元是约束变元？哪些客体变元是自由变元？ ?x(F(x,y)→?yP(y))∧Q(z)∧?xA(x) 7.填空：一个谓词公式如果无自由变元，它就表示一个( )。 8.给出的谓词 J(x)：x是教练员， L(x) ：x是运动员， S(x) ：x是大学生，O(x) ：x是年老的，V(x) ：x是健壮的，C(x) ：x是国家选手，W(x) ：x是女同志， H(x) ：x是家庭妇女，A(x,y)：x钦佩y。客体 j：金某人。用上面给出的符号将下面命题符号化。 1．所有教练员是运动员。 2．某些运动员是大学生。 3．某些教练是年老的，但是健壮的。 4．金教练既不老，但也不是健壮的。 5．不是所有运动员都是教练。 6．某些大学生运动员是国家选手。 7．没有一个国家选手不是健壮的。 8．所有老的国家选手都是运动员。 9．没有一位女同志既是国家选手又是家庭妇女。 10．有些女同志既是教练又是国家选手。 11．所有运动员都钦佩某些教练。
12．有些大学生不钦佩运动员。 9.将下面命题符号化 1．金子闪光,但闪光的不一定都是金子。 2．没有大学生不懂外语。 3．有些液体可以溶解所有固体。 4．每个大学生都爱好一些文体活动。 5．每个自然数都有唯一的后继数。 10.令P表示天气好。Q表示考试准时进行。A(x)表示x是考生。B(x)表示x提前进入考场。C(x)表示x取得良好成绩。E(x,y)表示x=y。利用上述符号，分别写出下面各个命题的符号表达式。 1．如果天气不好，则有些考生不能提前进入考场。 2．只有所有考生提前进入考场，考试才能准时进行。 3．并非所有提前进入考场的考生都取得良好成绩。 4．有且只有一个提前进入考场的考生未能取得良好成绩。 11.将下面命题符号化。 1．对一个大学生来说，仅当他刻苦学习，才能取得优异成绩。 (S(x):x是大学生；Q(x):x取得了优异成绩；H(x):x刻苦学习。) 2．每个不等于0的自然数，都有唯一的前驱数。 (Z(x):x是自然数； E(x,y):x=y； Q(x,y):y是x的前驱数。) 12.
第二章 谓词逻辑 一、原子命题的内部结构 12．谓词逻辑·谓词和个体词·量词、全称量词和存在量词·个体域·量词的辖域·自由 个体变项和约束个体变项·一阶谓词逻辑 什么是谓词逻辑 在第一章中，我们知道，命题逻辑的根本特征，就在于把原子命题作为基本的单位，对原子命题的内部结构不再进行分析。在思维实际中，有时我们不涉及原子命题的内部结构，例如，命题推理只涉及命题之间的关系，这时命题逻辑的工具就足够了。但在更多的情况下需要涉及原子命题的内部结构。例如： 推理1： 所有的人都是要死的。 苏格拉底是人。 所以，苏格拉底是要死的。 推理1包括三个不同的原子命题，经过相应的设定后，它的真值形式是()r q p →∧。这不是一个重言式。因此，这个显然有效的推理在命题逻辑个被判定无效。这是因为，推理1的有效性的根据不在原于命题之间的关系，而在于原子命题内部的构成要素之间的关系。命题逻辑无法解决这样的推理的判定问题。传统逻辑中的词项逻辑把原子命题进一步分析为主项、谓项、量项和联项的合式构成，这样它就能处理命题逻辑所无法处5理的许多推理，如推理1这样的三段论。但是，词项逻辑的处理能力有着很大的局限。例如： 推理2： 所有的罪犯或者是故意犯罪，或者是过失犯罪。 有些罪犯不是故意犯罪。 因此，有些罪犯是过失犯罪。 这个有效性同样明显的推理的判定，命题逻辑解决不了，词项逻辑同样解决不了。 为了更为有效和尽量不失—般性地解决推理的判定，需要提出新的逻辑工具，进—步分析原子命题的内部结构。这就是谓词逻辑的任务。 在谓词逻辑中，原子命题被进一步分析为谓词、个体词、量词和联结词这样几个基本成分。谓词、个体词和量词是谓词逻辑中新引入的概念，联结词作为符号就是真值联结词。 谓词和个体词 我们通过以下实例来说明什么是谓词和个体词。 (1) 这张桌子是方的。 (2) 陈先生是贾女土的丈夫。 显然，以上两个命题都是原子命题。 在(1)中，今F(x)表示“x 是方的”，a 表示“这张桌子”，这样，F(a)就表示“这张桌子是方的”，也就是说，命题(1)的表达式是F(a)。这里，F 就是谓词，表示“方”这种性质；x 和a 就是个体词，表示具有“方”这种性质的个体。其中，x 称为个体变项，它只表示某一个个体，而不表示一个确定的个体；a 称为个体常项，它表示一个确定的个体，即这张桌子。 在(2)中，令H(x ，y)表示“x 是y 的丈夫”，a 表示陈先生，b 表示贾女士，这样，H(a ，b)就表示“陈先生是贾女士的丈夫”，也就是说，命题(2)的表达式是H(a ，b)。这里，H 是谓词，表示某人是某人的丈夫”这种关系，x 、y 和a 、b 是个体词，同样，x 和y 是个体变项，a 和b 是个体常项。
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧??α，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧?α，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧??α （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨?α （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。求下列各式 的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ， ?? （4）)(y x yP x ， ?? （5）)(y x yP x ，?? （6）)(y x xP y ，?? 解： (2) 当3=x 时可使式子成立，所以为Ture 。 (3) 当1≠y 时就不成立，所以为False 。
第2章谓词逻辑 本章主要内容包括谓词逻辑的基本概念、谓词逻辑命题的符号化，谓词公式及其真值，谓词公式的前束范式，重言蕴含式与推理规则等。下面就此作一简要介绍。 一、谓词逻辑的基本概念及其符号化 个体是指可以独立存在的客观实体，它可以是具体的，也可以是抽象的。具体的特定个体称为个体常量；抽象的、泛指的或在一定范围内变化的个体称为个体变量，也称为个体变元；个体变量的取值范围称为个体域(或论域)；在命题中，表示一个个体性质、特征或多个个体之间关系的成份称为谓词；表示具体性质或关系的谓词称为谓词常量或常谓词，否则称为谓词变量。 一般用大写字母F、G、H等表示谓词，而用X、Y、Z等表示谓词变量。表示一个个体性质的谓词称为一元谓词：表示多个个体之间关系的谓词称为多元谓词。 在命题中除了个体和谓词外，有时还出现表示数量的词称为量词。我们讨论的量词有两个，即存在量词和全称量词。全称量词对应于汉语中的“每个”、“所有的”、“任意的”等，用符号“?”表示。存在量词对应于汉语中的“有的”、“至少有一个”、“存在”等，用符号“?”表示。 在个体域事先给定的情形下，我们只有将个体域中的每个具体的个体代入到F(x)中去确定其真假，才能断定?xF(x)的真假。当每一个个体都使得F(x)=1时，就有?xF(x)=l；否则?xF(x)=0。对于?F(x)，我们只要发现个体域中有(一个或多个)个体使得F(x)=1时，就有?xF(x)=1；否则(即任何个体都使得F(x)=O)?xF(x)=0。 在用量词符号化命题时，首先强调的是个体域，同一命题在不同的个体域内可能有不同的符号化形式，同时也可能有不同的真值，因此必须先清楚个体域，不先确定所考虑的个体域就不能准确地表达原命题的意思。为了解决这一问题，使得符号化表达式有确定的含义而不需事先考虑个体域，我们在符号化表达式中增加一个指出个体变量的变化范围的谓词，这样就可以不需事先考虑个体域而能够准确地把命题的意思表示出来。这样我们考虑含有量词的命题时，总是在由一切事物构成的总体个体域上考虑问题。 当符号化时，如果命题中含有全称量词，则把所增加的指出个体变化范围的谓词(称为特性谓词)作为前件，而命题中原有的谓词作为后件，构成一个蕴含式来表示命题的意思：如果命题中含有存在量词，则用增加的特性谓词和原命题中的谓词构成的合取式表示命题的意思。 在对给定的自然语言形式的命题进行符号化时，若是为了确定命题的真值，一般约定在某个个体域上进行，否则一般在总体个体域上进行，要根据具体情况而定。若是在总体个体域上进行，则需按上面的说明加上特性谓词及相应的联结词来表示。
第2xx谓词逻辑 本章主要内容包括谓词逻辑的基本概念、谓词逻辑命题的符号化，谓词公式及其真值，谓词公式的前束范式，重言蕴含式与推理规则等。下面就此作一简要介绍。 一、谓词逻辑的基本概念及其符号化 个体是指可以独立存在的客观实体，它可以是具体的，也可以是抽象的。具体的特定个体称为个体常量；抽象的、泛指的或在一定范围内变化的个体称为个体变量，也称为个体变元；个体变量的取值范围称为个体域(或论域)；在命题中，表示一个个体性质、特征或多个个体之间关系的成份称为谓词；表示具体性质或关系的谓词称为谓词常量或常谓词，否则称为谓词变量。 一般用大写字母 F、G、H等表示谓词，而用X、Y、Z等表示谓词变量。表示一个个体性质的谓词称为一元谓词： 表示多个个体之间关系的谓词称为多元谓词。 在命题中除了个体和谓词外，有时还出现表示数量的词称为量词。我们讨论的量词有两个，即存在量词和全称量词。全称量词对应于汉语中的“每个”、“所有的”、“任意的”等，用符号“”表示。存在量词对应于汉语中的“有的”、“至少有一个”、“存在”等，用符号“”表示。 在个体域事先给定的情形下，我们只有将个体域中的每个具体的个体代入到F(x)中去确定其真假，才能断定xF(x)的真假。当每一个个体都使得F(x)=1时，就有xF(x)=l；否则xF(x)=0。对于F(x)，我们只要发现个体域中有(一个或多个)个体使得F(x)=1时，就有xF(x)=1；否则(即任何个体都使得F(x)= O)xF(x)=0。 在用量词符号化命题时，首先强调的是个体域，同一命题在不同的个体域内可能有不同的符号化形式，同时也可能有不同的真值，因此必须先清楚个体域，不先确定所考虑的个体域就不能准确地表达原命题的意思。为了解决这一