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

( x)¬S(x)∨( y)R(y)

¬( x)S(x)∨( y)R(y)

( x)S(x)→( y)R(y)

(3) ( x)(A(x)→B) ( x)A(x)→B

证明：( x)(A(x)→B) ( x)(¬A(x)∨B) ( x)¬A(x)∨B

¬( x)A(x)∨B ( x)A(x)→B

(4) ( x)(B→A(x)) B→( x)A(x)

证明：( x)(B→A(x)) ( x)(¬B∨A(x)) ¬B∨( x)A(x) B→( x)A(x)

(5) ( x)(A(x)→B(x)) ( x)A(x)→( x)B(x)

证明：因为( x)(A(x)→B(x))，所以对于任意个体c，A(c)→B(c)和A(c)，从而有B(c)，由c的任意性有( x)B(x)，根据CP规则，( x)(A(x)→B(x)) ( x)A(x)→( x)B(x)

(6) ( x)(A(x) B(x)) ( x)A(x) ( x)B(x)

证明：( x)(A(x) B(x)) ( x)((A(x)→B(x))∧(B(x)→A(x)))

( x)(A(x)→B(x))∧( x)(B(x)→A(x))

( x)(A(x)→B(x))∧( x)(B(x)→A(x)) ( x)(A(x)→B(x)) ( x)A(x)→( x)B(x)

同理，( x)(A(x)→B(x))∧( x)(B(x)→A(x)) ( x)B(x)→( x)A(x)

所以，( x)(A(x)→B(x))∧( x)(B(x)→A(x)) (( x)A(x)→( x)B(x))∧(( x)B(x)→( x)A(x)) 而(( x)A(x)→( x)B(x))∧(( x)B(x)→( x)A(x)) ( x)A(x) ( x)B(x)

故有( x)(A(x) B(x)) ( x)A(x) ( x)B(x)

4. 判断下列证明是否正确。

( x) (A(x)→B(x)) ( x) (¬A(x)∨B(x)) ( x) (A(x)∧¬B(x))

¬( x) (A(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)B(x))

解：下列的推理是错的：¬( x) (A(x)∧¬B(x)) ¬(( x)A(x)∧( x)¬B(x))

习题 2.4

1. 求下列各式的前束范式。

(1) ( x)P(x)∧ ( x)Q(x)

解：( x)P(x)∧ ( x)Q(x) ( x)P(x)∧( x) Q(x) ( x)(P(x)∧ Q(x))

(2) ( x)P(x)∨ ( x)Q(x)

解：( x)P(x)∨ ( x)Q(x) ( x)P(x)∨( x) Q(x)

( x)P(x)∨( y) Q(y)

( x)( y) (P(x)∧ Q(y))

(3) ( x)( y)((( z)A(x,y,z)∧( u)B(x,u))→( v)B(x,v))

解：( x)( y)((( z)A(x,y,z)∧( u)B(x,u))→( v)B(x,v))

( x)( y)(( z)( u)(A(x,y,z)∧B(x,u))→( v)B(x,v))

( x)( y)( z)( u)( v)((A(x,y,z)∧B(x,u))→B(x,v))