第 2章 谓词逻辑第 2章 谓词逻辑
2.1 个体、谓词与量词
2.2 谓词公式
2.3 谓词演算的等价式与蕴含式
2.4 前束范式
2.5 谓词逻辑的推理理论返回总目录第 2章 谓词逻辑第 2章 谓词逻辑
2.1个体、谓词与量词
2.1.1个体考察下面的三个原子命题：
⑴ 李玲是优秀共产党员 。
⑵ 张华比李红高 。
⑶ 小高坐在小王和小刘的中间。
上述命题中的李玲、张华、李红、小高、小王、小刘等客体就是个体。所以可以这样说，个体是指所研究对象中可以独立存在的具体的或抽象的客体。它可以是独立存在的人或物体，也可以是抽象的概念，如,马列主义,,,资本主义,等。个体常用小写英文字母或小写英文字母带下标表示，叫做个体标识符。
第 2章 谓词逻辑表示具体或特定个体的标识符称作个体常元,一般用小写英文字母 a,b,c,? 或这些英文字母带下标表示 。 例如：李玲,张华,李红,小高,小王,小刘可如下表示：
a：李玲
b：张华
c：李红
d：小高
e：小王
f：小刘
a,b,c,d,e,f都是个体常元 。
将表示任意个体或泛指某类个体的标识符称为个体变元,常表示为 x,y,z,? 等或这些英文字母带下标 。
个体变元的变化范围称为个体域或论域 。 个体域可以是有穷集合,也可以是无穷集合,包含任意个体域的个体域称为全总个体域,它是由宇宙间一切对象组成的集合 。
在本书中,如无特别说明,所采用的都是全总个体域 。
第 2章 谓词逻辑
2.1.2谓 词在上面的三个原子命题中,⑴ 可以分解成为个体,李玲,
和,? 是优秀共产党员,两部分 。,? 是优秀共产党员,是用来描述个体,李玲,的性质的； ⑵ 可以分解成为个体,张华,,
,李红,和,? 比? 高,两部分 。,? 比? 高,是用来描述个体,张华,和,李红,的身高关系的； ⑶ 可以分解成为个体
,小高,,,小王,,,小刘,和,? 坐在? 和? 的中间,两部分 。,? 坐在? 和? 的中间,是用来描述个体,小高,,
,小王,,,小刘,的位置关系的 。 这些刻划个体性质或几个个体关系的模式叫做谓词 。 谓词常用大写英文字母表示,叫做谓词标识符 。
例如可以用 F,G,H表示上面三个命题中谓词：
F,? 是优秀共产党员 。
G,? 比? 高 。
H,? 坐在? 和? 的中间 。
第 2章 谓词逻辑把与一个个体相关联的谓词叫做一元谓词 。 F是一元谓词；把与两个个体相关联的谓词叫做二元谓词 。 G是二元谓词；把与三个个体相关联的谓词叫做三元谓词 。 H是三元谓词；? 。 一般的,把与 n个个体相关联的谓词叫做 n元谓词 。
设 F是一元谓词,a是个体常元,用 F(a)表示个体常元 a
具有性质 F；设 G是二元谓词,a,b是个体常元,用 G(a,b)表示个体常元 a和 b具有关系 G；?
于是上面三个命题就表示为：
F(a)：李玲是优秀共产党员 。
G(b,c)：张华比李红高 。
H(d,e,f)：小高坐在小王和小刘的中间 。
将谓词后面填上相关联的个体常元所得的式子叫做谓词填式 。 F(a),G(b,c),H(d,e,f)都是谓词填式 。 谓词填式表示的是命题 。
第 2章 谓词逻辑类似的,用 F(x)表示个体变元 x具有性质 F；用 G(x,y)表示个体变元 x和 y具有关系 G；?,用 P(x1,x2,?,xn)(n≥1)表示个体变元 x1,x2,?,xn具有关系 P。 如果谓词后面有 n个个体变元,则称为 n元命题函数 。 例如 F(x),G(x,y),P(x1,x2,?,xn)
分别叫做一元命题函数,二元命题函数,n元命题函数
(n≥ 1)。 因为命题函数中包含个体变元,因此命题函数没有确定的真值,它不是命题 。 只要用个体常元取代所有的个体变元,就得到了命题 。
例如,用 H(x,y),x+y≥0,显然此命题函数不是命题,因为它无法判断真假 。 令
a,5,b：－ 7
用 a,b分别取代 x,y,就得到 H(a,b),它表示 5+(－ 7)≥0，
这是个假命题,它的真值为假 。
其实,用个体常元取代命题函数的所有个体变元所得到的表达式就是前面所说的谓词填式 。 因为它由个体常元取代命题函数中所有的个体变元而得到,所以也把谓词填式 叫做第 2章 谓词逻辑
0元命题函数 。 F(a),G(b,c),H(d,e,f)都是 0元命题函数,它们都是命题 。 于是命题逻辑中的命题均可以表示为谓词逻辑中的 0元命题函数 (谓词填式 ),命题成为命题函数的特例 。
【 例 2.1】 将下列命题符号化,并讨论它们的真值 。
⑴ 2与 3都是偶数 。
⑵ 如果 5大于 3,则 2大于 6。
解,⑴ 设 F(x),x是偶数 。
a,2,b,3
该命题符号化为,F(a)∧ F(b)
F(b)表示 3是偶数,它是个假命题 。 所以 F(a)∧ F(b)为假 。
⑵ 设 G(x,y),x大于 y
a,5,b,3,c,2,d,6
该命题符号化为,G(a,b)→ G(c,d)
G(a,b)表示 5大于 3,它是真命题 。 G(c,d)表示 2大于 6，
这是个假命题 。 所以 G(a,b)→ G(c,d)为假 。
第 2章 谓词逻辑
2.1.3量词量词分两种 。
⑴ 全称量词日常生活和数学中常用的,一切的,,,所有的,,
,每一个,,,任意的,,,凡,,,都,等词统称为全称量词，将它们符号化为,?” 。并用 (?x),(?y)等表示个体域里的所有个体，而用 (?x)F(x)和 (?y)G(y)等分别表示个体域中的所有个体都有性质 F和都有性质 G。
⑵ 存在量词
,存在,,,有一个,,,有些,,,至少有一个,等词统称为存在量词,将它们符号化为,?” 。 并用 (?x),(?y)
等表示个体域里有些个体,而用 (?x)F(x)和 (?y)G(y)等分别表示在个体域中存在个体具有性质 F和存在个体具有性质 G。
全称量词与存在量词统称为量词。
第 2章 谓词逻辑
【 例 2.2】 个体域是人类集合,对下列命题符号化 。
⑴ 凡人要死 。
⑵ 有的人是研究生 。
解,⑴ 令 F (x),x要死 。
命题,凡人要死 。,符号化为,(?x)F (x)
⑵ 令 G(x),x是研究生 。
命题,有的人是研究生 。,符号化为,(?x)G(x)
在命题函数前加上量词 (?x)和 (?x)分别叫做个体变元 x
被全称量化和存在量化 。 一般地说,命题函数不是命题,
如果对命题函数中所有命题变元进行全称量化或存在量化,
该函数就变成了命题 。 这一结论在例 2.2中得到验证 。
虽然对命题函数中所有命题变元进行量化后,该命题函数就变成了命题,但所得命题的真值与个体域的选定有关 。 请看下列例题：
第 2章 谓词逻辑
【 例 2.3】 对下列命题符号化,并在 ①,②,③ 三个个体域中考察命题的真值 。
命题,⑴ 所有数小于 5。
⑵ 至少有一个数小于 5。
个体域：
①?-1,0,1,2,4?
②?3,-2,7,8?
③?15,20,24?
解,设 L(x),x小于 5。
⑴,所有数小于 5。,符号化为,(?x) L(x)
在个体域 ①,②,③ 中,它们的真值分别为：真,假,假 。
⑵,至少有一个数小于 5。,符号化为,(?x)L(x)
在个体域 ①,②,③ 中,它们的真值分别为：真,真,假 。
命题函数中的个体变元被量化以后变成命题,其真值又与个体域的选定有关,这对命题函数的研究带来了一定的困难,为了统一,我们今后使用全总个体域 。 而将其它个体域第 2章 谓词逻辑用一个谓词来表示,叫做特性谓词 。 特性谓词加入的方法为：
⑴ 对全称量词,特性谓词作为条件命题的前件加入 。
⑵ 对存在量词,特性谓词作为合取项加入 。
【 例 2.4】 对下列命题在 ①,② 两个个体域中符号化 。
命题,⑴ 所有老虎是要吃人 。
⑵ 存在一个老虎要吃人 。
个体域：
① 所有老虎组成的集合 。
② 全总个体域 。
解,设 A(x),x是要吃人的 。 个体域为所有老虎的集合 。
⑴ 符号化为 (?x)A(x)
⑵ 符号化为 (?x)A(x)
个体域为全总个体域 。 设特性谓词 T(x),x是老虎 。
⑴ 符号化为 (?x)(T(x)→ A(x))
⑵ 符号化为 (?x) (T(x)∧ A(x))
返回章目录第 2章 谓词逻辑
2.2谓词公式
2.2.1谓词公式我们把命题,命题变元,谓词填式和命题函数叫做谓词演算的原子公式 。
定义 2.2.1按下列规则构成的表达式称为谓词演算的合式公式,简称谓词公式 。
⑴ 谓词演算的原子公式是合式公式 。
⑵ 若 A是合式公式,则?A是合式公式 。
⑶ 若 A和 B是合式公式,则 (A∧ B),(A∨ B),(A→ B)和
(A? B)是合式公式 。
⑷ 如果 A是合式公式,x是 A中出现的任意个体变元,则
(?x)A,(?x)A是合式公式 。
⑸ 只有有限次地应用 ⑴,⑵,⑶,⑷ 所得的公式是合式公式 。
谓词公式也有以下约定：
第 2章 谓词逻辑
⑴ 最外层的括号可以省略 。
⑵ 如果按?,∧,∨,→,? 在运算中的优先级别,省略括号后不改变原来的运算次序,可以省略括号,但量词后面括号不能省略 。
下面举例说明如何用谓词公式表达自然语言中的命题 。
【 例 2.5】 并非每个实数都是有理数 。
解,设 R(x),x是实数
Q(x),x是有理数该命题符号化为,?(?x)(R(x)→ Q(x))
【 例 2.6】 没有不犯错误的人 。
解,设 M(x),x是人
F(x),x犯错误此命题可以理解为：存在一些人不犯错误,这句话是不对的 。 此时,符号化为,?(?x) (M(x)∧?F(x) )
也可以理解为：任何人都是要犯错误的 。 此时,符号化为,(?x) (M(x)→ F(x))
第 2章 谓词逻辑
【 例 2.7】 并不是所有的兔子都比所有的乌龟跑得快 。
解,设 F(x),x是兔子 。
G(x),x是乌龟 。
H(x,y),x比 y跑得快 。
该命题符号化为,?(?x) (?y) (F(x)∧ G(y)→ H(x,y))
2.2.2约束变元与自由变元定义 2.2.2如果 A是谓词公式 B的一部分且是谓词公式,则称 A是 B的子公式 。
定义 2.2.3紧接量词以后的最小子公式叫做该量词的辖域或作用域 。
定义 2.2.4量词 (?x)和 (?x)中的 x叫做该量词的指导变元或作用变元 。
定义 2.2.5量词 (?x)和 (?x)的辖域内 x的一切出现叫约束出现,x叫做约束变元；约束变元以外的其它变元的出现叫自由出现,自由出现的变元叫自由变元 。
第 2章 谓词逻辑
【 例 2.10】 说明下列各式量词的辖域,找出约束变元和自由变元 。
⑴ (?x)P(x)→ Q(y)
⑵ (?x) (P(x)∧ (?y)Q(x,y))
⑶ (?x) P(x)∧ (?y)Q(x,y)
⑷ (?x)(?y)(P(x,y)∧ Q(y,z))? (?x) R(x,y)
⑸ (?x) P(x)∨ R(x,y)
解,⑴ (?x)的辖域为 P(x),x是约束变元,y是自由变元 。
⑵ (?x)的辖域为 P(x)∧ (?y)Q(x,y),(?y)的辖域为 Q(x,y)，
x和 y都是约束变元,无自由变元 。
⑶ (?x)的辖域为 P(x),(?y)的辖域为 Q(x,y),P(x)中的 x和
Q(x,y) 中的 y是约束变元,Q(x,y)中的 x是自由变元 。
⑷ (?x) 的辖域为 (?y)(P(x,y)∧ Q(y,z)),(?y) 的辖域为
P(x,y)∧ Q(y,z),(?x)的辖域为 R(x,y),x是约束变元,z是自由变元,(P(x,y)∧ Q(y,z))中的 y是约束变元,R(x,y)中的 y是自由变元 。
第 2章 谓词逻辑
⑸ (?x)的辖域为 P(x),y是自由变元,P(x)中 x是约束变元,R(x,y)中 x是自由变元 。
由例 2.10可以看出,在一个公式中,同一个变元既可以是约束的,又可以是自由的,容易混淆 。 因为 (?x)P(x)与
(?y)P(y),(?x)P(x)与 (?y)P(y)都具有相同意义,所以约束变元与表示该变元的符号无关 。 根据这个特点,可以对约束变元换名 。 为了使换名后的公式中出现的变元要么是约束的,
要么是自由的,我们提出如下的换名规则：
⑴ 对约束变元可以换名,其更改变元名称的范围是量词的指导变元,以及该量词辖域中的所有该变元,公式的其余部分不变 。
⑵ 换名时一定要更改成辖域中没有出现的变元名,最好是公式中没有的变量名 。
第 2章 谓词逻辑
【 例 2.11】 对 (?x)(?y)(P(x,y)∧ Q(y,z))?(?x) R(x,y)中的约束变元 y换名 。
解,用 u置换约束变元 y。 换名后为：
(?x)(?u)(P(x,u)∧ Q(u,z))?(?x) R(x,y)
不能换成,(?x)(?u)(P(x,u)∧ Q(y,z))?(?x) R(x,y)
也不能换成,(?x)(?z)(P(x,z)∧ Q(z,z))?(?x) R(x,y)
对公式中的自由变元也可以进行更改,用来解决公式中约束变元与自由变元的同名问题 。 这种更改叫做代入,代入规则是：
⑴ 对于谓词公式中的自由变元可以代入,代入时需对公式中该变元自由出现的每处进行 。
⑵ 代入的变元与原公式中其他变元的名称不能相同。
第 2章 谓词逻辑
【 例 2.12】 对 (?x)(P(y)∧ R(x,y))→ (?y)Q(y) 中的自由变元 y
进行代入 。
解,用 z代换 y,代入后为：
(?x)(P(z)∧ R(x,z))→ (?y)Q(y)
不能换成,(?x)(P(x)∧ R(x,x))→ (?y)Q(y)
或 (?x)(P(z)∧ R(x,y))→ (?y)Q(y)
2.3谓词演算的等价式与蕴含式定义 2.3.1 设 A是谓词公式,如果对 A的任何赋值,A都为真,则称 A是有效的或永真的 。
定义 2.3.2 设 A是谓词公式,如果对 A的任何赋值,A都为假,则称 A是不可满足的或永假的 。
定义 2.3.3 设 A是谓词公式,如果至少有一组赋值使 A为真,则称 A是可满足的 。
根据定义 2.3.1和定义 2.3.3,如果一个谓词公式是有效的,
它一定是可满足的 。
返回章目录第 2章 谓词逻辑定义 2.3.4设 A,B是任意两个谓词公式,对 A,B的任何赋值,若其真值相同,则称 A与 B是等价的,记作 A?B；若
A→ B是有效的,则称 A蕴含 B,记作 A?B。 设 A,B是任意两个谓词公式 。 当 A?B时,由定义 2.3.1和定义 2.3.4知 A? B是永真式 。 反之,当 A? B是永真式时,A?B。 所以,也可以用 A? B是永真式描述 A?B。
1,命题逻辑中的等价式的推广
⑴ 命题演算中的所有等价式都是谓词演算中的等价式 。
从定义 2.2.1可以看出,命题演算的合式公式都是谓词演算的合式公式 。 再根据定义 2.3.4,命题演算中的所有等价式都是谓词演算中的等价式 。
⑵ 命题逻辑中的等价式的推广在命题逻辑中,重言式的同一分量出现的每一处都用同一合式公式置换,其结果仍是重言式 (定理 1.4.2)。 在谓词逻辑中可以推广为：在永真的谓词公式中,命题变元出现的每一处都用同一谓词公式置换,其结果仍是永真式 。 例如：
第 2章 谓词逻辑因为?(p∨ q)p∧?q,故?(p∨ q)?(?p∧?q)为永真式,
用 (?x)P(x) 代替 p,(?y)R(y)代替 q,得到永真式：
((?x)P(x)∨ (?y)R(y))?(?(?x)P(x)∧?(?y)R(y))
所以?((?x)P(x)∨ (?y)R(y))(?x)P(x)∧?(?y)R(y)
2,消去量词等价式设个体域为有限集?a1,a2,?,an?,A(x)是含自由变元
x的任意谓词公式,有下列等价式成立：
(?x)A(x)?A(a1)∧ A(a2)∧? ∧ A(an)
(?x)A(x)?A(a1)∨ A(a2)∨? ∨ A(an)
3,量词否定等价式设 A(x)是含自由变元 x的任意谓词公式 。 则
(?x)A(x)?(?x)?A(x)
(?x)A(x)?(?x)?A(x)
约定,量词之前的否定联结词,不是否定该量词,而是否定该量词及其辖域 。
第 2章 谓词逻辑这两个等价式可在有限个体域上证明,设个体域为?a1，
a2,…,an?
(?x)A(x)(A(a1)∧ A(a2)∧? ∧ A(an))
A(a1)∨?A(a2)∨? ∨?A(an)
(?x)?A(x)
(?x)A(x)(A(a1)∨ A(a2)∨? ∨ A(an))
A(a1)∧?A(a2)∧? ∧?A(an)
(?x)?A(x)
当个体域为无限集时,等价式也是成立的 。 但因为情况复杂,仅作以下说明：对等价式?(?x)A(x)?(?x)?A(x)，
(?x)A(x)表示：并不是所有的 x都有性质 A。 (?x)?A(x) 表示：
存在 x没有性质 A。 显然,并不是所有的 x都有性质 A” 和,存在 x没有性质 A” 是相同的,所以?(?x)A(x)?(?x)?A(x)。 对等价式?(?x)A(x)?(?x)?A(x)来说,,不存在某个 x有性质 A” 和
,所有的 x都没有性质 A” 是相同的 。
第 2章 谓词逻辑
4,量词作用域的扩展与收缩等价式设 A(x)是含自由变元 x的任意谓词公式 。 B是不含变元 x的谓词公式,则
(?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)?(?x)A(x)∧ B
利用上述四式可以得到以下四式：
(?x)(A(x)→ B)?(?x)A(x)→ B
(?x)(A(x)→ B)?(?x)A(x)→ B
(?x)(B→ A(x))?B→(?x)A(x)
(?x)(B→ A(x))?B→(?x)A(x)
【 例 2.13】 证明 (?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章 谓词逻辑
5,量词分配等价式设 A(x)和 B(x)是含自由变元 x的任意谓词公式,则
(?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
前者可以理解为：,所有的 x有性质 A和性质 B” 和,所有的 x有性质 A且所有的 x有性质 B” 是等同的 。 后者可以利用前者来证明 。
【 例 2.14】 证明 (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
解,因为 (?x)(?A(x)∧?B(x))?(?x)?A(x)∧ (?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))
所以?(?x) (A(x)∨ B(x))((?x) A(x)∨ (?x) B(x))
于是 (?x) (A(x)∨ B(x))?(?x) A(x)∨ (?x) B(x)
第 2章 谓词逻辑
6,量词与联结词的蕴含式设 A(x)和 B(x)是含自由变元 x的任意谓词公式 。
(?x)A(x)∨ (?x)B(x)?(?x) (A(x)∨ B(x))
(?x) (A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(?x) (A(x)→ B(x))?(?x)A(x)→ (?x)B(x)
(?x) (A(x)?B(x))?(?x)A(x)?(?x)B(x)
对第一式作如下说明：令 A(x)表示 x有一支钢笔,B(x)
表示 x有一支铅笔,个体域是 2000级计算机 1班全体同学 。
全班每个同学都有一支钢笔或每个同学都有一支铅笔,当然可以推出全班每个同学有一支钢笔或有一支铅笔 。 但反过来是不对的 。
第二式可用第一式推出 。
第 2章 谓词逻辑
【 例 2.15】 证明 (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
解,由第一式可得：
(?x)?A(x)∨ (?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))
(?x)(?A(x)∨?B(x))?(?x)?(A(x)∧ B(x))
(?x)(A(x)∧ B(x))
故有?((?x)A(x)∧ (?x) B(x))(?x)(A(x)∧ B(x))
由双条件否定等价式有
(?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x) B(x)
第三,四式可以类似推出 。
第 2章 谓词逻辑
7,多个量词的使用
⑴ 约定,(?x)(?y) A(x,y)表示 (?x) ((?y) A(x,y))
⑵ 一般地说,多个量词相连时,同名量词是无序的,即改变它们的次序,命题真值不变 。 异名量词是有序的,即改变它们的次序,命题真值发生变化 。 对后者作如下的说明：
令 A(x,y)表示 x+y=10,个体域为整数集合 I。
(?x)(?y)A(x,y)表示对任一整数 x,存在整数 y,使 x+y=10。
这是一个真命题 。
(?y)(?x)A(x,y)表示存在整数 y,对任一整数 x,有 x+y=10。
这是一个假命题 。
因为同名量词是无序的,所以有：
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
异名量词有下列的蕴含关系：
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
第 2章 谓词逻辑
⑶ 具有两个量词的谓词公式还有下列的蕴含式：
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
2.4前束范式定义 2.4.1一个公式,如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾,则称为前束范式 。
根据这个定义前束范式可表示成如下形式：
(□ v1)(□ v2)? (□ vn)A
其中,□ 是?或?
vi是个体变元,i=1,?,n
A是不含量词的谓词公式返回章目录第 2章 谓词逻辑例如,(?x)(?y)(F(x)∨ G(y)→ L(x,y))
(?y)(?x)(?z)(?H(x,y)∧ F(x)→ L(x,z))
都是前束范式 。 而
(?x)F(x)∨ (?y)(G(y)→ L(x,y))
(?y)(?x)(?H(x,y)∧ F(x))→(?z)L(x,z)
都不是前束范式 。
定理 2.4.1任何谓词公式,都可以化成与其等价的前束范式 。
本定理的证明从略 。
利用上一节介绍的等价式,2.2节介绍的代入规则和换名规则可以求出任何谓词公式的前束范式 。
【 例 2.16】 求公式 (?x)F(x)→ (?x)G(x) 的前束范式 。
解,(?x)F(x)→ (?x)G(x)(?x)F(x)∨ (?x)G(x)
(?x)?F(x)∨ (?x)G(x)
(?x)(?F(x)∨ G(x)) (前束范式 )
(?x)( F(x)→ G(x)) (前束范式 )
从本例可以看出,谓词公式的前束范式并不惟一 。
第 2章 谓词逻辑
【 例 2.17】 把公式 (?y)G(x,y)→ (?x)F(x,y)化为等价的前束范式 。
解,(?y)G(x,y)→ (?x)F(x,y)?(?t)G(x,t)→ (?s)F(s,y)
(?t)(?s)(G(x,t)→ F(s,y))
定义 2.4.2一个谓词公式 A,如果具有如下形式称为前束合取范式 。
(□ v1)(□ v2)? (□ vn)((A11∨ A12∨ … ∨ )∧
(A21∨ A22∨ … ∨ )∧
(Am1∨ Am2∨ … ∨ ))
其中,□ 是?或?
vi是个体变元,i=1,?,n
Aij是原子公式或其否定 。
例如 (?x)(?y)(?z)((?F(x)∨ H(x,y)∨ G(x))∧ (F(x)∨ L(x,z)))
是前束合取范式 。
22lA
11lA
mmlA
第 2章 谓词逻辑定理 2.4.2 每个谓词公式都可化为与其等价的前束合取范式 。
证明从略 。
【 例 2.18】 将 ((?x)F(x)∨ (?x)G(x))→ (?x)(F(x)∨ G(x))化为与其等价的前束合取范式 。
解,((?x)F(x)∨ (?x)G(x))→ (?x)(F(x)∨ G(x))
(?x)(F(x)∨ G(x))→ (?y)(F(y)∨ G(y))
(?x)(?y)((F(x)∨ G(x))→ (F(y)∨ G(y)))
(?x)(?y)(?(F(x)∨ G(x))∨ (F(y)∨ G(y)))
(?x)(?y)((?F(x)∧?G(x))∨ (F(y)∨ G(y)))
(?x)(?y)((?F(x)∨ F(y)∨ G(y))∧ (?G(x)∨ F(y)∨ G(y)))
第 2章 谓词逻辑定义 2.4.3一个谓词公式 A,如果具有如下形式称为前束析取范式 。
(□ v1)(□ v2)? (□ vn) ((A11∧ A12∧? ∧ )∨
(A21∧ A22∧? ∧ )∨
(Am1∧ Am2∧? ∧ ))
其中,□ 是?或?
vi是个体变元,i=1,?,n
Aij是原子公式或其否定 。
定理 2.4.3 每一个谓词公式 A都可以化为与它等价的前束析取范式 。
证明从略 。
22lA
返回章目录
11lA
mmlA
第 2章 谓词逻辑2.5谓词逻辑的推理理论在谓词演算中,C是一组前提 A1,A2,?,An的有效结论,仍然定义为 A1∧ A2∧? ∧ An?C。 命题演算推理中的 P规则,T规则,置换规则,合取引入规则,所有的等价式和蕴含式在谓词推理中都是对的,都可以使用；另外,2.3节中介绍的谓词演算中的等价式与蕴含式也可以在谓词推理中使用 。
除此之外,还有以下的规则 。
⑴ 全称指定规则 (US规则 )
(?x)A(x)?A(c)
此式成立的条件是：
① c是个体域中任一个体 。
② 用 c取代 A(x)中 x时,一定在 x出现的所有地方进行取代 。
全称指定规则说明：若个体域中的所有个体都满足谓词 A，
则个体域中任一个体 c也满足谓词 A。 利用这个规则,可以从带有全称量词的前提中,推导出不带全称量词的特殊结论 。
它体现了在逻辑推理中由一般到特殊的推导方法 。
第 2章 谓词逻辑
⑵ 全称推广规则 (UG规则 )
A(y)?(?x)A(x)
此式成立的条件是：
① y是个体域中任一个体且对 y,A(y)为真 。
② x是不出现在 A(y)中的个体变元 。
例如,个 体域为 实数集 合 R,G(x,y) 表示 x>y,设
A(y)?(?x)G(x,y),显然 A(y) 满足条件 ①,一定能推出
(?z)A(z)?(?z)(?x)G(x,z)?(?z)(?x)(x>z),这是一个真命题 。
若推成 (?x)A(x)?(?x)(?x)G(x,x)?(?x)(?x)(x>x),就产生了错误,因为这是一个假命题 。 错误的原因是违背了条件 ② 。
⑶ 存在指定规则 (ES规则 )
(?x)A(x)?A(c)
此式成立的条件是：
① c是个体域中的某个确定的个体,而不是个体变元 。
② c是不出现在 A(x)中的个体 。
第 2章 谓词逻辑存在指定规则说明,若个体域中存在一些个体满足谓词 A,则至少有某个确定的个体 c满足谓词 A。
例如,设个体域为整数集合 I,A(x)表示 x是奇数,B(x)
表示 x是偶数 。
(?x)A(x)?A(c),它表示：若存在一些整数是奇数,令 c
为 3,则 c是奇数 。 这个推理是对的 。
(?x)B(x)?B(d),它表示：若存在一些整数是偶数,令 d
为 4,则 d是偶数 。 这个推理也是对的 。 因此有下列推理成立：
(?x)A(x)∧ (?x)B(x)?A(c)∧ B(d)
而下列推理是错误的：
(?x)A(x)∧ (?x)B(x)?A(c)∧ B(c)
(?x)A(x)∧ (?x)B(x)?A(d)∧ B(d)
因为 3不能既是奇数,又是偶数；同样,4也不能既是奇数,又是偶数 。 错误的原因是违背了条件 ② 。
第 2章 谓词逻辑
⑷ 存在推广规则 (EG规则 )
A(c)?(?x)A(x)
此式成立的条件是：
① c是个体域中确定的个体 。
② x不能是出现在 A(c)中的个体变元 。
存在推广规则说明：对于个体域中的某个个体 c满足谓词 A,当然有 (?x)A(x)。
第 2章 谓词逻辑
【 例 2.19】 证明苏格拉底论证：凡人要死 。 苏格拉底是人,苏格拉底要死 。
设,H(x),x是人 。
M(x),x是要死的 。
s：苏格拉底 。
本题要证明,(?x)(H(x)→ M(x))∧ H(s)?M(s)
证明：
⑴ (?x)(H(x)→ M(x)) P
⑵ H(s)→ M(s) US⑴
⑶ H(s) P
⑷ M(s) T⑵⑶ 假言推理第 2章 谓词逻辑
【 例 2.20】 证明 (?x)(H(x)→ M(x)),(?x)H(x)?(?x)M(x)
证明：
⑴ (?x)H(x) P
⑵ H(c) ES⑴
⑶ (?x)(H(x)→ M(x)) P
⑷ H(c)→ M(c) US⑶
⑸ M(c) T⑵⑷ 假言推理
⑹ (?x)M(x) EG⑸
若把 ⑴,⑵ 写在 ⑶,⑷ 的后面,得到如下的推理：
⑴ (?x)(H(x)→ M(x)) P
⑵ H(c)→ M(c) US⑴
⑶ (?x)H(x) P
⑷ H(c) ES⑶
⑸ M(c) T⑵⑷ 假言推理
⑹ (?x)M(x) EG⑸
第 2章 谓词逻辑这个推理在逻辑上是错误的。因为⑵中的 c为个体域中一个个体，用 ES规则由⑶推到⑷不能选择⑵中的 c，因为它要选的个体和⑵中的个体 c不一定是同一个个体，故推理是错误的。
【 例 2.21】 证明 (?x)(A(x)∨ B(x)),(?x)?A(x)?(?x)B(x)
证明,用直接法证明 。
⑴ (?x)(A(x)∨ B(x)) P
⑵ A(s)∨ B(s) US⑴
⑶ (?x)?A(x) P
⑷?A(s) US⑶
⑸ B(s) T⑵⑷ 析取三段论
⑹ (?x)B(x) EG⑸
第 2章 谓词逻辑用归谬法证明 。
⑴?(?x)B(x) P(附加前提 )
⑵ (?x)?B(x) T⑴ 量词否定等价式
⑶?B(s) US⑵
⑷ (?x)(A(x)∨ B(x)) P
⑸ A(s)∨ B(s) US⑷
⑹ A(s) T⑶⑸ 析取三段论
⑺ (?x)?A(x) P
⑻?A(s) US⑺
⑼ A(s)∧?A(s)(矛盾 ) T⑹⑻ 合取引入第 2章 谓词逻辑
【 例 2.22】 用 CP规则证明：
(?x)(F(x)∨ G(x))?(?x)F(x)∨ (?x)G(x)
原题可改写成,(?x)(F(x)∨ G(x))(?x)F(x)→ (?x)G(x)
证明：
⑴?(?x)F(x) P(附加前提 )
⑵ (?x)?F(x) T⑴ 量词否定等价式
⑶?F(c) ES⑵
⑷ (?x) (F(x)∨ G(x)) P
⑸ F(c)∨ G(c) US⑷
⑹ G(c) T⑶⑸ 析取三段论
⑺ (?x)G(x) EG⑹
⑻?(?x)F(x)→ (?x)G(x) CP
第 2章 谓词逻辑
【 例 2.23】 设个体域为全总个体域 。 证明推理：学术会的成员都是工人并且是专家 。 有些成员是青年人 。 所以有的成员是青年专家 。
首先将命题符号化：
F(x),x是学术会成员 。 G(x),x是专家 。
H(x),x是工人 。 R(x),x是青年人 。
本题要证明,(?x)(F(x)→ G(x)∧ H(x)),(?x)(F(x)∧ R(x))
(?x)(F(x)∧ R(x)∧ G(x))
第 2章 谓词逻辑证明：
⑴ (?x)(F(x)∧ R(x)) P
⑵ F(c)∧ R(c) ES⑴
⑶ F(c) T⑵ 化简律
⑷ (?x)(F(x)→ G(x)∧ H(x)) P
⑸ F(c)→ G(c)∧ H(c) US⑷
⑹ G(c)∧ H(c) T⑶⑸ 假言推理
⑺ R(c) T⑵ 化简律
⑻ G(c) T⑹ 化简律
⑼ F(c)∧ R(c)∧ G(c) T⑵⑺⑻ 合取引入
⑽ (?x)(F(x)∧ R(x)∧ G(x)) EG⑼
返回总目录返回章目录
2.1 个体、谓词与量词
2.2 谓词公式
2.3 谓词演算的等价式与蕴含式
2.4 前束范式
2.5 谓词逻辑的推理理论返回总目录第 2章 谓词逻辑第 2章 谓词逻辑
2.1个体、谓词与量词
2.1.1个体考察下面的三个原子命题：
⑴ 李玲是优秀共产党员 。
⑵ 张华比李红高 。
⑶ 小高坐在小王和小刘的中间。
上述命题中的李玲、张华、李红、小高、小王、小刘等客体就是个体。所以可以这样说，个体是指所研究对象中可以独立存在的具体的或抽象的客体。它可以是独立存在的人或物体，也可以是抽象的概念，如,马列主义,,,资本主义,等。个体常用小写英文字母或小写英文字母带下标表示，叫做个体标识符。
第 2章 谓词逻辑表示具体或特定个体的标识符称作个体常元,一般用小写英文字母 a,b,c,? 或这些英文字母带下标表示 。 例如：李玲,张华,李红,小高,小王,小刘可如下表示：
a：李玲
b：张华
c：李红
d：小高
e：小王
f：小刘
a,b,c,d,e,f都是个体常元 。
将表示任意个体或泛指某类个体的标识符称为个体变元,常表示为 x,y,z,? 等或这些英文字母带下标 。
个体变元的变化范围称为个体域或论域 。 个体域可以是有穷集合,也可以是无穷集合,包含任意个体域的个体域称为全总个体域,它是由宇宙间一切对象组成的集合 。
在本书中,如无特别说明,所采用的都是全总个体域 。
第 2章 谓词逻辑
2.1.2谓 词在上面的三个原子命题中,⑴ 可以分解成为个体,李玲,
和,? 是优秀共产党员,两部分 。,? 是优秀共产党员,是用来描述个体,李玲,的性质的； ⑵ 可以分解成为个体,张华,,
,李红,和,? 比? 高,两部分 。,? 比? 高,是用来描述个体,张华,和,李红,的身高关系的； ⑶ 可以分解成为个体
,小高,,,小王,,,小刘,和,? 坐在? 和? 的中间,两部分 。,? 坐在? 和? 的中间,是用来描述个体,小高,,
,小王,,,小刘,的位置关系的 。 这些刻划个体性质或几个个体关系的模式叫做谓词 。 谓词常用大写英文字母表示,叫做谓词标识符 。
例如可以用 F,G,H表示上面三个命题中谓词：
F,? 是优秀共产党员 。
G,? 比? 高 。
H,? 坐在? 和? 的中间 。
第 2章 谓词逻辑把与一个个体相关联的谓词叫做一元谓词 。 F是一元谓词；把与两个个体相关联的谓词叫做二元谓词 。 G是二元谓词；把与三个个体相关联的谓词叫做三元谓词 。 H是三元谓词；? 。 一般的,把与 n个个体相关联的谓词叫做 n元谓词 。
设 F是一元谓词,a是个体常元,用 F(a)表示个体常元 a
具有性质 F；设 G是二元谓词,a,b是个体常元,用 G(a,b)表示个体常元 a和 b具有关系 G；?
于是上面三个命题就表示为：
F(a)：李玲是优秀共产党员 。
G(b,c)：张华比李红高 。
H(d,e,f)：小高坐在小王和小刘的中间 。
将谓词后面填上相关联的个体常元所得的式子叫做谓词填式 。 F(a),G(b,c),H(d,e,f)都是谓词填式 。 谓词填式表示的是命题 。
第 2章 谓词逻辑类似的,用 F(x)表示个体变元 x具有性质 F；用 G(x,y)表示个体变元 x和 y具有关系 G；?,用 P(x1,x2,?,xn)(n≥1)表示个体变元 x1,x2,?,xn具有关系 P。 如果谓词后面有 n个个体变元,则称为 n元命题函数 。 例如 F(x),G(x,y),P(x1,x2,?,xn)
分别叫做一元命题函数,二元命题函数,n元命题函数
(n≥ 1)。 因为命题函数中包含个体变元,因此命题函数没有确定的真值,它不是命题 。 只要用个体常元取代所有的个体变元,就得到了命题 。
例如,用 H(x,y),x+y≥0,显然此命题函数不是命题,因为它无法判断真假 。 令
a,5,b：－ 7
用 a,b分别取代 x,y,就得到 H(a,b),它表示 5+(－ 7)≥0，
这是个假命题,它的真值为假 。
其实,用个体常元取代命题函数的所有个体变元所得到的表达式就是前面所说的谓词填式 。 因为它由个体常元取代命题函数中所有的个体变元而得到,所以也把谓词填式 叫做第 2章 谓词逻辑
0元命题函数 。 F(a),G(b,c),H(d,e,f)都是 0元命题函数,它们都是命题 。 于是命题逻辑中的命题均可以表示为谓词逻辑中的 0元命题函数 (谓词填式 ),命题成为命题函数的特例 。
【 例 2.1】 将下列命题符号化,并讨论它们的真值 。
⑴ 2与 3都是偶数 。
⑵ 如果 5大于 3,则 2大于 6。
解,⑴ 设 F(x),x是偶数 。
a,2,b,3
该命题符号化为,F(a)∧ F(b)
F(b)表示 3是偶数,它是个假命题 。 所以 F(a)∧ F(b)为假 。
⑵ 设 G(x,y),x大于 y
a,5,b,3,c,2,d,6
该命题符号化为,G(a,b)→ G(c,d)
G(a,b)表示 5大于 3,它是真命题 。 G(c,d)表示 2大于 6，
这是个假命题 。 所以 G(a,b)→ G(c,d)为假 。
第 2章 谓词逻辑
2.1.3量词量词分两种 。
⑴ 全称量词日常生活和数学中常用的,一切的,,,所有的,,
,每一个,,,任意的,,,凡,,,都,等词统称为全称量词，将它们符号化为,?” 。并用 (?x),(?y)等表示个体域里的所有个体，而用 (?x)F(x)和 (?y)G(y)等分别表示个体域中的所有个体都有性质 F和都有性质 G。
⑵ 存在量词
,存在,,,有一个,,,有些,,,至少有一个,等词统称为存在量词,将它们符号化为,?” 。 并用 (?x),(?y)
等表示个体域里有些个体,而用 (?x)F(x)和 (?y)G(y)等分别表示在个体域中存在个体具有性质 F和存在个体具有性质 G。
全称量词与存在量词统称为量词。
第 2章 谓词逻辑
【 例 2.2】 个体域是人类集合,对下列命题符号化 。
⑴ 凡人要死 。
⑵ 有的人是研究生 。
解,⑴ 令 F (x),x要死 。
命题,凡人要死 。,符号化为,(?x)F (x)
⑵ 令 G(x),x是研究生 。
命题,有的人是研究生 。,符号化为,(?x)G(x)
在命题函数前加上量词 (?x)和 (?x)分别叫做个体变元 x
被全称量化和存在量化 。 一般地说,命题函数不是命题,
如果对命题函数中所有命题变元进行全称量化或存在量化,
该函数就变成了命题 。 这一结论在例 2.2中得到验证 。
虽然对命题函数中所有命题变元进行量化后,该命题函数就变成了命题,但所得命题的真值与个体域的选定有关 。 请看下列例题：
第 2章 谓词逻辑
【 例 2.3】 对下列命题符号化,并在 ①,②,③ 三个个体域中考察命题的真值 。
命题,⑴ 所有数小于 5。
⑵ 至少有一个数小于 5。
个体域：
①?-1,0,1,2,4?
②?3,-2,7,8?
③?15,20,24?
解,设 L(x),x小于 5。
⑴,所有数小于 5。,符号化为,(?x) L(x)
在个体域 ①,②,③ 中,它们的真值分别为：真,假,假 。
⑵,至少有一个数小于 5。,符号化为,(?x)L(x)
在个体域 ①,②,③ 中,它们的真值分别为：真,真,假 。
命题函数中的个体变元被量化以后变成命题,其真值又与个体域的选定有关,这对命题函数的研究带来了一定的困难,为了统一,我们今后使用全总个体域 。 而将其它个体域第 2章 谓词逻辑用一个谓词来表示,叫做特性谓词 。 特性谓词加入的方法为：
⑴ 对全称量词,特性谓词作为条件命题的前件加入 。
⑵ 对存在量词,特性谓词作为合取项加入 。
【 例 2.4】 对下列命题在 ①,② 两个个体域中符号化 。
命题,⑴ 所有老虎是要吃人 。
⑵ 存在一个老虎要吃人 。
个体域：
① 所有老虎组成的集合 。
② 全总个体域 。
解,设 A(x),x是要吃人的 。 个体域为所有老虎的集合 。
⑴ 符号化为 (?x)A(x)
⑵ 符号化为 (?x)A(x)
个体域为全总个体域 。 设特性谓词 T(x),x是老虎 。
⑴ 符号化为 (?x)(T(x)→ A(x))
⑵ 符号化为 (?x) (T(x)∧ A(x))
返回章目录第 2章 谓词逻辑
2.2谓词公式
2.2.1谓词公式我们把命题,命题变元,谓词填式和命题函数叫做谓词演算的原子公式 。
定义 2.2.1按下列规则构成的表达式称为谓词演算的合式公式,简称谓词公式 。
⑴ 谓词演算的原子公式是合式公式 。
⑵ 若 A是合式公式,则?A是合式公式 。
⑶ 若 A和 B是合式公式,则 (A∧ B),(A∨ B),(A→ B)和
(A? B)是合式公式 。
⑷ 如果 A是合式公式,x是 A中出现的任意个体变元,则
(?x)A,(?x)A是合式公式 。
⑸ 只有有限次地应用 ⑴,⑵,⑶,⑷ 所得的公式是合式公式 。
谓词公式也有以下约定：
第 2章 谓词逻辑
⑴ 最外层的括号可以省略 。
⑵ 如果按?,∧,∨,→,? 在运算中的优先级别,省略括号后不改变原来的运算次序,可以省略括号,但量词后面括号不能省略 。
下面举例说明如何用谓词公式表达自然语言中的命题 。
【 例 2.5】 并非每个实数都是有理数 。
解,设 R(x),x是实数
Q(x),x是有理数该命题符号化为,?(?x)(R(x)→ Q(x))
【 例 2.6】 没有不犯错误的人 。
解,设 M(x),x是人
F(x),x犯错误此命题可以理解为：存在一些人不犯错误,这句话是不对的 。 此时,符号化为,?(?x) (M(x)∧?F(x) )
也可以理解为：任何人都是要犯错误的 。 此时,符号化为,(?x) (M(x)→ F(x))
第 2章 谓词逻辑
【 例 2.7】 并不是所有的兔子都比所有的乌龟跑得快 。
解,设 F(x),x是兔子 。
G(x),x是乌龟 。
H(x,y),x比 y跑得快 。
该命题符号化为,?(?x) (?y) (F(x)∧ G(y)→ H(x,y))
2.2.2约束变元与自由变元定义 2.2.2如果 A是谓词公式 B的一部分且是谓词公式,则称 A是 B的子公式 。
定义 2.2.3紧接量词以后的最小子公式叫做该量词的辖域或作用域 。
定义 2.2.4量词 (?x)和 (?x)中的 x叫做该量词的指导变元或作用变元 。
定义 2.2.5量词 (?x)和 (?x)的辖域内 x的一切出现叫约束出现,x叫做约束变元；约束变元以外的其它变元的出现叫自由出现,自由出现的变元叫自由变元 。
第 2章 谓词逻辑
【 例 2.10】 说明下列各式量词的辖域,找出约束变元和自由变元 。
⑴ (?x)P(x)→ Q(y)
⑵ (?x) (P(x)∧ (?y)Q(x,y))
⑶ (?x) P(x)∧ (?y)Q(x,y)
⑷ (?x)(?y)(P(x,y)∧ Q(y,z))? (?x) R(x,y)
⑸ (?x) P(x)∨ R(x,y)
解,⑴ (?x)的辖域为 P(x),x是约束变元,y是自由变元 。
⑵ (?x)的辖域为 P(x)∧ (?y)Q(x,y),(?y)的辖域为 Q(x,y)，
x和 y都是约束变元,无自由变元 。
⑶ (?x)的辖域为 P(x),(?y)的辖域为 Q(x,y),P(x)中的 x和
Q(x,y) 中的 y是约束变元,Q(x,y)中的 x是自由变元 。
⑷ (?x) 的辖域为 (?y)(P(x,y)∧ Q(y,z)),(?y) 的辖域为
P(x,y)∧ Q(y,z),(?x)的辖域为 R(x,y),x是约束变元,z是自由变元,(P(x,y)∧ Q(y,z))中的 y是约束变元,R(x,y)中的 y是自由变元 。
第 2章 谓词逻辑
⑸ (?x)的辖域为 P(x),y是自由变元,P(x)中 x是约束变元,R(x,y)中 x是自由变元 。
由例 2.10可以看出,在一个公式中,同一个变元既可以是约束的,又可以是自由的,容易混淆 。 因为 (?x)P(x)与
(?y)P(y),(?x)P(x)与 (?y)P(y)都具有相同意义,所以约束变元与表示该变元的符号无关 。 根据这个特点,可以对约束变元换名 。 为了使换名后的公式中出现的变元要么是约束的,
要么是自由的,我们提出如下的换名规则：
⑴ 对约束变元可以换名,其更改变元名称的范围是量词的指导变元,以及该量词辖域中的所有该变元,公式的其余部分不变 。
⑵ 换名时一定要更改成辖域中没有出现的变元名,最好是公式中没有的变量名 。
第 2章 谓词逻辑
【 例 2.11】 对 (?x)(?y)(P(x,y)∧ Q(y,z))?(?x) R(x,y)中的约束变元 y换名 。
解,用 u置换约束变元 y。 换名后为：
(?x)(?u)(P(x,u)∧ Q(u,z))?(?x) R(x,y)
不能换成,(?x)(?u)(P(x,u)∧ Q(y,z))?(?x) R(x,y)
也不能换成,(?x)(?z)(P(x,z)∧ Q(z,z))?(?x) R(x,y)
对公式中的自由变元也可以进行更改,用来解决公式中约束变元与自由变元的同名问题 。 这种更改叫做代入,代入规则是：
⑴ 对于谓词公式中的自由变元可以代入,代入时需对公式中该变元自由出现的每处进行 。
⑵ 代入的变元与原公式中其他变元的名称不能相同。
第 2章 谓词逻辑
【 例 2.12】 对 (?x)(P(y)∧ R(x,y))→ (?y)Q(y) 中的自由变元 y
进行代入 。
解,用 z代换 y,代入后为：
(?x)(P(z)∧ R(x,z))→ (?y)Q(y)
不能换成,(?x)(P(x)∧ R(x,x))→ (?y)Q(y)
或 (?x)(P(z)∧ R(x,y))→ (?y)Q(y)
2.3谓词演算的等价式与蕴含式定义 2.3.1 设 A是谓词公式,如果对 A的任何赋值,A都为真,则称 A是有效的或永真的 。
定义 2.3.2 设 A是谓词公式,如果对 A的任何赋值,A都为假,则称 A是不可满足的或永假的 。
定义 2.3.3 设 A是谓词公式,如果至少有一组赋值使 A为真,则称 A是可满足的 。
根据定义 2.3.1和定义 2.3.3,如果一个谓词公式是有效的,
它一定是可满足的 。
返回章目录第 2章 谓词逻辑定义 2.3.4设 A,B是任意两个谓词公式,对 A,B的任何赋值,若其真值相同,则称 A与 B是等价的,记作 A?B；若
A→ B是有效的,则称 A蕴含 B,记作 A?B。 设 A,B是任意两个谓词公式 。 当 A?B时,由定义 2.3.1和定义 2.3.4知 A? B是永真式 。 反之,当 A? B是永真式时,A?B。 所以,也可以用 A? B是永真式描述 A?B。
1,命题逻辑中的等价式的推广
⑴ 命题演算中的所有等价式都是谓词演算中的等价式 。
从定义 2.2.1可以看出,命题演算的合式公式都是谓词演算的合式公式 。 再根据定义 2.3.4,命题演算中的所有等价式都是谓词演算中的等价式 。
⑵ 命题逻辑中的等价式的推广在命题逻辑中,重言式的同一分量出现的每一处都用同一合式公式置换,其结果仍是重言式 (定理 1.4.2)。 在谓词逻辑中可以推广为：在永真的谓词公式中,命题变元出现的每一处都用同一谓词公式置换,其结果仍是永真式 。 例如：
第 2章 谓词逻辑因为?(p∨ q)p∧?q,故?(p∨ q)?(?p∧?q)为永真式,
用 (?x)P(x) 代替 p,(?y)R(y)代替 q,得到永真式：
((?x)P(x)∨ (?y)R(y))?(?(?x)P(x)∧?(?y)R(y))
所以?((?x)P(x)∨ (?y)R(y))(?x)P(x)∧?(?y)R(y)
2,消去量词等价式设个体域为有限集?a1,a2,?,an?,A(x)是含自由变元
x的任意谓词公式,有下列等价式成立：
(?x)A(x)?A(a1)∧ A(a2)∧? ∧ A(an)
(?x)A(x)?A(a1)∨ A(a2)∨? ∨ A(an)
3,量词否定等价式设 A(x)是含自由变元 x的任意谓词公式 。 则
(?x)A(x)?(?x)?A(x)
(?x)A(x)?(?x)?A(x)
约定,量词之前的否定联结词,不是否定该量词,而是否定该量词及其辖域 。
第 2章 谓词逻辑这两个等价式可在有限个体域上证明,设个体域为?a1，
a2,…,an?
(?x)A(x)(A(a1)∧ A(a2)∧? ∧ A(an))
A(a1)∨?A(a2)∨? ∨?A(an)
(?x)?A(x)
(?x)A(x)(A(a1)∨ A(a2)∨? ∨ A(an))
A(a1)∧?A(a2)∧? ∧?A(an)
(?x)?A(x)
当个体域为无限集时,等价式也是成立的 。 但因为情况复杂,仅作以下说明：对等价式?(?x)A(x)?(?x)?A(x)，
(?x)A(x)表示：并不是所有的 x都有性质 A。 (?x)?A(x) 表示：
存在 x没有性质 A。 显然,并不是所有的 x都有性质 A” 和,存在 x没有性质 A” 是相同的,所以?(?x)A(x)?(?x)?A(x)。 对等价式?(?x)A(x)?(?x)?A(x)来说,,不存在某个 x有性质 A” 和
,所有的 x都没有性质 A” 是相同的 。
第 2章 谓词逻辑
4,量词作用域的扩展与收缩等价式设 A(x)是含自由变元 x的任意谓词公式 。 B是不含变元 x的谓词公式,则
(?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)?(?x)A(x)∧ B
利用上述四式可以得到以下四式：
(?x)(A(x)→ B)?(?x)A(x)→ B
(?x)(A(x)→ B)?(?x)A(x)→ B
(?x)(B→ A(x))?B→(?x)A(x)
(?x)(B→ A(x))?B→(?x)A(x)
【 例 2.13】 证明 (?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章 谓词逻辑
5,量词分配等价式设 A(x)和 B(x)是含自由变元 x的任意谓词公式,则
(?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
前者可以理解为：,所有的 x有性质 A和性质 B” 和,所有的 x有性质 A且所有的 x有性质 B” 是等同的 。 后者可以利用前者来证明 。
【 例 2.14】 证明 (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
解,因为 (?x)(?A(x)∧?B(x))?(?x)?A(x)∧ (?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))
所以?(?x) (A(x)∨ B(x))((?x) A(x)∨ (?x) B(x))
于是 (?x) (A(x)∨ B(x))?(?x) A(x)∨ (?x) B(x)
第 2章 谓词逻辑
6,量词与联结词的蕴含式设 A(x)和 B(x)是含自由变元 x的任意谓词公式 。
(?x)A(x)∨ (?x)B(x)?(?x) (A(x)∨ B(x))
(?x) (A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(?x) (A(x)→ B(x))?(?x)A(x)→ (?x)B(x)
(?x) (A(x)?B(x))?(?x)A(x)?(?x)B(x)
对第一式作如下说明：令 A(x)表示 x有一支钢笔,B(x)
表示 x有一支铅笔,个体域是 2000级计算机 1班全体同学 。
全班每个同学都有一支钢笔或每个同学都有一支铅笔,当然可以推出全班每个同学有一支钢笔或有一支铅笔 。 但反过来是不对的 。
第二式可用第一式推出 。
第 2章 谓词逻辑
【 例 2.15】 证明 (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
解,由第一式可得：
(?x)?A(x)∨ (?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))
(?x)(?A(x)∨?B(x))?(?x)?(A(x)∧ B(x))
(?x)(A(x)∧ B(x))
故有?((?x)A(x)∧ (?x) B(x))(?x)(A(x)∧ B(x))
由双条件否定等价式有
(?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x) B(x)
第三,四式可以类似推出 。
第 2章 谓词逻辑
7,多个量词的使用
⑴ 约定,(?x)(?y) A(x,y)表示 (?x) ((?y) A(x,y))
⑵ 一般地说,多个量词相连时,同名量词是无序的,即改变它们的次序,命题真值不变 。 异名量词是有序的,即改变它们的次序,命题真值发生变化 。 对后者作如下的说明：
令 A(x,y)表示 x+y=10,个体域为整数集合 I。
(?x)(?y)A(x,y)表示对任一整数 x,存在整数 y,使 x+y=10。
这是一个真命题 。
(?y)(?x)A(x,y)表示存在整数 y,对任一整数 x,有 x+y=10。
这是一个假命题 。
因为同名量词是无序的,所以有：
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
异名量词有下列的蕴含关系：
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
第 2章 谓词逻辑
⑶ 具有两个量词的谓词公式还有下列的蕴含式：
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?y)(?x)A(x,y)?(?x)(?y)A(x,y)
2.4前束范式定义 2.4.1一个公式,如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾,则称为前束范式 。
根据这个定义前束范式可表示成如下形式：
(□ v1)(□ v2)? (□ vn)A
其中,□ 是?或?
vi是个体变元,i=1,?,n
A是不含量词的谓词公式返回章目录第 2章 谓词逻辑例如,(?x)(?y)(F(x)∨ G(y)→ L(x,y))
(?y)(?x)(?z)(?H(x,y)∧ F(x)→ L(x,z))
都是前束范式 。 而
(?x)F(x)∨ (?y)(G(y)→ L(x,y))
(?y)(?x)(?H(x,y)∧ F(x))→(?z)L(x,z)
都不是前束范式 。
定理 2.4.1任何谓词公式,都可以化成与其等价的前束范式 。
本定理的证明从略 。
利用上一节介绍的等价式,2.2节介绍的代入规则和换名规则可以求出任何谓词公式的前束范式 。
【 例 2.16】 求公式 (?x)F(x)→ (?x)G(x) 的前束范式 。
解,(?x)F(x)→ (?x)G(x)(?x)F(x)∨ (?x)G(x)
(?x)?F(x)∨ (?x)G(x)
(?x)(?F(x)∨ G(x)) (前束范式 )
(?x)( F(x)→ G(x)) (前束范式 )
从本例可以看出,谓词公式的前束范式并不惟一 。
第 2章 谓词逻辑
【 例 2.17】 把公式 (?y)G(x,y)→ (?x)F(x,y)化为等价的前束范式 。
解,(?y)G(x,y)→ (?x)F(x,y)?(?t)G(x,t)→ (?s)F(s,y)
(?t)(?s)(G(x,t)→ F(s,y))
定义 2.4.2一个谓词公式 A,如果具有如下形式称为前束合取范式 。
(□ v1)(□ v2)? (□ vn)((A11∨ A12∨ … ∨ )∧
(A21∨ A22∨ … ∨ )∧
(Am1∨ Am2∨ … ∨ ))
其中,□ 是?或?
vi是个体变元,i=1,?,n
Aij是原子公式或其否定 。
例如 (?x)(?y)(?z)((?F(x)∨ H(x,y)∨ G(x))∧ (F(x)∨ L(x,z)))
是前束合取范式 。
22lA
11lA
mmlA
第 2章 谓词逻辑定理 2.4.2 每个谓词公式都可化为与其等价的前束合取范式 。
证明从略 。
【 例 2.18】 将 ((?x)F(x)∨ (?x)G(x))→ (?x)(F(x)∨ G(x))化为与其等价的前束合取范式 。
解,((?x)F(x)∨ (?x)G(x))→ (?x)(F(x)∨ G(x))
(?x)(F(x)∨ G(x))→ (?y)(F(y)∨ G(y))
(?x)(?y)((F(x)∨ G(x))→ (F(y)∨ G(y)))
(?x)(?y)(?(F(x)∨ G(x))∨ (F(y)∨ G(y)))
(?x)(?y)((?F(x)∧?G(x))∨ (F(y)∨ G(y)))
(?x)(?y)((?F(x)∨ F(y)∨ G(y))∧ (?G(x)∨ F(y)∨ G(y)))
第 2章 谓词逻辑定义 2.4.3一个谓词公式 A,如果具有如下形式称为前束析取范式 。
(□ v1)(□ v2)? (□ vn) ((A11∧ A12∧? ∧ )∨
(A21∧ A22∧? ∧ )∨
(Am1∧ Am2∧? ∧ ))
其中,□ 是?或?
vi是个体变元,i=1,?,n
Aij是原子公式或其否定 。
定理 2.4.3 每一个谓词公式 A都可以化为与它等价的前束析取范式 。
证明从略 。
22lA
返回章目录
11lA
mmlA
第 2章 谓词逻辑2.5谓词逻辑的推理理论在谓词演算中,C是一组前提 A1,A2,?,An的有效结论,仍然定义为 A1∧ A2∧? ∧ An?C。 命题演算推理中的 P规则,T规则,置换规则,合取引入规则,所有的等价式和蕴含式在谓词推理中都是对的,都可以使用；另外,2.3节中介绍的谓词演算中的等价式与蕴含式也可以在谓词推理中使用 。
除此之外,还有以下的规则 。
⑴ 全称指定规则 (US规则 )
(?x)A(x)?A(c)
此式成立的条件是：
① c是个体域中任一个体 。
② 用 c取代 A(x)中 x时,一定在 x出现的所有地方进行取代 。
全称指定规则说明：若个体域中的所有个体都满足谓词 A，
则个体域中任一个体 c也满足谓词 A。 利用这个规则,可以从带有全称量词的前提中,推导出不带全称量词的特殊结论 。
它体现了在逻辑推理中由一般到特殊的推导方法 。
第 2章 谓词逻辑
⑵ 全称推广规则 (UG规则 )
A(y)?(?x)A(x)
此式成立的条件是：
① y是个体域中任一个体且对 y,A(y)为真 。
② x是不出现在 A(y)中的个体变元 。
例如,个 体域为 实数集 合 R,G(x,y) 表示 x>y,设
A(y)?(?x)G(x,y),显然 A(y) 满足条件 ①,一定能推出
(?z)A(z)?(?z)(?x)G(x,z)?(?z)(?x)(x>z),这是一个真命题 。
若推成 (?x)A(x)?(?x)(?x)G(x,x)?(?x)(?x)(x>x),就产生了错误,因为这是一个假命题 。 错误的原因是违背了条件 ② 。
⑶ 存在指定规则 (ES规则 )
(?x)A(x)?A(c)
此式成立的条件是：
① c是个体域中的某个确定的个体,而不是个体变元 。
② c是不出现在 A(x)中的个体 。
第 2章 谓词逻辑存在指定规则说明,若个体域中存在一些个体满足谓词 A,则至少有某个确定的个体 c满足谓词 A。
例如,设个体域为整数集合 I,A(x)表示 x是奇数,B(x)
表示 x是偶数 。
(?x)A(x)?A(c),它表示：若存在一些整数是奇数,令 c
为 3,则 c是奇数 。 这个推理是对的 。
(?x)B(x)?B(d),它表示：若存在一些整数是偶数,令 d
为 4,则 d是偶数 。 这个推理也是对的 。 因此有下列推理成立：
(?x)A(x)∧ (?x)B(x)?A(c)∧ B(d)
而下列推理是错误的：
(?x)A(x)∧ (?x)B(x)?A(c)∧ B(c)
(?x)A(x)∧ (?x)B(x)?A(d)∧ B(d)
因为 3不能既是奇数,又是偶数；同样,4也不能既是奇数,又是偶数 。 错误的原因是违背了条件 ② 。
第 2章 谓词逻辑
⑷ 存在推广规则 (EG规则 )
A(c)?(?x)A(x)
此式成立的条件是：
① c是个体域中确定的个体 。
② x不能是出现在 A(c)中的个体变元 。
存在推广规则说明：对于个体域中的某个个体 c满足谓词 A,当然有 (?x)A(x)。
第 2章 谓词逻辑
【 例 2.19】 证明苏格拉底论证：凡人要死 。 苏格拉底是人,苏格拉底要死 。
设,H(x),x是人 。
M(x),x是要死的 。
s：苏格拉底 。
本题要证明,(?x)(H(x)→ M(x))∧ H(s)?M(s)
证明：
⑴ (?x)(H(x)→ M(x)) P
⑵ H(s)→ M(s) US⑴
⑶ H(s) P
⑷ M(s) T⑵⑶ 假言推理第 2章 谓词逻辑
【 例 2.20】 证明 (?x)(H(x)→ M(x)),(?x)H(x)?(?x)M(x)
证明：
⑴ (?x)H(x) P
⑵ H(c) ES⑴
⑶ (?x)(H(x)→ M(x)) P
⑷ H(c)→ M(c) US⑶
⑸ M(c) T⑵⑷ 假言推理
⑹ (?x)M(x) EG⑸
若把 ⑴,⑵ 写在 ⑶,⑷ 的后面,得到如下的推理：
⑴ (?x)(H(x)→ M(x)) P
⑵ H(c)→ M(c) US⑴
⑶ (?x)H(x) P
⑷ H(c) ES⑶
⑸ M(c) T⑵⑷ 假言推理
⑹ (?x)M(x) EG⑸
第 2章 谓词逻辑这个推理在逻辑上是错误的。因为⑵中的 c为个体域中一个个体，用 ES规则由⑶推到⑷不能选择⑵中的 c，因为它要选的个体和⑵中的个体 c不一定是同一个个体，故推理是错误的。
【 例 2.21】 证明 (?x)(A(x)∨ B(x)),(?x)?A(x)?(?x)B(x)
证明,用直接法证明 。
⑴ (?x)(A(x)∨ B(x)) P
⑵ A(s)∨ B(s) US⑴
⑶ (?x)?A(x) P
⑷?A(s) US⑶
⑸ B(s) T⑵⑷ 析取三段论
⑹ (?x)B(x) EG⑸
第 2章 谓词逻辑用归谬法证明 。
⑴?(?x)B(x) P(附加前提 )
⑵ (?x)?B(x) T⑴ 量词否定等价式
⑶?B(s) US⑵
⑷ (?x)(A(x)∨ B(x)) P
⑸ A(s)∨ B(s) US⑷
⑹ A(s) T⑶⑸ 析取三段论
⑺ (?x)?A(x) P
⑻?A(s) US⑺
⑼ A(s)∧?A(s)(矛盾 ) T⑹⑻ 合取引入第 2章 谓词逻辑
【 例 2.22】 用 CP规则证明：
(?x)(F(x)∨ G(x))?(?x)F(x)∨ (?x)G(x)
原题可改写成,(?x)(F(x)∨ G(x))(?x)F(x)→ (?x)G(x)
证明：
⑴?(?x)F(x) P(附加前提 )
⑵ (?x)?F(x) T⑴ 量词否定等价式
⑶?F(c) ES⑵
⑷ (?x) (F(x)∨ G(x)) P
⑸ F(c)∨ G(c) US⑷
⑹ G(c) T⑶⑸ 析取三段论
⑺ (?x)G(x) EG⑹
⑻?(?x)F(x)→ (?x)G(x) CP
第 2章 谓词逻辑
【 例 2.23】 设个体域为全总个体域 。 证明推理：学术会的成员都是工人并且是专家 。 有些成员是青年人 。 所以有的成员是青年专家 。
首先将命题符号化：
F(x),x是学术会成员 。 G(x),x是专家 。
H(x),x是工人 。 R(x),x是青年人 。
本题要证明,(?x)(F(x)→ G(x)∧ H(x)),(?x)(F(x)∧ R(x))
(?x)(F(x)∧ R(x)∧ G(x))
第 2章 谓词逻辑证明：
⑴ (?x)(F(x)∧ R(x)) P
⑵ F(c)∧ R(c) ES⑴
⑶ F(c) T⑵ 化简律
⑷ (?x)(F(x)→ G(x)∧ H(x)) P
⑸ F(c)→ G(c)∧ H(c) US⑷
⑹ G(c)∧ H(c) T⑶⑸ 假言推理
⑺ R(c) T⑵ 化简律
⑻ G(c) T⑹ 化简律
⑼ F(c)∧ R(c)∧ G(c) T⑵⑺⑻ 合取引入
⑽ (?x)(F(x)∧ R(x)∧ G(x)) EG⑼
返回总目录返回章目录
