离散 第一部分－练习－答案学习资料.doc

1．设个体域D={a,b,c},消去下列公式的量词

(1)xF(x)$úyG(y)

(2)x$y(F(x)úG(y))

(3)x(F(x)$?yG(y))

解:

(1)xF(x)$úyG(y)

?(F(a)ùF(b)ùF(c))ú(G(a)úG(b)úG(c))

(2)先将量词辖域缩小,再消量词方便

x$y(F(x)úG(y))

?xF(x)$úyG(y)(量词辖域收缩扩张等值式)

?(F(a)ùF(b)ùF(c))ú(G(a)úG(b)úG(c))

原来(1)与(2)等值

(3)先将量词辖域缩小

x(F(x)$?yG(y))

?$xF(x)$?yG(y)(量词辖域收缩扩张等值式)

?(F(a)úF(b)úF(c))?(G(a)úG(b)úG(c))

说明:在做此类问题时,若能将量词辖域缩小,就缩小后再消量词,否则太麻烦.

2.求下列各公式的前束范式

(1)xF(x)$??yG(x,y)

(2)xF(x,y)$?xG(x,y)

(3)($x1F(x1,x2)$?x2G(x2))$?x2H(x1,x2)

解:求前束范式时,要用换名规则、代替规则、量词否定等值式、量词辖域收缩与扩张等值式.

(1)xF(x)$??yG(x,y)

?xF(x)?y?G(x,y)(量词否定等值式)

?xF(x)?y?G(z,y)(代替规则)

?$xy(F(x)??G(z,y))(辖域收缩扩张等值式)

(2)xF(x,y)$?xG(x,y)

?xF(x,y)$?zG(z,y)(换名规则)

?$x$z(F(x,y)?G(z,y))

(3)($x1F(x1,x2)$?x2G(x2))$?x2H(x1,x2)

?($x1F(x1,x2)$?x3G(x3))$?x4H(x5,x4)

?x1$x3(F(x1,x2)?G(x3))$?x4H(x5,x4)

?$x1x3$x4((F(x1,x2)?G(x3))?H(x5,x4))

请填上每步用的等值式或规则.

3.在自然推理系统F中构造下面推理的证明.

每个喜欢步行的人都不喜欢骑自行车.每个人或者是喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车.所以,有人不喜欢步行(个体域为人的集合)

令F(x):x喜欢步行,G(x):x喜欢骑自行车

H(x):x喜欢乘汽车

因为个体域是人的集合,故不引入特性谓词

前提:x(F(x)??G(x)),x(G(x)úH(x)),$x?H(x)

结论:$x?F(x)

证明:

①$x?H(x)前提引入

②?H(c)①EI

③x(G(x)úH(x))前提引入

④G(c)úH(c)③UI

⑤G(c)②④析取三段论

⑥x(F(x)??G(x))前提引入

⑦F(c)??G(c)⑥UI

⑧?F(c)⑤⑦拒取式

⑨$x?F(x)⑧EG

注意:先消去存在量词