第3 章
一阶逻辑
3.1 一阶逻辑基本概念
3.1.1 命题逻辑的局限性
在命题逻辑中,命题是最基本的单位,对简单命题不再进行分解,并且不考虑命题之间
的内在联系和数量关系.因而命题逻辑具有局限性,甚至无法判断一些简单而常见的推理.
考虑下面的推理:
凡偶数都能被2整除.
6是偶数.
所以,6能被2整除.
这个推理显然是数学中的正确推理,但在命题逻辑中却无法证明它的正确性.因为在命题
逻辑中只能将推理中出现的3个句子看作简单命题,依次符号化为p,q,r,将推理的形式
结构符号化为
(p ∧q)→r
由于上式不是重言式,所以认为这个推理是错误的.为了克服命题逻辑的局限性,就需要引
入个体词、谓词和量词,以期达到表达出个体与总体的内在联系和数量关系,这就是一阶逻
辑所研究的内容.一阶逻辑也称一阶谓词逻辑或谓词逻辑.
3.1.2 个体词、谓词与量词
在一阶逻辑中,要求将简单的陈述句(可能是命题,也可能不是命题)细分成主语与谓
语,用P(x)表示x 具有性质P ,讨论P(x)在什么情况下为真,在什么情况下为假,并且讨
论在x 的指定的取值范围内是否对所有的x 均为真,或存在x 使其为真等,在讨论中有3
个要素是必不可少的,这就是个体词、谓词与量词.有了这3个要素的概念之后,就可以讨
论一阶逻辑中命题(可含命题变项)符号化的问题了.
1.个体词
个体词是指所研究对象中可以独立存在的具体的或抽象的客体.例如,小王、小李、中
国、2和3等都可作为个体词.将表示具体或特定的客体的个体词称作个体常项,一般用小
写英文字母a,b,c,…表示,而将表示抽象或泛指的个体词称为个体变项,常用x,y,z,…
表示.并称个体变项的取值范围为个体域(或称论域).个体域可以是有穷集合,例如,
一阶逻辑
{1,3},{b,d},{b,x,z}
.
例如, 0,
2,a,c,a,c,…,y,也可以是无穷集合, 自然数集合N={1,
2,…}, 实数集合R={x|
x
是实数}.有一个特殊的个体域,它是由宇宙间一切事物组成的,
称为全总个体域.本书在论述或推理中如无指明所采用的个体域,都是使用的全总个体域
.
项;
例如,在“5是素数”和“ x>y”中,5,素数,x,
y
都是个体词,其中,5和素数是个体常
x
和
y
为个体变项
.
2.
谓词
谓词是用来刻画个体词性质及个体词之间相互关系的词.考虑下面4个命题(或命题
变项):
(1)2是无理数
.
(2)
x
是有理数
.
(3)小王与小李同岁
.
(4)
x
与
y
具有关系L.
在(1)中,2是个体常项,“…… 是无理数”是谓词,记为F,并用F(2)表示(1)中命题
.
在(2)中,
x
是个体变项,“…… 是有理数”是谓词,记为G,用G(x)表示(2)中命题.在(3)
中,小王、小李都是个体常项,“…… 与…… 同岁”是谓词,记为
H
,则(3)中命题符号化形式
为
H
(b), a:小王,在(中,
y
为两个个体变项,…… 与…… 有关系L”
a,其中,b:小李
.
4) x,“
是谓词,符号化为L(y)
x,
.
同个体词一样,谓词也有常项与变项之分.表示具体性质或关系的谓词称为谓词常项,
表示抽象的或泛指的性质或关系的谓词称为谓词变项.无论是谓词常项还是变项都用大写
英文字母F,G,
H
,…表示,要根据上下文区分.在上面4个命题中,(1),(2),(3)中谓词
F,G,而(中谓词
L
是变项.a) F
H
是常项, 4) 一般地,用F(表示个体常项
a
具有性质F(
是谓词常项或谓词变项), 用
F
(x)表示个体变项
x
具有性质F.而用
F
(a,b)表示个
体常项a,x,y)表示个体变项x,更一般地,用
b
具有关系F,用
F
(
y
具有关系F.
P(x1,xn
表示含n(个命题变项x1,xn
n=P(表
x2,…,) n≥1) x2,…,的
n
元谓词,1时,x1)
示x1 具有性质P,n≥2 时,x1,xn
表示x1,xn
实质上,
P(x2,…,) x2,…,具有关系P. n
元
谓词P(x1,xn
) 以{1} 它
x2,…,可以看成以个体域为定义域, 0,为值域的
n
元函数或关系
.
不是命题.要想使它成为命题,必须用谓词常项取代F,用个体常项a1,a2,…,an
取代
x2,…,得F(a2,…,)是命题,或加量词(见下文)
有时将不带个体变项的谓词称为0元谓词.例如,a),b),a2,…,)等
x1,xn
, a1,an .
F(G(a,P(a1,an
都是0元谓词,当F,G,
P
为谓词常项时,0元谓词为命题.这样一来,命题逻辑中的命题均
可以表示成0元谓词,因而可将命题看成特殊的谓词
.
例3.1
将下列命题在一阶逻辑中用0元谓词符号化,并讨论它们的真值
.
(1)只有2是素数,4才是素数
.
(2)如果5大于4,则4大于6.
解(1)设1元谓词F(x):
x
是素数.a:2,b:4.(1)中命题符号化为0元谓词的
蕴
涵
式
F(a)
b)→F(
由于此蕴涵前件为假,所以(1)中命题为真
.
(2)设2元谓词G(y)
x
大于y.4,5,6.b,G(c)
x,:a:b:c:G(a),a,是两个0元谓词,
第
章
67
68
离散数学(第4版)
把(2)中命题符号化为
G(a)→G(c)
b,a,
b,a,2)
由于G(a)为真,而G(c)为假,所以(中命题为假
.
3.
量词
有了个体词和谓词的概念之后,对有些命题来说,还是不能准确地符号化,原因是还缺
少表示个体常项或变项之间数量关系的词.表示个体常项或变项之间数量关系的词称为量
词.量词有下述两个
.
(1)全称量词:日常生活和数学中常用的“一切的”“所有的”“每一个”“任意的”“凡”
“都”等词可统称为全称量词,将它们符号化为..并用.x,.
y
等表示个体域里的所有个
体,而用.xF(y)等分别表示个体域里所有个体都有性质
F
和都有性质G.
x),.yG(
(2)存在量词:日常生活和数学中常用的“存在”“有一个”“有的”“至少有一个”等词统
称为存在量词,将它们都符号化为..并用.x,.
y
等表示个体域里有的个体,而用.xF(x),
.yG(等分别表示在个体域里存在个体具有性质
F
和存在个体具有性质
G
等.
y)
3.3
一阶逻辑命题符号化
1.
本节将用例题说明一阶逻辑中命题符号化的形式,以及注意事项
.
例3.2
在个体域分别限制为(a)和(b)条件时,将下面两个命题符号化
.
(1)凡是人都呼吸
.
(2)有的人用左手写字
.
其中
,
(a)个体域D1 为人类集合;
(b)个体域D2 为全总个体域
.
解(x):G(
:
a)令F(
x
呼吸.x)
x
用左手写字
.
(1)在D1 中除人外,再无别的东西,因而“凡是人都呼吸”应符号化为
3..xF(x) (1)
(2)在D1 中的有些个体(人)用左手写字,因而“有的人用左手写字”符号化为
.xG(3.
x) (2)
(b)D2 中除有人外,还有万物,因而在(1)和(2)符号化时,必须考虑将人先分离出来
.
令
M
(x):在D2 中,(和(2)可分别重述如下:
x
是人
.
1)
(1)对于宇宙间一切事物而言,如果事物是人,则他要呼吸
.
(2)在宇宙间存在着用左手写字的人
.
于是(1)和(2)的符号化形式应分别为
3..x(
M
(x)→F(x)) (3)
和
.x(
M
(x)) 3.
其中,F(x)与G(x)的含义同(a)中.
x)∧G((4)
由例3.2可知,命题(1)和(2)在不同的个体域D1 和D2 中符号化的形式不一样,主要
区别在于,在使用个体域D2 时,要将人与其他事物区别开来,为此引进了谓词
M
(x), 像这
样的谓词称为特性谓词.在命题符号化时一定要正确使用特性谓词
.
一阶逻辑
第
在个体域D1 与D2 中,命题(1)与(2)都是真命题(在这里讨论的人是活着的人).在D1
3
中,式(3.1)与式(3.正确地给出了(1)与(的符号化形式
3.
.
在D2 中,式(3.与式(3.
若
给
x
2) 2) 3)4)
章
出的(1)与(2)的符号化形式的正确性可作如下说明.在式(3)中,对于任意的x∈D2,
代表某个人a,则因
M
(与F(均为真, a)a) 而当
x
代表人以
a) a) 因而蕴涵式
M
(→F(为真
.
外的事物,如某棵树b, b) 所以
3M
)
(b) 因而在式(中的蕴涵
69
则因
M
(为假, b)也为真, 3)
式不会出现前件真后件假的情况,所以式(3.正确给出了(1)的符号化形式.而有些初学
者,在D2 中常将(1)符号化为下面形式:
3.
.x(
M
(x)∧F(x)) (5)
式(3.不是(1)的符号化形式,若将它翻译成自然语言,应该是“宇宙间的任何事物都是人5)
这显然不是(的符号化形式,
M
(为假,
→F(3.
并且都呼吸”, 1) 任何非人的个体
c
代入后,c) 所以
式(3.为假
.
1) 3.的形式
.
3.由于存在用左手写字
5) 因而命题(不能符号化为式(5) 对于式(4),
的人,比如前任美国总统克林顿就用左手写字,
M
(a) 所
4)
当用
a
代表克林顿时,a)∧G(为真,
以式(3.为真.有些人将(2)符号化为下面形式:
.x(
M
(x)) 3.
x)→G((6)
式(6)已不是(2)的符号化形式,将它翻译成自然语言应该为“在宇宙间存在个体,如果此
个体为人
例3.3,则他用左手写字”,这显然改变了原命题的含义,因而式(3.不能代替式(3.
.
在个体域限制为(a)和(b)条件时,将下列命题符号化
.
6) 4)
3.
(1)对于任意的x,均有x2-3x+2=(x-1)(x-2)
.
(2)存在x,使得x+5=3.
其中,
(a)个体域D1=N(
N
为自然数集)
.
(b)个体域D2=R(
R
为实数集)
.
a)令F(x2-3x+2=(x-x-x+5=3.
1)
解(x):1)(2),G(x):命题(的符号化形
式为
(7)
命题(2)的符号化形式为
.xF(x)3.
3.
显然(1)为真命题,而(2)为假命题
.
.xG(x) (8)
(b)在D2 内,(1)与(2)的符号化形式还是式(7)和式(8),(1)仍然是真命题,而此
时(2)也为真命题
.
3.3.
从例3.3可以看出以下两点:
2和例3.
(1)在不同个体域内,同一个命题的符号化形式可能不同,也可能相同
.
(2)同一个命题,在不同个体域中的真值也可能不同
.
另外,作为一种规定,在本书中,讨论命题符号化时,若没有指明个体域,就采用全总
个
体域,见下例
.
将下列命题符号化,并讨论真值.
例3.4
(1)所有的人都长着黑头发
.
(2)有的人登上过月球
.
(3)没有人登上过木星
.
70
离散数学(第4版)
(4)在美国留学的学生未必都是亚洲人
.
解
由于本题没提出个体域,因而应采用全总个体域,并令
M
(x):
x
为人
.
x)
x
长着黑头发
.
.x(x)→F(
a)a) 9)
3.
(1)令F(:命题(1)符号化为
M
(x)) (9)
a) a)→F(3.
设
a
为某金发姑娘,则
M
(为真,而F(为假,所以
M
(为假,故式(所表示
的命题为假
.
(2)令G(x):
x
登上过月球.命题(2)的符号化形式
为
3.
.x(
M
(x)∧G(x)) (10)
设
a
是1969 年登上月球完成阿波罗计划的阿姆斯特朗,则
M
(a)∧
G
(a)为真,所以
式(3.表示的命题为真.
10)
(3)令
H
(x):
x
登上过木星.命题(3)符号化形式
为
3.
...x(
M
(x)∧
H
(x)) (11)
到目前为止,对于任何一个人(含已经去世的人)都还没有登上过木星,所以对任何人a,
M
(a) 因而.x(x)∧
H
(为假,3.表示的命题为真.
a)∧
H
(均假,
M
(x)) 故式(11)
(4)令F(
:
G(:命题(符号化形式为
12)
x)
x
是在美国留学的学生,x)
x
是亚洲人
.
4)
容易讨论,(4)中命题为真
.
...x(F(x)→G(x)) (3.
例3.5
下面讨论n(元谓词的符号化问题.
n≥2)
将下列命题符号化
.
(1)兔子比乌龟跑得快
.
(2)有的兔子比所有的乌龟跑得快
.
(3)并不是所有的兔子都比乌龟跑得快
.
(4)不存在跑得同样快的两只兔子
.
解因为本题没有指明个体域,因而采用全总个体域.因为本例中出现2元谓词,因而
引入两个个体变项
x
与y.令F(x):
x
是兔子,G(y):
y
是乌龟,
N
(x,y):x≠y,
H
(x,
y):x,
x
与
y
跑得同样快.这4个命题分别符号化为
x
比
y
跑得快,L(y):
x)∧G(x,13).x.y(F(y)→
H
(y)) (3.
.x(F(x)∧.y(y)→
H
(x,(14)
G(y))) 3.
...x.y(F(x)∧G(y)→
H
(x,3.
y)) (15)
...x.y(F(y)∧
N
(y)∧L(y)) 3.
x)∧F(x,x,(16)
对于存在
n
元谓词的命题,在符号化时应该注意以下4点:
(1)分析命题中表示性质和关系的谓词,分别符号化为1元和n(元谓词
.
(2)根据命题的实际意义选用全称量词或存在量词.
n≥2)
(3)一般说来,多个量词出现时,它们的顺序不能随意调换.例如,考虑个体域为实数
集,
H
(y) 10, 对于任意的x, 使得x+y=”
x,表示x+y=则命题“ 都存在y, 10的符号化形
式为
.x.yH
(x,
(3.
y) 17)
所给命题显然为真命题.但如果改变两个量词的顺序,得
.y.xH
(x,(18)
y)
3.
一阶逻辑
第
它的含义是“存在y,使得所有的x,有x+y=10,(”) 这显然是假命题
.
3
(4)有些命题的符号化形式可不仅一种
.
在例3.3)还可以说成“有的兔子
章
不比有的乌龟跑得快”,从而又可以符号化为
例如,5中,(
.x.y(F(x)∧G(y)∧..
H
(x,3.
y)) (19)
71
(4)还可以说成“任何两只兔子都跑得不一样快”,因而又可以符号化为
.x.y(F(y)∧
N
(y)→..L(x,3.
x)∧F(x,y)) (20)
这样,式(15) 3.都是(的符号化形式,3.与式(20) 4)的符号化形
3.和式(192)
.3) 式(16)
3.3.都是(
式,它们都是正确的(1小节可以证明式(15)和式(19)是等值的,式(16)和
式(3.是等值的)
3.3.3.
20)
.
由于引进了个体词、谓词和量词的概念,现在可以将本章开始时讨论的推理在一阶逻辑
中符号化为如下形式:
.x(F(x))∧F(a)3.
x)→G(a)→G((21)
其中,F(x):
x
是偶数,G(x):
x
能被2整除,a:6.由于.x(F(x)→G(x)) 为真,F(a)→
a) 又由于F(→G(和F(为真, 得到G(
G(为真.a)a) a) 根据假言推理, a)为真.这就解决了
本章开头提出的推理问题
.
1.一阶逻辑公式与分类
3.4
同在命题逻辑中一样,为在一阶逻辑中进行演算和推理,还必须给出一阶逻辑中公式的
抽象定义,以及它们的解释和分类.为此,首先给出一阶语言的概念,所谓一阶语言是用于
一阶逻辑的形式语言,而一阶逻辑就是建立在一阶语言基础上的逻辑体系,一阶语言本身不
具备任何含义,但可以根据需要被解释成具有某种含义.一阶语言的形式是多种多样的.本
书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言,记它为L.
定义3.一阶语言L的字母表定义如下:
1
(1)个体常项:b,ai,i,i,…,
a,c,…,bci≥1.
x,z,…,yi,i,…,
(2)个体变项:y,xi,zi≥1.
g,fi,hi,…,
(3)函数符号:f,h,…,gi,i≥1.
G,Fi,Hi,…,
(4)谓词符号:F,
H
,…,Gi,i≥1.
(5)量词符号:.,.
.
(6)联结词符号:..,∧,∨,→,.
.
(7)括号与逗号:(),,
.
3节式(1)~式(21)所用符号均为L字母表中的符号
.
为方便起见,再给出L的项的概念
.
3.1.3.3.
定义3.
2
L的项的定义如下:
(1)个体常项和个体变项是项
.
(2)若
φ
(x1,x2,…,xn
)是任意的
n
元函数,t1,t2,…,t
φ(t2,…,
n
)是项.
n
是任意的
n
个项,则
t1,t
(3)所有的项都是有限次使用(1),(2)得到的
.
定义3.设R(x2,…,)是L的任意
n
元谓词,t2,…,
n
是L的任意的
n
个
3
x1,xn
t1,t
72
离散数学(第4版)
项,则称R(t2,…,
n
)是L的原子公式
.
t1,tG(x,L(y)等都是原子公式
.
例3.5中的1元谓词F(x),y),2元谓词
H
(y),x,
定义3.
4
L的合式公式定义如下:
(1)原子公式是合式公式
.
(2)若
A
是合式公式,则(..A)也是合式公式
.
(3)若A,
B
是合式公式,则(A∧B),(A∨B),(A→B),(A.B)也是合式公式
.
(4)若
A
是合式公式,则.xA,.xA
也是合式公式
.
(5)只有有限次应用(1)~(4)构成的符号串才是合式公式
.
合式公式也称为谓词公式,简称公式
.
在定义3.4中出现的字母A,
B
是代表任意公式的元语言符号.为方便起见,公
式
(..A),(A∧B),…的最外层括号可以省去,使其变成..A,
A
∧B,….式(1)式(3.
3.~ 21)
都是L中的公式
.
因为本书只引进一种一阶语言L,下文的讨论中都是在L中,因而一般不再提及L.另
外,下文中出现的A,
B
等符号均指任意的合式公式,简称为公式.例如,
A
可以是F(x),
G(x) 也可以不是原子公式, x)→.yG(y),.x(x,x,等
等原子公式, 如F(F(y)∧G(z))
按合式公式形成规则形成的各种公式
.
定义3.5
在公式.xA
和.xA
中,称
x
为指导变元,
A
为相应量词的辖域.在.
x
和
.
x
的辖域中,
A
中不是约束出现的其他变项均称为是自由
x
的所有出现都称为约束出现,
出现的
.
指出下列各公式中的指导变元,各量词的辖域,自由出现以及约束出现的个
体变项
.
(x,→G(z)) (3.
例3.6
1).x(F(y)x,22)
(2).x(x)y))→.y(x)∧L(y,(23)
F(→G(
H
(x,z)) 3.
解(
x
是指导变元.F(y)→G(x,在
A
中,
1)量词.的辖域A=(x,z)),
x
是约束出
现的,而且约束出现两次,而且各自由出现一次.
y
和
z
均为自由出现的,
(2)公式中含两个量词,前件中的量词的指导变元为x,.
x
的辖域
A
=(
F
(x)→
G(y)), 其中
x
是约束出现的,后件中的量词的指导变元为y,.
y
的辖域
为(
H
(x)∧L(x,y,z)),
y
是自由出现的.
x,
z
均为自由出现的.在整个公式中,
其中
y
是约束出现的,
x
约
束出现一次,自由出现两次,约束出现一次,注意,在这
y
自由出现一次,
z
只自由出现一次
.
里前件中的
x
和后件中的
x
是两个不同的变元,如同两个人取同一个名字一样.同样地,前
件中的
y
和后件中的
y
也是两个不同的变元.也就是说,在不同的辖域内出现的同一个字
母代表不同的变元
.
本书用A(x1,x2,…,)表示含x1,x2,…,为自由出现的公式.用Δ表示量词(.
xn
xn
x2,…,)
在Δx1,-xi,xn
xi
或.)
.
xiA(xi1,xi+1,…,中,是约束出现的,其余的个体变项都
是自由出现的.而在ΔA(x2,…,)中,无自由出现的个体变项
.
可将例3.6(1) y,这表明(1)中公式含自由出现的个体变项y,
x1Δx2…Δxnx1,xn
中公式简记为A(z), z.
而.yA(z) y,中已无自由出现的个体变项了,
y,中只含
z
为自由出现的公式,.z.yA(z)
此时的公式
为
一阶逻辑
第
y)→G(z)) 24)
.z.y.x(F(x,x,(3.
3
定义3.设
A
是任意的公式,若
A
中不含自由出现的个体变项,则称
A
为封闭的公
6
章
式,简称闭式
.
1)3.以及式(24) 而式(22) 3.则不是闭式.
易知式(3.~式(21) 3.都是闭式,3.和式(23) 要
想使含r(个自由出现个体变项的公式变成闭式至少要加上
r
个量词,将式(22)加了
73
r≥1) 3.
两个量词就变成了闭式(3..类似地,也可以用加量词的方法将式(23)变成闭式
.
按定义3.24)
一般说来没有确定的含义,3.
个体变项,
4定义的合式公式, 一旦将其中的变项(
项的变项,谓词变项等)用指定的常项代替,所得公式可能具备一定的含义,有时可以变成命
题了
.
例3.7
将下面公式
.x(F(x)→G(x)) (3.
中的变项指定成常项,使其成为命题
.
25)
解指定个体变项的变化范围,并指定谓词F,
G
的含义,下面给出两种指定法
.
(a)令个体域D1 为全总个体域,F(x)为
x
是人,G(x)为
x
是黄种人,则式(3.表达
25)
的命题为“所有的人都是黄种人”,这是假命题
.
25)
(b)令个体域D2 为实数集合R,F(x)为
x
是自然数,G(x)为
x
是整数,则式(3.表
达的命题为“自然数都是整数”,这是真命题
.
还可以给出其他各种不同指定,使式(25)
3.表达各种不同形式的命题
.
上面指定公式中的个体域以及个体变项、谓词变项等的具体含义称作对它的解释.一
般地,给定一阶语言的解释, 定义3.
在这个解释下解释公式
.
1给出了一般性的一阶语言的
定义.定义中的个体常项、函数符号和谓词符号称作非逻辑符号,其余的符号称作逻辑符号
.
就一个具体的应用而言,一阶语言L只涉及某些非逻辑符号.记它所使用的非逻辑符号集
为L,称L是非逻辑符号集
L
生成的一阶语言.不同的非逻辑符号集生成各种不同的具体
的一阶语言,但它们使用相同的逻辑符号和相同的生成规则.解释是对这种具体的一阶语
言而言的,定义如下.
定义3.设
L
是非逻辑符号集,L是由
L
生成的一阶语言,L的解释
I
由下面4部分
7
组成:
(a)非空的个体域D.
a∈D,
(b)对每一个个体常项a∈L,有一个
a
称作
a
的解释
.
(c)对每一个
n
元函数符号f,有一个
..
D
上的
..
n
元函数
f
-,
f
-称作
f
的解释
.
..
..
(d)对每一个
n
元谓词符号F,有一个
D
上的
n
元谓词F,
F
称作
F
的解释
.
设
A
是L中的一个公式,把
A
中的每一个个体常项、函数符号和谓词符号替换成它的
......
解释,得到公式A,在解释
I
下,称
A
是
A
的解释,或称在解释
I
下,
A
被解释成A.
给定解释
I
如下:
例38
(a)个体域D=N(
N
为自然数集合,即N={0,1,2,…})
.
b)
..
(a=0.
(-(y)x+y,..x,=y.
c)fx,=g(y)x
·
(F(y) y.
d)..x,为x=
74
离散数学(第4版)
在
I
下,下列哪些公式为真? 哪些为假? 哪些的真值还不能确定
?
(1)F(x,g(y))
.
f(y),x,
(a),y)
,
2)F(f(x,y)→F(g(x,z)
.
(3)..F(x,g(z))
g(y),y,
.
(y)
,
4).xF(g(x,z)
.
(5).xF(x,x)x,.
g(a),→F(y)
(a)
,
6).xF(g(x,x)
.
(7).x.y(f(a),→F(y,x))
F(x,y)f(a),
.
(8).x.y.zF(f(y),
.
x,z)
(9).xF(x,g(x)
)
f(x),x,
.
解(1)在
I
下,公式被解释成“ x+y=
x
· y”,这不是命题
.
(2)公式被解释成“(x+0=y)→(
x
· y=z)这也不是命题.,(”)
(3)公式被解释成“
x
· y≠y·
z
”,同样不是命题
.
(4)公式被解释成“.x(
x
· y=z)不是命题.,(”)
(5)公式被解释成“.x(
x
·0=x)→(x=y)由于蕴涵式的前件为假,所以被解释成
的公式为真
. ,(”)
(6)公式被解释成“.x(
x
·0=x)”,为假命题
.
x+0=y)y+0=
(7)公式被解释成“.x.y((→(x))为真命题.,(”)
(8)公式被解释成“.x.y.z(x+y=z)”,这也为真命题
.
(9)公式被解释成“.x(x+x=
x
· x)为真命题
.
从例3.闭式在给定的解释中都变成了命题( 6)~公式(9)), 其实闭,(”)
8可以看出, 见公式
(
式在任何解释下都变成命题
.
3.封闭的公式在任何解释下都变成命题.
1
本定理的证明略
.
在给定解释
I
后,如果进一步给公式中的每一个自由出现的个体变项指定个体域中的
一个元素,则非封闭的公式也变为命题了.给公式中的每一个自由出现的个体变项指定个
体域中的一个元素称作在解释
例3.8(
I
下的赋值.给定解释及赋值,任何公式都变为命题
.
续) 给定解释
I
下的赋值σ:σ(x)1,y)2,z)3.求(~(5)中公式
=σ(=σ(=1)
的真值
.
解在解释
I
和赋值
σ
下,其结果分别如下:
(1)1+2=1×2,这是假命题
.
(2)(1+0=2)→(1×2=3), 这是真命题
.
(3)1×2≠2×3,这是真命题
.
(4).x(2x=3), 这是假命题
.
(5).x(
x
·0=x)→(1=2), 这是真命题
.
这里需注意,在(4)中
x
是约束出现,对
x
不使用赋值.在(5)的前件中
x
是约束出现,
也不对其使用赋值.而在后件中,
x
是自由出现,应对其使用赋值,把它换成1.对于(6)~
(9), 由于都是闭式,所以与赋值无关
.
在一阶逻辑中同在命题逻辑中一样,有的公式在任何解释和任何赋值下均为真,有些公
一阶逻辑
式在任何解释和任何赋值下均为假,而又有些公式既存在成真的解释和赋值,又存在成假的
解释和赋值.下面给出公式类型的定义
.
定义3.设
A
为一公式, 则称
A
为永真式
8
若
A
在任何解释和任何赋值下均为真,
(或称逻辑有效式).若
A
在任何解释和任何赋值下均为假,则称
A
为矛盾式(或称永假式)
.
若至少存在一个解释和一个赋值使
A
为真,则称
A
是可满足式
.
从定义可知,永真式一定是可满足式, 在例3.公式
但可满足式不一定是永真式
.
8中,
(2),(3),(5),(7),(8),(9)都是可满足的,因为它们已存在使其成真的解释和赋值,而公式
(1),(4),(6)绝不是永真式,因为它已存在使其成假的解释和赋值
.
在一阶逻辑中,由于公式的复杂性和解释的多样性,公式的可满足性是不可判定的,即
不存在一个算法能在有限步内判断任意一个公式是否是可满足的,这与命题逻辑的情况是
完全不同的.下面考虑某些特殊情况
.
定义3.9
设A0 是含命题变项p1,p2,…,pn
的命题公式,A1,A2,…,An
是
n
个谓词
公式,用Ai
处处代替A0 中的pi(1≤i≤n), 所得公式
A
称为A0 的代换实例
.
例如,F(x)→
G
(x),.xF
(x)→.yG
(y)是
p
→
q
的代换实例,而.
x
(
F
(x)→
G(x)) 不是p→
q
的代换实例
.
3.2
重言式的代换实例都是永真式,矛盾式的代换实例都是矛盾式
.
证明略
.
例3.9
判断下列公式中哪些是永真式,哪些是矛盾式
.
(1).x(F(x)→G(x))
.
(2).x(F(x)∧G(x))
.
x)x,
(3).xF(→(.x.yG(y)→.xF(x))
.
(y))∧.yG(y)
4)..(.xF(x)→.yG(
.
(5).xF(y)
x,
.
解为方便起见,用A,B,C,D,
E
分别记(1),(2),(3),(4),(5)中的公式
.
(1)取解释I1:个体域为实数集合R,F(:..x):在I1 下A
..x)
x
是整数,G(
x
是有理数
.
为真,因而
A
不是矛盾式
.
..x):..x)
x
能表示
取解释I2:个体域仍为R,F(
x
是无理数,G(:
成分数.在I2 下
A
为假,所以
A
不是永真式,即
A
是非永真式的可满足式
.
(2)请读者给出
B
的一个成真解释,一个成假解释,从而说明
B
不是永真式,也不是矛
(
盾式,3B
)
是非永真式的可满足式
易知
C
是命题公式p→
.
(q→p)的代换实例,而该命题公式是重言式,所以
C
是永
真式
.
(p→q)∧
q
的代换实例, 所以
D
是矛盾式.
4)
D
是命题公式..(而该命题公式是矛盾式,
(5)取解释I:个体域为自然数集N,F(y):x≥y.
y)=0.
..x,取赋值σ1(在解释
I
和赋
值σ1 下,
E
为.x(x≥0), 这是真命题.在解释
I
下取赋值σ2(y)=1,在解释
I
和赋值σ2
下,
E
为.x(x≥1), 这是假命题.故
E
是非永真式的可满足式
.
第
章
75
76
离散数学(第4版)
3.一阶逻辑等值演算
2
3.1
一阶逻辑等值式与置换规则
2.
定义3.10
设A,
B
是一阶逻辑中任意两个公式,若A.
B
是永真式,则称
A
与
B
是
等值的.记作A.B,称A.
B
是等值式
.
由定义3.10 可知,判断公式
A
与
B
是否等值,等价于判断公式
A
.
B
是否为永真式
.
同命题逻辑中的等值式一样,人们证明出了一些重要的等值式,由这些重要的等值式可以推
演出更多的等值式来,这就是一阶逻辑等值演算的内容
.
下面给出一阶逻辑中的一些基本而重要的等值式
.
第一组由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式,因而第2章
的24 个等值式模式给出的代换实例都是一阶逻辑的等值式.例如
:
.xF(x)......xF(x)
.x.y(F(y)→G(y)).F(y)→G(y)
)
x,x,.....x.y(x,x,
等都是双重否定律的代换实例.又如:
y)...F(x)∨G(
F(x)→G(y)
.x(F(y))→.zH (
x)→G(z)
x)→G(z)
等都是蕴涵等值式的代替实例
.
第二组在一阶逻辑中,证明了下面重要的等值式
.
1)消去量词等值式
a1,}
,
设个体域为有限集D={a2,…,
n
则
有
(1).xA(x).A(a2)∧…(a) a)
....x(F(y))∨.zH
(
a1)∧A(∧A(
n
(2).xA(x).A(a2)∨…∨A(
n
) (3.2)量词否定等值式
a1)∨A(a26)
设A(x)是任意的含自由出现个体变项
x
的公式,则
(1)...xA(x)..x..A(x) (27)(2)...xA(x)..x..A(x)3.
式(3.的直观解释是容易的.对于(1),“并不是所有的
x
都有性质A”与“存在
x
没有性质
27)
A”是一回事.对于(2),“不存在有性质
A
的
x
”与“所有
x
都没有性质A”是一回事
.
3)量词辖域收缩与扩张等值
式
设A(x)是任意的含自由出现个体变项
x
的公式,
B
中不含
x
的出现,
则
(1).x(A(x)∨B)..xA(x)∨
B
.x(A(x)∧B)..xA(x)∧
B
28).x(A(x)→B)..xA(x)→
B
(3.
.x(B→A(x)).B→.xA(x)
一阶逻辑
(2).x(A(x)∨B)..xA(x)∨
B
.x(A(x)∧B)..xA(x)∧
B
(3..x(A(x)→B)..xA(x)→
B
29)
.x(B→A(x)).B→.xA(x)
4)量词分配等值式
设A(x),B(x)是任意的含自由出现个体变项
x
的公式,则
(1).x(A(x)∧B(x))..xA(x)∧.xB(x) (3.(2).x(A(x)∨B(x))..xA(x)∨.xB(x) 30)
进行等值演算,除使用以上重要的等值式外,还要使用以下2条规则
.
(1)置换规则
.
设Φ(A)是含公式
A
的公式,Φ(B)是用公式
B
取代Φ(A)中的所有的
A
之后的公式,
若A.B,则Φ(A).Φ(B)
.
一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同,只是在这里A,
B
是一阶逻辑公式
.
(2)换名规则
.
设
A
为一公式,将
A
中某量词辖域中某约束变项的所有出现及相应的指导变元,改成
该量词辖域中未曾出现过的某个体变项符号,公式中其余部分不变,设所得公式为A'
,则
A'.A.
例如,.xF(y)..tF(y), 写成.yF(y).
x,t,但不能把
x
换成y, y,
以上给出的重要等值式及2个变换规则在一阶逻辑等值演算中均起重要作用,因而必
须记住它们并且会灵活地运用
.
如果公式中含有既约束出现又自由出现的个体变项,很容易引起混淆,给演算带来不
便.对此,可以用换名规则解决这个问题
.
将下面公式化成与之等值的公式,使其没有既是约束出现的又是自由出现
的个体变项
.
(1).xF(x,z)→.yG(x,z)
.
例3.10
y,y,
(z)
)
2).x(F(x,y)→.yG(x,y,
.
1) .xF(y,z)解(
F(tx,y,
,
z)→.yG(xy,y,
,
(换名规则)
..tz)→.yG(x,z)
t,z)→.wG(w,
x,
..tF(y,x,z)
只有
z
仅自由出现
.
(换名规则)
原公式中,
y
都是既约束出现又自由出现的个体变项, 而在最后得到
的公式中,x,y,t,
z,
w
中再无既是约束出现又是自由出现的个体变项了
.
(2) .x(x,y,
F(y)→.yG(x,z))
例3.11..x(x,x,z)) (换名规则)
F(y)→.tG(t,
证明
:
(1).x(x)∨B(.x)∨.xB(
.
A(x))/.xA(x)
(2).x(A(x)∧B(x))/.xA(x)
.
.x)∧.xB(
其中,A(x),B(x)为含
x
自由出现的公式
.
证明(1)只要证明.x(A(x)∨B(x))..xA(x)∨.xB(x)不是永真式
.
第
章
77
78
离散数学(第4版)
取解释
I
为:个体域为自然数集合N.
A
(x)解释成F(x):
x
是奇数,
B
(x)解释成
G(x):
x
是偶数.于是左端解释成.x(F(x)∨G(x)), 为真命题,而右端解释成.xF(x)∨
.xG(x), 为假命题,所以该公式存在成假解释,因而它不是永真式
.
对于(2)可以类似讨论
.
例3.11 说明,全称量词.对∨无分配律,存在量词.对∧无分配律.但当B(换成没
有
x
出现的
B
时,则有
.x(A(x)∨B)..xA(x)∨Bx)
.x(A(x)∧B)..xA(x)∧
B
这是式
例3.12(3.28)和式(3.中出现的两个等值式
.
29)
设个体域为D={b,将下面各公式的量词消去.
a,c}
,
(1).x(F(x)→G(x))
.
(2).x(F(x)∨.yG(y))
.
(3).x.yF(x,
.
y)
解(1) .x(F(x)→G(x)
)
.(a)a))∧(b)b))∧(c)c))
F(→G(F(→G(F(→G(
(2) .x(F(y))
x)∨.yG(
..xF(y)(公式(28))
x)∨.yG(3.
.(a)∧F(c))∨(a)∨G(c))
F(b)∧F(G(b)∨G(
如果不用公式(3.将量词.
x
的辖域缩小, 注意, y)
28) 演算过程较长
.
此时.yG(为与
x
无
关的公式B.
(3) .x.yF(x,
y)
F(a)∧F(b)∧F(c))
..x(x,x,x,
F(a)∧F(b)∧F(c))∨(b,b,
∧F(b,c))∨(c,c,c,
.(a,a,a,F(a)∧F(b)
F(a)∧F(b)∧F(c)
)
在演算中先消去存在量词也可以,得到结果是等值的
.
给定解释
I
如下
:
例3.13
(a)个体域D={2,3}
.
(b)
..
a=2.
(c)
f
-(x)为:
f
-(2)=3,
f
-(3)=2.
(G(y) G(2)2,G(2)G(3)0.x,为:..2,=
d)..=..=..1,..
..
L(3,=2,=3,=F(为:..2)0,3)1.
x,为:..2,G(3)3,=3,=L(y) L(2)
..1,........
3)L(3)L(2)0.x) F(=F(
=
在
I
下求下列各式的真值
.
(a)
)
1).x(F(x)∧G(x,
.
(2).x(F(f(x))∧G(x,f(x)))
.
(3).x.yL(y)
x,
.
(4).y.xL(y)
.
x,
解设以上各式分别为A,B,C,D.
1)
A
.F(G(2,F(G(3,
((..2)∧..2))∧(..3)∧..2))
.(0∧1)∧(1∧1).0
一阶逻辑
((2))∧..2,F(G(3)))
F(G(2)))∨(3))∧..3,
2)
B
...
f
-(
f
-(..
f
-(
f
-
(
(..3)∧..3))∨(..2)∧..2)
)
.F(G(2,F(G(3,
.(1∧1)∨(0∧1).
1
..2)∨....2)∨
..
(3)
C
.(L(2,L(2,3))∧(L(3,L(3,3))
.(1∨0)∧(0∨1).
1
(..y)∧..y)
)
4)
D
..y(L(2,L(3,
..2)∧....3)∧..
.(L(2,L(3,2))∨(L(2,L(3,3))
.(1∧0)∨(0∧1).0
由(3
例3.14),(4)的结果也说明量词的次序不能随意颠倒
.
证明下列各等值式
.
(1)...x(
M
(x)∧F(x))..x(
M
(x)→..F(x))
.
(2)...x(F(x)→G(x))..x(F(x)∧..G(x))
(3)...x.y(F(x)∧G(y)→
H
(x,(F(.) (x)∧G(y)∧..
H
(y)).
y))..x.yx,
(4)...x.y(x)∧G(x,F(y)→..L(y))
F(y)∧L(y))..x.y(x)∧G(x,
.
证明
(1) ...x(
M
(x)∧F(x))
M
(公式(27))
..x..(x)∧F(x)) (3.
..x(..
M
(x)∨..F(x)) (置换规则)
..x(
M
(x)→..F(x)) (置换规则)
由此说明例3.3)有两种等值的符号化形式.
4中(
(2) ...x(F(x)→G(x))
..x..(x)x)) (公式(27))
F(→G(3.
..x..(..F(x)∨G(x)) (置换规则)
..x(F(x)∧..G(x)) (置换规则)
由此说明例3.4中(4)有两种等值的符号化形式
.
x)∧G(→
H
(y))
y))∨
H
(y)))
(3) ...x.y(F(y)x,
..x..(.y(..(F(x)∧G(x,
F(y))∨
H
(y))
F(y))∧..
H
(y))
..x.y..(..(x)∧G(x,
类似可证明(4)
.
3) 例3.3) 3.与式(3.(
..x.y((x)∧G(x,
由(可知,5中(的符号化形式式(15) 19)是等值的.4)
的符号化形式式(3.与式(20)也是等值的.
16) 3.
3.2
一阶逻辑前束范式
2.
定义3.设
A
为一个一阶逻辑公式,若
A
具有如下形式:
11
Q1x1Q2x2…QkxkB
则称
A
为前束范式,其中Qi(1≤i≤k)为.或.,
B
为不含量词的公式
.
例如,.x.y(F(x)∧G(→
H
(y))
.x.y.z(F(y)∧
H
(→L(y,
等公式都是前束范式,而
x)∧
yG)
(
x,
z)x,z))
第
章
79
80
离散数学(第4版)
x)→.y(y)∧
H
(y)))
.x(F(G(x,
.x(F(G(x,
x)∧.y(y)→
H
(y))
)
等都不是前束范式
.
3.3(前束范式存在定理) 一阶逻辑中的任何公式都存在与之等值的前束范式
.
本定理的证明略去
.
称与公式等值的前束范式为该公式的前束范式.本定理说明,任何公式的前束范式
都
是存在的,但一般说来,并不唯一
.
利用公式(3.至公式(30) 置换规则、就可以求出公
27) 3.以及2条变换规则( 换名规则
)
式的前束范式
.
例3.15
求下面公式的前束范式
.
(1).xF(x)∧...xG(x)
.
(2).xF(x)∨...xG(x)
.
解
(1) .xF(x)∧...xG(x)
..xF(x)∧...yG(y)(换名规则)
..xF(y) (3.第二式)
x)∧.y..G(公式(27)
F(y)) 28)
..x(x)∧.y..G((公式(3.第二式)
.x.y(F(y)) (公式(3.第二式)
或者
.x)∧..G(28)
.xF(x)∧...xG(x)
..xF(x) 公式(27)
x)∧.x..G((3.第二式)
..x(F(x)∧..G(x)) (公式(30)第一式)
3.
由此可知,(1)中公式的前束范式是不唯一的.其实,
y)
)
也是它的前束范式(为什么?)
.
.y.x(F(x)∧..G(
(2) .xF(x)∨...xG(x)
..xF(
x)∨.y..G(
x)(公式(3.第二式)x)∨.x..G(
(换名规则
27)
)
..xFF(
(
yy)
)) (公式(28)
..x(x)∨.y..G(3.第一式)
F(y)) 28)
由本例可以看出以下3点:
..x.y(x)∨..G((公式(3.第一式)
①由于.对∧适合分配律,所以(1)才有只带一个量词的前束范式.而.对∨不适合分
配律,因而(2)不可能有带一个量词的前束范式
.
②在使用公式(28) 3.时一定注意条件, y)
3.和公式(29) 在演算中都用到了.y..G(是
不含
x
的公式
B
的条件
.
例3.16
③公式的前束范式是不唯一的
.
求下列各式的前束范式,请读者填出每一步的根据
.
(1).xF(x)∧.xG(x)
.
(2).xF(x)→.xG(x)
.
一阶逻辑
(3).xF(x)→.xG(x)
.
(4).xF(x)→.yG(
.
y)
解
(1) .xF(x)∧.xG(x)
.yF(G(x)
.y)∧.x
..y.x(F(y)∧G(x))
(2) .xF(x)→.xG(x)
..yF(G(
y)→.xx)
..y.x(F(y)→G(x))
(3) .xF(x)→.xG(x)
..yF(G(
y)→.xx)
..y.x(F(y)→G(x))
(y)
4) .xF(x)→.yG(
..x.y(F(x)→G(y)
)
请读者再写出以上各式的不同形式的前束范式
.
例3.17
求下列各公式的前束范式
.
(x,y)
1).xF(y)→.yG(x,
.
(2)(.x1F(x1,x2)→.x2G(x2))→.x1H
(x2,
.
x1,x3)
解解本题时一定注意,哪些个体变项是约束出现,哪些是自由出现,特别要注意哪些
既是约束出现又是自由出现的个体变项.在求前束范式时,要保证它们约束和自由出现的
身份与次数都不能改变,并且不能混淆
.
1) .xF(y)→.yG(y)
(
..ttx,
,
xx,
,
(换名规则
)
F(y)→.wG(w)
..t.w(t,→G(w)) 公式(28),(29))
F(y)x,(3.3.
x1,x2))→.x1H
(x2,
(2) (.x1F(x2)→.x2G(x1,x3)
(.x4F(x4,x1,x3)
.x2)→.x5G(x5))→.x1(x2,
x4,→G(x2,
.x4.x5.x1((x5))x3))
..x4.x5(F(x2)x5))→.x1H
(x1,x3)
.F(x4,x2)→G(→
H
(x1,x2,
习题
3.设个体域为实数集R,F(x):x>5,求下列0元谓词的真值.
1
(1)F(5) (2)F(2) (3)F(-2) (4)F(6)
(5)F(72)
x|
(6)F(7.9)
令F(
x
含字母c求下列各0元谓词的真值.
3.2
设个体域D={
x
为英语单词}, x):
.
(1)F(about) (2)F(cal) (3)F(eror) (4)F(erect)
3.将下列命题用0元谓词符号化.
3
(1)王小山来自山东省或河北省
.
(2)除非李联不怕吃苦,否则她不会取得这样好的成绩
.
第
章
81
离散数学(第4版)
82
(3)2不是有理数
.
(4)3大于2仅当3大于4.
y):
3.4
设个体域为D={x|
x
是人},L(x,
x
喜欢y.将下列命题符号化
.
(1)所有的人都喜欢赵小宝
.
(2)所有的人都喜欢某些人
.
(3)没有人喜欢所有的人
.
(4)每个人都喜欢自己
.
4中4个命题符号化.
3.5
设个体域为全总个体域,又令
M
(x):
x
是人.将题3.
3.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的
6
真值
.
(1)凡整数都能被2整除
.
(2)有的整数能被2整除
.
其中,(a)个体域为整数集合,(b)个体域为实数集合
.
3.设个体域为整数集Z,L(y):x-求下列各式的真值.
7
x,x+y=y.
(1)L(1,1)
.
(2)L(2,0)
.
(1,(L(x,2)
3).yL(y)
.
4).x.
(5).x.yL(x,
.
(x,
.
y)6).x.yL(y)
(7).y.xx,
.
(8).x.yL(y)
L(y)x,
3.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制),(b)条件时命题的为(a(.)
8
真值
.
(1)对于任意的x,均有x2-2=(x+2)(x-2)
.
(2)存在x,使得x+5=9.
其中,(a)个体域为自然数集合,(b)个体域为实数集合
.
3.设个体域为整数集Z,确定下列各公式的真值.
9
(1).x(x2>0)
.
(3).x(x2≥x)
.
(5).x.y(x<y2)
.
(7).x.y(x2+y2=6)
.
3.在一阶逻辑中将下列命题符号化.
10
(1)没有不吃饭的人
.
(2)在北京卖菜的人不全是东北人
.
(3)自然数全是整数
.
(4)有的人天天锻炼身体
.
3.在一阶逻辑中将下列命题符号化.
11
(1)火车都比汽车快
.
(2)有的火车比有的汽车快
.
(3)不存在比所有火车都快的汽车
.
(2).x(x2=0)
.
(4).x.y(x2<y)
.
(6).x.y(x+y=0)
.
(z=(x+y)/2)
8).x.y.z(
.
(4)说凡是汽车就比火车慢是不对的
.
3.将下列命题符号化,个体域为实数集合R,并指出各命题的真值.
12
(1)对所有的x,都存在y,使得
x
· y=0.
(2)存在着x,对所有的
y
都有
x
· y=0.
(3)对所有x,都存在着y,使得y=x+1.
(4)对所有的
x
和y,都有
x
· y=y· x.
3.将下列各公式翻译成自然语言,个体域为整数集Z,并判断各命题的真假
.
(1).x.y.z(x-y=z)
.
(2).x.y(
x
· y=1)
.
(3).x.y.z(x+y=z)
.
一阶逻辑
第
章
83
3.指出下列公式中的指导变元, 各个体变项的自由出现和约束出现.
14
(1).x(x)x,
.
量词的辖域
,
F(→G(y)
)
(2).xF(y)→.yG(y)
.
x,x,
(3).x.y(x,y,x,z)
F(y)∧G(z))∨.xH
(y,
.
3.给定解释
I
如下:
15
(a)个体域DI
为实数集R.
b)
..
(a=0.
(c)
f
-(y)x-x,
x,=y,y∈DI.
(d)..:y,..y)
:
说明下列公式在
I
下的含义,并指出各公式的真值
.
(1).x.y(x,x,
.
y)G(x<y,y∈DI.
F(x,x=x,x,
G(y)→..F(y)
)
(2).x.y(f(y),→G(y)
)
F(x,a)x,
.
(3).x.y(x,f(y),
.
G(y)→..F(x,a)
)
(4).x.y(f(y),→F(y)
)
G(x,a)x,
.
3.给定解释
I
如下:
16
(a)个体域D=N(
N
为自然数集)
.
(b)..2.
a=
(c)
D
上函数
f
-(y)x+y,g(y)=
x
· y.
x,=..x,
(d)
D
上谓词F(y):x=y.
..x,
及赋值σ:σ(=0,y)=1,σ(=2.
x)σ(z)
说明下列各式在
I
及
σ
下的含义,并讨论其真值
.
(a)
,
1).xF(g(x,y)
.
(a),x)
)
2).x(F(x,f(a),.
f(y)→.yF(y,
(y)
,
3).x.y.zF(f(x,z)
.
(4).xF(x,g(z))
f(y),x,
.
3.判断下列各式的类型.
17
()F(x,→(x,→F(y))
y)G(y)x,
.
().x(F(x)→F(x))→.y(G(y)∧..G(y))
.
().x.yF(x,x,
.
y)→.y.xF(y)
().x.yF(x,x,
.
y)→.y.xF(y)
().x.y(F(y)y,
.
x,→F(x))
离散数学(第4版)
84
(6)..(.xF(y))∧.yG(.
x)→.yG(y)
(7).xF(x,
.
y)
(8).xF(x,.yF(x,
.
y)→y)
3.18
(1)给出一个非闭式的永真式
.
(2)给出一个非闭式的永假式
.
(3)给出一个非闭式的可满足式,但不是永真式
.
3.证明下面公式既不是永真式也不是矛盾式.
19
F(y)∧
H
(y))
)
(2).x.y(F(x)∧G(y)→
H
(x,y))
.
(1).x(x)→.y(G(x,
.
3.将下列各式的否定号内移,使得否定号只能出现在谓词前.
20
(1)...x.yL(y)
x,
.
(2)...x.yL(x,
.
y)
(3)...x(F(x)∧.y..L(y))
.
x,
(4)...x(.yL(y)∨.yH
(y))
.
x,x,
3.将下列公式化成与之等值的公式,使其没有既是约束出现的,又是自由出现的个体
21
变项
.
(1).xF(x,x,z)
.
y)∧.yG(y,
(2).x(x,y)
)
3.证明:
F(y)∧.yG(x,
.
22
(1).x(A(→B(x))/.x(A(x)∧B(x))
x).
.
(2).x(A(x)∧B(x))/.x(A(x)→B(x)
)
.
.
其中,A(x),B(x)为含
x
自由出现的公式
.
3.23
设个体域D={b},
a,消去下列各公式的量词
.
(1).x.y(F(x)∧G(y))
.
(y)
)
2).x.y(F(x)∧G(x,
.
(3).xF(x)∧.xG(x)
.
(4).x(x,y))
.
F(y)∨.yG(
设个体域D={c}, 消去下列各公式中的量词.
b,
(1).xF(y)
3.24
a,
x)→.yG(
.
(2).x(F(y)→.yG(y)
)
x,
.
3.设个体域D={1,2}, 给出两种不同的解释I1 和I2,使得下面公式在I1 下都是真命
25
题,而在I2 下都是假命题
.
(1).x(F(x)→G(x))
.
(2).x(F(x)∧G(x))
.
3.给定公式A=.xF(xF(x).26
(1)在解释I1 中,
x)→.
a},
个体域D1={证明公式
A
在I1 下的真值为1.
(2)在解释I2 中, a1,an
n≥2,
吗? 为什么?
个体域D2={a2,…,},
A
在I2 下的真值还一定是1
3.给定解释
I
如下:
27
(a)个体域D={3,4}
.
(b)
f
-(x)为
f
-(3)=4,
f
-(4)=3.
(F(y) F(3)F(4)0,3,=4,
=
c)..........
x,为3,=4,=F(4)F(3)1.
试求下列公式在
I
下的真值
.
(1).x.yF(y).
x,
(2).x.yF(y)
.
x,
(F(x,x),y))
)
3).x.y(y)→F(f(f(
.
3.在一阶逻辑中将下面命题符号化,要求用两种不同的等值形式.
28
(1)没有小于负数的正数
.
(2)相等的两个角未必都是对顶角
.
3.求下列各式的前束范式.
29
(1).xF(x,.
x)→.yG(y)
(2).x(x,x,z)
)
F(y)→.yG(y,
.
3.求下列各式的前束范式.
30
x)∧G(→L(y)
(2).x1(F(x1)→G(x1,x2))→(.x2H
(x2)→.x3L(x2,x3))
.
(3).x1F(x2)
H
(x1,
.
(1)F(x)x,
.
x1,→(x1)→...x2G(x2))
3.31
将下列命题符号化,要求符号化的公式为前束范式
.
(1)有的汽车比有的火车跑得快
.
(2)有的火车比所有的汽车跑得快
.
(3)说所有的火车比所有汽车都跑得快是不对的
.
(4)说有的飞机比有的汽车慢是不对的
.
3.求下列各公式的前束范式.
32
G(x,
(2)..(.xF(x)∨.xG(x))
.
(1).xF(x)∨.xx)∨L(y)
.
一阶逻辑
第
章
85