?(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) →
(
离散数学课后习题答案 - （左孝凌版）
