离散数学期末复习试题及答案（七）

第七章 谓词逻辑 １．用谓词表达下列命题�� 1) 小张不是工人。��

设 c:小张 W(x): x是工人 ?W(c)

2) 所有教练员都是运动员。��

设 J(x):x是教练, W(x):x是运动员 (?x)(J(x)?W(x))

3) 没有一个国家选手不健壮。��

设 C(x):x是国家选手,J(x):x健壮 ?(?x)(C(x)??J(x))

4) 有些大学生不钦佩老师。��

设 D(x):x是大学生, L(x):x是老师, P(x,y):x钦佩y

(?x)(D(x)?(?y)(L(y)?P(x,y)))

5) 小莉既聪明又美丽。��

设 l:小李 C(x):x聪明 M(x):x美丽 C(l)?M(l)

6) 不是所有的高中生都能上大学。��

设 G(x):x是高中生, D(x):x上大学 ?(?x)(G(x)?D(x))

7) 每个有理数都是实数。��

设Q(x):x是有理数, R(x):x是实数 (?x)(Q(x)?R(x))

8) 某些实数是有理数。��

设R(x):x是实数, Q(x):x是有理数 (?x)(R(x)?Q(x))

9) 并非每个实数都是有理数。�� 设R(x):x是实数, Q(x):x是有理数

?(?x)(R(x)?Q(x))

10) 若m是奇数，则2m不是奇数。�� 设Q(x):x是奇数， Q(m)??Q(2m)

68

11) 直线A与直线B平行，当且仅当直线 A与B不相交。��

设L(x):x是直线，P(x,y):x平行于y, X(x,y):x与y相交

(L(A)?L(B)?P(A,B))??(L(A)?L(B)??X(A,B))

12) 对于每个实数ｘ，存在一个更大的实数ｙ。�� 设R(x):x是实数, D(x,y):x大于y,

(?x)(R(x)?(?y)(R(y)?D(y,x)))

2. 设P(x)为“x是质数”，E(x)为“ｘ是偶数”， Q(x)为“x是奇数”，D(x,y)为“x除尽y”，把下 列各式译成汉语：�� 1）P(5)；��

2）E(2)∧P(2)；��

3）(?ｘ)(E(x)∧D(x,6))；�� 4）(?ｘ)(D(2,x)→E(x))；�� 5) (?ｘ)(E(x)→D(2,x))；

6）(?ｘ)(E(x)→(?ｙ)(D(x,y)→E(y)))； 7) (?ｘ)(P(x)→(?ｙ)(E(y)∧D(x,y)))； 8) (?ｘ)(Q(x)→(?ｙ)(P(y)→D(x,y))

1) P(5)；5是偶数。

2) E(2)∧P(2)；2是偶数也是质数。

3) (?x)(E(x)?D(x,6));存在偶数可以除尽6。 4) (?x)(D(2,x)?E(x));被2除尽的数都是偶数。 5) (?x)(?E(x)??D(2,x)); 非偶数都不能被2除尽。

6) (?x)(E(x)?(?y)(D(x,y)?E(y)));

所有能被偶数除尽的数都是偶数。

7) (?x)(P(x)?(?y)(E(y)?D(x,y)));

对任给的质数，存在偶数可被质数除尽。

8) (?x)(Q(x)?(?y)(P(y)?D(x,y)))；

所有质数都不能被任意奇数整除。

69

3. 求下列各式真值：��

1)(?x)(P(x)?Q(x))其中P(x):x?1,Q(x):x?2,个体域是{1,2}?(P(1)?Q(1))?(P(2)?Q(2))

?(T?F)?(F?T)?T?T?T

2)(?x)(P?Q(x))?R(a),其中P:2?1,Q(x):x?3,R(x):x?5,a?5,个体域:{?2,3,6}?((P?Q(?2))?(P?Q(3))?(P?Q(6)))?R(5)?((T?T)?(T?T)?(T?F))?F?F?F?F

3)(?x)(P(x)?Q(x))?T,其中P(x):x?2,Q(x):x?0,T是任何永真式,个体域:{1},?(P(1)?Q(1))?T?(F?F)?T?T?T?T

4. 如果论域是集合{a,b,c}，试消去下面公式中的量词。��

1)(?x)P(x)?P(a)?P(b)?P(c)2)(?x)R(x)?(?x)S(x)?(R(a)?R(b)?R(c))?(S(a)?S(b)?S(c))3)(?x)(P(x)?Q(x)) ?(P(a)?Q(a))?(P(b)?Q(b))?(P(c)?Q(c)

4)(?x)?P(x)?(?x)P(x)?(?P(a)??P(b)??P(c))?(P(a)?P(b)?P(c))5)(?x)R(x)?(?x)S(x)?(R(a?)R(b)?R(c))?(S(a)?S(b)?S(c))

5. 对下列谓词公式中的约束变元进行改名：��

1) (?x)(?y)(P(x,z)?Q(y))?S(x,y)?(?u)(?v)(P(u,z)?Q(v))?S(x,y)

70

2)((?x)(P(x)?(R(x)?Q(x)))?(?x)R(x))?(?z)S(x,z)?((?u)(P(u)?(R(u)?Q(u)))?(?v)R(v))

?(?w)S(x,w)

6. 对下列谓词公式中的自由变元进行代换：��

1)((?y)A(x,y)?(?x)B(x,z)?(?x)(?z)C(x,y,z)?((?y)A(u,y)?(?x)B(x,v)?(?x)(?z)C(x,w,z)2)((?y)P(x,y)?(?z)Q(x,z))?(?x)R(x,y)?((?y)P(u,y)?(?z)Q(v,z))?(?x)R(x,w)

7. 设个体域是自然数集，试证明下列关系式：

1)(?x)(?y)(P(x)?Q(y))?(?x)P(x)?(?y)Q(y)右?(?x)(P(x)?(?y)Q(y))?(?x)((?y)Q(y)?P(x))

?(?x)(?y)(Q(y)?P(x))?(?x)(?y)(P(x)?Q(y))?左

2)(?x)(?y)(P(x)?Q(y))?(?x)P(x)左?(?x)(?y)(Q(y)?P(x))?(?x)((?y)Q(y)?P(x))

?(?x)(P(x)?(?y)Q(y))?(?x)P(x)?(?y)Q(y)?(?x)P(x)(I1)

3)(?x)(?y)(P(x)?Q(y))?(?x)P(x)?(?y)Q(y)左?(?x)(?y)(Q(y)?P(x))?(?x)((?y)Q(y)?P(x))

?(?x)(P(x)?(?y)Q(y))?(?x)P(x)?(?y)Q(y)?右

71