离散数学谓词逻辑作业

1. 将下列命题符号化

1）人都生活在地球上； 2）有的人长着黑头发； 3）中国人都用筷子吃饭；

4）并不是所有的实数都能表示成分数； 5）没有能表示成分数的无理数； 6）不存在比所有火车都快的汽车； 7）有的火车比有的汽车快；

8）说凡是汽车就比火车慢是不对的。

2. 设下面所有谓词的个体域D={a，b，c}。试将下面谓词公式中的量词消除， 写成与之等价的命题公式。 1) ?xF(x)??xG(x) 2) ?x(P(x)?Q(x)) 3） ?x?P(x)??xP(x)

3．指出下列表达式中的自由变量和约束变量，并指明量词的作用域：

1）(?xP(x)??xQ(x))?(?xP(x)?Q(y)) 2）?x?y((P(x)?Q(y))??zR(z)) 3）F(z)?(??x?yG(x，y，a)) 4）?x F(x)??yG(x，y)

5）(?xF(x)??yG(x，y，z))??zH(x，y，z) 4.设I是如下一个解释： D={a，b}

P(a，a)=1 P(a，b)=0 P(b，a)=0 P(b，b)=1 试确定下列公式在I下的真值：

1）?x?yP(x，y)； 2）?x?yP(x，y)； 3）?x?yP(x，y)； 4）?y?P(a，y)；

5）?x?y(P(x，y)?P(y，x))； 6）?xP(x，x) 5.判断下列公式的类型

1）?xP (x)??xP(x)

2）?x?y（F(x，y) ?F（y，x）） 3）?（?xF(x) ??yG（y））∧?yG（y） 4）?x?yP(x，y) ? ?y?x P(x，y) 6.设I是如下一个解释：

D={3，2}； a=3 b=2 ； f(3)=2 f(2)=3；

P(3，3)=1 P(3，2)=1 P(2，3)=0 P(2，2)=0

试求出下列公式在I下的真值：

1）(a，f(a))?P(b，f(b))； 2）?x?yP(y，x)；

3）?x?y(P(x，y)?P(f(x)，f(y)))； 7.试将下列公式化成等价的前束范式：

1)?x(P(x)??yQ(x，y))；

2)?x((??yP(x，y))?(?zQ(z)?R(x)))；

3)?x?y(?zP(x，y，z)?(?uQ(x，u)??vQ(y，v)))。