1、下列说法正确的是：
(a) 命题 (p !q) ! r 在逻辑上等价于 (p _ q) _ r。
(b) 命题 q \$ (p !:q) 在逻辑上暗指 :q。
(c) 命题 (q !r) ! :(:r !:q) 是一个矛盾。
(d) 命题 (p ! (q !r)) ！ ((p !q) ! (p !r)) 是同义反复。
[1 分]

2.设n>1为正整数，设a； b 是整数。

(a) 如果 a b (mod n)，则对于每个正整数 m，am bm (mod n)。
(b) 如果 a + b 0 (mod n)，那么对于某个整数 k，b = kn + a。
(c) 如果ab 0 (mod n)，并且n j a，则n j b。
(d) 如果 a b (mod n)，则 a b (mod n2
[1 分]

3. 设 A 是一个大小为 3 的集合。设 P 表示 A 的所有子集的集合。

G 有多少度为 0 的顶点？
(a) 23
(b) 4
(c) 1
(d) 3
[1 分]

4. 设 T 是一棵完全二叉树，其中每个内部节点恰好有两个孩子。

(a) 49
(b) 25
(c) 99
(d) 101
[1 分]

5. 设 S = f000； 111; 11010; 111000； 1100 克。考虑等价关系
R 定义在 S 上使得 sRt 如果 s 和 t 具有相同数量的 1。

(a) 5
(b) 2
(c) 3
(d) 4
[1 分]

Multiple choice.
Place answers in order on the rst page of your answer booklet (do not write them here!)
1. Which of the following is true:
(a) The proposition (p ! q) ! r is logically equivalent to (p _ q) _ r.
(b) The proposition q \$ (p ! :q) logically implies :q.
(c) The proposition (q ! r) ! :(:r ! :q) is a contradiction.
(d) The proposition (p ! (q ! r)) ! ((p ! q) ! (p ! r)) is a tautology.
[1 marks]

2. Let n > 1 be a positive integer and let a; b be integers.
Which of the following must be true?
(a) If a  b (mod n), then am  bm (mod n) for every positive integer m.
(b) If a + b  0 (mod n), then b = kn + a for some integer k.
(c) If ab  0 (mod n), and n j a, then n j b.
(d) If a  b (mod n), then a  b (mod n2
[1 marks]

3. Let A be a set of size 3. Let P denote the collection of all subsets of A.
Let G be a graph whose vertex set is P; two vertices in G are adjacent if and only if
the intersection of their corresponding subsets contains exactly two elements.
How many vertices of degree 0 does G have?
(a) 23
(b) 4
(c) 1
(d) 3
[1 marks]

4. Let T be a full binary tree in which every internal node has precisely two children.
The tree has 100 leaf nodes. How many internal nodes are there in T?
(a) 49
(b) 25
(c) 99
(d) 101
[1 marks]

5. Let S = f000; 111; 11010; 111000; 1100g. Consider the equivalence relation
R de ned on S such that sRt if s and t have the same number of 1s.
How many equivalence classes does this relation partition S into?
(a) 5
(b) 2
(c) 3
(d) 4
[1 marks]