⑴并非每个实数都是有理数。 ⑵没有不犯错误的人。
⑶并不是所有的兔子都比所有的乌龟跑得快。 25说明下列各式量词的辖域，找出约束变元和自由变元。
⑴ (?x)P(x)→Q(y) ⑵ (?x) (P(x)∧(?y)Q(x,y)) ⑶ (?x) P(x)∧(?y)Q(x,y)
⑷ (?x)(?y)(P(x,y)∧Q(y,z))? (?x) R(x,y) ⑸ (?x) P(x)∨R(x,y)
26对(?x)(?y)(P(x,y)∧Q(y,z))?(?x) R(x,y)中的约束变元y换名。 27对(?x)(P(y)∧R(x,y))→(?y)Q(y) 中的自由变元y进行代入。 28证明：
⑴(?x)(A(x)→B)?(?x)A(x)→B
⑵(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x) ⑶(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) 29求公式(?x)F(x)→(?x)G(x) 的前束范式。
30将((?x)F(x)∨(?x)G(x))→(?x)(F(x)∨G(x))化为与其等价的前束合取范式。 31证明：苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。 32证明：(?x)(H(x)→M(x))，(?x)H(x)?(?x)M(x)。 33证明：(?x)(A(x)∨B(x))，(?x)?A(x)?(?x)B(x)。
34用CP规则证明：(?x)(F(x)∨G(x))?(?x)F(x)∨(?x)G(x)。
35设个体域为全总个体域。证明推理：学术会的成员都是工人并且是专家。有些成员是青年人。所以有的成员是青年专家。
第13页 共53页
第二章 集合
2.1 集合论的基本概念
1. 用列举法表示下列集合： (a) 小于20的质数集合； (b) 构成evening的字母集合； (c) {x|x2?x?6?0}。 2. 列出下列集合的成员： (a) {x|x是36的因子}； (b) {x|x?a?x?b}。
3. 证明：若a,b,c,d是任意客体，则{{a},{a,b}}?{{c},{c,d}}当且仅当a?c和b?d。 4. 列举下列集合的全部子集： (a) {?}； (b) {?,{?}}； (c) {{?,a},{a}}；
(d) {{a,b},{a,a,b},{b,a,b}}。
5. 设A,B,C是集合，证明或否定以下断言： (a) [A?B?B?C]?A?C； (b) [A?B?B?C]?A?C； (c) [A?B?B?C]?A?C。 6. 确定下列各命题的真和假： (a) ???； (b) ???；
(c) {a,b}?{a,b,c,{a,b,c}}； (d) {a,b}?{a,b,{{a,b}}}。
2.2 集合上的运算
7. 给定自然数集合N的下列子集：
第14页 共53页
A?{1,2,7,8}B?{i|i2?50}C?{i|i可被30整除}D?{i|i?2k?k?I?0?k?6}
求出下列集合 (a) A(B(C(b) A(B(CD))； D))；
(c) B?(AC)。
8. 设x和y是实数，定义运算xy是x（x的y次幂） (a) 证明运算既非可交换的也非可结合的。
(b) 设?代表乘法运算，确定下列分配律哪些是成立的：
(i) x?(yz)?(x?y)(x?z)；
（y?z)x?(yx)?(zx)。 (ii)
y9. 设A,B,C是任意集合，把ABC表示成不相交集合之并。
10. (a) 证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，
使A?B?B?A；
(b) A?B?B?A可能吗？刻画此式出现的全部条件； (c) “相对补”是一个可结合的运算吗？证明你的断言。 11. 设A,B,C是论述域U的任意子集，证明下列各式： (a) A(B?A)??；
(b) A?(BC)?(A?B)(A?C)； (c) A?(BC)?(A?B)(A?C)。
12. 证明A?B，AB，AB??三者是等价的。 13. 在下列命题中找出
S?CS和
S?CS：
(a) C?{?}； (b) C?{?,{?}}； (c) C?{{i}|i?I}。
14. 设C是一非空的某论述域U的子集的搜集，B是U的子集，证明下列分配律的推广：
___(a)
S?CS＝S?CS；
第15页 共53页
___(b)
S?CS?S?CS。
15. 指出下列集合的幂集合： (a) {a,b,c}；(b) {{a,b},{c}}。 16. 证明下列各式： (a) A?A?B?B； (b) (A?B)?B?AB； (c) C(A?B)?(C
A)?(CB)。
2.1 归纳法和自然数
17. 对下列集合给出归纳定义：
(a) 十进制无符号整数集合，定义集合将包含6，235，0045等等；
(b) 十进制的以小数部分为结束的实数集合，定义的集合包含5.3，453.，01.2700，0.480； (c) 二进制形式的不以0开头的正偶数和0组成的集合，定义的集合包含0,110,1010等； (d) 把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如
[],[[]],[][],[[[]][]]等都是成形括号串（例中用[]代（）是为了明晰），试定义成形括号串集合。
18. 用{a}代替N的定义中的?，但仍用这一定义，可否生成自然数集合？有何不同？ 19. 证明成形括号串的左右括号个数相等。
20. 我们有3分和5分两种不同票值的邮票，试证明用这两种邮票就足以组成8分或者更多
的任意邮资。
21. 用归纳法证明：对一切n?I?，(1?2?22. 对所有n?N，证明下列每一关系式： (a) ?i2?n(n?1)(2n?1)/6；
i?0nn?n)2?13?23??n3。
(b) ?(2i?1)?(n?1)2；
i?0n(c) ?i(i!)?(n?1)!?1；
i?0第16页 共53页
