离散数学代考 |Discrete Structures in Mathematics and Computer Science|COMPSCI 225

问题 1. 此页面上的问题不需要任何理由：只需回答。
将答案按顺序放在答案手册的第一页上（不要在这里写！）
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.

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.

3. 设 A 是一个大小为 3 的集合。设 P 表示 A 的所有子集的集合。
设 G 为顶点集为 P 的图； G 中的两个顶点相邻当且仅当
它们对应子集的交集正好包含两个元素。
G 有多少度为 0 的顶点？
(a) 23
(b) 4
(c) 1
(d) 3
[1 分]

问题 4.

4. 设 T 是一棵完全二叉树，其中每个内部节点恰好有两个孩子。
这棵树有 100 个叶节点。 T 中有多少个内部节点？
(a) 49
(b) 25
(c) 99
(d) 101
[1 分]

问题 5.

5. 设 S = f000； 111; 11010; 111000； 1100 克。考虑等价关系
R 定义在 S 上使得 sRt 如果 s 和 t 具有相同数量的 1。
这个关系把 S 分成多少个等价类？
(a) 5
(b) 2
(c) 3
(d) 4
[1 分]

问题 6.

Multiple choice.
No justication is needed for the problems on this page: just answers.
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]

问题 7.

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]

问题 8.

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]

问题 9.

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]

问题 10.

5. Let S = f000; 111; 11010; 111000; 1100g. Consider the equivalence relation
R dened 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]