? (P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2))) ∧(P(2,1)→P(f(2),f(1)))∧(P(2,2) →P(f(2),f(2)))
? 前提：对论域中所有x，如果x不是研究生则x是大学生。
对论域中所有x， x不是大学生。
结论：对论域中所有x都是研究生。
(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1)) ? (T→F∧(T→F)∧(F→T)∧(F→T)?F∧F∧T∧T?F （2）解：a) (?x)(P(x)→Q(f(x),a))??
?(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1)) ? (F→Q(2,1))∧(T→Q(1,1))??? (F→F)∧(T→T)??T b) (?x)(P(f(x))∧Q(x,f(a))??? (P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) ? (T∧T)(F∧F)??T
c) (?x)(P(x)∧Q(x,a)) ? (P(1)∧Q(1,a))∨(P(2)∧Q(2,a)) ? (P(1)∧Q(1,1))∨(P(2)∧Q(2,1))??? (F∧T)∨(T∧F)??F d) (?x)( ?y)(P(x)∧Q(x,y))??? (?x) (P(x)∧(?y)Q(x,y))??? (?x) (P(x)∧(Q(x,1)∨Q(x,2))) ? (P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2))) ? (F∧(T∨T))∧(T∧(F∨F))??F
(3) 举例说明下列各蕴含式。
a) ?((?x)(P(x)∧Q(a))? (?x)P(x)??Q(a) b) (?x) (? P(x) ?Q(x)), (?x) ?Q(x)?P(a)
c) (?x) (P(x) ?Q(x)), (?x) (Q(x) ?R(x))? (?x) (P(x) ?R(x)) d) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) e) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) 解：a）因为?((?x)(P(x)∧Q(a)) ??(?x)P(x)∨?Q(a) 故原式为?(?x)P(x)∨?Q(a) ? (?x)P(x)??Q(a) 设P（x）：x是大学生。Q（x）：x是运动员
前提 或者不存在x，x是大学生，或者a是运动员 结论 如果存在x是大学生，则必有a是运动员。 b)设P（x）：x是研究生。Q（x）：x是大学生。a：论域中的某人。 故，对论域中某个a，必有结论a是研究生，即P（a）成立。 c）设P（x）：x是研究生。Q（x）：x曾读过大学。R（x）：x曾读过中学。
前提 对所有x，如果x是研究生，则x曾读过大学。
对所有x，如果x曾读过大学，则x曾读过中学。
结论：对所有x，如果x是研究生，则x曾读过中学。 d）设P（x）：x是研究生。Q（x）：x是运动员。
前提 对所有x，或者x是研究生，或者x是运动员。
对所有x，x不是研究生
结论 必存在x，x是运动员。 e）设P（x）：x是研究生。Q（x）：x是运动员。
前提 对所有x，或者x是研究生，或者x是运动员。
对所有x，x不是研究生
结论 对所有x，x是运动员。 （4）证明：(?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)
（5） 设论域D={a，b，c}，求证(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) 证明：因为论域D={a，b，c}，所以
(?x)A(x)∨(?x)B(x) ?(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c)) ?(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧
(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a)) ∧(A(c) ∨B(b)) ∧(A(c) ∨B(c))
?(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))) 前束析取范式
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))) 前束合取范式
习题2-7 (1) 证明：
(2) a) ①(?x)(┐A(x)→B(x)) P
②┐A(u)→B(u) US① ③( ?x)┐B(x) P ④┐B(u) US③ ⑤A(u)∨B(u) T②E ⑥A(u) T④⑤I ⑦ ( ?x)A(x) EG⑥
b) ①┐( ?x)(A(x)→B(x)) P（附加前提） ②( ?x)┐(A(x)→B(x)) T①E ③┐(A(c)→B(c)) ES② ④A(c) T③I ⑤┐B(c) T③I ⑥( ?x)A(x) EG④ ⑦ (?x)A(x)→(?x)B(x) P
⑧(?x)B(x) T⑥⑦I ⑨B(c) US⑧ ⑩B(c)∧ ┐B(c) T⑤⑨矛盾 c）①(?x)(A(x)→B(x)) P ②A(u)→B(u) US① ③( ?x)(C(x)→┐B(x)) P ④C(u)→┐B(u) US③ ⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥
d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P
②B(u)→┐C(u) US① ③( ?x)C(x) P
④C(u) US③ ⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US
⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明：
a)①( ?x)P(x) P（附加前提）②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)
故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P（附加前提） ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)
解：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。 本题符号化为：
(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P
④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I ⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧ b)设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车
本题符号化为：
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③
⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。 设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。S（x）：x是优秀生。c：小张。 本题符号化为：
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c)
①G(c) P（附加前提） ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P
⑥ L(c) T④⑤I ⑦G(c) →L(c) CP 注意：本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S（x）：x是优秀生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证仍是有效的。
3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解：Z1={} Z2={