第 2章 一阶逻辑第 2章 一阶逻辑
2.1 一阶逻辑的基本概念
2.2 一阶逻辑公式及解释
2.3 等值演算和前束范式
2.4 一阶逻辑推理理论
2.5 例题选解习 题 二第 2章 一阶逻辑
2.1 一阶逻辑的基本概念首先我们将简单命题的结构分解成个体和谓词 。
个体 （ 客体 ） 我们讨论的对象 。 可以是具体的,
也可以是抽象的 。
个体域 （ 论域 ） 个体所构成的非空集合 。
全总个体域 （ 无限域 ） 包含宇宙中一切事物的个体域 。
谓词 简单命题中,表示一个个体的性质或多个个体间的关系的词 。
第 2章 一阶逻辑之所以称之为谓词,是因为谓词和个体词一起构成了简单命题中的主谓结构 。 如：
小王是学生 。
3是素数 。
整除 6。
2加 3等于 5。
上面这些简单命题中,小王,2,3,5,6均是个体,"…… 是学生 ","…… 是素数 ","…… 整除 …… "，
"…… 加 …… 等于 …… "均是谓词 。
第 2章 一阶逻辑前两个谓词描述的是一个个体的性质,称为一元谓词；第三个表示两个个体之间的关系,称为二元谓词；第四个表示三个个体之间的关系,称为三元谓词 。
以此类推,我们将描述 n（ n≥2） 个个体之间关系的谓词称为 n元谓词 。 通常用大写字母 F,G,H（ 可加下标 ）
来表示谓词 。
第 2章 一阶逻辑
F表示 "…… 是学生 "；
G表示 "…… 整除 …… "；
H表示 "…… 加 …… 等于 …… "。
这时 F,G,H表示的是具体的谓词,称为谓词常元,否则,称为谓词变元 。 显然,单独的一个谓词
（ 即使是谓词常元 ） 并不能构成一个完整的句子,必须以个体词取代 "…… "方能构成一个句子 。
第 2章 一阶逻辑通常我们用小写的英文字母 a,b,c（ 可加下标 ）
等表示个体 。 这样,"小王是学生 "可符号化为 F（ a）,
其中 a表示小王 。 若用 b表示小李,则 F（ b） 就表示 "小李是学生 "。 若用 c1表示 2,用 c2表示 6,则 G（ c1,c2）
就表示 "2整除 6"。
这里,a,b,c1,c2均是具体的个体,称为个体常元 。 一般地,我们用 F（ x） 表示 "x是学生 ",其中的 x
称为个体变元 （ 简称变元,亦称个体词 ） 。 类似,我们也可用 G（ x,y） 表示 "x整除 y"。
第 2章 一阶逻辑我们称由谓词符和变元符组成的符号串为命题函数 。 之所以称为命题函数,是因为命题函数不是命题,
只有谓词为常元并将其中的变元代以具体的个体后,
才能构成命题 。 例如,"G（ x,y）,x整除 y。 "并不是命题,但若取 a,2,b,6,则 G（ a,a）,G（ a,b）
以及 G（ b,a） 均是命题,前两个是真命题,第三个是假命题 。 G（ a,a）,G（ a,b） 等称为 0元谓词,它们不含个体变元,0元谓词即命题 。
第 2章 一阶逻辑
【 例 2.1.1】 将下列语句形式化为谓词逻辑中的命题或命题函数 。
（ 1） 小王是二年级大学生 。
（ 2） 小王是李老师的学生 。
（ 3） 如果 x≤y且 y≤x,则 x=y。
解
（ 1） 令 F（ x）,x是大学生； G（ x）,x是二年级的； a：小王 。 则原句形式化为：
F（ a） ∧ G（ a） 。
第 2章 一阶逻辑
（ 2） 令 F（ x,y）,x是 y的学生； a：小王； b：李老师 。 则原句形式化为：
F（ a,b） 。
（ 3） 令 F（ x,y）,x≤y； G（ x,y）,x=y。 式化为：
（ F（ x,y） ∧ F（ y,x）） → G（ x,y） 。
第 2章 一阶逻辑前两句均是命题,第三句因为含有变元所以是命题函数 。 但实际上我们知道,只要将 x,y限制在数的范围内,第三句是定理,是永真的 。 这就涉及到了个体域 。 在简单命题中,常有一些表示数量关系的词语,
诸如 "所有的 ","有一些 "等等,用来表示论域中的全体或部分个体,在谓词逻辑中,我们用量词把它们形式化 。
第 2章 一阶逻辑
1,全称量词,"
全称量词用来表示个体域中的全体 。 表自然语言中的 "所有的 ","任意的 ","每一个 "等等 。 如：
"任意偶数均能被 2整除 。 "
句子可改写成：“在偶数集合中的任意的 x,x能被 2整除。”取个体域为偶数集，用 F（ x）表示,x能被 2整除”，用 x表示“任意的 x”，则原句形式化为：
xF（ x）。
第 2章 一阶逻辑
2,存在量词,"
。 表自然语言中的 "存在着一些 ","至少有一个 ","有 "等等 。 如：
"我们班有人会吸烟 。 "
句子可改写成,"在我们班有一些 x,x会吸烟 。 "
取个体域为 "我们班的同学 ",用 G（ x） 表示 "x会吸烟 ",x表示 "有些 x",xG（ x） 。
第 2章 一阶逻辑
【 例 2.1.2】 在全总个体域中形式化下列命题：
（ 1） 任意的偶数均能被 2整除 。
（ 2） 我们班有人吸烟 。
解
（ 1） 引入特性谓词 H（ x）,x是偶数 。
"任意的偶数均能被 2整除 "的涵义是：全总个体域中有子集 --偶数集,该子集中的每个元素均具有一种性质,世间万物,只要你属于这个子集,你就必然具有这种性质,所以是蕴含式 。 特性谓词以蕴含式的前件加入 。 则原句可形式化为：
x（ H（ x） → F（ x））?
第 2章 一阶逻辑
（ 2） 引入特性谓词 W（ x）,x是我们班的人 。
"我们班有人吸烟 "的涵义可以这样理解：在宇宙间的万物 （ 全总个体域 ） 中,有一个子集 --我们班,还有另一个子集 --吸烟的人 。 强调的是既在我们班,又吸烟的的人,所以是两个子集的交集 。 特性谓词用合取项加入 。 则原句可形式化为：
x（ W（ x） ∧ G（ x））?
第 2章 一阶逻辑
【 例 2.1.3】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 没有不犯错误的人 。
（ 2） 人总是要犯错误的 。
解 设 M（ x）,x是人,F（ x）,x犯错误 。 则原句形式化为：
（ 1） x（ M（ x） ∧ F（ x））
（ 2） x（ M（ x） → F（ x））
第 2章 一阶逻辑
【 例 2.1.4】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 所有的病人都相信医生 。
（ 2） 有的病人相信所有的医生 。
（ 3） 有的病人不相信某些医生 。
（ 4） 所有的病人都相信某些医生 。
第 2章 一阶逻辑解 设 F（ x）,x是病人,G（ x）,x是医生,H（ x，
y）,x相信 y。
（ 1） 本命题的意思是：对于每一个 x,如果 x是病人,那么对于每一个 y,只要 y是医生,x就相信 y。 因此,
本命题符号化为：
x（ F（ x） → y（ G（ y） → H（ x,y）））
或 x y（（ F（ x） ∧ G（ y）） → H（ x,y）
第 2章 一阶逻辑
（ 2） 本命题的意思是：存在着这样的 x,x是病人且对于每一个 y,只要 y是医生,x就相信 y。 因此,本命题符号化为：
x（ F（ x） ∧ y（ G（ y） → H（ x,y））
第 2章 一阶逻辑
（ 3） 本命题的意思是：存在着这样的 x和 y,x是病人,y是医生,x不相信 y。 因此,本命题符号化为：
x y（ F（ x） ∧ G（ y） ∧ H（ x,y））
或 (x（ F（ x） ∧ y（ G（ y） ∧ H（ x,y）））
（ 4） 本命题的意思是：对于每个 x,如果 x是病人,
就存在着医生 y,使得 x相信 y。 因此,本命题符号化为：
x（ F（ x） → y（ G（ y） ∧ H（ x,y）） )?
第 2章 一阶逻辑例 2.1.5】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 任意一个整数 x,均有另一个整数 y,使得 x+y等于 0。
（ 2） 存在这样的实数 x,它与任何实数 y的乘积均为 y。
解
（ 1）设 Z（ x）,x是整数,E（ x,y）,x=y,f（ x，
y） =x+y。则原句形式化为：
x（ Z（ x） → y（ Z（ y） ∧ E（ f（ x,y）,0）））
第 2章 一阶逻辑
（ 2） 设 R（ x）,x是实数,E（ x,y）,x=y,g（ x，
y） =xy。 则原句形式化为：
x（ R（ x） ∧ y（ R（ y） → E（ g（ x,y）,y）））
第 2章 一阶逻辑
2.2 一阶逻辑公式及解释上一节中我们在一阶逻辑中符号化得到的命题和命题函数就是一阶逻辑公式 (谓词公式 )。 至此,在一阶逻辑中,我们已涉及到以下这些符号：
(1)个体变元符号：用小写的英文字母 x,y,z（ 或加下标 ） … 等表示 。
(2)个体常元符号：用小写的英文字母 a,b,c（ 或加下标 ） … 等表示 。
第 2章 一阶逻辑
(3)运算符号：用小写的英文字母 f,g,h（ 或加下标 ） … 等表示 。
(4)谓词符号：用大写的英文字母 F,G,H（ 或加下标 ） … 等表示 。
(5)量词符号：,。
(6)联结词符号：,∧,∨,→,。
(7)逗号和圆括号 。
第 2章 一阶逻辑一个符号化的命题是一串由这些符号所组成的表达式,但并不是任意一个由此类符号组成的表达式就对应于一个命题 。 所以要给出严格的定义 。
定义 2.2.1 项的定义：
(1)任何一个个体变元或个体常元是项 。
(2)如果 f是 n元运算符,t1,t2,…,tn是项,则 f
（ t1,t2,…,tn） 是项 。
(3)所有的项由且仅由有限次使用 （ 1）,（ 2） 所生成 。
第 2章 一阶逻辑例如,x,a,f（ x,a）,f（ g（ x,a,b）,h
（ x））均是项，其中 h,f和 g分别是一元、二元和三元运算符。而 h（ a,b）不是项，因为 h是一元运算符，
但 h（ a,b）中 h的后面跟了两个项，同样 g（ x）也不是项（理由请读者自己考虑）。
第 2章 一阶逻辑定义 2.2.2 若 F是 n元谓词,t1,t2,…,tn是项，则
F（ t1,t2,…,tn）是原子公式。
由定义可知,原子命题是不含量词和联结词的谓词公式 。 同命题逻辑中的情况相似,这里也可以用联结词将原子公式复合成分子公式 。 （ 事实上我们已经这样做了 。 ）
第 2章 一阶逻辑定义 2.2.3 一阶逻辑中的合式公式 （ wff） 的递归定义：
（ 1） 原子公式是合式公式 。
（ 2） 若 A 是合式公式,则 （ A） 也是合式公式 。
（ 3） 若 A,G均是合式公式,则 （ A∧ B ）,
（ A∨ B）,（ A→ B） 和 （ A B） 也均是合式公式 。
（ 4） 若 F是合式公式,x是个体变元,则 xF、
xF也是合式公式 。
（ 5） 只有有限次按规则 （ 1） ～ （ 4） 构成的谓词公式才是合式公式 。
第 2章 一阶逻辑
【 例 2.2.1】 考察下列一阶公式中每个量词的辖域及每个变元的出现是约束的或自由的 。
（ 1） x（ F（ x） → yH（ x,y））
（ 2） x（ F（ x） → G（ x）） ∨ x（ F（ x） → H（ x））
（ 3） xF（ x） ∧ G（ x）
第 2章 一阶逻辑解 （ 1）全称量词 x的辖域是
（ F（ x） → yH（ x,y）），其中 x的两次出现均是约
y的辖域是 H（ x，
y），其中 y的出现是约束的,y是约束变元。
（ 2） 第一个全称量词 x的辖域是 （ F（ x） → G
（ x））,其中 x的出现均是约束出现,是约束变元；
第二个全称量词 x的辖域是 （ F（ x） → H（ x））,其中 x的出现均是约束出现,是约束变元 。
第 2章 一阶逻辑
（ 3 x的辖域是 F（ x），其中 x
的出现是约束出现，是约束变元；而 x的第三次出现是在 G（ x）中的出现，是自由出现，第三个 x是自由变元。
由例题可见，在一个一阶逻辑公式中，某个个体变元（符）的出现可以既是约束的，又是自由的，如
（ 3）中的 x。另外，同一个变元（符）即使都是约束的，也可能是在不同的量词辖域中出现，如（ 2）中的
x。为了避免混淆，可对约束变元进行换名，使得一个变元（符）在一个公式中只以一种形式出现。这样做时需遵守下面的规则：
第 2章 一阶逻辑换名规则
（ 1） 将量词的作用元及其辖域中所有同符号的变元用一个新的变元符代替 。
（ 2） 新的变元符是原公式中所没有出现的 。
（ 3） 用 （ 1）,（ 2） 得到的新公式与原公式等值 。
第 2章 一阶逻辑
【 例 2.2.2】 对公式
x（ F（ x） → G（ x,y）） ∧ H（ x,y）
换名,下面的几种做法中哪个是正确的？
（ 1） z（ F（ z） → G（ z,y）） ∧ H（ x,y）
（ 2） y（ F（ y） → G（ y,y）） ∧ H（ x,y）
（ 3） z（ F（ z） → G（ x,y）） ∧ H（ x,y）
第 2章 一阶逻辑解 只有 （ 1） 是正确的 。 （ 2） 的换名违反了规则
（ 2）,使得 G（ x,y） 中的 y的出现改变了性质 。 （ 3）
的换名违反了规则 （ 1）,使得 G（ x,y） 中的 x的出现改变了性质 。
对公式中自由出现的变元也可换符号,称为代替,
同样需要遵守下面的规则：代替规则
（ 1） 将公式中所有同符号的自由变元符用新的变元符替换 。
（ 2） 新的变元符是原公式中所没有出现的 。
（ 3） 用 （ 1）,（ 2） 得到的新公式与原公式等值 。
第 2章 一阶逻辑
【 例 2.2.3】 对公式
x（ F（ x） → G（ x,y）） ∧ H（ x,y）
做代替,下面的几种做法中哪个是正确的？
（ 1） x（ F（ x） → G（ x,y）） ∧ H（ z,y）
（ 2） x（ F（ x） → G（ x,z）） ∧ H（ u,y）
（ 3） z（ F（ z） → G（ x,y）） ∧ H（ y,y）
请读者自己做出分析 。
第 2章 一阶逻辑定义 2.2.4 没有自由变元的公式称为闭式 。
如例 2.2.1中的 （ 1）,（ 2） 两式均是闭式,而 （ 3）
不是闭式 。 事实上,仅就个体变元而言,自由变元才是真正的变元,而约束变元只在表面上是变元,实际上并不是真正意义上的变元 。 换言之,含有自由变元的公式在解释后仍是命题函数,还需赋值方成命题,
而不含自由变元的闭式一旦给出解释就成了命题 。
第 2章 一阶逻辑定义 2.2.5 一个解释 I由以下四部分组成：
（ 1） 为个体域指定一个非空集合 DI。
（ 2） 为每个个体常元指定一个个体 。
（ 3） 为每个 n元运算符指定 DI上的一个 n元运算 。
（ 4） 为每个 n元谓词符指定 DI上的一个 n元谓词 。
第 2章 一阶逻辑
【 例 2.2.4】 设 f,g均为二元运算符,E,L均为二元谓词符,给定解释 I如下：
个体域 DI为自然数集合；
f（ x,y） =x+y,g（ x,y） =x·y,a=0；
E（ x,y）,x=y,L（ x,y）,x＜ y。
求下列公式在解释 I下的真值 。
第 2章 一阶逻辑
（ 1） x yL（ x,y）
（ 2） x（ E（ f（ x,a）,x） ∧ L（ g（ x,a）,a））
（ 3） y（ E（ x,y） ∨ L（ x,y））
（ 4） E（ f（ x,a）,g（ x,a））
第 2章 一阶逻辑解 (1)式中没有自由变元,是闭式,在解释 I下的意义是：对于每一个自然数 x,均存在着自然数 y,使得 x＜ y。 显然这是一个真命题 。
（ 2） 式中也没有自由变元,是闭式,在解释 I下的意义是：对于每一个自然数 x,x+0=x并且 x·0＜ 0。 0＜ 0
不真,所以这是一个假命题 。
（ 3） 式中 x是自由变元,不是闭式,在解释 I下的意义是：对于每一个自然数 y,x=y或者 x＜ y。 因为 x取 0时,
原式为真； x取 1时,原式为假,所以这是命题函数,
而非命题 。
第 2章 一阶逻辑
（ 4） 式中 x是自由变元,不是闭式,在解释 I下的意义是,x+0=x·0。 因为 x取 0时,原式为真； x非 0时,
原式为假,所以这是命题函数,而非命题 。 如上所言,
含有自由变元的公式在解释后仍是命题函数,还需赋值方成命题 。
第 2章 一阶逻辑定义 2.2.6 赋值 υ是建立在解释 I上的函数,且有：
（ 1） υ（ xi） =,
即对自由变元 xi指派一个 DI中的个体 。
（ 2） υ（ f（ t1,t2,…,tn）） = （ υ（ t1）,
υ（ t2）,…,υ（ tn））,
其中 fi是 I对 f的解释,ti（ i=1,2,…,n） 是项 。
ia
ia
if
第 2章 一阶逻辑
【 例 2.2.5】 设 f,g均为二元运算符,E,L均为二元谓词符,给定解释 I及赋值 υ如下：
个体域 DI为自然数集合；
f（ x,y） =x+y,g（ x,y） =x·y,a=0；
E（ x,y）,x=y,L（ x,y）,x＜ y。
υ1（ x） =0,υ2（ x） =1。
求下列公式在解释 I和赋值分别为 υ1,υ2下的真值 。
第 2章 一阶逻辑
（ 1） y（ E（ x,y） ∨ L（ x,y））
（ 2） E（ f（ x,a）,g（ x,a））
（ 3） xE（ g（ x,a）,a）?
第 2章 一阶逻辑解 (1)式在解释 I及赋值 υ1下的含义是：对于每个自然数 y,0=y或者 0＜ y。 即 0是最小的自然数,这是真命题 。 在解释 I及赋值 υ2下的含义是：对于每个自然数 y，
1=y或者 1＜ y。 即 1是最小的自然数,这是假命题 。
(2)式在解释 I及赋值 υ1下的含义是,0+0=0·0,这是真命题 。 在解释 I及赋值 υ2下的含义是,1+0=1·0,这是假命题 。
第 2章 一阶逻辑
(3)式中不含自由变元,无需考虑赋值 。 在解释 I下的意义是：对于每一个自然数 x,x·0=0。 这是真命题 。
在上一节我们曾提到过,当个体域为有穷集 DI={a1，
a2,…,an}时：
xF（ x） F（ a1） ∧ F（ a2） ∧ … ∧ F（ an）
xG（ x） G（ a1） ∨ G（ a2） ∨ … ∨ G（ an）
因此，当解释 I中的个体域 D为有穷集时，可先消量词再求真值。
第 2章 一阶逻辑
【 例 2.2.6】
设解释 I为,DI={2,3},f（ 2） =3,f（ 3） =2，
F（ 2,2） =F（ 2,3） =0,F（ 3,2） =F（ 3,3） =1。
在 I下消去下列公式的量词并求真值 。
（ 1） F（ 2,f（ 2）） ∧ F（ 3,f（ 3））
（ 2） x yF（ y,x）
（ 3） x（ F（ x,f（ x）） → yF（ f（ x）,f（ y）））
第 2章 一阶逻辑解 （ 1） 式中不含量词,所以直接求真值 。
F（ 2,f（ 2）） ∧ F（ 3,f（ 3））
F（ 2,3） ∧ F（ 3,2）
0∧ 1
0
第 2章 一阶逻辑
(2) x yF（ y,x）
x（（ F（ 2,x） ∨ F（ 3,x）））
（ F（ 2,2） ∨ F（ 3,2））
∧ （ F（ 2,3） ∨ F（ 3,3））
（ 0∨ 1） ∧ （ 0∨ 1）
1∧ 1
1
第 2章 一阶逻辑
(3) x（ F（ x,f（ x）） → yF（ f（ x）,f（ y）））
（ F（ 2,f（ 2）） → yF（ f（ 2）,f（ y）） ∧ （ F（ 3,f（ 3））
→ yF（ f（ 3）,f（ y））））
（ F（ 2,f（ 2）） → （ F（ f（ 2）,f（ 2）） ∧ F（ f（ 2）,f（ 3））））
（ F（ 3,f（ 3）） → （ F（ f（ 3）,f（ 2）） ∧ F（ f（ 3）,f（ 3））））
（ F（ 2,3） → （ F（ 3,3） ∧ F（ 3,2）））
∧ （ F（ 3,2） → （ F（ 2,3） ∧ F（ 2,2）））
（ 0→ （ 1∧ 1）） ∧ （ 1→ （ 0∧ 0））
（ 0→ 1） ∧ （ 1→ 0）
1∧ 0
0
第 2章 一阶逻辑定义 2.2.7 一阶逻辑公式的分类：
永真式 （ 逻辑有效式 ） 在任何解释 I及 I的任何赋值下均为真的一阶公式；
永假式 （ 矛盾式 ） 在任何解释 I及 I的任何赋值下均为假的一阶公式；
可满足式 至少有一种解释和一种赋值使其为真的一阶公式 。
第 2章 一阶逻辑由定义可知,要判定一个公式 A不是永真式,只需找到一个解释 I和 I下的一个赋值 υ,使 A在 I和 υ下为假；
要判定一个公式 A不是永假式,只需找到一个解释 I和 I
下的一个赋值 υ,使 A在 I和 υ下为真；要判定一个公式 A
是可满足式,只需找到一个解释 I和 I下的一个赋值 υ，
使 A在 I和 υ下为真,再找到一个解释 I和 I下的一个赋值 υ，
使 A在 I和 υ下为假 。
第 2章 一阶逻辑
【 例 2.2.7】 讨论下列公式的类型：
（ 1） xF（ x） → xF（ x）
（ 2） x G（ x） ∧ xG（ x）
（ 3） x yF（ x,y） → y xF（ x,y）
第 2章 一阶逻辑解 （ 1） 公式 xF（ x） → xF（ x） 在任何解释 I
下的含义是：如果个体域 DI中的每个元素 x均有性质 F，
则 DI中的某些元素 x必有性质 F。 前件 xF（ x） 为真时,
xF（ x） 永远为真,所以公式
xF（ x） → xF（ x） 是永真式 。
第 2章 一阶逻辑
（ 2）公式 x G（ x） ∧ xG（ x）在任何解释 I下的含义是：个体域 DI中的每个元素 x均不具有性质 G，
且 DI中的某些元素 x具有性质 G。这是两个互相矛盾的命题，不可能同时成立，所以公式
x G（ x） ∧ xG（ x）是永假式。
第 2章 一阶逻辑
（ 3）公式 x yF（ x,y） → yxF（ x,y）既不是永真式，也不是永假式。由于这是闭式，故无需考虑赋值，只要给出一个使其成真的解释和一个使其成假的解释即可。
① 给定解释 I1,DI1为自然数集,F（ x,y）,x＜ y。
此时公式的前件 x yF（ x,y） 表示,对于每个自然数 x,均有自然数 y比 x大,是真命题,y xF
（ x,y） 表示,存在着自然数 y比每个自然数 x均大,是假命题 。 因此,I1是使 x yF（ x,y） → y xF
（ x,y） 为假的解释 。
第 2章 一阶逻辑
② 给定解释 I2,DI2为自然数集,F（ x,y）,x＞ y。
此时公式的前件 x yF（ x,y） 表示,对于每个自然数 x,均有自然数 y比 x小,是假命题 （ x为 0时,y不存在 ）,因此,I2是使 x yF（ x,y） → y xF（ x，
y） 为真的解释 。
第 2章 一阶逻辑定义 2.2.8 设 A（ p1,p2,…,pn）是含命题变元 p1，
p2,…,pn的命题公式,B（ B1,B2,…,Bn）是以一阶公式 B1,B2,…,Bn分别代替 p1,p2,…,pn在 A中的所有出现后得到的一阶公式，称 B是 A的一个代换实例。
例如,F（ x） → G（ y）,xF（ x） → yG（ y）
均是命题公式 p→q 的代换实例,也是 p的代换实例 。 显然有以下定理 。
第 2章 一阶逻辑定理 2.2.1 命题逻辑永真式的任何代换实例必是一阶逻辑的永真式 。 同样,命题逻辑永假式的任何代换实例必是一阶逻辑的永假式 。
证明略 。
定理 2.2.1为我们提供了一大类一阶逻辑的有效式 。
因此,判断一个一阶逻辑公式是否是永真式或永假式,
我们既可以用定义 2.2.7（ 如例 2.2.7）,也可以用其是否是命题逻辑的永真式或永假式的代换实例来判断 。
第 2章 一阶逻辑
2.3 等值演算和前束范式定义 2.3.1 设 A与 B是公式,若 A B是永真式,则称 A与 B等值,或称 A与 B逻辑等价,记作 A B。
第 2章 一阶逻辑显然,A B当且仅当在任何解释 I和 I中的任意赋值 υ下,A与 B有相同的真值。即在 I和 υ下,A为真当且仅当 B为真，或者,A为假当且仅当 B为假。同时，要证明两个公式不等值，只需找到一个解释 I和 I中的一个赋值 υ，使得两个公式在 I和 υ下，一个为真，另一个为假。
第 2章 一阶逻辑
【 例 2.3.1】 判断公式 F（ x） 和 F（ y） 是否等值 。
解 F（ x）表示 "x具有性质 F",F（ y）表示 "y具有性质 F"，容易看出两个意思并不一样。取解释 I：个体域 D为整数集,F（ x）,x是奇数，赋值 υ（ x） =1,υ
（ y） =2，则在 I和 υ下,F（ x）为真,F（ y）为假。因此,F（ x）与 F（ y）不等值。
第 2章 一阶逻辑
【 例 2.3.2】 判断公式 x yF（ x,y）
y xF（ x,y） 是否等值 。
解 直接观察是不等值的。由于两个公式均是闭式，
所以只需给出一个解释 I，使其在 I下一个为真，另一个为假。取解释 I,D为鞋子的集合,F（ x,y）,x与 y能配成一双。则在 I下,x yF（ x,y）表示“每一只鞋子均有另一只鞋子能与其配成一双”是真命题，而公式
y xF（ x,y）表示“有这样的鞋子能与任何一只鞋子配成一双”是假命题。因此，两个公式 x yF
（ x,y y xF（ x,y）不等值。
第 2章 一阶逻辑量词转换律 （ A（ x） 是任一一阶公式 ）
xA（ x） x A（ x） （ 1）
xA（ x） x A（ x） （ 2）
第 2章 一阶逻辑量词辖域扩缩律 （ A（ x） 是任一一阶公式,B是任一不含 x的一阶公式 ）
xA（ x） ∧ B x（ A（ x） ∧ B） （ 1）
xA（ x） ∨ B x（ A（ x） ∨ B） （ 2）
xA（ x） ∧ B x（ A（ x） ∧ B） （ 3）
xA（ x） ∨ B x（ A（ x） ∨ B） （ 4）
第 2章 一阶逻辑证明
（ 1） 在任何解释 I和 I中的任意赋值 υ下,
xA（ x） ∧ B=1
当且仅当 xA（ x） =1且 B=1
当且仅当 B=1且对于 DI中的每一个元素 c,A（ c） =1
当且仅当 对于 DI中的每一个元素 c,A（ c） ∧ B=1
当且仅当 x（ A（ x） ∧ B） =1
第 2章 一阶逻辑
（ 2） 在任何解释 I和 I中的任意赋值 υ下,
xA（ x） ∨ B=0
当且仅当 xA（ x） =0且 B=0
当且仅当 B=0且存在 DI中的元素 c,使得 A（ c） =0
当且仅当 存在 DI中的元素 c,使得 A（ c） ∨ B=0
当且仅当 x（ A（ x） ∨ B） =0
第 2章 一阶逻辑
( 3 ) ( ) ( ( ) )
( ( ) ) )
( ( ) ) )
( ( ) )
()
()
x A x B x A x B
x A x B
x A x B
x A x B
x A x B
x A x B
第 2章 一阶逻辑
（ 4） 式的证明留给读者 。
另外,下面的等值式也称作量词辖域的扩缩律 。
( 5 ) ( ) ( ( ) )
( 6 ) ( ) ( ( ) )
( 7 ) ( ) ( ( ) )
( 8 ) ( ) ( ( ) )
x A x B B x A x B
B x A x x B A x
x A x B x A x B
B x A x x B A x
第 2章 一阶逻辑证明 （ 5）
( ) ( )
()
( ( ) )
( ( ) )
x A x B x A x B
x A x B
x A x B
x A x B
（ 6）、（ 7）、（ 8）的证明留给读者。
第 2章 一阶逻辑量词分配律 A（ x）,B（ x）是任一一阶公式）
( 1 ) ( ( ) ( ) ) ( ) ( )
( 2) ( ( ) ( ) ) ( ) ( )
x A x B x x A x x B x
x A x B x x A x x B x
第 2章 一阶逻辑证明 （ 1） 在任何解释 I和 I中的任意赋值 υ下,
x（ A（ x） ∧ B（ x）） =1
当且仅当 对于 DI中的每一个元素 c，
A（ c） ∧ B（ c） =1
当且仅当 对于 DI中的每一个元素 c，
A（ c） =1且 B（ c） =1
当且仅当 xA（ x） =1且 xB（ x） =1
当且仅当 xA（ x） ∧ xB（ x） =1
第 2章 一阶逻辑
( 2 ) ( ( ) ( ) ) ( ( ( ) ( ) ) )
( ( ( ) ( ) ) )
( ( ( ) ( ) ) )
( ( ) ( ) )
( ( ) ( ) )
( ) ( )
x A x B x x A x B x
x A x B x
x A x B x
x A x x B x
x A x x B x
x A x x B x
第 2章 一阶逻辑
【 例 2.3.3】 证明下列等值式,
( 1 ) ( ( ) ( )) ( ( ) ( ))
( 2 ) ( ( ) ( ) (,))
(( ( ) ( )) (,))
x F x G x x F x G x
x y F x G x H x y
x y F x G y H x y
第 2章 一阶逻辑证明
( 1 ) ( ( ) ( )
( ( ) ( ) )
( ( ) ( ) )
( ( ) ( ) )
( 2 ) ( ( ) ( ) (,) )
( ( ) ( ) (,) )
( ( ) ( ) (,) )
( ( ( ) ( ) ) (,) )
x F x G x
x F x G x
x F x G x
x F x G x
x y F x G y H x y
x y F x G y H x y
x y F x G y H x y
x y F x G y H x y
第 2章 一阶逻辑定义 2.3.2 设 A为一阶公式,若 A具有如下形式
Q1x1Q2x2…QkxkB
则称 A为前束范式 。 其中 Qi（ 1≤i≤k） 是量词符或
,xi（ 1≤i≤k） 是变元符,B是不含量词的公式 。
第 2章 一阶逻辑在一阶逻辑推理中,需要将公式化成前束范式形式,这总是可以办到的 。 即任何一个一阶公式均可等值演算成前束范式,化归过程如下：
（ 1） 消去除,∧,∨ 之外的联结词；
（ 2） 将否定符 移到量词符后；
（ 3） 换名使各变元不同名；
（ 4） 扩大辖域使所有量词处在最前面 。
第 2章 一阶逻辑
【 例 2.3.4】 将下面公式化成前束范式。
( 1 ) ( ( ) (,) (,))
( 2 ) ( ( ) ( ( ) ( (,)) )) ( (,) ( )
x F x yG y z z H x z
x F x y F y F f x y y G x y F y
第 2章 一阶逻辑解
( 1 ) ( ( ) (,) (,)
( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z t H x t
x y t F x G y z H x z
第 2章 一阶逻辑
( 2 ) ( ( ) ( ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( (,) ( ))
((
x F x y F y F f x y y G x y F y
x F x y F y F f x y y y G x y F y
x F x y F y F f x y y G x y F y
x F x y F y F f x y y G x y F y
t F t
) ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ) ( (,)) (,) ( ))
yF y F f t y z G x z F z
t y z F t F y F f t y G x z F z
第 2章 一阶逻辑
2.4 一阶逻辑推理理论在一阶逻辑中,由前提 A1,A2,…,An推出结论 B
的形式结构仍然是 A1∧ A2∧ …∧ An→ B。 如果此式是永真式,则称由前提 A1,A2,…,An推出结论 B的推理正确,记作 A1∧ A2∧ …∧ An B或者 A1,A2,…,An B，
否则称推理不正确 。
第 2章 一阶逻辑由于谓词演算是在命题演算的基础上,进一步扩大了谓词与量词的功能,因此容易想到,命题演算中有关推理演绎的规则基本上适用于谓词演算,即在命题逻辑中的各项推理规则在一阶逻辑推理中仍然适用,
当然也会有不少只适用于谓词演算的概念与规则 。
全称量词消去规则 （ 简称 UI规则 ）
()
()
x A x
At
第 2章 一阶逻辑规则成立的条件：
（ 1） t是任意个体变项或常项 。
（ 2） A（ t） 中约束变元个数与 A（ x） 中约束变元个数相同 。
第 2章 一阶逻辑全称量词引入规则（简称 UG规则）
()
()
At
x A x?
规则成立的条件：
（ 1） A（ t） 在任何解释 I及 I中对 t的任何赋值下均为真 。
（ 2） x不在 A（ t） 中约束出现 。
第 2章 一阶逻辑存在量词引入规则 （ 简称 EG规则 ）
()
()
Ac
x A x?
规则成立的条件：
（ 1） c是特定的个体常元 。
（ 2） x不在 A（ c）中出现。
第 2章 一阶逻辑规则成立的条件：
（ 1） c是使 A（ c） 为真的特定的个体常元 。
（ 2） xA（ x） 是闭式,且 c不在 A（ x） 中出现 。
特别需要注意的是,使用这些规则的条件非常重要,如在使用过程中违反了这些条件就可能导致错误的结论 。
()
()
x A x
Ac
存在量词消去规则（简称 EI规则）
第 2章 一阶逻辑
【 例 2.4.1】 证明推理 "所有的自然数均是实数,3
是自然数,因此,3是实数 。 "正确 。
解 设 N（ x）,x是自然数,R（ x）,x是实数,则推理形式化为：
x（ N（ x） → R（ x））,N（ 3） R（ 3）
下面进行证明 。
（ 1） x（ N（ x） → R（ x）） 前提引入
（ 2） N（ 3） → R（ 3） （ 1） UI
（ 3） N（ 3） 前提引入
（ 4） R（ 3） （ 2） （ 3） 假言推理
第 2章 一阶逻辑
【 例 2.4.2】 构造下面推理的证明：
前提 x（ F（ x） → （ G（ x） ∧ H（ x）））,
x（ F（ x） ∧ P（ x））
x（ P（ x） ∧ H（ x））
第 2章 一阶逻辑解
（ 1） x（ F（ x） → （ G（ x） ∧ H（ x））） 前提引入
（ 2） x（ F（ x） ∧ P（ x）） 前提引入
（ 3） F（ c） ∧ P（ c） (2)EI
（ 4） F（ c） → （ G（ c） ∧ H（ c）） （ 1） UI
（ 5） F（ c） （ 3） 化简
（ 6） G（ c） ∧ H（ c） （ 4） （ 5） 假言推理
（ 7） P（ c） （ 3） 化简
（ 8） H（ c） （ 6） 化简
（ 9） P（ c） ∧ H（ c） （ 7） （ 8） 合取引入
（ 10） x（ P（ x） ∧ H（ x）） （ 9） EG
第 2章 一阶逻辑
【 例 2.4.3】 设前提为 x yF（ x,y）,下面推理是否正确？
（ 1） x yF（ x,y） 前提引入
（ 2） y F（ y,y） （ 1） UI
解 x yF（ x,y yF（ y,y）的推理并不正确。如果给定解释 I：个体域为实数集,F（ x,y）,x
＞ y。则 x yF（ x,y）意为 "对于每个实数 x，均存在着比之更小的实数 y" yF（ y，
y）意为 "存在着比自己小的实数 "，是假命题。之所以出现这样的错误，是违反了 UI规则成立的条件（ 2）。
第 2章 一阶逻辑
【 例 2.4.4】 设前提为 x yF（ x,y）,下面推理是否正确？
（ 1） x yF（ x,y） 前提引入
（ 2） yF（ t,y） （ 1） UI
（ 3） F（ t,c） （ 2） EI
（ 4） xF（ x,c） （ 3） UG
（ 5） y xF（ x,y） （ 4） EG
第 2章 一阶逻辑解 x yF（ x,y） y xF（ x,y） 的推理并不正确 。 取与例 2.4.3相同的解释,则由 x yF（ x,y）
为真,y xF（ x,y） 意为 "存在着最小实数 ",是假命题,知推理不正确 。 之所以出现这样的错误,是第 （ 3） 步违反了 EI规则成立的条件 （ 2） 。
第 2章 一阶逻辑
【 例 2.4.5】 构造下面推理的证明：
前提 x（ F（ x） → G（ x））
结论 xF（ x） → xG（ x）
分析 本题直接证明很困难,注意到结论部分是蕴涵式,应考虑用附加前提证明法 。
第 2章 一阶逻辑证明
（ 1） x（ F（ x） → G（ x）） 前提引入
（ 2） xF（ x） 附加前提引入
（ 3） F（ t） （ 2） UI
（ 4） F（ t） → G（ t） （ 3） UI
（ 5） G（ t） （ 3） （ 4） 假言推理
（ 6） xG（ x） （ 5） UG
（ 7） xF（ x） → xG（ x） CP
第 2章 一阶逻辑
【 例 2.4.6】 构造下面推理的证明：
前提 x（ F（ x） → G（ x））
结论 x（ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
分析 本题直接证明会感到无从下手,而由于结论并非蕴涵式 （ x的辖域是其后整个公式 ）,附加证明法也不适用,此时我们应考虑归缪法 。
第 2章 一阶逻辑证明
（ 1） x（ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
否定结论引入
（ 2） x （ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
（ 1） 置换
第 2章 一阶逻辑
（ 3） （ y（ F（ y） ∧ H（ a,y））
→ z（ G（ z） ∧ H（ a,z）））
（ 2） EI
（ 4） y（（ F（ y） ∧ H（ a,y）） ∧
z（ G（ z） ∧ H（ a,z）））
（ 3） 置换
第 2章 一阶逻辑
（ 5） y（ F（ y） ∧ H（ a,y）） （ 4） 化简
（ 6） F（ b） ∧ H（ a,b） （ 5） EI
（ 7） F（ b） （ 6） 化简
（ 8） x（ F（ x） → G（ x）） 前提引入
（ 9） F（ b） → G（ b） （ 8） UI
（ 10） G（ b） （ 7） （ 9） 假言推理
（ 11） z（ G（ z） ∧ H（ a,z）） （ 3） 化简
第 2章 一阶逻辑
（ 12） z（ G（ z） ∨ H（ a,z）） （ 11） 置换
（ 13） G（ b） ∨ H（ a,b） （ 12） UI
（ 14） H（ a,b） （ 6） 化简
（ 15） H（ a,b） （ 14） 置换
（ 16） G（ b） （ 13） （ 15） 析取三段论
（ 17） G（ b） ∧ G（ b） （ 10） （ 16） 合取引入
第 2章 一阶逻辑
2.5 例题选解
【 例 2.5.1】 在高等数学中极限定义为：任给小正数 ε,则存在正数 δ,使得当
0＜ |x-a|＜ ε时,恒有 |f（ x） -b|＜ δ成立 。
将上述定义用一阶逻辑公式表示 。
lim ( )xa f x b
第 2章 一阶逻辑分析 因为高等数学中的极限概念是在实数范围内给出的,所以不妨设定个体域为实数域 。 观察整个定义,
只有一种,小于,关系,这应当用一个二元谓词表示；
而,差的绝对值,是一个运算,应当用运算符表示 。
解 设 L（ x,y）,x＜ y,g（ x,y）,|x-y|,则定义可表示为：
ε（ L（ 0,ε） → δ（ L（ 0,δ） ∧ x（（ L（ 0,g
（ x,a）） ∧ L（ g（ x,a）,δ））
→ L（ g（ f（ x）,b）,ε））））
第 2章 一阶逻辑
【 例 2.5.2】 在一阶逻辑中符号化自然数的三条公理 。
（ 1） 每个数都有唯一的一个数是它的后继数 。
（ 2） 没有一个数使 0为它的后继数 。
（ 3） 每个不等于 0的数都有唯一的一个数是它的直接先行者 。
分析 在符号化命题的过程中,设定谓词尽可能少是一个原则 。 注意到 "x是 y的后继数 "与 "y是 x的直接先行者 "含义相同,所以可用一个谓词表示 。
第 2章 一阶逻辑解 设 N（ x）,x是自然数,F（ x,y）,x是 y的后继数,G（ x,y）,x=y,则
（ 1） x（ N（ x） → !y（ N（ y） ∧ F（ y,x）））
（ 2） x（ N（ x） ∧ F（ 0,x））
（ 3） x（（ N（ x） ∧ G（ x,1））
→ !y（ N（ y） ∧ F（ x,y）））
第 2章 一阶逻辑
【 例 2.5.3】 !xF（ x） 表达成仅用量词和
。
分析 !xF（ x） 的意思是：有唯一的 x具有性质 F。
即有 x具有性质 F,且若还有 y也具有性质 F,则必有 x=y。
解
!xF（ x） x（ F（ x） ∧ y（ F（ y） → x=y））
第 2章 一阶逻辑
【 例 2.5.4】 设个体域为 {a,b,c},消去下列公式中的量词 。
（ 1） xF（ x） ∧ yG（ y）
（ 2） x y（ F（ x） ∧ G（ y））
（ 3） x y（ F（ x,y） → G（ y））
第 2章 一阶逻辑解 （ 1） xF（ x） ∨ yG（ y）
（ F（ a） ∧ F（ b） ∧ F（ c）） ∧ （ F（ a）
∨ F（ b） ∨ F（ c））
（ 2） x y（ F（ x） ∧ G（ y））
y（ F（ a） ∧ G（ y）） ∧ y（ F（ b） ∧ G（ y）） ∧
y（ F（ c） ∧ G（ y））
（（ F（ a） ∧ G（ a）） ∨ （ F（ a） ∧ G（ b）） ∨ （ F
（ a） ∧ G（ c））） ∧
（（ F（ b） ∧ G（ a）） ∨ （ F（ b） ∧ G（ b）） ∨
（ F（ b） ∧ G（ c））） ∧ （（ F（ c） ∧ G（ a）） ∨ （ F
（ c） ∧ G（ b）） ∨ （ F（ c） ∧ G（ c）））
第 2章 一阶逻辑
（ 3） x y（ F（ x,y） → G（ y））
y（ F（ a,y） → G（ y）） ∧ y（ F（ b,y） → G
（ y）） ∧ y（ F（ c,y） → G（ y））
（（ F（ a,a） → G（ a）） ∨ （ F（ a,b） → G（ b））
∨ （ F（ a,c） → G（ c））） ∧
（（ F（ b,a） → G（ a）） ∨ （ F（ b,b） → G（ b））
∨ （ F（ b,c） → G（ c））） ∧
（（ F（ b,a） → G（ a）） ∨ （ F（ b,b） → G（ b））
∨ （ F（ b,c） → G（ c）））
第 2章 一阶逻辑
【 例 2.5.5】 构造下面推理的证明：
前提 xF（ x） ∨ xG（ x）
结论 x（ F（ x） ∨ G（ x））
证明
（ 1） xF（ x） ∨ xG（ x） 前提引入
（ 2） x y（ F（ x） ∨ G（ y）） （ 1） 置换
（ 3） y（ F（ t） ∨ G（ y）） （ 2） UI
（ 4） F（ t） ∨ G（ t） （ 3） UI
（ 5） x（ F（ x） ∨ G（ x）） （ 4） UG
第 2章 一阶逻辑习 题 二
1,在一阶逻辑中将下列命题符号化 。
（ 1） 天下乌鸦一般黑 。
（ 2） 没有不散的筵席 。
（ 3） 闪光的未必是金子 。
（ 4） 有不是奇数的素数 。
（ 5） 有且仅有一个偶素数 。
（ 6） 猫是动物,但并非所有的动物都是猫 。
第 2章 一阶逻辑
（ 7） 骆驼都比马大 。
（ 8） 有的骆驼比所有的马都大 。
（ 9） 所有的骆驼都比某些马大 。
（ 10） 有的骆驼比某些马大 。
第 2章 一阶逻辑
2,取个体域为实数集 R,函数 f在点 a处连续的定义是,f在 a点连续,当且仅当对每一个小正数 ε,都存在正数 δ,使得对所有的 x,若 |x-a|＜ δ,则 |f（ x） -f（ a）
|＜ ε。 把上述定义用符号的形式表示 。
3,在整数集中,确定下列命题的真值,运算 "·"
是普通乘法 。
（ 1） x y（ x·y=0）
（ 2） x y（ x·y=1）
（ 3） y x（ x·y=1）
（ 4） y x（ x·y=x）
第 2章 一阶逻辑
4,给定谓词如下,试将下列命题译成自然语言 。
P（ x）,x是素数 。 E（ x）,x是偶数 。 O（ x）,x是奇数 。 D（ x,y）,x整除 y。
（ 1） E（ 2） ∧ P（ 2）
（ 2） x（ D（ 2,x） → E（ x））
（ 3） x（ E（ x） ∧ D（ x,6））
（ 4） x（ E（ x） → D（ 2,x））
第 2章 一阶逻辑
（ 5） x（ E（ x） → y（ D（ x,y） → E（ y）））
（ 6） x（ O（ x） → y（ P（ y） → D（ x,y）））
（ 7） x（ P（ x） → y（ E（ y） ∧ D（ x,y）））
（ 8） x（ E（ x） ∧ P（ x） ∧ y（ E（ y） ∧ P（ y）
∧ x≠y））
第 2章 一阶逻辑
5,指出下面公式中的变量是约束的,还是自由的,
并指出量词的辖域 。
（ 1） x（ F（ x） ∧ G（ x）） → x（ F（ x） ∧ H（ x））
（ 2） xF（ x） ∧ xG（ x） ∨ （ xF（ x） → G（ x）））
（ 3） x（（ F（ x） ∧ G（ x,y））
→ （ xF（ x） ∧ R（ x,y,z）））
（ 4） x(yF（ x,y,z） y xF（ x,y,z）
第 2章 一阶逻辑
6,设个体域 D={a,b,c},消去下列各式中的量词 。
（ 1） xF（ x） → y F（ y）
（ 2） x（ F（ x） ∨ yG（ y））
（ 3） x y（ F（ x） → G（ y））
（ 4） x yF（ x,y,z）
7,求下列公式在解释 I下的真值 。
（ 1） x（ F（ x） ∨ G（ x））,解释 I：个体域 D={1,2}；
F（ x）,x=1； G（ x）,x=2。
（ 2） x（ p→Q （ x）） ∨ R（ a）,解释 I：个体域 D={-2，
3,6}； p,1＜ 2； Q（ x）,x≤3,R（ x）,x＞ 5； a,5。
第 2章 一阶逻辑
8,给定解释 I和 I中赋值 v如下：
个体域 D为实数集,E（ x,y）,x=y,G（ x,y）,x＞
y,N（ x）,x是自然数,
f（ x,y） =x-y,g（ x,y） =x+y,N（ x,y） =x·y
v（ x） =1,v（ y） =-2
第 2章 一阶逻辑求下列公式在解释 I和赋值 v下的真值 。
（ 1） x yE（ g（ x,y）,g（ y,x））
（ 2） N（ x） ∧ y（ N（ y） →
（ G（ y,x） ∨ E（ y,x）））
（ 3） y zE（ N（ y,z）,x）
（ 4） x yE（ N（ f（ x,y）,g（ x,y））,
f（ N（ x,x）,N（ y,y）））
（ 5） E（ g（ x,g（ x,y））,a）
第 2章 一阶逻辑
11,证明量词辖域扩缩律 （ 4）,
x A（ x） ∨ B x（ A（ x） ∨ B）
12,证明量词辖域扩缩律：
（ 6） B→ xA（ x） x（ B→ A（ x））
（ 7） xA（ x） → B x（ A（ x） → B）
（ 8） B→ xA（ x） x（ B→ A（ x））
13,用等值演算证明下列等值式 。
（ 1） x（ F（ x） → G（ x）） y F（ y） → zG（ z）
（ 2） x y（ F（ x） → G（ y）） xF（ x） → yG（ y）
（ 3） x（ F（ x） ∧ G（ x）） （ xG（ x） → xF（ x））
第 2章 一阶逻辑
14,将下列公式化成与之等值的前束范式 。
（ 1） x（ F（ x） → yG（ x,y））
（ 2） （ xF（ x） ∨ xG（ x）） → x（ F（ x） ∨ G（ x））
（ 3） xF（ x） → x（ yG（ x,y） ∨ yH（ x,y,z））
（ 4） （ xF（ x） ∨ yG（ y）） ∧ （ F（ x） → zH（ z））
第 2章 一阶逻辑
15,构造下列推理的证明：
（ 1） xF（ x） ∧ xG（ x）
x（ F（ x） ∧ G（ x））
（ 2） 前提,x（ F（ x） ∨ G（ x））
结论,xF（ x） ∨ xG（ x）
（ 提示：用附加前提法或归缪法证明 ）
（ 3） 前提,x（ F（ x） → G（ x））
结论,x y（ F（ y） ∧ H（ x,y））
→ x（ G（ x） ∧ H（ x,x））
第 2章 一阶逻辑
（ 4） 前提,xF（ x）,x（（ F（ x） ∨ G（ x））
→ H（ x））
xH（ x）
（ 5） xF（ x） → x（（ F（ x） ∨ G（ x））
→ R（ x））,xF（ x）,xG（ x）
x y（ R（ x） ∧ R（ y））
（ 6） 前提,x（ y（ S（ x,y） ∧ M（ y））
→ z（ P（ z） ∧ R（ x,z）））
结论,zP（ z） → x y（ S（ x,y） → M（ y））
第 2章 一阶逻辑
16,在一阶逻辑中构造下列推理的证明 。
（ 1） 有理数都是实数 。 有的有理数是整数 。 因此,
有的实数是整数 。
（ 2） 所有的有理数都是实数 。 所有的无理数也都是实数 。 任何虚数都不是实数 。 所以,虚数既非有理数也非无理数 。
（ 3） 不存在不能表示成分数的有理数 。 无理数都不能表示成分数 。 所以,无理数都不是有理数 。
第 2章 一阶逻辑
17,在一阶逻辑中构造下列推理的证明 。
（ 1） 有些病人相信所有的医生 。 所有的病人都不相信骗子 。 因此,所有的医生都不是骗子 。
（ 2） 任何人如果他喜欢步行,他就不喜欢乘汽车 。
每个人或者喜欢乘汽车,或者喜欢骑自行车 。 有的人不爱骑自行车 。 因此有的人不爱步行 。
2.1 一阶逻辑的基本概念
2.2 一阶逻辑公式及解释
2.3 等值演算和前束范式
2.4 一阶逻辑推理理论
2.5 例题选解习 题 二第 2章 一阶逻辑
2.1 一阶逻辑的基本概念首先我们将简单命题的结构分解成个体和谓词 。
个体 （ 客体 ） 我们讨论的对象 。 可以是具体的,
也可以是抽象的 。
个体域 （ 论域 ） 个体所构成的非空集合 。
全总个体域 （ 无限域 ） 包含宇宙中一切事物的个体域 。
谓词 简单命题中,表示一个个体的性质或多个个体间的关系的词 。
第 2章 一阶逻辑之所以称之为谓词,是因为谓词和个体词一起构成了简单命题中的主谓结构 。 如：
小王是学生 。
3是素数 。
整除 6。
2加 3等于 5。
上面这些简单命题中,小王,2,3,5,6均是个体,"…… 是学生 ","…… 是素数 ","…… 整除 …… "，
"…… 加 …… 等于 …… "均是谓词 。
第 2章 一阶逻辑前两个谓词描述的是一个个体的性质,称为一元谓词；第三个表示两个个体之间的关系,称为二元谓词；第四个表示三个个体之间的关系,称为三元谓词 。
以此类推,我们将描述 n（ n≥2） 个个体之间关系的谓词称为 n元谓词 。 通常用大写字母 F,G,H（ 可加下标 ）
来表示谓词 。
第 2章 一阶逻辑
F表示 "…… 是学生 "；
G表示 "…… 整除 …… "；
H表示 "…… 加 …… 等于 …… "。
这时 F,G,H表示的是具体的谓词,称为谓词常元,否则,称为谓词变元 。 显然,单独的一个谓词
（ 即使是谓词常元 ） 并不能构成一个完整的句子,必须以个体词取代 "…… "方能构成一个句子 。
第 2章 一阶逻辑通常我们用小写的英文字母 a,b,c（ 可加下标 ）
等表示个体 。 这样,"小王是学生 "可符号化为 F（ a）,
其中 a表示小王 。 若用 b表示小李,则 F（ b） 就表示 "小李是学生 "。 若用 c1表示 2,用 c2表示 6,则 G（ c1,c2）
就表示 "2整除 6"。
这里,a,b,c1,c2均是具体的个体,称为个体常元 。 一般地,我们用 F（ x） 表示 "x是学生 ",其中的 x
称为个体变元 （ 简称变元,亦称个体词 ） 。 类似,我们也可用 G（ x,y） 表示 "x整除 y"。
第 2章 一阶逻辑我们称由谓词符和变元符组成的符号串为命题函数 。 之所以称为命题函数,是因为命题函数不是命题,
只有谓词为常元并将其中的变元代以具体的个体后,
才能构成命题 。 例如,"G（ x,y）,x整除 y。 "并不是命题,但若取 a,2,b,6,则 G（ a,a）,G（ a,b）
以及 G（ b,a） 均是命题,前两个是真命题,第三个是假命题 。 G（ a,a）,G（ a,b） 等称为 0元谓词,它们不含个体变元,0元谓词即命题 。
第 2章 一阶逻辑
【 例 2.1.1】 将下列语句形式化为谓词逻辑中的命题或命题函数 。
（ 1） 小王是二年级大学生 。
（ 2） 小王是李老师的学生 。
（ 3） 如果 x≤y且 y≤x,则 x=y。
解
（ 1） 令 F（ x）,x是大学生； G（ x）,x是二年级的； a：小王 。 则原句形式化为：
F（ a） ∧ G（ a） 。
第 2章 一阶逻辑
（ 2） 令 F（ x,y）,x是 y的学生； a：小王； b：李老师 。 则原句形式化为：
F（ a,b） 。
（ 3） 令 F（ x,y）,x≤y； G（ x,y）,x=y。 式化为：
（ F（ x,y） ∧ F（ y,x）） → G（ x,y） 。
第 2章 一阶逻辑前两句均是命题,第三句因为含有变元所以是命题函数 。 但实际上我们知道,只要将 x,y限制在数的范围内,第三句是定理,是永真的 。 这就涉及到了个体域 。 在简单命题中,常有一些表示数量关系的词语,
诸如 "所有的 ","有一些 "等等,用来表示论域中的全体或部分个体,在谓词逻辑中,我们用量词把它们形式化 。
第 2章 一阶逻辑
1,全称量词,"
全称量词用来表示个体域中的全体 。 表自然语言中的 "所有的 ","任意的 ","每一个 "等等 。 如：
"任意偶数均能被 2整除 。 "
句子可改写成：“在偶数集合中的任意的 x,x能被 2整除。”取个体域为偶数集，用 F（ x）表示,x能被 2整除”，用 x表示“任意的 x”，则原句形式化为：
xF（ x）。
第 2章 一阶逻辑
2,存在量词,"
。 表自然语言中的 "存在着一些 ","至少有一个 ","有 "等等 。 如：
"我们班有人会吸烟 。 "
句子可改写成,"在我们班有一些 x,x会吸烟 。 "
取个体域为 "我们班的同学 ",用 G（ x） 表示 "x会吸烟 ",x表示 "有些 x",xG（ x） 。
第 2章 一阶逻辑
【 例 2.1.2】 在全总个体域中形式化下列命题：
（ 1） 任意的偶数均能被 2整除 。
（ 2） 我们班有人吸烟 。
解
（ 1） 引入特性谓词 H（ x）,x是偶数 。
"任意的偶数均能被 2整除 "的涵义是：全总个体域中有子集 --偶数集,该子集中的每个元素均具有一种性质,世间万物,只要你属于这个子集,你就必然具有这种性质,所以是蕴含式 。 特性谓词以蕴含式的前件加入 。 则原句可形式化为：
x（ H（ x） → F（ x））?
第 2章 一阶逻辑
（ 2） 引入特性谓词 W（ x）,x是我们班的人 。
"我们班有人吸烟 "的涵义可以这样理解：在宇宙间的万物 （ 全总个体域 ） 中,有一个子集 --我们班,还有另一个子集 --吸烟的人 。 强调的是既在我们班,又吸烟的的人,所以是两个子集的交集 。 特性谓词用合取项加入 。 则原句可形式化为：
x（ W（ x） ∧ G（ x））?
第 2章 一阶逻辑
【 例 2.1.3】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 没有不犯错误的人 。
（ 2） 人总是要犯错误的 。
解 设 M（ x）,x是人,F（ x）,x犯错误 。 则原句形式化为：
（ 1） x（ M（ x） ∧ F（ x））
（ 2） x（ M（ x） → F（ x））
第 2章 一阶逻辑
【 例 2.1.4】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 所有的病人都相信医生 。
（ 2） 有的病人相信所有的医生 。
（ 3） 有的病人不相信某些医生 。
（ 4） 所有的病人都相信某些医生 。
第 2章 一阶逻辑解 设 F（ x）,x是病人,G（ x）,x是医生,H（ x，
y）,x相信 y。
（ 1） 本命题的意思是：对于每一个 x,如果 x是病人,那么对于每一个 y,只要 y是医生,x就相信 y。 因此,
本命题符号化为：
x（ F（ x） → y（ G（ y） → H（ x,y）））
或 x y（（ F（ x） ∧ G（ y）） → H（ x,y）
第 2章 一阶逻辑
（ 2） 本命题的意思是：存在着这样的 x,x是病人且对于每一个 y,只要 y是医生,x就相信 y。 因此,本命题符号化为：
x（ F（ x） ∧ y（ G（ y） → H（ x,y））
第 2章 一阶逻辑
（ 3） 本命题的意思是：存在着这样的 x和 y,x是病人,y是医生,x不相信 y。 因此,本命题符号化为：
x y（ F（ x） ∧ G（ y） ∧ H（ x,y））
或 (x（ F（ x） ∧ y（ G（ y） ∧ H（ x,y）））
（ 4） 本命题的意思是：对于每个 x,如果 x是病人,
就存在着医生 y,使得 x相信 y。 因此,本命题符号化为：
x（ F（ x） → y（ G（ y） ∧ H（ x,y）） )?
第 2章 一阶逻辑例 2.1.5】 将下列命题形式化为一阶逻辑中的命题：
（ 1） 任意一个整数 x,均有另一个整数 y,使得 x+y等于 0。
（ 2） 存在这样的实数 x,它与任何实数 y的乘积均为 y。
解
（ 1）设 Z（ x）,x是整数,E（ x,y）,x=y,f（ x，
y） =x+y。则原句形式化为：
x（ Z（ x） → y（ Z（ y） ∧ E（ f（ x,y）,0）））
第 2章 一阶逻辑
（ 2） 设 R（ x）,x是实数,E（ x,y）,x=y,g（ x，
y） =xy。 则原句形式化为：
x（ R（ x） ∧ y（ R（ y） → E（ g（ x,y）,y）））
第 2章 一阶逻辑
2.2 一阶逻辑公式及解释上一节中我们在一阶逻辑中符号化得到的命题和命题函数就是一阶逻辑公式 (谓词公式 )。 至此,在一阶逻辑中,我们已涉及到以下这些符号：
(1)个体变元符号：用小写的英文字母 x,y,z（ 或加下标 ） … 等表示 。
(2)个体常元符号：用小写的英文字母 a,b,c（ 或加下标 ） … 等表示 。
第 2章 一阶逻辑
(3)运算符号：用小写的英文字母 f,g,h（ 或加下标 ） … 等表示 。
(4)谓词符号：用大写的英文字母 F,G,H（ 或加下标 ） … 等表示 。
(5)量词符号：,。
(6)联结词符号：,∧,∨,→,。
(7)逗号和圆括号 。
第 2章 一阶逻辑一个符号化的命题是一串由这些符号所组成的表达式,但并不是任意一个由此类符号组成的表达式就对应于一个命题 。 所以要给出严格的定义 。
定义 2.2.1 项的定义：
(1)任何一个个体变元或个体常元是项 。
(2)如果 f是 n元运算符,t1,t2,…,tn是项,则 f
（ t1,t2,…,tn） 是项 。
(3)所有的项由且仅由有限次使用 （ 1）,（ 2） 所生成 。
第 2章 一阶逻辑例如,x,a,f（ x,a）,f（ g（ x,a,b）,h
（ x））均是项，其中 h,f和 g分别是一元、二元和三元运算符。而 h（ a,b）不是项，因为 h是一元运算符，
但 h（ a,b）中 h的后面跟了两个项，同样 g（ x）也不是项（理由请读者自己考虑）。
第 2章 一阶逻辑定义 2.2.2 若 F是 n元谓词,t1,t2,…,tn是项，则
F（ t1,t2,…,tn）是原子公式。
由定义可知,原子命题是不含量词和联结词的谓词公式 。 同命题逻辑中的情况相似,这里也可以用联结词将原子公式复合成分子公式 。 （ 事实上我们已经这样做了 。 ）
第 2章 一阶逻辑定义 2.2.3 一阶逻辑中的合式公式 （ wff） 的递归定义：
（ 1） 原子公式是合式公式 。
（ 2） 若 A 是合式公式,则 （ A） 也是合式公式 。
（ 3） 若 A,G均是合式公式,则 （ A∧ B ）,
（ A∨ B）,（ A→ B） 和 （ A B） 也均是合式公式 。
（ 4） 若 F是合式公式,x是个体变元,则 xF、
xF也是合式公式 。
（ 5） 只有有限次按规则 （ 1） ～ （ 4） 构成的谓词公式才是合式公式 。
第 2章 一阶逻辑
【 例 2.2.1】 考察下列一阶公式中每个量词的辖域及每个变元的出现是约束的或自由的 。
（ 1） x（ F（ x） → yH（ x,y））
（ 2） x（ F（ x） → G（ x）） ∨ x（ F（ x） → H（ x））
（ 3） xF（ x） ∧ G（ x）
第 2章 一阶逻辑解 （ 1）全称量词 x的辖域是
（ F（ x） → yH（ x,y）），其中 x的两次出现均是约
y的辖域是 H（ x，
y），其中 y的出现是约束的,y是约束变元。
（ 2） 第一个全称量词 x的辖域是 （ F（ x） → G
（ x））,其中 x的出现均是约束出现,是约束变元；
第二个全称量词 x的辖域是 （ F（ x） → H（ x））,其中 x的出现均是约束出现,是约束变元 。
第 2章 一阶逻辑
（ 3 x的辖域是 F（ x），其中 x
的出现是约束出现，是约束变元；而 x的第三次出现是在 G（ x）中的出现，是自由出现，第三个 x是自由变元。
由例题可见，在一个一阶逻辑公式中，某个个体变元（符）的出现可以既是约束的，又是自由的，如
（ 3）中的 x。另外，同一个变元（符）即使都是约束的，也可能是在不同的量词辖域中出现，如（ 2）中的
x。为了避免混淆，可对约束变元进行换名，使得一个变元（符）在一个公式中只以一种形式出现。这样做时需遵守下面的规则：
第 2章 一阶逻辑换名规则
（ 1） 将量词的作用元及其辖域中所有同符号的变元用一个新的变元符代替 。
（ 2） 新的变元符是原公式中所没有出现的 。
（ 3） 用 （ 1）,（ 2） 得到的新公式与原公式等值 。
第 2章 一阶逻辑
【 例 2.2.2】 对公式
x（ F（ x） → G（ x,y）） ∧ H（ x,y）
换名,下面的几种做法中哪个是正确的？
（ 1） z（ F（ z） → G（ z,y）） ∧ H（ x,y）
（ 2） y（ F（ y） → G（ y,y）） ∧ H（ x,y）
（ 3） z（ F（ z） → G（ x,y）） ∧ H（ x,y）
第 2章 一阶逻辑解 只有 （ 1） 是正确的 。 （ 2） 的换名违反了规则
（ 2）,使得 G（ x,y） 中的 y的出现改变了性质 。 （ 3）
的换名违反了规则 （ 1）,使得 G（ x,y） 中的 x的出现改变了性质 。
对公式中自由出现的变元也可换符号,称为代替,
同样需要遵守下面的规则：代替规则
（ 1） 将公式中所有同符号的自由变元符用新的变元符替换 。
（ 2） 新的变元符是原公式中所没有出现的 。
（ 3） 用 （ 1）,（ 2） 得到的新公式与原公式等值 。
第 2章 一阶逻辑
【 例 2.2.3】 对公式
x（ F（ x） → G（ x,y）） ∧ H（ x,y）
做代替,下面的几种做法中哪个是正确的？
（ 1） x（ F（ x） → G（ x,y）） ∧ H（ z,y）
（ 2） x（ F（ x） → G（ x,z）） ∧ H（ u,y）
（ 3） z（ F（ z） → G（ x,y）） ∧ H（ y,y）
请读者自己做出分析 。
第 2章 一阶逻辑定义 2.2.4 没有自由变元的公式称为闭式 。
如例 2.2.1中的 （ 1）,（ 2） 两式均是闭式,而 （ 3）
不是闭式 。 事实上,仅就个体变元而言,自由变元才是真正的变元,而约束变元只在表面上是变元,实际上并不是真正意义上的变元 。 换言之,含有自由变元的公式在解释后仍是命题函数,还需赋值方成命题,
而不含自由变元的闭式一旦给出解释就成了命题 。
第 2章 一阶逻辑定义 2.2.5 一个解释 I由以下四部分组成：
（ 1） 为个体域指定一个非空集合 DI。
（ 2） 为每个个体常元指定一个个体 。
（ 3） 为每个 n元运算符指定 DI上的一个 n元运算 。
（ 4） 为每个 n元谓词符指定 DI上的一个 n元谓词 。
第 2章 一阶逻辑
【 例 2.2.4】 设 f,g均为二元运算符,E,L均为二元谓词符,给定解释 I如下：
个体域 DI为自然数集合；
f（ x,y） =x+y,g（ x,y） =x·y,a=0；
E（ x,y）,x=y,L（ x,y）,x＜ y。
求下列公式在解释 I下的真值 。
第 2章 一阶逻辑
（ 1） x yL（ x,y）
（ 2） x（ E（ f（ x,a）,x） ∧ L（ g（ x,a）,a））
（ 3） y（ E（ x,y） ∨ L（ x,y））
（ 4） E（ f（ x,a）,g（ x,a））
第 2章 一阶逻辑解 (1)式中没有自由变元,是闭式,在解释 I下的意义是：对于每一个自然数 x,均存在着自然数 y,使得 x＜ y。 显然这是一个真命题 。
（ 2） 式中也没有自由变元,是闭式,在解释 I下的意义是：对于每一个自然数 x,x+0=x并且 x·0＜ 0。 0＜ 0
不真,所以这是一个假命题 。
（ 3） 式中 x是自由变元,不是闭式,在解释 I下的意义是：对于每一个自然数 y,x=y或者 x＜ y。 因为 x取 0时,
原式为真； x取 1时,原式为假,所以这是命题函数,
而非命题 。
第 2章 一阶逻辑
（ 4） 式中 x是自由变元,不是闭式,在解释 I下的意义是,x+0=x·0。 因为 x取 0时,原式为真； x非 0时,
原式为假,所以这是命题函数,而非命题 。 如上所言,
含有自由变元的公式在解释后仍是命题函数,还需赋值方成命题 。
第 2章 一阶逻辑定义 2.2.6 赋值 υ是建立在解释 I上的函数,且有：
（ 1） υ（ xi） =,
即对自由变元 xi指派一个 DI中的个体 。
（ 2） υ（ f（ t1,t2,…,tn）） = （ υ（ t1）,
υ（ t2）,…,υ（ tn））,
其中 fi是 I对 f的解释,ti（ i=1,2,…,n） 是项 。
ia
ia
if
第 2章 一阶逻辑
【 例 2.2.5】 设 f,g均为二元运算符,E,L均为二元谓词符,给定解释 I及赋值 υ如下：
个体域 DI为自然数集合；
f（ x,y） =x+y,g（ x,y） =x·y,a=0；
E（ x,y）,x=y,L（ x,y）,x＜ y。
υ1（ x） =0,υ2（ x） =1。
求下列公式在解释 I和赋值分别为 υ1,υ2下的真值 。
第 2章 一阶逻辑
（ 1） y（ E（ x,y） ∨ L（ x,y））
（ 2） E（ f（ x,a）,g（ x,a））
（ 3） xE（ g（ x,a）,a）?
第 2章 一阶逻辑解 (1)式在解释 I及赋值 υ1下的含义是：对于每个自然数 y,0=y或者 0＜ y。 即 0是最小的自然数,这是真命题 。 在解释 I及赋值 υ2下的含义是：对于每个自然数 y，
1=y或者 1＜ y。 即 1是最小的自然数,这是假命题 。
(2)式在解释 I及赋值 υ1下的含义是,0+0=0·0,这是真命题 。 在解释 I及赋值 υ2下的含义是,1+0=1·0,这是假命题 。
第 2章 一阶逻辑
(3)式中不含自由变元,无需考虑赋值 。 在解释 I下的意义是：对于每一个自然数 x,x·0=0。 这是真命题 。
在上一节我们曾提到过,当个体域为有穷集 DI={a1，
a2,…,an}时：
xF（ x） F（ a1） ∧ F（ a2） ∧ … ∧ F（ an）
xG（ x） G（ a1） ∨ G（ a2） ∨ … ∨ G（ an）
因此，当解释 I中的个体域 D为有穷集时，可先消量词再求真值。
第 2章 一阶逻辑
【 例 2.2.6】
设解释 I为,DI={2,3},f（ 2） =3,f（ 3） =2，
F（ 2,2） =F（ 2,3） =0,F（ 3,2） =F（ 3,3） =1。
在 I下消去下列公式的量词并求真值 。
（ 1） F（ 2,f（ 2）） ∧ F（ 3,f（ 3））
（ 2） x yF（ y,x）
（ 3） x（ F（ x,f（ x）） → yF（ f（ x）,f（ y）））
第 2章 一阶逻辑解 （ 1） 式中不含量词,所以直接求真值 。
F（ 2,f（ 2）） ∧ F（ 3,f（ 3））
F（ 2,3） ∧ F（ 3,2）
0∧ 1
0
第 2章 一阶逻辑
(2) x yF（ y,x）
x（（ F（ 2,x） ∨ F（ 3,x）））
（ F（ 2,2） ∨ F（ 3,2））
∧ （ F（ 2,3） ∨ F（ 3,3））
（ 0∨ 1） ∧ （ 0∨ 1）
1∧ 1
1
第 2章 一阶逻辑
(3) x（ F（ x,f（ x）） → yF（ f（ x）,f（ y）））
（ F（ 2,f（ 2）） → yF（ f（ 2）,f（ y）） ∧ （ F（ 3,f（ 3））
→ yF（ f（ 3）,f（ y））））
（ F（ 2,f（ 2）） → （ F（ f（ 2）,f（ 2）） ∧ F（ f（ 2）,f（ 3））））
（ F（ 3,f（ 3）） → （ F（ f（ 3）,f（ 2）） ∧ F（ f（ 3）,f（ 3））））
（ F（ 2,3） → （ F（ 3,3） ∧ F（ 3,2）））
∧ （ F（ 3,2） → （ F（ 2,3） ∧ F（ 2,2）））
（ 0→ （ 1∧ 1）） ∧ （ 1→ （ 0∧ 0））
（ 0→ 1） ∧ （ 1→ 0）
1∧ 0
0
第 2章 一阶逻辑定义 2.2.7 一阶逻辑公式的分类：
永真式 （ 逻辑有效式 ） 在任何解释 I及 I的任何赋值下均为真的一阶公式；
永假式 （ 矛盾式 ） 在任何解释 I及 I的任何赋值下均为假的一阶公式；
可满足式 至少有一种解释和一种赋值使其为真的一阶公式 。
第 2章 一阶逻辑由定义可知,要判定一个公式 A不是永真式,只需找到一个解释 I和 I下的一个赋值 υ,使 A在 I和 υ下为假；
要判定一个公式 A不是永假式,只需找到一个解释 I和 I
下的一个赋值 υ,使 A在 I和 υ下为真；要判定一个公式 A
是可满足式,只需找到一个解释 I和 I下的一个赋值 υ，
使 A在 I和 υ下为真,再找到一个解释 I和 I下的一个赋值 υ，
使 A在 I和 υ下为假 。
第 2章 一阶逻辑
【 例 2.2.7】 讨论下列公式的类型：
（ 1） xF（ x） → xF（ x）
（ 2） x G（ x） ∧ xG（ x）
（ 3） x yF（ x,y） → y xF（ x,y）
第 2章 一阶逻辑解 （ 1） 公式 xF（ x） → xF（ x） 在任何解释 I
下的含义是：如果个体域 DI中的每个元素 x均有性质 F，
则 DI中的某些元素 x必有性质 F。 前件 xF（ x） 为真时,
xF（ x） 永远为真,所以公式
xF（ x） → xF（ x） 是永真式 。
第 2章 一阶逻辑
（ 2）公式 x G（ x） ∧ xG（ x）在任何解释 I下的含义是：个体域 DI中的每个元素 x均不具有性质 G，
且 DI中的某些元素 x具有性质 G。这是两个互相矛盾的命题，不可能同时成立，所以公式
x G（ x） ∧ xG（ x）是永假式。
第 2章 一阶逻辑
（ 3）公式 x yF（ x,y） → yxF（ x,y）既不是永真式，也不是永假式。由于这是闭式，故无需考虑赋值，只要给出一个使其成真的解释和一个使其成假的解释即可。
① 给定解释 I1,DI1为自然数集,F（ x,y）,x＜ y。
此时公式的前件 x yF（ x,y） 表示,对于每个自然数 x,均有自然数 y比 x大,是真命题,y xF
（ x,y） 表示,存在着自然数 y比每个自然数 x均大,是假命题 。 因此,I1是使 x yF（ x,y） → y xF
（ x,y） 为假的解释 。
第 2章 一阶逻辑
② 给定解释 I2,DI2为自然数集,F（ x,y）,x＞ y。
此时公式的前件 x yF（ x,y） 表示,对于每个自然数 x,均有自然数 y比 x小,是假命题 （ x为 0时,y不存在 ）,因此,I2是使 x yF（ x,y） → y xF（ x，
y） 为真的解释 。
第 2章 一阶逻辑定义 2.2.8 设 A（ p1,p2,…,pn）是含命题变元 p1，
p2,…,pn的命题公式,B（ B1,B2,…,Bn）是以一阶公式 B1,B2,…,Bn分别代替 p1,p2,…,pn在 A中的所有出现后得到的一阶公式，称 B是 A的一个代换实例。
例如,F（ x） → G（ y）,xF（ x） → yG（ y）
均是命题公式 p→q 的代换实例,也是 p的代换实例 。 显然有以下定理 。
第 2章 一阶逻辑定理 2.2.1 命题逻辑永真式的任何代换实例必是一阶逻辑的永真式 。 同样,命题逻辑永假式的任何代换实例必是一阶逻辑的永假式 。
证明略 。
定理 2.2.1为我们提供了一大类一阶逻辑的有效式 。
因此,判断一个一阶逻辑公式是否是永真式或永假式,
我们既可以用定义 2.2.7（ 如例 2.2.7）,也可以用其是否是命题逻辑的永真式或永假式的代换实例来判断 。
第 2章 一阶逻辑
2.3 等值演算和前束范式定义 2.3.1 设 A与 B是公式,若 A B是永真式,则称 A与 B等值,或称 A与 B逻辑等价,记作 A B。
第 2章 一阶逻辑显然,A B当且仅当在任何解释 I和 I中的任意赋值 υ下,A与 B有相同的真值。即在 I和 υ下,A为真当且仅当 B为真，或者,A为假当且仅当 B为假。同时，要证明两个公式不等值，只需找到一个解释 I和 I中的一个赋值 υ，使得两个公式在 I和 υ下，一个为真，另一个为假。
第 2章 一阶逻辑
【 例 2.3.1】 判断公式 F（ x） 和 F（ y） 是否等值 。
解 F（ x）表示 "x具有性质 F",F（ y）表示 "y具有性质 F"，容易看出两个意思并不一样。取解释 I：个体域 D为整数集,F（ x）,x是奇数，赋值 υ（ x） =1,υ
（ y） =2，则在 I和 υ下,F（ x）为真,F（ y）为假。因此,F（ x）与 F（ y）不等值。
第 2章 一阶逻辑
【 例 2.3.2】 判断公式 x yF（ x,y）
y xF（ x,y） 是否等值 。
解 直接观察是不等值的。由于两个公式均是闭式，
所以只需给出一个解释 I，使其在 I下一个为真，另一个为假。取解释 I,D为鞋子的集合,F（ x,y）,x与 y能配成一双。则在 I下,x yF（ x,y）表示“每一只鞋子均有另一只鞋子能与其配成一双”是真命题，而公式
y xF（ x,y）表示“有这样的鞋子能与任何一只鞋子配成一双”是假命题。因此，两个公式 x yF
（ x,y y xF（ x,y）不等值。
第 2章 一阶逻辑量词转换律 （ A（ x） 是任一一阶公式 ）
xA（ x） x A（ x） （ 1）
xA（ x） x A（ x） （ 2）
第 2章 一阶逻辑量词辖域扩缩律 （ A（ x） 是任一一阶公式,B是任一不含 x的一阶公式 ）
xA（ x） ∧ B x（ A（ x） ∧ B） （ 1）
xA（ x） ∨ B x（ A（ x） ∨ B） （ 2）
xA（ x） ∧ B x（ A（ x） ∧ B） （ 3）
xA（ x） ∨ B x（ A（ x） ∨ B） （ 4）
第 2章 一阶逻辑证明
（ 1） 在任何解释 I和 I中的任意赋值 υ下,
xA（ x） ∧ B=1
当且仅当 xA（ x） =1且 B=1
当且仅当 B=1且对于 DI中的每一个元素 c,A（ c） =1
当且仅当 对于 DI中的每一个元素 c,A（ c） ∧ B=1
当且仅当 x（ A（ x） ∧ B） =1
第 2章 一阶逻辑
（ 2） 在任何解释 I和 I中的任意赋值 υ下,
xA（ x） ∨ B=0
当且仅当 xA（ x） =0且 B=0
当且仅当 B=0且存在 DI中的元素 c,使得 A（ c） =0
当且仅当 存在 DI中的元素 c,使得 A（ c） ∨ B=0
当且仅当 x（ A（ x） ∨ B） =0
第 2章 一阶逻辑
( 3 ) ( ) ( ( ) )
( ( ) ) )
( ( ) ) )
( ( ) )
()
()
x A x B x A x B
x A x B
x A x B
x A x B
x A x B
x A x B
第 2章 一阶逻辑
（ 4） 式的证明留给读者 。
另外,下面的等值式也称作量词辖域的扩缩律 。
( 5 ) ( ) ( ( ) )
( 6 ) ( ) ( ( ) )
( 7 ) ( ) ( ( ) )
( 8 ) ( ) ( ( ) )
x A x B B x A x B
B x A x x B A x
x A x B x A x B
B x A x x B A x
第 2章 一阶逻辑证明 （ 5）
( ) ( )
()
( ( ) )
( ( ) )
x A x B x A x B
x A x B
x A x B
x A x B
（ 6）、（ 7）、（ 8）的证明留给读者。
第 2章 一阶逻辑量词分配律 A（ x）,B（ x）是任一一阶公式）
( 1 ) ( ( ) ( ) ) ( ) ( )
( 2) ( ( ) ( ) ) ( ) ( )
x A x B x x A x x B x
x A x B x x A x x B x
第 2章 一阶逻辑证明 （ 1） 在任何解释 I和 I中的任意赋值 υ下,
x（ A（ x） ∧ B（ x）） =1
当且仅当 对于 DI中的每一个元素 c，
A（ c） ∧ B（ c） =1
当且仅当 对于 DI中的每一个元素 c，
A（ c） =1且 B（ c） =1
当且仅当 xA（ x） =1且 xB（ x） =1
当且仅当 xA（ x） ∧ xB（ x） =1
第 2章 一阶逻辑
( 2 ) ( ( ) ( ) ) ( ( ( ) ( ) ) )
( ( ( ) ( ) ) )
( ( ( ) ( ) ) )
( ( ) ( ) )
( ( ) ( ) )
( ) ( )
x A x B x x A x B x
x A x B x
x A x B x
x A x x B x
x A x x B x
x A x x B x
第 2章 一阶逻辑
【 例 2.3.3】 证明下列等值式,
( 1 ) ( ( ) ( )) ( ( ) ( ))
( 2 ) ( ( ) ( ) (,))
(( ( ) ( )) (,))
x F x G x x F x G x
x y F x G x H x y
x y F x G y H x y
第 2章 一阶逻辑证明
( 1 ) ( ( ) ( )
( ( ) ( ) )
( ( ) ( ) )
( ( ) ( ) )
( 2 ) ( ( ) ( ) (,) )
( ( ) ( ) (,) )
( ( ) ( ) (,) )
( ( ( ) ( ) ) (,) )
x F x G x
x F x G x
x F x G x
x F x G x
x y F x G y H x y
x y F x G y H x y
x y F x G y H x y
x y F x G y H x y
第 2章 一阶逻辑定义 2.3.2 设 A为一阶公式,若 A具有如下形式
Q1x1Q2x2…QkxkB
则称 A为前束范式 。 其中 Qi（ 1≤i≤k） 是量词符或
,xi（ 1≤i≤k） 是变元符,B是不含量词的公式 。
第 2章 一阶逻辑在一阶逻辑推理中,需要将公式化成前束范式形式,这总是可以办到的 。 即任何一个一阶公式均可等值演算成前束范式,化归过程如下：
（ 1） 消去除,∧,∨ 之外的联结词；
（ 2） 将否定符 移到量词符后；
（ 3） 换名使各变元不同名；
（ 4） 扩大辖域使所有量词处在最前面 。
第 2章 一阶逻辑
【 例 2.3.4】 将下面公式化成前束范式。
( 1 ) ( ( ) (,) (,))
( 2 ) ( ( ) ( ( ) ( (,)) )) ( (,) ( )
x F x yG y z z H x z
x F x y F y F f x y y G x y F y
第 2章 一阶逻辑解
( 1 ) ( ( ) (,) (,)
( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
( ( ( ) (,) ) (,) )
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z z H x z
x F x y G y z t H x t
x y t F x G y z H x z
第 2章 一阶逻辑
( 2 ) ( ( ) ( ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ( ) ( (,))) ) ( (,) ( ))
((
x F x y F y F f x y y G x y F y
x F x y F y F f x y y y G x y F y
x F x y F y F f x y y G x y F y
x F x y F y F f x y y G x y F y
t F t
) ( ) ( (,))) ) ( (,) ( ))
( ( ) ( ) ( (,)) (,) ( ))
yF y F f t y z G x z F z
t y z F t F y F f t y G x z F z
第 2章 一阶逻辑
2.4 一阶逻辑推理理论在一阶逻辑中,由前提 A1,A2,…,An推出结论 B
的形式结构仍然是 A1∧ A2∧ …∧ An→ B。 如果此式是永真式,则称由前提 A1,A2,…,An推出结论 B的推理正确,记作 A1∧ A2∧ …∧ An B或者 A1,A2,…,An B，
否则称推理不正确 。
第 2章 一阶逻辑由于谓词演算是在命题演算的基础上,进一步扩大了谓词与量词的功能,因此容易想到,命题演算中有关推理演绎的规则基本上适用于谓词演算,即在命题逻辑中的各项推理规则在一阶逻辑推理中仍然适用,
当然也会有不少只适用于谓词演算的概念与规则 。
全称量词消去规则 （ 简称 UI规则 ）
()
()
x A x
At
第 2章 一阶逻辑规则成立的条件：
（ 1） t是任意个体变项或常项 。
（ 2） A（ t） 中约束变元个数与 A（ x） 中约束变元个数相同 。
第 2章 一阶逻辑全称量词引入规则（简称 UG规则）
()
()
At
x A x?
规则成立的条件：
（ 1） A（ t） 在任何解释 I及 I中对 t的任何赋值下均为真 。
（ 2） x不在 A（ t） 中约束出现 。
第 2章 一阶逻辑存在量词引入规则 （ 简称 EG规则 ）
()
()
Ac
x A x?
规则成立的条件：
（ 1） c是特定的个体常元 。
（ 2） x不在 A（ c）中出现。
第 2章 一阶逻辑规则成立的条件：
（ 1） c是使 A（ c） 为真的特定的个体常元 。
（ 2） xA（ x） 是闭式,且 c不在 A（ x） 中出现 。
特别需要注意的是,使用这些规则的条件非常重要,如在使用过程中违反了这些条件就可能导致错误的结论 。
()
()
x A x
Ac
存在量词消去规则（简称 EI规则）
第 2章 一阶逻辑
【 例 2.4.1】 证明推理 "所有的自然数均是实数,3
是自然数,因此,3是实数 。 "正确 。
解 设 N（ x）,x是自然数,R（ x）,x是实数,则推理形式化为：
x（ N（ x） → R（ x））,N（ 3） R（ 3）
下面进行证明 。
（ 1） x（ N（ x） → R（ x）） 前提引入
（ 2） N（ 3） → R（ 3） （ 1） UI
（ 3） N（ 3） 前提引入
（ 4） R（ 3） （ 2） （ 3） 假言推理
第 2章 一阶逻辑
【 例 2.4.2】 构造下面推理的证明：
前提 x（ F（ x） → （ G（ x） ∧ H（ x）））,
x（ F（ x） ∧ P（ x））
x（ P（ x） ∧ H（ x））
第 2章 一阶逻辑解
（ 1） x（ F（ x） → （ G（ x） ∧ H（ x））） 前提引入
（ 2） x（ F（ x） ∧ P（ x）） 前提引入
（ 3） F（ c） ∧ P（ c） (2)EI
（ 4） F（ c） → （ G（ c） ∧ H（ c）） （ 1） UI
（ 5） F（ c） （ 3） 化简
（ 6） G（ c） ∧ H（ c） （ 4） （ 5） 假言推理
（ 7） P（ c） （ 3） 化简
（ 8） H（ c） （ 6） 化简
（ 9） P（ c） ∧ H（ c） （ 7） （ 8） 合取引入
（ 10） x（ P（ x） ∧ H（ x）） （ 9） EG
第 2章 一阶逻辑
【 例 2.4.3】 设前提为 x yF（ x,y）,下面推理是否正确？
（ 1） x yF（ x,y） 前提引入
（ 2） y F（ y,y） （ 1） UI
解 x yF（ x,y yF（ y,y）的推理并不正确。如果给定解释 I：个体域为实数集,F（ x,y）,x
＞ y。则 x yF（ x,y）意为 "对于每个实数 x，均存在着比之更小的实数 y" yF（ y，
y）意为 "存在着比自己小的实数 "，是假命题。之所以出现这样的错误，是违反了 UI规则成立的条件（ 2）。
第 2章 一阶逻辑
【 例 2.4.4】 设前提为 x yF（ x,y）,下面推理是否正确？
（ 1） x yF（ x,y） 前提引入
（ 2） yF（ t,y） （ 1） UI
（ 3） F（ t,c） （ 2） EI
（ 4） xF（ x,c） （ 3） UG
（ 5） y xF（ x,y） （ 4） EG
第 2章 一阶逻辑解 x yF（ x,y） y xF（ x,y） 的推理并不正确 。 取与例 2.4.3相同的解释,则由 x yF（ x,y）
为真,y xF（ x,y） 意为 "存在着最小实数 ",是假命题,知推理不正确 。 之所以出现这样的错误,是第 （ 3） 步违反了 EI规则成立的条件 （ 2） 。
第 2章 一阶逻辑
【 例 2.4.5】 构造下面推理的证明：
前提 x（ F（ x） → G（ x））
结论 xF（ x） → xG（ x）
分析 本题直接证明很困难,注意到结论部分是蕴涵式,应考虑用附加前提证明法 。
第 2章 一阶逻辑证明
（ 1） x（ F（ x） → G（ x）） 前提引入
（ 2） xF（ x） 附加前提引入
（ 3） F（ t） （ 2） UI
（ 4） F（ t） → G（ t） （ 3） UI
（ 5） G（ t） （ 3） （ 4） 假言推理
（ 6） xG（ x） （ 5） UG
（ 7） xF（ x） → xG（ x） CP
第 2章 一阶逻辑
【 例 2.4.6】 构造下面推理的证明：
前提 x（ F（ x） → G（ x））
结论 x（ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
分析 本题直接证明会感到无从下手,而由于结论并非蕴涵式 （ x的辖域是其后整个公式 ）,附加证明法也不适用,此时我们应考虑归缪法 。
第 2章 一阶逻辑证明
（ 1） x（ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
否定结论引入
（ 2） x （ y（ F（ y） ∧ H（ x,y））
→ z（ G（ z） ∧ H（ x,z）））
（ 1） 置换
第 2章 一阶逻辑
（ 3） （ y（ F（ y） ∧ H（ a,y））
→ z（ G（ z） ∧ H（ a,z）））
（ 2） EI
（ 4） y（（ F（ y） ∧ H（ a,y）） ∧
z（ G（ z） ∧ H（ a,z）））
（ 3） 置换
第 2章 一阶逻辑
（ 5） y（ F（ y） ∧ H（ a,y）） （ 4） 化简
（ 6） F（ b） ∧ H（ a,b） （ 5） EI
（ 7） F（ b） （ 6） 化简
（ 8） x（ F（ x） → G（ x）） 前提引入
（ 9） F（ b） → G（ b） （ 8） UI
（ 10） G（ b） （ 7） （ 9） 假言推理
（ 11） z（ G（ z） ∧ H（ a,z）） （ 3） 化简
第 2章 一阶逻辑
（ 12） z（ G（ z） ∨ H（ a,z）） （ 11） 置换
（ 13） G（ b） ∨ H（ a,b） （ 12） UI
（ 14） H（ a,b） （ 6） 化简
（ 15） H（ a,b） （ 14） 置换
（ 16） G（ b） （ 13） （ 15） 析取三段论
（ 17） G（ b） ∧ G（ b） （ 10） （ 16） 合取引入
第 2章 一阶逻辑
2.5 例题选解
【 例 2.5.1】 在高等数学中极限定义为：任给小正数 ε,则存在正数 δ,使得当
0＜ |x-a|＜ ε时,恒有 |f（ x） -b|＜ δ成立 。
将上述定义用一阶逻辑公式表示 。
lim ( )xa f x b
第 2章 一阶逻辑分析 因为高等数学中的极限概念是在实数范围内给出的,所以不妨设定个体域为实数域 。 观察整个定义,
只有一种,小于,关系,这应当用一个二元谓词表示；
而,差的绝对值,是一个运算,应当用运算符表示 。
解 设 L（ x,y）,x＜ y,g（ x,y）,|x-y|,则定义可表示为：
ε（ L（ 0,ε） → δ（ L（ 0,δ） ∧ x（（ L（ 0,g
（ x,a）） ∧ L（ g（ x,a）,δ））
→ L（ g（ f（ x）,b）,ε））））
第 2章 一阶逻辑
【 例 2.5.2】 在一阶逻辑中符号化自然数的三条公理 。
（ 1） 每个数都有唯一的一个数是它的后继数 。
（ 2） 没有一个数使 0为它的后继数 。
（ 3） 每个不等于 0的数都有唯一的一个数是它的直接先行者 。
分析 在符号化命题的过程中,设定谓词尽可能少是一个原则 。 注意到 "x是 y的后继数 "与 "y是 x的直接先行者 "含义相同,所以可用一个谓词表示 。
第 2章 一阶逻辑解 设 N（ x）,x是自然数,F（ x,y）,x是 y的后继数,G（ x,y）,x=y,则
（ 1） x（ N（ x） → !y（ N（ y） ∧ F（ y,x）））
（ 2） x（ N（ x） ∧ F（ 0,x））
（ 3） x（（ N（ x） ∧ G（ x,1））
→ !y（ N（ y） ∧ F（ x,y）））
第 2章 一阶逻辑
【 例 2.5.3】 !xF（ x） 表达成仅用量词和
。
分析 !xF（ x） 的意思是：有唯一的 x具有性质 F。
即有 x具有性质 F,且若还有 y也具有性质 F,则必有 x=y。
解
!xF（ x） x（ F（ x） ∧ y（ F（ y） → x=y））
第 2章 一阶逻辑
【 例 2.5.4】 设个体域为 {a,b,c},消去下列公式中的量词 。
（ 1） xF（ x） ∧ yG（ y）
（ 2） x y（ F（ x） ∧ G（ y））
（ 3） x y（ F（ x,y） → G（ y））
第 2章 一阶逻辑解 （ 1） xF（ x） ∨ yG（ y）
（ F（ a） ∧ F（ b） ∧ F（ c）） ∧ （ F（ a）
∨ F（ b） ∨ F（ c））
（ 2） x y（ F（ x） ∧ G（ y））
y（ F（ a） ∧ G（ y）） ∧ y（ F（ b） ∧ G（ y）） ∧
y（ F（ c） ∧ G（ y））
（（ F（ a） ∧ G（ a）） ∨ （ F（ a） ∧ G（ b）） ∨ （ F
（ a） ∧ G（ c））） ∧
（（ F（ b） ∧ G（ a）） ∨ （ F（ b） ∧ G（ b）） ∨
（ F（ b） ∧ G（ c））） ∧ （（ F（ c） ∧ G（ a）） ∨ （ F
（ c） ∧ G（ b）） ∨ （ F（ c） ∧ G（ c）））
第 2章 一阶逻辑
（ 3） x y（ F（ x,y） → G（ y））
y（ F（ a,y） → G（ y）） ∧ y（ F（ b,y） → G
（ y）） ∧ y（ F（ c,y） → G（ y））
（（ F（ a,a） → G（ a）） ∨ （ F（ a,b） → G（ b））
∨ （ F（ a,c） → G（ c））） ∧
（（ F（ b,a） → G（ a）） ∨ （ F（ b,b） → G（ b））
∨ （ F（ b,c） → G（ c））） ∧
（（ F（ b,a） → G（ a）） ∨ （ F（ b,b） → G（ b））
∨ （ F（ b,c） → G（ c）））
第 2章 一阶逻辑
【 例 2.5.5】 构造下面推理的证明：
前提 xF（ x） ∨ xG（ x）
结论 x（ F（ x） ∨ G（ x））
证明
（ 1） xF（ x） ∨ xG（ x） 前提引入
（ 2） x y（ F（ x） ∨ G（ y）） （ 1） 置换
（ 3） y（ F（ t） ∨ G（ y）） （ 2） UI
（ 4） F（ t） ∨ G（ t） （ 3） UI
（ 5） x（ F（ x） ∨ G（ x）） （ 4） UG
第 2章 一阶逻辑习 题 二
1,在一阶逻辑中将下列命题符号化 。
（ 1） 天下乌鸦一般黑 。
（ 2） 没有不散的筵席 。
（ 3） 闪光的未必是金子 。
（ 4） 有不是奇数的素数 。
（ 5） 有且仅有一个偶素数 。
（ 6） 猫是动物,但并非所有的动物都是猫 。
第 2章 一阶逻辑
（ 7） 骆驼都比马大 。
（ 8） 有的骆驼比所有的马都大 。
（ 9） 所有的骆驼都比某些马大 。
（ 10） 有的骆驼比某些马大 。
第 2章 一阶逻辑
2,取个体域为实数集 R,函数 f在点 a处连续的定义是,f在 a点连续,当且仅当对每一个小正数 ε,都存在正数 δ,使得对所有的 x,若 |x-a|＜ δ,则 |f（ x） -f（ a）
|＜ ε。 把上述定义用符号的形式表示 。
3,在整数集中,确定下列命题的真值,运算 "·"
是普通乘法 。
（ 1） x y（ x·y=0）
（ 2） x y（ x·y=1）
（ 3） y x（ x·y=1）
（ 4） y x（ x·y=x）
第 2章 一阶逻辑
4,给定谓词如下,试将下列命题译成自然语言 。
P（ x）,x是素数 。 E（ x）,x是偶数 。 O（ x）,x是奇数 。 D（ x,y）,x整除 y。
（ 1） E（ 2） ∧ P（ 2）
（ 2） x（ D（ 2,x） → E（ x））
（ 3） x（ E（ x） ∧ D（ x,6））
（ 4） x（ E（ x） → D（ 2,x））
第 2章 一阶逻辑
（ 5） x（ E（ x） → y（ D（ x,y） → E（ y）））
（ 6） x（ O（ x） → y（ P（ y） → D（ x,y）））
（ 7） x（ P（ x） → y（ E（ y） ∧ D（ x,y）））
（ 8） x（ E（ x） ∧ P（ x） ∧ y（ E（ y） ∧ P（ y）
∧ x≠y））
第 2章 一阶逻辑
5,指出下面公式中的变量是约束的,还是自由的,
并指出量词的辖域 。
（ 1） x（ F（ x） ∧ G（ x）） → x（ F（ x） ∧ H（ x））
（ 2） xF（ x） ∧ xG（ x） ∨ （ xF（ x） → G（ x）））
（ 3） x（（ F（ x） ∧ G（ x,y））
→ （ xF（ x） ∧ R（ x,y,z）））
（ 4） x(yF（ x,y,z） y xF（ x,y,z）
第 2章 一阶逻辑
6,设个体域 D={a,b,c},消去下列各式中的量词 。
（ 1） xF（ x） → y F（ y）
（ 2） x（ F（ x） ∨ yG（ y））
（ 3） x y（ F（ x） → G（ y））
（ 4） x yF（ x,y,z）
7,求下列公式在解释 I下的真值 。
（ 1） x（ F（ x） ∨ G（ x））,解释 I：个体域 D={1,2}；
F（ x）,x=1； G（ x）,x=2。
（ 2） x（ p→Q （ x）） ∨ R（ a）,解释 I：个体域 D={-2，
3,6}； p,1＜ 2； Q（ x）,x≤3,R（ x）,x＞ 5； a,5。
第 2章 一阶逻辑
8,给定解释 I和 I中赋值 v如下：
个体域 D为实数集,E（ x,y）,x=y,G（ x,y）,x＞
y,N（ x）,x是自然数,
f（ x,y） =x-y,g（ x,y） =x+y,N（ x,y） =x·y
v（ x） =1,v（ y） =-2
第 2章 一阶逻辑求下列公式在解释 I和赋值 v下的真值 。
（ 1） x yE（ g（ x,y）,g（ y,x））
（ 2） N（ x） ∧ y（ N（ y） →
（ G（ y,x） ∨ E（ y,x）））
（ 3） y zE（ N（ y,z）,x）
（ 4） x yE（ N（ f（ x,y）,g（ x,y））,
f（ N（ x,x）,N（ y,y）））
（ 5） E（ g（ x,g（ x,y））,a）
第 2章 一阶逻辑
11,证明量词辖域扩缩律 （ 4）,
x A（ x） ∨ B x（ A（ x） ∨ B）
12,证明量词辖域扩缩律：
（ 6） B→ xA（ x） x（ B→ A（ x））
（ 7） xA（ x） → B x（ A（ x） → B）
（ 8） B→ xA（ x） x（ B→ A（ x））
13,用等值演算证明下列等值式 。
（ 1） x（ F（ x） → G（ x）） y F（ y） → zG（ z）
（ 2） x y（ F（ x） → G（ y）） xF（ x） → yG（ y）
（ 3） x（ F（ x） ∧ G（ x）） （ xG（ x） → xF（ x））
第 2章 一阶逻辑
14,将下列公式化成与之等值的前束范式 。
（ 1） x（ F（ x） → yG（ x,y））
（ 2） （ xF（ x） ∨ xG（ x）） → x（ F（ x） ∨ G（ x））
（ 3） xF（ x） → x（ yG（ x,y） ∨ yH（ x,y,z））
（ 4） （ xF（ x） ∨ yG（ y）） ∧ （ F（ x） → zH（ z））
第 2章 一阶逻辑
15,构造下列推理的证明：
（ 1） xF（ x） ∧ xG（ x）
x（ F（ x） ∧ G（ x））
（ 2） 前提,x（ F（ x） ∨ G（ x））
结论,xF（ x） ∨ xG（ x）
（ 提示：用附加前提法或归缪法证明 ）
（ 3） 前提,x（ F（ x） → G（ x））
结论,x y（ F（ y） ∧ H（ x,y））
→ x（ G（ x） ∧ H（ x,x））
第 2章 一阶逻辑
（ 4） 前提,xF（ x）,x（（ F（ x） ∨ G（ x））
→ H（ x））
xH（ x）
（ 5） xF（ x） → x（（ F（ x） ∨ G（ x））
→ R（ x））,xF（ x）,xG（ x）
x y（ R（ x） ∧ R（ y））
（ 6） 前提,x（ y（ S（ x,y） ∧ M（ y））
→ z（ P（ z） ∧ R（ x,z）））
结论,zP（ z） → x y（ S（ x,y） → M（ y））
第 2章 一阶逻辑
16,在一阶逻辑中构造下列推理的证明 。
（ 1） 有理数都是实数 。 有的有理数是整数 。 因此,
有的实数是整数 。
（ 2） 所有的有理数都是实数 。 所有的无理数也都是实数 。 任何虚数都不是实数 。 所以,虚数既非有理数也非无理数 。
（ 3） 不存在不能表示成分数的有理数 。 无理数都不能表示成分数 。 所以,无理数都不是有理数 。
第 2章 一阶逻辑
17,在一阶逻辑中构造下列推理的证明 。
（ 1） 有些病人相信所有的医生 。 所有的病人都不相信骗子 。 因此,所有的医生都不是骗子 。
（ 2） 任何人如果他喜欢步行,他就不喜欢乘汽车 。
每个人或者喜欢乘汽车,或者喜欢骑自行车 。 有的人不爱骑自行车 。 因此有的人不爱步行 。
