离散数学课后习题答案 - （左孝凌版） 

?(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c))

?( ?x)(A(x)∨B(x))

所以(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) （6）解：推证不正确，因为

┐(?x)(A(x)∧┐B(x))?┐((?x)A(x)∧(?x)┐B(x))

（7）求证(?x)( ?y)(P(x)→Q(y)) ? ( ?x)P(x)→(?y)Q(y)

证明：(?x)( ?y)(P(x)→Q(y)) ?(?x)( ?y)( ┐P(x) ∨Q(y)) ?(?x) ┐P(x) ∨( ?y)Q(y) ?┐(?x)P(x) ∨( ?y)Q(y) ? ( ?x)P(x)→(?y)Q(y)

习题2-6

（1）解：a) (?x)(P(x)→(?y)Q(x,y)) ?(?x)( ┐P(x) ∨(?y)Q(x,y)) ?(?x) (?y) (┐P(x) ∨Q(x,y))

b) (?x)(┐((?y)P(x,y))→((?z)Q(z)→R(x))) ?(?x)((?y)P(x,y)∨((?z)Q(z)→R(x))) ?(?x)((?y)P(x,y) ∨(┐(?z)Q(z) ∨R(x))) ?(?x)((?y)P(x,y) ∨((?z)┐Q(z) ∨R(x))) ?(?x) (?y) (?z) ( P(x,y) ∨┐Q(z) ∨R(x)) c)(?x)( ?y)(((?zP(x,y,z)∧(?u)Q(x,u))→(?v)Q(y,v))

?(?x)( ?y)( ┐((?z)P(x,y,z)∧(?u)Q(x,u))∨(?v)Q(y,v))

?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v))

?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v))

?(?x)( ?y) (?z) (?u) (?v) (┐P(x,y,z) ∨┐Q(x,u)∨Q(y,v))

（2）解：a) ((?x)P(x)∨(?x)Q(x))→(?x)(P(x)∨Q(x))

?┐((?x)P(x)∨(?x)Q(x)) ∨(?x)(P(x)∨Q(x)) ?┐(?x) (P(x)∨Q(x)) ∨(?x)(P(x)∨Q(x)) ?T b) (?x)(P(x)

→

(?y)((?z)Q(x,y)

→

┐

(?z)R(y,x)))

?(?x)( ┐P(x) ∨(?y)( Q(x,y)→┐R(y,x))) ?(?x) (?y) ( ┐P(x) ∨┐Q(x,y) ∨┐R(y,x)) 前束合取范式

?(?x) (?y)( (P(x) ∧Q(x,y) ∧R(y,x)) ∨(P(x) ∧Q(x,y) ∧┐R(y,x)) ∨ (P(x) ∧┐Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧R(y,x))

∨(┐P(x) ∧┐Q(x,y) ∧R(y,x)) ∨( (P(x) ∧┐Q(x,y) ∧┐R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧┐R(y,x))) 前束析取范式

c) (?x)P(x)→(?x)((?z)Q(x,z)∨(?z)R(x,y,z)) ?┐(?x)P(x) ∨(?x)((?z)Q(x,z)∨

(?z)R(x,y,z)) ?(?x)

┐

P(x)

∨

(?x)((?z)Q(x,z)

∨

(?u)R(x,y,u))

?(?x)(┐P(x) ∨(?z)Q(x,z)∨(?u)R(x,y,u)) ?(?x) (?z) (?u)(┐P(x) ∨Q(x,z)∨R(x,y,u)) 前束合取范式

?(?x) (?z) (?u)(( P(x) ∧Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧┐R(x,y,u))

∨(┐P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧┐R(x,y,u))) 前束析取范式

习题2-7 (1)证明：

(2)a) ①(?x)(┐A(x)→B(x)) P d)(?x)(P(x)→Q(x,y))→((?y)P(y)∧(?z)Q(y,z)) ?┐(?x)( ┐P(x) ∨Q(x,y)) ∨((?y)P(y)∧(?z)Q(y,z))

?(?x)( P(x) ∧┐Q(x,y)) ∨((?u)P(u)∧(?z)Q(y,z))

?(?x) (?u) (?z) (( P(x) ∧┐Q(x,y)) ∨(P(u)∧Q(y,z))) 前束析取范式

?(?x) (?u) (?z) (( P(x)∨P(u)) ∧ (P(x)∨Q(y,z)) ∧(┐Q(x,y)∨P(u)) ∧ (┐Q(x,y)∨Q(y,z))) 前束合取范式

②┐

US① ③(

P ④US③ ⑤A(u)

T②E ⑥T④⑤I ⑦

EG⑥

A(u)

?x)

┐

(

→

┐

B(u) B(x) B(u) B(u) A(u) ?x)A(x)

∨

b) ②①(

┐?x)

( ┐

?x)(A(x)(A(x)

→→

B(x)) ⑨

US⑧

B(x)) ⑩ B(c) ∧

┐B(c) B(c) P（附加前提）

T①E ③ES② ④T③I ⑤T③I ⑥

EG④ ⑦P ⑧T⑥⑦I

┐

(A(c)

┐(

(?x)A(x)

→

→

B(c)) A(c) B(c) ?x)A(x) (?x)B(x) (?x)B(x) T⑤⑨矛盾

c ） ① ( ? x)(A(x)

→

P

② A(u) → US①

③ ( ? x)(C(x) → ┐ P

④ C(u) → ┐

US③

⑤ ┐ B(u) →

┐

T②E

⑥ C(u) → ┐

T④⑤I

B(x)) B(u) B(x)) B(u) A(u) A(u)

⑦UG⑥

(?x)(C(x)

∨

→B(x)),(

┐?x)(B(x)A(x)) ⑦ A(u)

US

→

┐

⑧T⑤⑦I

∨B(u) A(u) d) (?x)(A(x)C(x)),( ?x)C(x)? (?x)A(x)

①(

?x)(B(x)

P ②B(u)→US① ③(

P ④US③ ⑤┐

T②④I ⑥ (?x)(A(x)

P

┐

┐∨

C(x)) C(u) ?x)C(x) C(u) B(u) B(x)) ⑨

UG⑧

(2) 证明： a)①

P （附加前提） ②

US ① ③

(?x)(P(x) P ④P(u)

US ③ ⑤

→ →

(?x)A(x) ?x)P(x) P(u)

Q(x)) Q(u) Q(u) →

(