第3章
谓词逻辑
【本章知识结构图】
92
离散数学及应用学习指导与习题解析
【由命题逻辑到谓词逻辑】
3.谓词与量词
1
3.1.1
内容提要
定义3.个体词是一个命题里表示思维对象的词,表示独立存在的具体或抽象的客
1
体。简单地讲,个体词表示各种事物,相当于汉语中的名词。具体的、确定的个体词称为
个体常项,一般用a、b、
c
表示;抽象的、不确定的个体词称为个体变项,一般用x、y、
z
表
示。个体变项的取值范围称为个体域或论域,宇宙间一切事物组成的个体域称为全总个
体域。
定义3.在命题中,表示个体词性质或相互关系的词称作谓词。
2
零元谓词不包含个体变项的谓词。
一元(目)谓词只有一个个体词的谓词。通常表示该个体词的性质或属性。
关系
n
。
元(目)谓词有
n
个个体的谓词P(x1,x2,…,xn
)。通常表示这几个个体词间的
用来表示个体数量的词是量词,给谓词加上量词称作谓词的量化。
定义3.符号.称作全称量词, 所有的
x
”任意
x
” 一切
x
”含义相当于
3
读作““ 或“,
自然语言中的“任意的”“所有的”“一切的”“每一个”“凡”等。(.x)P(x)意指对论域
D
中的所有个体都具有性质P。命题(.x)P(x)当且仅当对论域中的所有
x
来说,P(x)
均为真时方为真,此时称P(x)被全称量化。
定义3.符号.称作存在量词,读作“存在x”,含义相当于自然语言中的“某个”存(“) 在”“有的”“至少有一个”“有些”等。(.x)P(x)意指论域
D
中至少有一个个体具有性质
P,此时称P(x)被存在量化。
4
第
3
章 谓词逻辑
93
3.1.2
主教材习题参考解答
3.将下列命题用零元谓词表示。
1
(a)天安门位于北京。
(b)小李不是教师,而是运动员。
(c)苗苗非常聪明和美丽。
(d)π和e都是无理数。
(e)俞伯牙和钟子期是好朋友
。
(
f)
α
属于集合
A
或者集合B。
(g)乐乐既熟悉C++语言,又熟悉Java语言。
(h)鱼我所欲也,熊掌亦我所欲也
。
(则4大于2
。
i)若3大于2且4大于3,
解
:
(a)令谓词P(x,表示“。则P(天安门, 表示“。
y)
x
位于y” 北京) 天安门位于北京”
(b)令谓词P(x)表示“
x
是教师”,Q(x)表示“
x
是运动员”,则~P(小李)∧Q(小
李)表示“小李不是教师,而是运动员”。
(c)令谓词P(x)表示“
x
非常聪明”,Q(x)表示“
x
非常美丽”,则P(苗苗)∧Q(苗
苗)表示“苗苗非常聪明和美丽”。
(d)令谓词P(x)表示“
x
是无理数”,则P(π)∧P(e)表示“π和e都是无理数”。
(e)令谓词P(y)
x
和
y
是好朋友”则P( 钟子期) 俞伯牙和钟
子期是好朋友”。
x,表示“, 俞伯牙, 表示“
(f)令谓词P(x,表示“, α,α,表示“
或者集合B”。
y)
x
属于集合y”则P(A)∨P(B)
α
属于集合
A
(g)令谓词P(x,y)表示“
x
熟悉
y
语言”。则P(乐乐,C++)∧P(乐乐,Java)表示
“乐乐既熟悉C++语言,又熟悉Java语言”。
(h)令谓词P(x)表示“
x
是我所欲”,则P(鱼)∧P(熊掌)表示“鱼我所欲也,熊掌亦
我所欲也”。
(x,表示“ , 3,4,.P(2) 若3大于2
i)令谓词P(y)
x
大于y”则P(2)∧P(3)4,表示“
且4大于3,则4大于2”。
3.令论域为正整数集合, x)
x
是奇数”Eex)
x
是偶
2
谓词Odd(表示“ ,vn(表示“
数”,Prime(x)表示“
x
是素数”,Equal(x,y)表示“ x=y”,Greater(x,y)表示“ x>y”。
将以下各式译为汉语,并判断其真值。
(a)Prime(6)
。
(b)(.x)~Odd(x)
。
(c)(.x)rae5,)
。
Getr(
ex
tr(x)∧Piy))。
(d)(.x)(.y)(Graey,rme(
(e)(.x)(.y)(ul(y+2)∧Pix)∧Pime())
。
Eqax,rme(ry
(Eqaz,x)∧Odd(vn())。
f)(.x)(.y)(.z)((ul(x+y)∧Odd(y)).Eez
94
离散数学及应用学习指导与习题解析
解:
(a)表示“6是素数”,真值为“假”。
(b)表示“所有正整数都不是奇数”,真值为“假”。
(c)表示“有小于5的正整数”,真值为“真”。
(d)表示“对于任意正整数,都存在大于它的素数”,真值为“真”。
(e)表示“存在相差2的一对素数”,真值为“真”。
①
(任意两个奇正整数的和是偶正整数”真值为“真”
。
f)表示“,
3.谓词公式及分类
2
3.2.1
内容提要
(
定义3.谓词逻辑中的谓词公式递归地定义为:
5
公式。
1)个体常项、个体变项、个体词的函数和原子谓词公式(不含联结词的谓词)是谓词
(2)如果
A
是谓词公式,则~
A
也是谓词公式。
(3)如果
A
和
B
是谓词公式,则由逻辑联结词联结
A
和
B
构成的符号串也是谓词
公式,如(A∧B)、(A∨B)、(A.B)、(A.B)等。
(4)若
A
是谓词公式,且
A
中无.
x
及.
x
出现,则(.x)A(x)、(.x)A(x)也是
谓词公式。
(5)只有有限次地应用(1)~(4)构成的符号串才是谓词公式
。
在不引起混淆的情况下,谓词公式也称为合式公式,简称公式
。
(
定义3.谓词公式的一个解释由下面4部分组成
:
6
1)非空的论域D。
(2)
D
中一部分特定元素的具体取值。
(3)
D
上一些特定的函数的具体含义。
(4)
D
上一些特定的谓词的具体含义。
定义3.设
A
为一个谓词公式,若
A
在任何解释下真值均为真,则称
A
为普遍有
效的公式或
7
逻辑有效式。若
A
在任何解释下真值均为假,则称
A
为不可满足式或矛盾
式;若至少存在一个解释使
A
为真,则称
A
为可满足式。
定理3.(丘奇图灵定理)谓词逻辑是不可判定的。即,对任一谓词公式而言,没有
一个可行的方法判定它是否是逻辑有效的。
1
定义3.设命题公式A0 含命题变项p1,p2,…,用
n
个谓词公式A1,A2,…,
An
分别处处代换p1,p2,…,pn
,所得公式
A
称为A0 的代换实例。
定理3.2
命题公式中的重言式的代换实例都是逻辑有效式,在谓词公式中可仍称为
重言式;命题公式中的矛盾式的代换实例都是矛盾式。
8
pn
,
① 希尔伯特在1900 年国际数学家大会的报告中的第8个问题为“孪生质数猜想”:存在无穷多个素数p,使得
p+2 是素数。该问题目前尚未得到证明。
95
第
3
章 谓词逻辑
定义3.9
设
A
为谓词公式,
B
为
A
中的一个连续的符号串,且
B
为谓词公式,则称
B
为
A
的子公式。
定义3.设
A
为谓词公式,(.x)或(.x)为公式
A
的子公式,此时紧
10
P(x) P(x)
跟在.、.之后的
x
称为量词的指导变项或作用变项,P(x)称为相应量词的作用域或辖
域,即量词的约束范围。在辖域中
x
的一切出现均称为约束出现,受指导变项的约束。
所有约束出现的变项称为约束变项;在
A
中除了约束变项之外的变项均称为自由变项,
不受指导变项的约束。
3.2.2
主教材习题参考解答
3.3
给定解释
I
为:论域D=
Z,x,=x+y, x,表示x=a=2。
求下列各公式在解释
I
下的真值。
f(y)谓词F(y) y,
(a)(.x)f(x),)。
F(x,
a
(b)(.x)f(x,x)
。
F(a)
,
(c)(.x)(.y)(a),a),))
。
F(f(x,y).F(f(y,
x
(d)(.x)(.y)(.z)f(y),)
。
F(x,
z
(e)(.x)(.y)(.z)z),)
。
y,
(f)(.x)(.y)F(xF,
(f(
x)。
x
f(y)
,
(g)(.x)(.y)F(x,y)
。
f(y)
,
(h)(.x)(.y)y),)
。
F(f(x,
(F(x,y)。(x)
i)(.x)(.y)f(y)
,
解:(a)、(f) i) 真”b)、(e)、(g) h) 假
”
d)、(和(的真值为“ ,(c)、(和(的真值为“。
3.讨论公式(.x)(.y)x,在下列解释下的真值。
4
P(y)
(a)D={ 谓词P(y)表示xy=0
。
所有实数}, x,
y)
(b)D={所有实数},谓词P(x,表示xy=1
。
(c)D={ 谓词P(y) y=
所有正实数}, x,表示x1。
解:在解释(a)下该公式的真值为“真”,在解释(b)和(c)下该公式的真值为“假”。
3.给出解释I, P(.Q(x)) P(x))具
5
使得在解释
I
下(.x)(x)和(.x)(x)∧Q(
有不同的真值。
解:例如,论域
D
={全体正整数},
P
(x)表示x<0,
Q
(x)表示x>0时,(.x)
(P(x).Q(x))的真值为“真”,而(.x)(P(x)∧Q(x))的真值为“假”。
3.指出下列公式的辖域、自由变项和约束变项。
6
(a)(.x)(P(x)∧Q(x))∧(.x)R(x)
。
(b)(.x)(.y)(P(x).R(x,))
。
y
(c)(.x)(P(x)∧(.y)(D(x,)))
。
y).L(
y
(d)(.x)(x)y))
H
(x,
z
F(.G(.(.y)(x)∧L(y,))
。
(e)(.x)x,z)∨((.u)x,.(.w)y,
w
P(y,Q(u)Q())。
解:
(a)(.x)(P(x)∧Q(x))中,(P(x)∧Q(x))是(.x)的辖域,其中
x
是约束变项;
96
离散数学及应用学习指导与习题解析
(.x)R(x)中,R(x)是(.x)的辖域,其中
x
是约束变项。
(b)(.x)(.y)(P(x).R(x,y)) 中,(.y)(P(x).R(x,y)) 是(.x)的辖域,
(y))
P(x).R(x,是(.y)的辖域,其中
x
和
y
是约束变项。
(c)(.x)(x)∧(.y)(y)x,中,(x)∧(.y)(y)x,是
P(D(.L(y))) P(D(.L(y)))
(.x)的辖域,(y)x,是(.y) 其中
x
和
y
是约束变项。
D(.L(y)) 的辖域,
(d)(.x)(F(x).
G
(y)).(.y)(
H
(x)∧
L
(x,y,z)) 中,(
F
(x).
G
(y)) 是
(.x)的辖域,
y
是自由变项;(x)∧L(y,是(.y)
其中
x
是约束变项,
H
(x,z)) 的辖域,
其中
y
是约束变项,
x
和
z
是自由变项。
(e)(.x)x,z)∨((.u)x,.(.w)y,中,x,z)是(.x)的
P(y,Q(u)Q(w)) P(y,
辖域,其中
x
是约束变项,Q(u) 的辖域,
y
和
z
是自由变项;x,是(.u) 其中
u
是约束变
项,
x
是自由变项;y,是(.w)的辖域,其中
w
是约束变项,
Q(w)
y
是自由变项。
3.自然语言形式化
3
3.3.1
内容提要
谓词逻辑中的自然语言形式化的基本方法如下:
(1)将问题分解成一些原子命题和逻辑联结符。
(2)分解出各个原子命题的个体词、谓词和量词。
(3)按照谓词公式的表示规则将自然语言的语句翻译为谓词公式。
常见规律
(a)“ 所有的
A
是B”“是
A
的都是B”“一切
A
都是B”应形式化为(.x)(A(x).
B(x))。
(b)“ 有的
A
是B”应形式化为(.x)(A(x)∧B(x))。
(c)“ 所有的
A
都不是B”“是
A
的都不是B”“一切
A
都不是B”应形式化为(.x)
(A(x).~B(x)) 或者~(.x)(A(x)∧B(x))。
(d)“ 有的
A
不是B”应形式化为(.x)(
A
(x)∧~B(x)) 或者~(.x)(
A
(x).
B(x))。
(e)“ 只有一个A”应形式化为(.x)(A(x)∧(.y)(A(y).Equal(x,y)))。
(若存在
A
则唯一” .(.y)(y))); 有
f)“ 应形式化为(.x)(A(x)A(y).Equal(x,
时也使用符号.! 表示量词“存在且唯一”。
y))。
(g)“ 所有的
A
和
B
都具有关系C”应形式化为(.x)(.y)(A(x)∧B(y).C(x,
(h)“ 任何一个
A
都存在一个
B
与之对应满足性质C”应形式化为(.x)(
A
(x).
(.y)(B(x,)))。
y)∧C(
y
3.3.2
主教材习题参考解答
3.7
令论域为正整数集合,谓词Odd(x)表示“
x
是奇数”,Even(x)表示“
x
是偶
97
第
3
章 谓词逻辑
数”,Prime(x)表示“
x
是素数”,Equal(x,y)表示“ x=y”,Greater(x,y)表示“ x>y”。
利用谓词公式翻译下列命题。
(a)有不是奇数的素数。
(b)存在奇数x、
y
和偶数
z
使得
x
与
y
的和大于
x
与
z
的和。
(c)对于任意的正整数x、y,存在正整数
z
使得x+z=y。
(d)存在大于10000 的偶数。
(e)存在介于2和6之间的正整数
。
(
f)只存在唯一的奇数1。
(g)没有最大的素数
。
解
:
(a)(.x)(~Odd(x)∧Prime(x)
)
(b)(.x)(.y)(.z)(x)∧Odd(vn(raex+y,
Odd(y)∧Eez)∧Getr(x+z))
(c)(.x)(.y)(.z)Equl(x+z,
ay)
(d)(.x)(Even(x)∧Greater(x,10000)
)
(e)(.x)(Greater(x,2)∧Greater(6,x)
)
(1)∧(.x)(1)
)
f)Odd(Odd(x).Equal(x,
(g)~(.x)(Pix)∧(.y)(rme(.(raex,ul(y))))
rme(Piy)Getr(y)∨Eqax,
3.将下列命题用谓词表示出来,使用全总个体域。
8
(a)人都生活在地球上。
(b)有的人长着金色头发。
(c)并不是所有的实数都能表示成分数。
(d)没有能表示成分数的无理数。
(e)任意的偶数
x
与
y
都有大于1的公因子
。
(它们没有大于1的公因子
。
f)存在奇数
x
与y,
(g)只有一个北京。
(h)任何金属都可以溶解在某种液体中
。
(
i)有一种液体可以溶解任何金属。
(j)尽管有些人是勤奋的,但并非所有人都勤奋。
解:
(a)(.x)(P(x).Q(x)), 其中P(x)表示“
x
是人”,Q(x)表示“
x
生活在地球上”。
(b)(.x)(P(x)∧Q(x)), 其中P(x)表示“
x
是人”,Q(x)表示“
x
长着金色头发”。
(c)~(.x)(P(x).Q(x)), 其中P(x)表示“
x
是实数”,Q(x)表示“
x
能表示成
分数”。
(d)~(.x)(P(x)∧Q(x)), 其中P(x)表示“
x
能表示成分数”,Q(x)表示“
x
是
无理数”。
P(y)x,其中P(表示“,x,表
(e)(.x)(.y)(x)∧P(.Q(y)), x)
x
是偶数”Q(y)
示“
x
与
y
有大于1的公因子”。
(P(y)∧~Q(y)), x)
x
是奇数”Q(y)
f)(.x)(.y)(x)∧P(x,其中P(表示“,x,
98
离散数学及应用学习指导与习题解析
表示“
x
与
y
有大于1的公因子”。
y).Q(y)(g)(.x)(P(P(y))), x)
x
是北京”Q(
表示“
x
与
y
相同”。
x)∧(.y)(x,其中P(表示“,x,
(h)(.x)(x)Q(y)∧R(x,其中P(x)表示“,y)表
P(.(.y)(y))),
x
是金属”Q(
示“,x,表示“。
y
是液体”R(y)
y
可以溶解x”
(i)(.y)(Q(P(.R(y))), x)
x
是金属”Q(y)表
y)∧(.x)(x)x,其中P(表示“,
示“,x,表示“。
y
是液体”R(y)
y
可以溶解
x
”
(j)(.x)(P(x)∧Q(x))∧~(.x)(
P
(x).
Q
(x)), 其中
P
(x)表示“
x
是人”,
Q(x)表示“
x
勤奋”。
3.谓词逻辑的等值演算
4
3.4.1
内容提要
定义3.设
A
和
B
是两个谓词公式, 则称
A
与
B
等值,
11
若A.
B
是逻辑有效式,
记作A≡
B 3
。
消去量词等值式) a1,am
} 则有
定理3.( 设论域D={a2,…,是有限集合
,
A(a1)∧A(
(a)(.x)x)≡A(a2)∧…∧A(am
)
。
(b)(.x)A(x)≡A(a2)∨…∨A()
。
a1)∨A(am
定理3.(量词否定等值式/德摩根律)设A(x)是含
x
自由出现的公式,则有
4
(a)~(.x)A(x)≡(.x)~A(x)。
(b)~(.x)A(x)≡(.x)~A()。
定理3.(量词辖域收缩与扩值式) x) 谓词公式
B
中不含
x 5
的出现,则有张等(x) 设A(是含
x
自由出现的公式,
(a)(.x)(A(x)∨B)≡(.x)A(x)∨B。
(b)(.x)(A(x)∨B)≡(.x)A(x)∨B。
(c)(.x)(A(x)∧B)≡(.x)A(x)∧B。
(d)(.x)(A(x)∧B)≡(.x)A(x)∧B。
定理3.(量词分配等值式) x) x) 则有
6
设A(和B(是含
x
自由出现的谓词公式,
(a)(.x)(A(x)∧B(x))≡(.x)A(x)∧(.x)B(x)。
(b)(.x)(A(x)∨B(x))≡(.x)A(x)∨(.x)B()。
请注意,.对∨不满足分配律,.对∧不满足分配律。(x) 定理3.7
设A(y)、
y
自由出现的谓词公式,则有
(a)(.x)(.y)
x,
x,
是含xA(y)。
A(y)≡(.y)(.x)x,
(b)(.x)(.y)y)≡(.y)(.x)A(y)
。
A(x,x,
请注意,对于不同量词,不能随意更换次序
。
定义3.在仅含有联结词~、∧、∨的谓词公式
A
中,将∨换成∧,将∧换成∨,将
全称量词.换成存在量词.,将存在量词.换成全称量词.,若包含F和T也相互取代,
12
99
第
3
章 谓词逻辑
所得谓词公式称为
A
的对偶式,记作A*。
定理3.(对偶原理)设
A
和
B
为两个仅含有联结词~、∧、∨的谓词公式,若A≡
B,则A*≡B*。
8
谓词逻辑的等值演算规则
定理3.(置换规则)设Φ(是含谓词公式
A
的公式,是用谓词公式
B
取代
9
A) Φ(B)
Φ(A)中的A(不一定是每一处)之后得到的谓词公式,若A≡B,则Φ(A)≡Φ(B)。
定理3.(代替规则)将谓词公式
A
中某个自由出现的个体变项的所有自由出现
10
改成
A
中未曾出现的某个个体变项符号,其余部分不变,记所得谓词公式为A'
,则
A≡A'。
定理3.(换名规则)将谓词公式
A
中某量词的指导变项及其在辖域内的所有约
11
束出现改成该量词辖域内未曾出现的某个个体变项符号,其余部分不变,记所得谓词公式
为A'
,则A≡A'。
3.4.2
主教材习题参考解答
3.判断下列公式的类型,若是逻辑有效式,则给出证明,否则举出反例。
9
(a)(.x)P(x).((.x)P(x)∨(.y)G())。
y
(b)(.x)P(x).((.x)(.y)x,.(.x)P(x))
。
H
(y)
(c)~((.x)A(x).(.x)B(x))∧(.x)B(x)
。
(d)(.x)(.y)x,.(.x)(.y)P(x,
P(y)y)
。
解
:
(a)是命题逻辑中重言式p.(p∨q)的代换实例,因此是逻辑有效式。
(b)是命题逻辑中重言式p.(的代换实例,因此是逻辑有效式。
q.p)
(c)是命题逻辑中矛盾式~(p.q)∧
q
的代换实例,因此不是逻辑有效式。
(d)不是逻辑有效式。例如,论域D={全体正整数},P(x,表示“ 时,命
y) x×y=y”
题(.x)(.y)P(y) 命题(.x)(.y)x,为真。此时蕴含式为假,
逻辑有效式。
x,为假, P(y) 因此不是
设论域为{c}, 试消去下列谓词公式中的量词。
b,
(a)(.x)P(x).(.x)Q(x)
。
(b)(.x)(P(
H
(yQ())
。
3.10
a,
x)∨(.y)
y
(c)(.y)(.x)x,)。
解:
(a)(.x).(.x)x)≡(a)∧P(c)).(a)∨Q(c))。
P(x)Q(P(b)∧P(Q(b)∨Q(
(b)(.x)(P(x)∨(.y)
Q
(y))≡(.x)
P
(x)∨(.y)
Q
(y)≡
P
(a)∨
P
(b)∨
P(c)∨(Q(b)∧Q())。
a)∧Q(
c
(c) (.y)(.x)x,
H
(a)∧(.x)x,
H
(c)
H
(y)≡(.x)x,
H
(b)∧(.x)x,
≡(
H
(a)∨
H
(a)∨
H
(a))∧(a,b,c,
a,b,c,
H
(b)∨
H
(b)∨
H
(b))∧
(
H
(c)∨
H
(c)∨
H
(c))。
a,b,c,
3.11
将下列公式化为与之等值的公式,使其没有既是约束出现又是自由出现的个
100
离散数学及应用学习指导与习题解析
体变项符号。
P(y)∨(.y)x,z(a)(.x)x,
y)∨(.yQ)
(
xy,
,
z
)。
(b)(.x)(P(x,Q(y,))。
(c)(.x)(.y)(x)x,.L(y)。
P(.R(y))x,
(d)((.x)x,Q(y))R()
。
P(.(.y)x,.(.x)(.y)x,
y)
y
解
:
(a)(.x)x,Q(y,P(y)∨(.v)x,
z
PP(
(xy,
)∨(.y)
Qx(
,
yz,
)≡(.u)u,
x,
Q(
Qv(
,
v)。
,(b)(.x)(y)∨(.y)x,z))≡(.x)(P(y)∨(.v)x,z))。
(c)(.x)(.y)(P(x).R(x,y)).L(x,y)≡(.u)(.v)(P(u).R(u,v)).
L(x,)。
P(x,.(.y)x,x,
y
(d) ((.x)y)Q(y)).(.x)(.y)R(y)
≡((.u)P(y)Q(v))R(
z
u,.(.v)x,.(.w)(.z)w,)。
3.设A(x)是含
x
自由出现的公式,谓词公式
B
中不含
x
的出现,证明下列等
12
值式
(
。
a)(.x)(A(x).B)≡(.x)A(x).B。
(b)(.x)(A(x).B)≡(.x)A(x).B。
(c)(.x)(B.A(x))≡B.(.x)A(x)。
(d)(.x)(B.A(x))≡B.(.x)A(x)。
解:
(a)(.x)(x)~x)∨B)≡(.x)x)∨B≡~(.x)x)∨
A(.B)≡(.x)(A(~A(A(
B≡(.x)A(.B。
x)
(b)(.x)(A(x).B)≡(.x)(~A(x)∨B)≡(.x)~A(x)∨B≡~(.x)A(x)
∨B≡(.x)A(x).B。
(c)(.x)(x))≡(.x)(B∨A(A()。
B.A(~x))≡~B∨(.x)x)≡B.(.x)A(
x
(d)(.x)(x))≡(.x)(B∨A(A(A()。
B.A(~x))≡~B∨(.x)x)≡B.(.x)
x
3.证明下列等值式。
13
(a)(.x)(.y)(A(x)∧B(y))≡(.x)A(x)∧(.x)B(x)。
(b)~(.x)(
M
(x)∧F(x))≡(.x)(
M
(x).~F())
。
(c)(.x)(.y)(P(x).Q(y))≡(.x)P(x).(.yy)
。)(x)
Q(
(d)((.x)P(x)∧(.x)
Q
(x)∧(.x)
R
(x))∨((.x)
P
(x)∧(.x)
Q
(x)∧
(.x)S(x))
≡(.x)(P(x)∧Q(x))∧(.x)(R(x)∨S(x))。
解:
(a)(.x)(.y)(A(x)∧
B
(y))≡(.x)(
A
(x)∧(.y)B(y))≡(.x)
A
(x)∧
(.x)B(x)。
(b)~(.x)(
M
(x)∧
F
(x))≡(.x)~(
M
(x)∧
F
(x))≡(.x)(~
M
(x)∨
~F(x))≡(.x)(
M
(x).~F(x))。
(c)(.x)(.y)(x)y))≡(.x)(.y)(P(y))≡(.x)P(
P(.Q(~x)∨Q(~x)∨
第
3
章 谓词逻辑
101
(.y)Q(y)
≡~(.x)Q(P(.(.y)y)。
P(x)∨(.y)y)≡(.x)x)Q(
(d)((.x)P(x)∧(.x)
Q
(x)∧(.x)
R
(x))∨((.x)
P
(x)∧(.x)
Q
(x)∧
(.x)S(x))
≡((.x)P(x)∧(.x)Q(x))∧((.x)R(x))∨(.x)S(x))
≡(.x)(P(x)∧Q(x))∧(.x)(R(x)∨S(x))。
3.前束范式
5
3.5.1
内容提要
定义3.设
A
为谓词公式,如果满足以下条件:
13
(1)所有量词都位于该公式的最左边。
(2)所有量词前都不含否定词。
(3)量词的辖域都延伸到整个公式的末端。
则称
A
为前束范式。
求前束范式的基本方法如下:
(1)消去谓词公式中的联结词.和.。
(2)将谓词公式中的否定词~右移。
(3)将谓词公式中的量词左移(使用量词分配等值式、量词辖域收缩与扩张等值式),
必要时将变项改名。
定理3.12
(前束范式存在定理)任一谓词公式都存在与之等值的前束范式,但其前
束范式并不唯一。
3.5.2
主教材习题参考解答
3.将下列公式化为等值的前束范式。
14
(a)(.x)F(x).(.x)G(x)
。
(b)(.x)F(x).(.x)G(x)
。
(c)(.x)(x)Q(x,))
。
P(.(.y)
y
(d)((.x)x,.(.y)y))
H
()
。
G(x,
解:
(a)(.x)F(x).(.x)G(x)≡~(.x)F(x)∨(.x)G(x)≡(.x)~F(x)∨
(.x)G(x)≡(.x)(~F(x)∨G(x))。
(b)(.x)F(x).(.x)G(x)≡~(.x)F(x)∨(.x)G(x)≡(.x)~F(x)∨
(.x)G(~x)∨(.y)y)≡(.x)(.y)(~x)∨G())。
F(y).(.x)
y
x)≡(.x)F(G(F(
y
(c)(.x)(P(x).(.y)Q(x,y))≡(.x)(~
P
(x)∨(.y)
Q
(x,y))≡(.x)
(.y)(~P(x,))。
x)∨Q(
y
102
离散数学及应用学习指导与习题解析
(d)((.x)x,.(.y)y))
H
(y)
F(y)G(.(.x)x,
≡~(~(.x)x,G(y))∨(.x)x,
F(y)∨(.y)
H
(y)
≡((.x)F(y)∧(.z)G(
H
(y)
x,~z))∨(.u)u,
≡(.x)(.z)(.u)((z))∨
H
())
。
F(x,u,
y)∧~G(
y
3.谓词逻辑的推理
6
3.6.1
内容提要
谓词逻辑中的正确推理(H1∧H2∧…∧Hn
).
C
为逻辑有效式
。
定理3.(基本推理公式)以下蕴涵式都是逻辑有效式
。
13
(a)(.x)P(x)∨(.x)Q(x).(.x)(P(x)∨Q(x))
。
(b)(.x)(P(x)∧Q(x)).(.x)P(x)∧(.x)Q(x)
。
(c)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))
。
(d)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))
。
(e)((.x)P(x).(.x)Q(x)).(.x)(P(x).Q(x))
。
(P(x).Q(x))P(x).(.x)Q(x))
。
f)(.x)(.((.x)
(g)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))。
(h)(.x)(P(x).Q(x))∧(.x)(Q(x).R(x)).(.x)(P(x).R(x))。
(P(.Q(x))∧P(.Q()。
i)(.x)(x)a)
a
定理3.以下谓词公式都是逻辑有效式。
14
(a)(.x)(.y)P(x,.(.y)(.x)P(y)。
y)x,
(b)(.x)(.y)x,.(.x)(.y)P(x,
P(y)y)
。
(c)(.y)(.x)P(x,.(.y)(.x)P(y)
。
y)x,
(d)(.x)(.y)x,.(.y)(.x)P(x,
P(y)y)
。
(e)(.y)(.x)x,.(.x)(.y)P(x,
y
P(y))
。
(f)(.y)(.x)P(x,.(.y)(.x)P(x,)
。
y)
y
(g)(.x)(.y)P(y)P(y)
。
x,.(.x)(.y)x,
(h)(.y)(.x)P(x,.(.x)(.y)P(y)
。
y)x,
有关量词的消去和引入规则有以下4个
。
(a)全称量词消去规则/全称举例规则:(.x)P(x).P(y)或(.x)P(x).P(a),
其中
y
是论域中任一个体。
该规则的使用条件如下:
(1)第一式中,取代
x
的
y
应为任意的不在P(x)中约束出现的个体变项。
(2)第二式中,
a
为任意个体常项。
(3)用
y
或
a
取代P(x)中自由出现的
x
时,必须对
x
的所有自由出现进行取代。
个体
(
。
b)全称量词引入规则/全称推广规则:P(y).(.x)P(x), 其中
y
是论域中任一
第
3
章 谓词逻辑
103
该规则的使用条件如下:
(1)无论P(中自由出现的个体变项
y
取何值,y)应该均为真。
y) P(
(2)取代自由出现的
y
的
x
不能在P(y)中约束出现。
(c)存在量词消去规则/存在举例规则:(.x)a), 其中
a
是论域中的一
个个体常项。
P(x).P(
该规则的使用条件如下:
(1)
a
是使
P
为真的特定的个体常项。
(2)
a
不在P(x)中出现。
(3)P(x)中没有其他自由出现的个体变项。
(4)
a
是在推导过程中未使用过的。
(d)存在量词引入规则/存在推广规则:P(a).(.x)P(x), 其中
a
是论域中的一
个个体常项。
该规则的使用条件如下:
(1)
a
是特定的个体常项
a
。
)
(2)取代
a
的
x
不在P(中出现
。
使用推理规则的推理演算过程如下
:
(1)将以自然语言表示的推理问题形式化,转换为谓词公式。
(2)若不能直接使用基本的推理公式则消去量词。
(3)在无量词的情况下使用规则和公式进行推理
。
(4)( 必要时)引入量词,得到相应结论
。
请注意
:
(1)当对带量词的谓词公式进行推理证明时,当既需要消去存在量词又需要消去全
称量词时,一般要先使用存在量词消去规则,再使用全称量词消去规则。
(2)使用上述4个规则时,量词的辖域都必须延伸到整个公式的末端。换言之,在含
有多个量词的谓词推理中,使用消去规则应该按照从左到右的顺序,而使用引入规则时应
该按照从右到左的顺序。
3.6.2
主教材习题参考解答
15
假定论域是整数集,谓词P(x)表示“
x
是4的倍数”,Q(x)表示“
x
是2的倍
数”,3.
x,表示“ x>y”。判断下述推理是否正确, 请指出错误的原因。
G(y) 如果不正确
,
(a)(1)(.x)G(x,5) (前提引入
)
(2)G(3,5) (存在量词消去
)
1)(.x)x,
(b)(G(a)(前提引入
)
(c)(
(
12)(
)G.
(
x)aG)
(x,
G(x)
(
存在量词消去
前提引入)
)
a,
(
a)
(2)(.x)(.x)x,(存在量词引入
)
(d)(1)(.x)(P(x).Q(x)) (前提引入
)
(2)P(4).Q(3) (全称量词消去
)
104
离散数学及应用学习指导与习题解析
(e)(1)(.x)Q(x).P(x)(前提引入
)
y)y)
(2)Q(.P((全称量词消去
)
(1)(.x)(.y)G(x,前提引入
)
f)(y)
(
(2)(.y)z,(全称量词消去
)
(3)G(bG)
(y)
存在量词消去
)
z,
(
(4)(.z)G(b)(全称量词引入
)
(5)G(b)
z,
全称量词消去
)
b,
(
G(x)
(6)(.x)x,(全称量词引入
)
解
:
(a)违反了存在量词消去规则的“1)。
(
a
是使
P
为真的特定的个体常项”
(b)违反了存在量词消去规则的“2)x)。
(
a
不在P(中出现”
(c)违反了存在量词引入规则的“(2) a)。
取代
a
的
x
不在P(中出现”
(d)违反了全称量词消去规则的“(3)用
y
或
a
取代P(x)中自由出现的
x
时,必须
对
x
的所有自由出现进行取代”;另外,应该使用相同的
y
或a。
(e)全称量词消去规则使用不正确,量词的辖域应该延伸到整个公式的末端。
(3) (x)。
f)步骤(违反了存在量词消去规则的“3)P(中没有其他自由出现的个体变项”
3.利用推理规则作推理演算,构造下列推理形式的证明。
16
(a)前提:(.x)(~P(x).Q(x)),(.x)~Q(x)
。
结论:P()
。
a
(b)前提:(.x)(P(x).Q)
。
结论:(.x)P(x).Q
。
(c)前提:(.x)(P(x)∨Q(x)),(.x)(Q(x).~R(x))
。
结论:(.x)(R(x).P(x))
。
(d)前提:(.x)(P(x).(Q(x)∧R(x))),(.x)(P(x)∧S(x))。
结论:(.x)(R(x)∧S(x))
。
解
:
(a)证明如下
:
(1)(.x)(~P(x).Q(x)) (前提引入
)
(2)~P(.Q((全称量词消去)
a)a)
(3)(.x)~Q(x)(前提引入
)
Q(
(
(5)P(((2)、(4)拒取
)
(4)~a) 全称量词消去)
a)
(b)证明如下
:
()(.x)P(x)(附加前提引入
)
()P(x)(全称量词消去
)
()(.x)(P(x).Q)(前提引入
)
()P(x).
Q
(全称量词消去
)
()
Q
((3)、(4)分离
)
第
3
章 谓词逻辑
105
(c)证明如下
:
(1)(.x)(P(x)∨Q(x)) (前提引入
)
(2)P(a)(全称量词消去
)
a)∨Q(
(3)(.x)(Q(x).~R(x)) (前提引入)
(4)Q(.~R((全称量词消去)
a)a)
(5)~Q(.P(((2)置换)
a)a)
(6)R(.~Q(((4)置换
)
a)a)
(7)R(.P(((6)
a)a) 5)、(假言三段论
)
(8)(.x)(R(x).P(x)) (存在量词引入
)
(d)证明如下
:
(1)(.x)(P(x)∧S(x)) (前提引入
)
(2)P(a) 存在量词消去
)
a)∧S((
(3)(.x)(P(x).(Q(x)∧R(x))) (前提引入)
(a)Q(a)) (全称量词消去)
4)P(.(a)∧R(
(5)P(((化简
)
a) 2)
(6)Q(a) 4)、(5)分离
)
a)∧R(((
(7)R(a) ((6)化简)
(8)S(((化简)
a) 2)
(9)R(a) 7)、(8)合取
)
a)∧S((
(
(10)(.x)(R(x)∧S(x)) (存在量词引入
)
3.在谓词逻辑中构造下列推理的证明。
17
(a)大熊猫都产在中国。欢欢是大熊猫。所以,欢欢产在中国。
(b)不存在不能表示成分数的有理数。无理数都不能表示成分数。所以,无理数都
不是有理数。
理数
(
。
c)有理数和无理数都是实数。虚数不是实数。因此,虚数既不是有理数也不是无
(d)所有的狮子都是凶猛动物。有些狮子不喝咖啡。所以有些凶猛动物不喝咖啡。
解:
(a)令P(x)表示“
x
是大熊猫”,Q(x)表示“
x
产在中国”,得到如下推理形式
:
前提:(.x)(P(x).Q(x)),P(欢欢)
。
结论:Q(欢欢)
。
然后进行谓词逻辑推理
:
(1)(.x)(P(x).Q(x)) (前提引入
)
(2)P(欢欢).Q(欢欢)(全称量词消去
)
(3)P(欢欢)(前提引入
)
(4)Q(欢欢) ((2)、(3)分离
)
(b)令P(x)表示“
x
是有理数”,Q(x)表示“
x
是无理数”,R(x)表示“
x
能表示成分
数”,得到如下推理形式:
106
离散数学及应用学习指导与习题解析
前提:~(.x)(P(x)∧~R(x)),(.x)(Q(x).~R(x))。
结论:(.x)(Q(x).~P(x))。
然后进行谓词逻辑推理:
(1)~(.x)(P(x)∧~R(x)) (前提引入
)
(2)(.x)(~R(x).~P(x)) ((1)置换
)
(3)~R(x).~P(x) ((2)全称量词消去
)
(4)(.x)(Q(x).~R(x)) (前提引入
)
(5)Q(x).~R(x) ((4)全称量词消去
)
(6)Q(x).~P(x) ((3)、(5)假言三段论
)
(7)(.x)(Q(x).~P(x)) ((6)全称量词引入
)
(c)令P(x)表示“
x
是有理数”,Q(x)表示“
x
是无理数”,R(x)表示“
x
是实数”,
S(x)表示“
x
是虚数”,得到如下推理形式:
前提:(.x)(P(x)∨Q(x).R(x)),(.x)(S(x).~R(x))。
结论:(.x)(S(x).~P(x)∧~Q(x))。
然后进行谓词逻辑推理:
(1)(.x)(P(x)∨Q(x).R(x)) (前提引入)
(2)P(x)∨Q(x).R(x) ((1)全称量词消去)
(3)~R(x).~P(x)∧~Q(x) ((2)置换
)
(4)(.x)(S(x).~R(x)) (前提引入
)
(5)S(x).~R(x) ((4)全称量词消去
)
(6)S(x).~P(x)∧~Q(x) ((3)、(5)假言三段论
)
(7)(.x)(S(x).~P(x)∧~Q(x)) ((6)全称量词引入
)
(d)令P(x)表示“
x
是狮子”,Q(x)表示“
x
是凶猛动物”,R(x)表示“
x
喝咖啡”,得
到如下推理形式:
前提:(.x)(P(x).Q(x)),(.x)(P(x)∧~R(x))。
结论:(.x)(Q(x)∧~R(x))。
然后进行谓词逻辑推理:
(1)(.x)(P(x)∧~R(x)) (前提引入)
(2)P(a) 1)存在量词消去)
a)∧~R(((
(3)(.x)(P(x).Q(x)) (前提引入)
(4)P(.Q(((3)全称量词消去)
a)a)
(5)P(((化简
)
a) 2)
(6)Q(((4)、(5)分离
)
a)
R((
(
(8)Q(a) 6)、(7)合取
)
(7)~a) 2)化简)
a)∧~R((
(
(9)(.x)(Q(x)∧~R(x)) ((8)存在量词引入
)
107
第
3
章 谓词逻辑
3.补充习题及参考解答
7
3.讨论公式(.x)(.y)x,在以下不同解释下的真值。
1
P(y)
(a)D={所有实数}, 谓词P(x,表示x×y=0
。
(
y)
1。
b)D={所有实数}, x,表示x×y=
谓词P(y)
(c)D={ 谓词P(y)表示x×y=1
。
所有正实数}, x,
解:在解释(a)和(c)下该公式的真值为“真”,在解释(b)下该公式的真值为“假”。
3.2
试给出解释I,使得在解释
I
下(.x)(Q(x)∧P(x)) 和(.x)(Q(x).P(x))
具有不同的真值。
Q
(x)
P
(x)
解:例如,论域
D
={全体正整数},表示x<0,表示x>0 时,(.x)
(Q(x)∧P(x)) 的真值为“假”,而(.x)(Q(x).P(x)) 的真值为“真”。
3.证明以下两个公式都不是逻辑有效式。
3
(a)(.x)(P(x)∨Q(x)).(.x)P(x)∨(.x)Q(x)
。
(b)(.x)P(x)∧(.x)Q(x).(.x)(P(x)∧Q(x))
。
证明
:
(a)例如,论域D={全体整数},
P
(x)表示“
x
是奇数”,Q(x)表示“
x
是偶数”时,
(.x)P(x)∨(.x)Q(x)的真值为“假”,而(.x)(P(x)∨Q(x)) 的真值为“真”。此时
蕴涵式的真值为“假”,因此不是逻辑有效式。
(b)例如,论域D={全体整数},P(x)表示“
x
是奇数”,Q(x)表示“
x
是偶数”时,
(.x)(P(x)∧Q(x)) 的真值为“假”,而(.x)P(x)∧(.x)Q(x)的真值为“真”。此时
蕴涵式的真值为“假”,因此不是逻辑有效式。□
3.将下列命题用谓词表示出来,使用全总个体域。
4
(a)一切反动派都是纸老虎。
(b)没有不透风的墙。
(c)有位老师又可爱又聪明。
(d)不存在又不好好学习又能得到好成绩的学生。
(e)世界上没有两个完全一样的鸡蛋
。
(
f)不是所有人都一样高。
(g)整数都可以比较大小。
(h)人固有一死,或重于泰山,或轻于鸿毛
。
(不预则废
。
i)凡事预则立,
(j)凡是敌人反对的,我们就要拥护;凡是敌人拥护的,我们就要反对。
(k)所有老师和有些学生总是准时到达教室
。
(但是相等的两个角未必都是对顶角
。
l)凡对顶角都相等,
(m)不是所有的男生都比任何一名女生成绩好,但是至少有一名男生成绩超过所有
女生
(
。
n)过平面上两个相异点有且仅有一条直线。
108
离散数学及应用学习指导与习题解析
解:
(a)(.x)(P(x).Q(x)), 其中P(x)表示“
x
是反动派”,Q(x)表示“
x
是纸老虎”。
(b)~(.x)(P(x)∧~Q(x)), 其中P(x)表示“
x
是墙”,Q(x)表示“
x
透风”。
(c)(.x)(P(x)∧Q(x)∧R(x)), 其中P(x)表示“
x
是老师”,Q(x)表示“
x
可
爱”,R(x)表示“
x
聪明”。
(d)~(.x)(P(x)∧~Q(x)∧R(x)), 其中P(x)表示“
x
是学生”,Q(x)表示“
x
好好学习”,R(x)表示“
x
得到好成绩”。
(e)~(.x)(.y)(x)∧P(x,其中P(表示“,x,
表示“
x
与
y
完全一样”。
P(y)∧Q(y)), x)
x
是鸡蛋”Q(y)
示“
x
(
与
y
一样高”。
P(y)x,其中P(表示“,Q(x,表
f)~(.x)(.y)(x)∧P(.Q(y)), x)
x
是人”y)
(g)(.x)(.y)(P(y)x,其中P(表示“,x,表
示“
x
与
y
能比较大小”。
x)∧P(.Q(y)), x)
x
是整数”Q(y)
(h)(.x)(P(x).(Q(x)∧(R(x)∨S(x)))), 其中P(x)表示“
x
是人”,Q(x)表
示“
x
会死”,R(x)表示“
x
的死轻于鸿毛”,S(x)表示“
x
的死重于泰山”。
(i)(.x)(P(x).(Q(x).R(x))∧(~Q(x).~R(x))), 其中P(x)表示“
x
是
事情”,Q(x)表示“对
x
有准备”,R(x)表示“
x
可以成功”。
(j)(.x)(P(x).S(x))∧(.x)(Q(x).R(x)), 其中P(x)表示“敌人拥护
x
”,
Q(x)表示“敌人反对
x
”,R(x)表示“我们拥护
x
”,S(x)表示“我们反对
x
”。
(k)(.x)(P(x).R(x))∧(.x)(Q(x)∧R(x)), 其中P(x)表示“
x
是老师”,
Q(x)表示“
x
是学生”,R(x)表示“
x
准时到达教室”。
(l)(.x)(.y)(P(y)x,~(.x)(.y)(x,.P(y)), 其中
x,.Q(y))∧Q(y)x,
P(x,表示“,x,表示“。
y)
x
与
y
是对顶角”Q(y)
x
与
y
是相等的两个角”
(m)~(.x)(.y)(P(x)∧Q(y).R(x,y))∧(.x)(P(x)∧(.y)(Q(y).
R(x,其中P(表示“,y)
y
是女生”R(y)
x
成绩超
过y”
y。
))), x)
x
是男生”Q(表示“,x,表示“
(n)(.x)(.y)(x,.(.z)(Q(z,y)∧(.u)(Q(u,y)
P(y)z)∧R(x,u)∧R(x,.
S(z,u)))), x,表示“,x)
x
是直线”
其中P(y)
x
和
y
是平面上的两个相异点”Q(表示“,
R(x,表示“,x,表示“。
z,y)
z
通过
x
和y”S(y)
x
与
y
相同”
3.假设论域是实数集,{(是一个函数序列,x) 将函数序列
5
fn
x)} f(为一个函数,
{fn
(在区间(b) x) 对任意的ε>0 和x∈(b),
x)} a,内收敛于f(的定义“ a,都存在正整数
N
,使得对任意n>
N
时有|f(x)-fn
(x)|<ε”翻译为谓词公式。
解:采用易于理解的谓词表示形式,原语句可以表示为
(.ε)(.x)(a,
ε
>0∧
x
∈(b)
.(.
N
)(
N
∈Z+
∧(.n)(x)x)|<ε)))
n
>
N
∧
n
∈Z+
.|f(-fn
(
3.假设论域是实数集,{fn
(x)} 是一个函数序列,f(x)是一个函数,将函数序列
6
{(在区间(b) x) 对任意ε>0, 使得
fn
x)} a,内一致收敛于f(的定义“ 都存在正整数
N
,
n>
N
时对所有x∈(a,b)有|f(x)-fn
(x)|<ε”翻译为谓词公式。
109
第
3
章 谓词逻辑
解:采用易于理解的谓词表示形式,原语句可以表示为
(.ε)(
N
∈Z+
∧(.n)(
x
∈(b)
ε
>0.(.
N
)(
n
>
N
∧
n
∈Z+
.(.x)(a,
.|f(x)-fn
(x)|<ε))))
3.7
判断公式((.x)P(x).(.x)Q(x)).(.x)(P(x).Q(x)) 的类型。如果
它是逻辑有效式,请给出证明;否则举出反例。
解:((.x)P(x).(.x)Q(x)).(.x)(P(x).Q(x))
≡~(~(.x)P(x)∨(.x)Q(x))∨(.x)(~P(x)∨Q(x))
≡((.x)P(x)∧~(.x)Q(x))∨(.x)~P(x)∨(.x)Q(x)
≡((.x)P(x)∨(.x)~P(x)∨(.x)Q(x))∧(~(.x)Q(x))∨(.x)~P(x)
∨(.x)Q(x))
≡(((.x)P(x)∨(.x)~
P
(x))∨(.x)
Q
(x))∧((~(.x)
Q
(x)∨(.x)
Q(x)))∨(.x)~P(x))
≡(T∨(.x)Q(x))∧(T∨(.x)~P(x))≡T
因此该公式是逻辑有效式。
3.证明下列各等值式:
8
(a)(.x)(.y)(y))≡(.x))。
P(x).Q(P(x).(.y)Q(
y
(b)~(.x)(.y)((x,x,R(y)∨S(y))
)
P(y)∨Q(y))∧(x,x,
≡(.x)(.y)((P(y)∨Q(y))R(x,
x,x,.(x,)))
。
(c)~(.x)((.y)y)
H
(y)
)
~y)∧~S(
y
L(x,.(.y)x,
≡(.x)(.y)(.z)(L(y)∧~
H
(
z
P(zx)
,
.Q(z))x∨
,
(
))。x,.S(x,(d)(.z)(.x)((x,x,R(z)z)))
≡((.z)(.x)P(x,z).(.z)(.x)Q(x,z))∨((.z)(.x)R(x,z).(.z)
(.x)S(x,))。
z
(e)(.x)(P(x)∨q).(.x)(P(x)∧q)
≡(q.(.x)P(x))∧(~q.(.x)~P(x))
。
解:
(a)(.x)(.y)(P(x).Q(y))≡(.x)(.y)(~P(x)∨Q(y))≡(.x)~P(x)
∨(.y)Q(P(Q(P(.(.y)y)。
y)≡~(.x)x)∨(.y)y)≡(.x)x)Q(
(b)~(.x)(.y)((y)∨Q(y))∧(R(y)∨S(y))
)
P(x,x,x,x,
≡(.x)(.y)~((x,x,R(y)∨S(y))
)
P(y)∨Q(y))∧(x,x,
≡(.x)(.y)(~(x,x,R(y)∨S(y))
)
P(y)∨Q(y))∨~(x,x,
≡(.x)(.y)(y))∨(y))
)
~(P(y)∨Q(~x,x,
x,x,R(y)∧~S(
≡(.x)(.y)((P(y)∨Q(y))~x,x,
x,x,.(R(y)∧~S(y)))
。
(c)~(.x)((.y)x,x,
L(y).(.y)
H
(y)
)
≡(.x)~(L(y)∨(.z)x,
~(.y)x,
H
(z)
)
≡(.x)((.y)L(y)∧~(.z)
H
(z)
)
x,x,
≡(.x)((.y)L(x,~
H
(z)
)
y)∧(.z)x,
≡(.x)(.y)(.z)(L(y)∧~
H
(
z
x,x,))。
110
离散数学及应用学习指导与习题解析
(d)(.z)(.x)((z))∨(z)))
P(x,.Q(R(z)x,
z)x,x,.S(
≡(.z)(.x)((~x,x,~x,x,
P(z)∨Q(z))∨(R(z)∨S(z)))
≡((.z)(.x)~
P
(x,z)∨(.z)(.x)
Q
(x,z))∨((.z)(.x)~
R
(x,z)∨
(.z)(.x)S(z)))
x,
≡(~(.z)(.x)
P
(x,z)∨(.z)(.x)
Q
(x,z))∨(~(.z)(.x)
R
(x,z)∨
(.z)(.x)z)))
S(x,
≡((.z)(.x)P(x,z).(.z)(.x)Q(x,z))∨((.z)(.x)R(x,z).(.z)
(.x)S(z))。
x,
(e)(.x)(P(x)∨q).(.x)(P(x)∧q)
≡~(.x)(P(x)∨q)∨(.x)(P(x)∧q)
≡(.x)~(P(x)∨q)∨(.x)(P(x)∧q)
≡(.x)(~P(x)∧~q)∨(.x)(P(x)∧q)
≡((.x)~P(x)∧~q)∨((.x)P(x)∧q)
≡((.x)~P(x)∨(.x)P(x))∧(~q∨(.x)P(x))∧((.x)~
P
(x)∨q)∧
(~q∨q)
≡(~q∨(.x)P(x))∧((.x)~P(x)∨q)
≡(q.(.x)P(x))∧(~q.(.x)~P(x))。
3.以下哪个公式与(.x)(A(x)↓B(x)) 等值?
9
(.x)A(x)↓(.x)B(x),(.x)A(x)↑(.x)B(x),(.x)A(x)↓(.x)B(x),
(.x)A(x)↑(.x)B(x)。
解:(.x)(A(x))≡(.x)A(A(x)~(x))≡~(.x)(x))
↓B(x)∨B(x)∨B(
≡~((.x)A(x)∨(.x)B(x))≡(.x)A(x)↓(.x)B(x)
。
3.将下列公式化为等值的前束范式。
10
(a)~((.x)(.y)P(a,x,Q(b)).R(x)
。
(b)(.x)x,.(.z)Q()
。
(c)(.x)(P.
(
y)(
y.
)
z)(P(xy,
)∧(
)
.
∧
x((
)
.ux)Q,
(x,u).(.w)Q()))
。
y,z(z) y,
w
(d)(.x)(P(x).(.y)((y)Q(.Q(y)))∨(.z)z)))
。
P(.(x)P(
解
:
(a)~((.x)(.y)P(a,x,Q(b)).R(x)
y)∧(.x)x,
≡((.x)(.y)P(x,Q(b))∨R(
a,y)∧(.x)x,x)
≡(.x)((.y)P(x,x,z)
a,y)∧Q(b))∨R(
≡(.x)(.y)((b))∨R())
。
P(a,x,x,
y)∧Q(
z
P(y)
(b)(.x)x,.(.z)Q(z)
≡((.x)P(y).(.z)Q(Q(.(.x)P(y))
x,z))∧((.z)z)x,
≡(~(.x)x,Q(~(.z)z)∨(.x)x,
P(y)∨(.z)z))∧(Q(P(y)
)
≡(~(.x)x,Q(~(.z)z)∨(.z)z,
P(y)∨(.u)u))∧(Q(P(y)
)
≡((.x)u))∧((.z)y)
)
x,Q(Q(P(
≡(.x)(.u)(~x,u))∧(.z)(Q(z,
~P(y)∨(.u)~z)∨(.z)z,
P(y)∨Q(~z)∨P(y))