（2）(?x)P(x)→(?x) Q(x) （3）((?x) P(x)∨(?y)Q(y))→(?x)R(x)
（4）(?x) (P(x)→Q(x，y))→((?y)R(y)→(?z)S(y，z)) 解：
（1）(?x) P(x)∧┐(?x)Q(x)
?(?x) P(x)∧┐(?y)Q(y) ?(?y)(?x) (P(x)∧┐Q(y)) （2）(?x)P(x)→(?x) Q(x)
?(?x)P(x)→(?y) Q(y)?(?x)(?y)(P(x)→Q(y)) （3）((?x) P(x)∨(?y)Q(y))→(?x)R(x) ?┐((?x)P(x)∨(?y)Q(y))∨(?x)R(x) ? (┐(?x) P(x)∧┐(?y)Q(y))∨(?x)R(x) ? ((?x)┐P(x)∧(?y)┐Q(y))∨(?x)R(x) ? (?x)(?y)(?z)(┐P(x)∧┐Q(y)∨R(z)) （4）(?x)(P(x)→Q(x，y))→((?y)R(y)→(?z)S(y，z)) ?┐(?x)(P(x)→Q(x，y))∨((?y)R(y)→(?z)S(y，z)) ? (?x)(P(x)∧┐Q(x，y))∨((?y) ┐R(y)∨(?z)S(y，z)) ? (?x)(?z)(?y)(P(x)∧┐Q(x，u)∨┐R(y)∨S(v，z)) 20. 证明下列各式。
（1）(?x)( ┐A(x)→B(x))，(?x) ┐B(x) ?(?x)A(x) （2）(?x)A(x)→(?x)B(x) ?(?x) (A(x)→B(x))
（3）(?x)(A(x)→B(x))，(?x)(C(x)→┐B(x))?(?x)(C(x)→┐A(x)) （4）(?x)(A(x)∨B(x))，(?x)(B(x)→┐C(x))，(?x)C(x)? (?x)A(x) 证明： （1）
(1) (?x) ┐B(x) P (2) ┐B(a) ES(1) (3) (?x)( ┐A(x)→B(x)) P (4) ┐A(a)→B(a) US(3) (5) A(a) T(2)(4) I (6) (?x)A(x) EG(5) （2）
(?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)→B(x)) （3）
(1) (?x)(C(x)→┐B(x)) P (2) C(a)→┐B(a) US(1) (3) (?x)(A(x)→B(x)) P (4) A(a)→B(a) US(3) (5) ┐B(a)→┐A(a) T(4) E (6) C(a)→┐A(a) T(2)(5) I (7) (?x)(C(x)→┐A(x)) UG(6) （4）(?x)(A(x)∨B(x))，(?x)(B(x)→┐C(x))，(?x)C(x)? (?x)A(x) (1) (?x)C(x) P (2) C(a) US(1) (3) (?x)(B(x)→┐C(x)) P (4) B(a)→┐C(a) US(3)
(5) ┐B(a) T(2)(4) I (6) (?x)(A(x)∨B(x)) P (7) A(a)∨B(a) US(6) (8) A(a) T(5)(7) I (9) (?x)A(x) UG(8) 21. 用CP规则证明。
（1）(?x) (P(x)→Q(x))? (?x)P(x)→(?x)Q(x) （2）(?x) (P(x)∨Q(x))? (?x)P(x)∨(?x)Q(x) 证明：
（1）(?x) (P(x)→Q(x))? (?x)P(x)→(?x)Q(x) 证明：
(1) (?x)P(x) P(附加前提) (2) P(a) ES(1) (3) (?x) (P(x)→Q(x)) P (4) P(a)→Q(a) US(3) (5) Q (a) T(2)(4) I (6) (?x)Q(x) UG(5) (7) (?x)P(x)→(?x)Q(x) CP(1) (6) （2）(?x) (P(x)∨Q(x))? (?x)P(x)∨(?x)Q(x) 证明：
(1) ┐(?x)P(x) P(附加前提) (2) (?x)┐P(x) T(1) E (3) ┐P(a) ES(2) (4) (?x) (P(x)∨Q(x)) P (5) P(a)∨Q(a) US(4) (6) Q(a) T(3)(5) I (7) (?x)Q(x) EG(6) (8) ┐(?x)P(x)→(?x)Q(x) CP(1) (7) (9) (?x)P(x)∨(?x)Q(x) T(8) E 22. 符号化下列命题，并推证其结论：
（1）任何人如果他喜欢步行，他就不喜欢乘汽车。每一个人或者喜欢汽车或者喜欢骑自行车。有的人不爱骑自行车。因而有人的不爱步行。
（2）不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。 （3）每个自然数不是奇数就是偶数。自然数是偶数当且仅当它能被2整除。并不是所以的自然数都能被2整除。因此，有的自然数是奇数。
（4）三角函数都是周期函数。一些三角函数是连续函数。所以，一些周期函数是连续函数。 （5）每个科学家都是勤奋的。每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以存在着事业获得成功的人或事业半途而废的人。 解：
（1）F(x)：x喜欢步行。C(x)：x喜欢喜欢乘汽车。B(x)：x喜欢骑自行车。论域是{人}。 (?x) (F(x)→┐C(x))，(?x) (C(x)∨B(x))，(?x)┐B(x) ? (?x)┐F(x) 证明：
(1) (?x)┐B(x) P (2) ┐B(a) ES(1)
(3) (?x) (C(x)∨B(x)) P (4) C(a)∨B(a) US(3) (5) C(a) T(2)(4) I (6) (?x) (F(x)→┐C(x)) P (7) F(a)→┐C(a) US(6) (8) C(a) →┐F(a) T(7) E (9) ┐F(a) T(5)(8) I (10) (?x)┐F(x) EG(9)
（2）Q(x)：x是有理数。W(x)：x是无理数。D(x)：x能表示成分数。
┐(?x)(W(x)∧D(x))，(?x)(Q(x)→D(x))?(?x)(Q(x)→┐W(x)) 证明：
(1) ┐(?x)(W(x)∧D(x)) P (2) (?x)┐(W(x)∧D(x)) T(1) E (3) (?x) (W(x)→┐D(x)) T(2 E (4) W(a)→┐D(a) US(3) (5) D(a)→┐W(a) T(4) E (6) (?x)(Q(x)→D(x)) P (7) Q(a)→D(a) US(6) (8) Q(a)→┐W(a) T(5)(7) I (9) (?x)(Q(x)→┐W(x)) UG(8)
（3）O(x)：x是奇数。E(x)：x是偶数。D(x)：x能被2整除。论域为{自然数}。
← D(x))，┐(?x)D(x)?(?x)O(x) (?x)(O(x) E(x))，(?x)(E(x)←∣→→
证明：
(1) ┐(?x)D(x) P (2) (?x) ┐D(x) T(1) E (3) ┐D(a) ES(2)
D(x)) (4) (?x)(E(x)← P → D(a) (5) E(a)← US(4) →
(6) ┐E(a) T(3)(5) I
←(7) (?x)(O(x) E(x)) P ∣→←(8) O(a) E(a) US(7) ∣→
(9) O(a) T(6)(8) I (10) (?x)O(x) EG(9)
（4）S(x)：x是三角函数。D(x)：x是周期函数。H(x)：x是连续函数。论域是{函数}。 (?x) (S(x)→D(x))，(?x)(S(x)∧H(x)) ?(?x)(D(x)∧H(x)) 证明：
(1) (?x)(S(x)∧H(x)) P (2) S(a)∧H(a) ES(1) (3) S(a) T(2) I (4) H(a) T(2) I (5) (?x) (S(x)→D(x)) P (6) S(a)→D(a) US(5) (7) D(a) T(3)(6) I (8) D(a)∧H(a) T(4)(7) I
(9) (?x)(D(x)∧H(x)) EG(8)
（5）S(x)：x是科学家。D(x)：x是勤奋的。H(x)：x是身体健康的。C(x)：x是成功的。论域是{人}。 (?x) (S(x)→D(x))，(?x) (D(x)∧H(x)→C(x))，(?x)(S(x)∧H(x)) ? (?x)C(x)∨(?x)┐C (x) 证明：
(1) (?x)(S(x)∧H(x)) P (2) S(a)∧H(a) ES(1) (3) S(a) T(2) I (4) H(a) T(2) I (5) (?x) (S(x)→D(x)) P (6) S(a)→D(a) US(5) (7) D(a) T(3)(6) I (8) (?x) (D(x)∧H(x)→C(x)) P (9) D(a)∧H(a)→C(a) US(8) (10) C(a) T(4)(7) (9) I (11) (?x)C(x) EG(10) (12) (?x)C(x)∨(?x)┐C (x) T(11) I
习题三
1. 分别用描述法和列举法表示下列集合：
(1) 非负偶数集；
(2) 整数24的全部正因子的集合；
(3) 不超过9且与9互质的正整数集合（该集合的元素个数称欧拉函数? (9)）。 解： 描述法
（1）{x|x是非负偶数} （2）{x|x是24的正因子}
（3）{x| x是不超过9且与9互质的正整数} 列举法
（1）{0,2,4,…}
（2）{1,2,3,4,6,8,12,24} （3）{1,2,4,5,7,8}
2. 是否存在集合A和B，使得A?B且A?B？若存在，请举一例。 解：存在。A={1}，B={1,{1}}，则A?B且A?B均成立。 3. 求下列集合的幂集： （1）?； （2）{?}； （3）{a,{a}}； （4）{{1,2}}。 解：
（1）P(?)={?}
（2）P({?})={?,{?}}
（3）P({a,{a}})={?,{a},{{a}},{a,{a}}}
（4）P({{1,2}})={?,{{1,2}}} 4. 设S = {0, 1}，求集合S×P(S)。 解：
P(S)={?,{0},{1},{0,1}}
S×P(S)={< 0, ?>, <0, {0}>,<0, {1}>,<0, {0,1}>,<1, ?>,<1, {0}>,<1, {1}>,<1, {0,1}>} 5. 证明：对任意集合A，B都有
P(A)∩P(B)＝P(A∩B)，P(A)∪P(B)?P(A∪B) 并举例说明，一般P(A)∪P(B)≠P(A∪B)。 证明：
对任意的集合C，若 C∈P(A)∩P(B)?C∈P(A)∧C∈P(B)?C?A∧C?B?C?A∩B 所以P(A)∩P(B)＝P(A∩B)成立。
对任意的集合C，若 C∈P(A)∪P(B)?C∈P(A)∨C∈P(B)?C?A∨C?B?C?A∪B 所以P(A)∪P(B)?P(A∪B)成立。
举例：A={1,2}，B={2,3}，P(A)={ ?，{1}，{2}，{1,2}}，P(B)={ ?，{2}，{3}，{2,3}}， P(A)∪P(B)={ ?，{1}，{2}，{1,2}，{3}，{2,3}}，
A∪B={1,2,3}，P(A∪B)= { ?，{1}，{2}，{1,2}，{3}，{2,3}，{1,3}，{1,2,3}}。 所以，P(A)∪P(B)≠P(A∪B)。
6. 设A，B，C是任意集合，证明： （1）C∩(A?B)=(C∩A)?(C∩B)；
（2）已知A∩B?B∩C，且有A-B?B-C，则A?B。 证明：
（1）C∩(A?B)
=C∩((A－B)∪(B－A))=(C∩(A－B))∪(C∩(B－A))
= ((C∩A)－(C∩B))∪((C∩B)－(C∩A))=(C∩A)?(C∩B)
（2）反证法。假设结论不成立，则存在x∈A，且x?B，则x∈A-B，x∈B-C，即x∈B。与x?B矛盾。
7. 确定下列关系具备哪些性质？
（1）当且仅当|i-k|<11(i, k?Z)时，有iRk； （2）当且仅当mn>8(m, n?N)时，有mRn； （3）当且仅当i≤k(i, k?N)时，有iRk。 解：
（1）自反，对称 （2）对称
（3）自反，对称，传递
8. 请在集合A＝{a,b,c}上分别构造满足下述要求的二元关系： （1）既是对称又是反对称的； （2）既不自反也不反自反； （3）对称且自反；
（4）自反,对称且传递；
（5）以{
（1）{