离散数学 第2章 习题解答(4)

( u)(P(u)→(R(u)∨Q(u,y)))∧( v)R(v)→( z)S(x,z)

将约束变元z换成w：( x)(P(x)→(R(x)∨Q(x,y)))∧( x)R(x)→( w)S(x,w)

3. 对下列谓词公式中的自由变元进行代入。

(1) (( y)Q(z,y)→( x)R(x,y))∨( x)S(x,y,z)

解：将自由变元z用u代入：(( y)Q(u,y)→( x)R(x,y))∨( x)S(x,y,u)

将自由变元y用v代入：(( y)Q(z,y)→( x)R(x,v))∨( x)S(x,v,z)

(2) ( y)P(x,y)∧( z)Q(x,z) ( x)R(x,y)

解：将自由变元x用u代入：( y)P(u,y)∧( z)Q(u,z) ( x)R(x,y)

将自由变元y用v代入：( y)P(x,y)∧( z)Q(x,z) ( x)R(x,v)

4. 利用谓词公式对下列命题符号化。

(1) 每列火车都比某些汽车快。

解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。

“每列火车都比某些汽车快。”符号化为：( x)(A(x)→( y)(B(y)∧C(x,y)))

(2) 某些汽车比所有火车慢。

解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。

“某些汽车比所有火车慢。”符号化为： ( x)(B(x)∧( y)(A(y)→C(y,x)))

(3) 对每一个实数x，存在一个更大的实数y。

解：设R(x)：x是实数。G(x,y)：x比y大。

“对每一个实数x，存在一个更大的实数y。”符号化为：( x)(R(x)→( y)(R(y)∧G(y,x)))

(4) 存在实数x，y和z，使得x与y之和大于x与z之积。

解：设R(x)：x是实数。G(x,y)：x比y大。

“存在实数x，y和z，使得x与y之和大于x与z之积。”符号化为：

( x)( y)( z)(R(x)∧R(y)∧R(z)∧G(x+y,xz))

(5) 所有的人都不一样高。

解：设R(x)：x是人。G(x,y)：x和y一样高。

“所有的人都不一样高。”符号化为：( x)( y)(R(x)∧R(y)→¬G(x,y))

5. 自然数一共有下述三条公理：

a) 每个数都有惟一的一个数是它的后继数。

b) 没有一个数使数1是它的后继数。

c) 每个不等于1的数都有惟一的一个数是它的直接先驱数。

用两个谓词表达上述三条公理。

注：设n是不等于1的自然数，则n＋1是n的后继数，n－1是n的先驱数。

解：设A(x)：x是数。B(x,y)：x是y后继数(根据定义，也可理解为y是x先驱数)。 a) “每个数都有惟一的一个数是它的后继数。”符号化为：

( x)(A(x)→( y)(A(y)∧B(y,x))∧(( z)(A(z)∧B(z,x))→(z=y)))

b) “没有一个数使数1是它的后继数。”符号化为：¬( x)(A(x)∧B(1,x))

c) “每个不等于1的数都有惟一的一个数是它的直接先驱数。”符号化为：

( x)(A(x)∧¬(x=1)→( y)(A(y)∧B(x,y))∧(( z)(A(z)∧B(x,z))→(z=y)))

6. 取个体域为实数集R，函数f在a点连续的定义是：对每个ε＞0，存在一个δ＞0，使得