COMP2121_1B-Assignment1
File description: Assignment 1 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
Document status: FIN
Last modified: 2026-09-11 21:12 HKT
COMP2121 Discrete Mathematics
25/26 Semester 1
Assignment 1 (Proposed Solutions)
SHING, Zhan Ho Jacob 3036228892
To distinguish, tautologies are represented as a bold T (𝑻), and contradictions a bold F (𝑭).
1. Let 𝐶 be the statement “Lady Furina has clues”, 𝑀 be the statement “Lady Furina has a motive”, 𝑆 be the statement “Lady Furina
solves the case” and 𝑇 be the statement “The truth is revealed”.
(a) Translate (𝐶 ∧ ¬𝑀) → ¬𝑆 into English.
Answers:
The statement translates to “If Lady Furina has clues and does not have motive, then she does not solve the case.”
(b) Rewrite the following sentence using logical operators: “The truth is revealed only if Lady Furina solves the case and has
clues.”
Answers:
The required logical expression is 𝑇 → (𝑆 ∧ 𝐶).
(c) Determine whether the argument
“If Lady Furina solves the case, then she has clues. The truth is not revealed unless she has clues. Therefore, if she
solves the case, the truth is revealed.”
is valid. Justify your answer.
Answers:
If we rewrite the argument in logical expressions, we have:
1. 𝑆 → 𝐶
2. ¬𝐶 → ¬𝑇
3. Therefore, from propositions 1 and 2, 𝑆 → 𝑇
For the argument to be valid, we require the conclusion (Proposition 3) is never false while all the premises (Propositions
1 and 2) are true. It can be verified by trying to find a counterexample, i.e., combinations of 𝑆, 𝐶, and 𝑇 such that the
conclusion is 𝑭 while all its premises are 𝑻.
For the conclusion to be 𝑭, the only possible case is when 𝑆 is 𝑻 and 𝑇 is 𝑭.
For Proposition 1 to be 𝑻 when 𝑆 is 𝑻, 𝐶 can only be 𝑻.
When 𝐶 is 𝑻 and 𝑇 is 𝑭, Proposition 2 is 𝑻.
Therefore, when 𝑆 is 𝑻, 𝐶 is 𝑻, and 𝑇 is 𝑭, all premises are 𝑻 but the conclusion is 𝑭, i.e., the argument is invalid.
2. In a town live three types of people: knights, who always tell the truth, knaves, who always lie, and spies, who sometimes tell the
truth and sometimes lie. You meet three individuals on the road and you know one of them is a knight, one is a knave and one
is a spy. However, the three persons are foreigners. They can understand English, but they can only say in their own language,
namely “Ja” and “Da”. You know they mean either “yes” or “no”, but you don’t know which means “yes” and which means “no”.
You ask A “If I asked you if B is the spy, would you say Ja?” A answers “Ja”.
Then you ask C “If I asked you if you were the knave, would you say Ja?” C answers “Ja”.
Finally, you ask C again “If I asked you if A is the spy, would you say Ja?” C answers “Da”.
According to the above information, can you determine who is the knight, who is the knave and who is the spy?
Answers:
The originally proposed solution was incorrect and is hence deleted. For copyright reasons, official solutions cannot be
provided here.
Page 1 of 10
Page 1 of 10
3. You are an experienced engineer who wants to design a new computer. A computer is composed of many logical gates, each
implements a logical operator. Therefore, your task is to implement every logical operator to realize universal computation. You
ask your assistant to buy some chips that integrates the basic logical gates inside, so that you can combine them to realize every
possible logical operator. Unfortunately, your assistant only bought you chips for NAND gate, which implements ¬(𝐴 ∧ 𝐵) for two
arbitrary inputs 𝐴 and 𝐵. This troubles you a lot, because you’ll have to implement other logical operators by yourself.
(a) Since you want to realize universal computation, first you have to decide how many different logical operators you have to
implement. For example, a 1-to-1 logical operator takes a 1-bit binary number 𝐴 ∈
{
0, 1
}
as input and 1-bit binary number
𝐵 ∈
{
0, 1
}
as output. There are four 1-to-1 logical operators in total. Two examples are IDENTITY (𝐵 = 𝐴) and NOT
(𝐵 = ¬𝐴).
A 2-to-1 logical operator takes two 1-bit binary numbers 𝐴, 𝐵 ∈
{
0, 1
}
as input and outputs 𝐶 ∈
{
0, 1
}
. Determine the total
number of possible 2-to-1 logical operators.
Answers:
Note that for two inputs 𝐴 and 𝐵, there are four possible combinations, i.e., (𝐴, 𝐵) ∈ {(0, 0), (0, 1), (1, 0), (1, 1)}. A
logical operator is a function 𝑓 that maps the combinations of inputs to an output, i.e., 𝑓 : {0, 1}
2
→ {0, 1}. Consider
the truth table of 𝑓 :
𝑨 𝑩 𝑪 = 𝒇 (𝑨, 𝑩)
0 0 𝑓 (0, 0)
0 1 𝑓 (0, 1)
1 0 𝑓 (1, 0)
1 1 𝑓 (1, 1)
Two logical operators 𝑓 and 𝑔 are said to be the same if and only if for all combinations of inputs, 𝑓 ( 𝐴, 𝐵) = 𝑔(𝐴, 𝐵).
Therefore, the problem reduces to counting the number of different ways to fill the truth table, which is given by 2
4
= 16.
Therefore, there are 16
possible 2-to-1 logical operators.
(b) Even though there are many different logical operators, you found that you can implement all of them using only NAND
operators. Please implement NOT, OR, AND, XOR, IMPLIES operators using NAND only. For simplicity, you may write, e.g.,
¬( 𝐴 ∧ 𝐵) as NAND( 𝐴, 𝐵).
[Hint: here’s an example of using NOR to implement NOT: NOT(𝐴) ≡ NOR( 𝐴, 𝐴), since ( 𝐴 ∨ 𝐴) ≡ 𝐴.]
Answers:
• NOT operator
Note that NAND( 𝐴, 𝐴) ≡ ¬( 𝐴 ∧ 𝐴) ≡ ¬𝐴 ∨ ¬𝐴 ≡ ¬𝐴.
Therefore, the NOT operator is implemented as NOT( 𝐴) = NAND( 𝐴, 𝐴) .
• OR operator
Note that ¬(¬𝐴 ∧ ¬𝐵) ≡ 𝐴 ∨ 𝐵, which means OR(𝐴, 𝐵) = NAND(NOT(𝐴), NOT(𝐵)).
Further expand the NOT operators as implemented before, we have: OR( 𝐴, 𝐵) = NAND
[
NAND( 𝐴, 𝐴), NAND(𝐵, 𝐵)
]
.
• AND operator
Note that if we apply NAND on the result of NAND( 𝐴, 𝐵), we have:
¬
[
¬
(
𝐴 ∧ 𝐵
)
∧ ¬
(
𝐴 ∧ 𝐵
)]
≡
(
𝐴 ∧ 𝐵
)
∨
(
𝐴 ∧ 𝐵
)
≡ 𝐴 ∧
(
𝐵 ∨ 𝐵
)
≡ 𝐴 ∧ 𝐵
Therefore, the AND operator is implemented as AND
(
𝐴, 𝐵
)
= NAND
(
NAND
(
𝐴, 𝐵
)
, NAND
(
𝐴, 𝐵
))
.
• XOR operator
Recall that 𝐴 ⊕ 𝐵 ≡ (𝐴 ∨ 𝐵) ∧ ¬( 𝐴 ∧ 𝐵). From this expression, we continue to derive:
( 𝐴 ∨ 𝐵) ∧ ¬( 𝐴 ∧ 𝐵) ≡ ( 𝐴 ∧ ¬( 𝐴 ∧ 𝐵)) ∨ (𝐵 ∧ ¬( 𝐴 ∧ 𝐵)) (Distributive Law)
≡ ¬[¬( 𝐴 ∧ ¬( 𝐴 ∧ 𝐵)) ∧ ¬(𝐵 ∧ ¬( 𝐴 ∧ 𝐵))] (De Morgan’s Law)
≡ NAND
(
NAND
(
𝐴, NAND
(
𝐴, 𝐵
))
, NAND
(
𝐵, NAND
(
𝐴, 𝐵
)))
Therefore, XOR is implemented as XOR
(
𝐴, 𝐵
)
= NAND
(
NAND
(
𝐴, NAND
(
𝐴, 𝐵
))
, NAND
(
𝐵, NAND
(
𝐴, 𝐵
)))
.
Page 2 of 10
Page 2 of 10
• IMPLIES operator
By logical equivalence, we have 𝐴 → 𝐵 ≡ ¬𝐴 ∨ 𝐵.
Expand the expression, we have:
¬𝐴 ∨ 𝐵 ≡ OR
(
NOT
(
𝐴
)
, 𝐵
)
≡ NAND
(
𝐴, NOT
(
𝐵
))
≡ NAND
(
𝐴, NAND
(
𝐵, 𝐵
))
Therefore, IMPLIES is as IMPLIES
(
𝐴, 𝐵
)
= NAND
(
𝐴, NAND
(
𝐵, 𝐵
))
.
4. Quantifiers and Predicates
(a) Rewrite expression ¬(∃𝑦¬(∀𝑥(𝑃(𝑥) ∧ 𝑄 (𝑦))) → ∃𝑧𝑅(𝑧)) so that all the negation signs immediately precedes predicates.
Answers:
¬[∃𝑦¬{∀𝑥 [𝑃(𝑥) ∧ 𝑄(𝑦)]} → ∃𝑧𝑅(𝑧)] ≡ ¬[∃𝑦∃𝑥 [¬𝑃(𝑥) ∨ ¬𝑄(𝑦)] → ∃𝑧𝑅(𝑧)]
≡ ¬[¬{∃𝑥∃𝑦[¬𝑃(𝑥) ∨ ¬𝑄(𝑦)]} ∨ ∃𝑧𝑅(𝑧)]
≡ ¬[∀𝑥∀𝑦[𝑃(𝑥) ∧ 𝑄 (𝑦)] ∨ ∃𝑧𝑅(𝑧)]
≡ ¬[(∀𝑥𝑃(𝑥) ∧ ∀𝑦𝑄 (𝑦)) ∨ ∃𝑧𝑅(𝑧)]
≡ ¬(∀𝑥𝑃(𝑥) ∧ ∀𝑦𝑄 (𝑦)) ∧ ∀𝑧¬𝑅(𝑧)
≡ [∃𝑥¬𝑃(𝑥) ∨ ∃𝑦¬𝑄(𝑦)] ∧ ∀𝑧¬𝑅(𝑧)
(b) Consider the two predicates 𝑃(𝑥) and 𝑄(𝑥) with the same universe of discourse.
Prove that ∀𝑥𝑃(𝑥) ∧ ∃𝑥𝑄(𝑥) ≡ ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄(𝑦)).
Proof:
Rename the variable on the left-hand side, we have:
∀𝑥𝑃(𝑥) ∧ ∃𝑦𝑄(𝑦) ≡ ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄(𝑦))
To prove equivalence, we prove both the sufficiency and necessity.
1. Sufficiency: ∀𝑥𝑃(𝑥) ∧ ∃𝑦𝑄 (𝑦) ⇒ ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄(𝑦))
Assume that the L.H.S. is true, then for all 𝑥, 𝑃(𝑥) must hold. Also, there must exist at least one 𝑦, say 𝑦
0
, such
that 𝑄 (𝑦
0
) holds. Therefore, for all 𝑥, we can always find a 𝑦, which is 𝑦
0
, such that 𝑃(𝑥) ∧ 𝑄 (𝑦) holds. We have
displayed that the R.H.S. must be true if the L.H.S. is true.
2. Necessity: ∀𝑥𝑃(𝑥) ∧ ∃𝑦𝑄(𝑦) ⇐ ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄 (𝑦))
Assume that the R.H.S. (i.e., ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄(𝑦))) is true, then for all 𝑥, we can always find a 𝑦, say 𝑦
0
, such that
𝑃(𝑥) ∧ 𝑄 (𝑦
0
) holds. Therefore, for all 𝑥, 𝑃(𝑥) must hold, and there must exist at least one 𝑦, which is 𝑦
0
, such
that 𝑄(𝑦
0
) holds. We have displayed that the L.H.S. must be true if the R.H.S. is true.
Since both the sufficiency and necessity have been proved, we conclude that ∀𝑥𝑃(𝑥) ∧ ∃𝑥𝑄(𝑥) ↔ ∀𝑥∃𝑦(𝑃(𝑥) ∧ 𝑄(𝑦))
is a tautology, i.e., the two statements are logically equivalent.
Q.E.D.
(c) Justify whether ∃𝑥∀𝑦𝑃(𝑥, 𝑦) → ∀𝑦∃𝑥𝑃(𝑥, 𝑦) is always a tautology for any predicate 𝑃(𝑥, 𝑦).
Answers:
We propose that the given proposition is not always a tautology, and we attempt to find an example, such that the
proposition is a contradiction.
Page 3 of 10
Page 3 of 10
∃𝑥∀𝑦𝑃(𝑥, 𝑦) → ∀𝑦∃𝑥𝑃(𝑥, 𝑦) is a contradiction iff ∃𝑥∀𝑦𝑃(𝑥, 𝑦) is 𝑻 and ∀𝑦∃𝑥𝑃(𝑥, 𝑦) is 𝑭.
If the antecedent is true, then, for at least one 𝑥, say 𝑥
0
, 𝑃(𝑥
0
, 𝑦) holds for all 𝑦.
If the consequent is false, then, for at least one 𝑦, say 𝑦
0
, there does not exist any 𝑥 such that 𝑃(𝑥, 𝑦
0
) holds.
However, if 𝑃(𝑥
0
, 𝑦) holds for all 𝑦, then 𝑃(𝑥
0
, 𝑦
0
) must also hold. Therefore, such 𝑦
0
does not exist, and the consequent
can never be false if the antecedent is true.
Therefore, we cannot find a counterexample such that the antecedent is true while the consequent is false. Hence, the
given proposition is always a tautology.
5. Proofs
(a) Consider the following proof that uses logical equivalence/implication:
∀𝑥(¬𝑃(𝑥) → 𝑄(𝑥)) ∧ ∀𝑦¬𝑄(𝑦) ≡ ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) ∧ ∀𝑦¬𝑄(𝑦) (1)
≡ ∀𝑥[(𝑃(𝑥) ∧ 𝑄(𝑥)) ∨ ¬𝑄(𝑥)] (2)
≡ ∀𝑥[𝑃(𝑥) ∧ ¬𝑄(𝑥)] (3)
⇒ ∀𝑥𝑃(𝑥) (4)
⇒ ∃𝑥𝑃(𝑥). (5)
Determine whether the proof is corrct.
Answers:
Step 1: Valid. This is implication law (𝑃 → 𝑄 ≡ ¬𝑃 ∨ 𝑄).
Step 2: Valid. Renaming the variable 𝑥 to 𝑦 does not change the meaning of the statement. This is also the distribution
law of ∀ over ∧ – ∀𝑥𝑃(𝑥) ∧ ∀𝑦𝑄(𝑦) ≡ ∀𝑥(𝑃(𝑥) ∧ 𝑄(𝑥)).
Step 3: Valid. This step combines application of several laws:
≡ ∀𝑥[(𝑃(𝑥) ∧ ¬𝑄(𝑥)) ∨ (𝑄(𝑥) ∧ ¬𝑄(𝑥))] (Distribution law)
≡ ∀𝑥[(𝑃(𝑥) ∧ ¬𝑄(𝑥)) ∨ 𝑭] (Contradiction law)
≡ ∀𝑥[𝑃(𝑥) ∧ ¬𝑄(𝑥)] (Identity law)
Step 4: Valid. This is the simplification (i.e., 𝑃 ∧ 𝑄 → 𝑃).
Step 5: Valid. First, since ∀𝑥𝑃(𝑥) is true, then 𝑃(𝑐) must be true for any 𝑐 in the universe of dicourse. Then, since there
exists at least one 𝑥, 𝑐 in this case, such that 𝑃(𝑥) is true, then ∃𝑥𝑃(𝑥) is true.
Therefore, the proof is sound and valid.
(b) Proof by induction that
𝑛
𝑘=1
cos(𝑘𝑥) =
1
2
©
«
sin
𝑛 +
1
2
𝑥
sin
1
2
𝑥
− 1
ª
®
®
¬
holds for all integers 𝑛 ≥ 1.
Proof:
Denote 𝑃(𝑛) :
𝑛
𝑘=1
cos(𝑘𝑥) =
1
2
©
«
sin
𝑛 +
1
2
𝑥
sin
1
2
𝑥
− 1
ª
®
®
¬
.
Base Case: 𝑛 = 1.
L.H.S. =
1
𝑘=1
cos(𝑘𝑥) = cos(𝑥)
R.H.S. =
1
2
sin
3
2
𝑥
sin
1
2
𝑥
− 1
Page 4 of 10
Page 4 of 10
=
1
2
sin
3
2
𝑥 − sin
1
2
𝑥
sin
1
2
𝑥
=
1
2
2 cos 𝑥 sin
1
2
𝑥
sin
1
2
𝑥
= cos 𝑥
= L.H.S.
Therefore, 𝑃(1) holds.
Inductive Step: Assume that 𝑃(𝑛) holds for 𝑛 ≥ 1. We show that 𝑃(𝑛 + 1) also holds.
L.H.S. =
𝑛+1
𝑘=1
cos(𝑘𝑥)
=
𝑛
𝑘=1
cos(𝑘𝑥) + cos
(
(𝑛 + 1)𝑥
)
= 𝑃(𝑛) + cos
(
(𝑛 + 1)𝑥
)
=
1
2
©
«
sin
𝑛 +
1
2
𝑥
sin
1
2
𝑥
− 1
ª
®
®
¬
+ cos
(
(𝑛 + 1)𝑥
)
=
1
2
©
«
sin
𝑛 +
1
2
𝑥
− sin
1
2
𝑥
sin
1
2
𝑥
ª
®
®
¬
+ cos
(
(𝑛 + 1)𝑥
)
=
1
2
2 cos
𝑛+1
2
𝑥
sin
𝑛
2
𝑥
sin
1
2
𝑥
+ cos
(
(𝑛 + 1)𝑥
)
=
cos
𝑛+1
2
𝑥
sin
𝑛
2
𝑥
+ cos
(
(𝑛 + 1)𝑥
)
sin
1
2
𝑥
sin
1
2
𝑥
=
sin
2𝑛+1
2
𝑥
− sin
1
2
𝑥 + sin
2𝑛+3
2
𝑥
− sin
2𝑛+1
2
𝑥
2 sin
1
2
𝑥
=
1
2
sin
2𝑛+3
2
𝑥
sin
1
2
𝑥
− 1
=
1
2
©
«
sin
(
𝑛 + 1
)
+
1
2
𝑥
sin
1
2
𝑥
− 1
ª
®
®
¬
= R.H.S.
Therefore, 𝑃(𝑛) ⇒ 𝑃(𝑛 + 1).
By the principle of mathematical induction, 𝑃(𝑛) holds for all 𝑛 ≥ 1.
Q.E.D.
Page 5 of 10
Page 5 of 10
(c) One day you are playing a card game with one friend. Suppose there are 191 cards in total. You and your friend take turns
to draw 1 to 5 cards once. The one who draws the last card will lose the game. Suppose you always draw the cards first, and
your friend is wise enough. Design a winning strategy and proof that you can always win.
Answers:
We may consider different cases at the end of the game. When 2 cards remain, and it is my turn to take cards, I can
take 1, and the opponent is left with 1 card, therefore losing the game. Similarly, when 3 cards remain, I can take 2 and
leave 1. This winning position goes on until there are 7 remaining cards, where, no matter how many cards I take, he
will be in the winning position as the case reduces to 1 to 6 remaining cards. Therefore, when the party who is left with
7 cards to draw must lose the game. When there are 8 cards remaining, I can take 1 card to reduce it to 7 and force my
opponent on the losing position. Similarly, when there are 9 remaining, I take 2, ..., until there are 12 remaining for
me and I take 5 to make it 7. Again, if I am left with 13 cards, no matter how many I take, it will reduce to 8 to 12
remaining cards, and my opponent can always make sure that I am left with 7 cards, thus losing.
From the above discussion, we can observe that if we can ensure the opponent is left with 6𝑛 + 1 cards to take where
𝑛 ∈ Z
+
, we can always win. Therefore, we can come up with this strategy:
Strategy: I first take 4 cards, so that the opponent is left with 191 − 4 = 187 = 6 × 31 + 1 cards. Suppose the opponent
then take 𝑝 ∈ [1, 5] cards in each round, I take (6 − 𝑝) cards, and repeat until the game ends.
Now we formally prove this strategy.
Proof:
Denote 𝑃(𝑛) : “When there are (6𝑛 + 1) cards remaining, the player who make a step from this state by taking 𝑝
cards must lose if the opponent takes (6 − 𝑝) cards.” We prove ∀𝑛 ≥ 1 : 𝑃(𝑛).
Base case: 𝑃(1) (i.e. 7 remaining cards). In the table below, the columns 𝑃 record number of cards taken by
the player making a move from the state of (6𝑛 + 1) cards, columns 𝑂 record the opponent. The numbers in the
brackets denote the cards remaining.
P O P Result of P
𝑷(1) : Case 1 1 (6) 5 (1) 1 (0) Lose
𝑷(1) : Case 2 2 (5) 4 (1) 1 (0) Lose
𝑷(1) : Case 3 3 (4) 3 (1) 1 (0) Lose
𝑷(1) : Case 4 4 (3) 2 (1) 1 (0) Lose
𝑷(1) : Case 5 5 (2) 1 (1) 1 (0) Lose
Therefore, regardless how many cards the player takes, he will always lose if the opponent is playing optimally.
Therefore, 𝑃(1) holds.
Inductive Step: Assume that for some 𝑘 ≥ 1, 𝑃(𝑘) holds. Consider 𝑃(𝑘 + 1), that is, we have [6(𝑘 + 1) + 1] cards
remaining. When compared with 𝑃(𝑘), we have [6(𝑘 + 1) + 1] − (6𝑘 + 1) = 6𝑘 + 7 − 6𝑘 − 1 = 6 more cards.
Observe that in each round, the player takes 𝑝 cards, and the opponent takes (6 − 𝑝) cards, removing a total of
𝑝 + (6 − 𝑝) = 6 cards. Then, after one round from 𝑃(𝑘 + 1), the number of remaining cards reduces by 6, reducing
the case back to 𝑃(𝑘), which is assumed to hold.
Therefore, we have 𝑃(𝑘) ⇒ 𝑃(𝑘 + 1).
By the principle of mathematical induction, 𝑃(𝑛) holds for all 𝑛 ≥ 1.
Now, integrate this 𝑃(𝑛) with our strategy. We first take away 4 cards, leaving 187 remaining cards, which
corresponds to the 𝑃(31) case. Since we have shown ∀𝑛 ≥ 1𝑃(𝑛), then 𝑃(31) must hold. And notice that after we
take the initial 4 cards, it is the opponent who starts to make a move from this state, therefore, the opponent must
lose, i.e., I must win.
Q.E.D.
Page 6 of 10
Page 6 of 10
6. Basics on Sets
(a) Determine the cardinality of the following sets:
(i) 𝐴 =
{{
0, 1
}
, 2, 3, ∅
}
(ii) The power set P (𝐵) of 𝐵 =
{
1, 2, ∅, |𝑥| = 2
}
(iii) The set 𝐶 =
𝑥 ∈ N | 𝑥
2
≤ 100
(Note that the set of natural numbers N includes zero).
(iv) The set 𝐷 =
{
𝑥 is a letter | 𝑥 does not appear in the word “artificial”
}
.
Answers:
(i)
|
𝐴
|
= 4
(ii)
|
P(𝐵)
|
= 2
|
𝐵
|
= 2
4
= 16 , provided that the set 𝐵 has two integers, one empty set, and one proposition.
(iii) Note that 𝐶 = [0, 10]. Therefore,
|
𝐶
|
= 11 .
(iv) Assuming that capital and small letters are the same, then
|
𝐷
|
= 26 − 7 = 19 .
(b) For 𝐴, 𝐵, 𝐶 in part a, determine the cardinalities of the following sets:
(i) 𝐴 ∩ 𝐵
(ii) 𝐵 ∪ (𝐶 ∩ ∅) − 𝐴
(iii) ( 𝐴 ∩ 𝐵) × (𝐵 ∩ 𝐶)
Answers:
(i) 𝐴 ∩ 𝐵 =
{
2, ∅
}
⇒
|
𝐴 ∩ 𝐵
|
= 2 .
(ii) Consider:
𝐵 ∪ (𝐶 ∩ ∅) − 𝐴 = 𝐵 ∪ ∅ − 𝐴
= 𝐵 − 𝐴
=
{
1, 2, ∅, |𝑥| = 2
}
−
{{
0, 1
}
, 2, 3, ∅
}
=
{
1, |𝑥 | = 2
}
⇒
|
𝐵 ∪ (𝐶 ∩ ∅) − 𝐴
|
= 2
(iii) Consider:
( 𝐴 ∩ 𝐵) × (𝐵 ∩ 𝐶) =
{
2, ∅
}
×
{
1, 2
}
=
{
(2, 1), (2, 2), (∅, 1), (∅, 2)
}
⇒
|
( 𝐴 ∩ 𝐵) × (𝐵 ∩ 𝐶)
|
= 4
Page 7 of 10
Page 7 of 10
7. Venn Diagrams
(a) Identify the set represented in the following figure:
𝐴
𝐵
𝐶
Answers:
The set represented in the figure is ( 𝐴 ∪ 𝐵) ∩ 𝐶.
(b) Draw Venn diagram for (𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐶).
Answers:
𝑈
𝐴
𝐵
𝐶
Page 8 of 10
Page 8 of 10
8. Set Theory and Logic
(a) Determine whether ∀ sets 𝐴, 𝐵, 𝐶, 𝐷 : ( 𝐴 ∩ 𝐵) × (𝐶 ∩ 𝐷) = ( 𝐴 × 𝐶) ∩ (𝐵 × 𝐷).
Answers:
To show that the two sets are equal, we show that whenever an element is in the L.H.S. set, it must also be in the R.H.S.
set, and vice versa.
Recall that 𝑥 ∈ ( 𝐴 ∩ 𝐵) ≡ (𝑥 ∈ 𝐴) ∧ (𝑥 ∈ 𝐵) and (𝑥, 𝑦) ∈ ( 𝐴 × 𝐵) ≡ (𝑥 ∈ 𝐴) ∧ (𝑦 ∈ 𝐵). Therefore, for L.H.S., we have:
(𝑥, 𝑦) ∈ ( 𝐴 ∩ 𝐵) × (𝐶 ∩ 𝐷) ≡ (𝑥 ∈ 𝐴 ∩ 𝐵) ∧ (𝑦 ∈ 𝐶 ∩ 𝐷)
≡ (𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵) ∧ (𝑦 ∈ 𝐶 ∧ 𝑦 ∈ 𝐷)
≡ 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐶 ∧ 𝑥 ∈ 𝐵 ∧ 𝑦 ∈ 𝐷 (Associative Law)
≡ (𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐶) ∧ (𝑥 ∈ 𝐵 ∧ 𝑦 ∈ 𝐷)
≡ (𝑥, 𝑦) ∈ (𝐴 × 𝐶) ∧ (𝑥, 𝑦) ∈ (𝐵 × 𝐷) (Definition of Cartesian Product)
≡ (𝑥, 𝑦) ∈ (𝐴 × 𝐶) ∩ (𝐵 × 𝐷)
Therefore, whenever we have (𝑥, 𝑦) ∈ ( 𝐴 ∩ 𝐵) × (𝐶 ∩ 𝐷), we must also have (𝑥, 𝑦) ∈ ( 𝐴 × 𝐶) ∩ (𝐵 × 𝐷), i.e., the two
sets are equal, and the given proposition holds for all sets 𝐴, 𝐵, 𝐶, 𝐷.
(b) Prove ∀ arbitrary sets 𝐴, 𝐵, 𝐶 : ( 𝐴 ∪ 𝐵) − 𝐶 = ( 𝐴 − 𝐶) ∪ (𝐵 − 𝐶).
Proof:
To proof the equality of two sets, we show that whenever an element is in the L.H.S. set, it must also be in the R.H.S.
set, and vice versa.
Recall the definitions that 𝑥 ∈ (𝐴 ∪ 𝐵) ≡ (𝑥 ∈ 𝐴) ∨ (𝑥 ∈ 𝐵) and 𝑥 ∈ ( 𝐴 − 𝐵) ≡ (𝑥 ∈ 𝐴) ∧ ¬(𝑥 ∈ 𝐵). Then, for L.H.S.,
we have
𝑥 ∈
[
( 𝐴 ∪ 𝐵) − 𝐶
]
≡ 𝑥 ∈ ( 𝐴 ∪ 𝐵) ∧ ¬(𝑥 ∈ 𝐶)
≡ (𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵) ∧ (𝑥 ∉ 𝐶)
≡ (𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐶) ∨ (𝑥 ∈ 𝐵 ∧ 𝑥 ∉ 𝐶)
≡ [𝑥 ∈ (𝐴 − 𝐶)] ∨ [𝑥 ∈ (𝐵 − 𝐶)]
≡ 𝑥 ∈ [( 𝐴 − 𝐶) ∪ (𝐵 − 𝐶)]
Hence, we have shown that the sets on L.H.S. and R.H.S. are equal. Since 𝐴, 𝐵, and 𝐶 are chosen to be arbitrary,
therefore the proposition also holds for any arbitrary sets.
Q.E.D.
Page 9 of 10
Page 9 of 10
9. Relations
(a) For the relation 𝑅
1
= {(𝑥, 𝑦) ∈ Z × Z | 𝑥 + 2𝑦 is an even number}, prove or disprove that 𝑅
1
is
(1) reflexive
Proof:
To verify reflexivity, we need to check whether 𝑥𝑅
1
𝑥, i.e., whether 𝑥 + 2𝑥 = 3𝑥 is an even number. Note that any
arbitrary even number can be expressed in the form of 2𝑛 for some 𝑛 ∈ Z.
Case 1: when 𝑥 is an even number, i.e., 𝑥 = 2𝑛. Then, we have 3𝑥 = 3(2𝑛) = 6𝑛 = 2(3𝑛), which is an even
number. Therefore, 𝑥𝑅
1
𝑥 holds when 𝑥 is an even number.
Case 2: when 𝑥 is an odd number, i.e., 𝑥 = 2𝑛 + 1. Then, we have 3𝑥 = 3(2𝑛 + 1) = 6𝑛 + 3 = 2(3𝑛 + 1) + 1, which
is an odd number. Therefore, 𝑥𝑅
1
𝑥 does not hold when 𝑥 is an odd number.
Having exhausted all the cases and shown that ∃𝑥 : (𝑥, 𝑥) ∉ 𝑅
1
, we conclude that 𝑅
1
is not reflexive .
Q.E.D.
(2) symmetric
Proof:
To verify symmetry, we need to check whether 𝑦𝑅
1
𝑥 whenever 𝑦𝑅
1
𝑥 for all 𝑥, 𝑦 ∈ Z.
Let 𝑥 be an arbitrary even number, i.e., 𝑥 = 2𝑛 for some 𝑛 ∈ Z, and 𝑦 be an arbitrary odd number, i.e., 𝑦 = 2𝑚 + 1
for some 𝑚 ∈ Z.
Then, for 𝑥𝑅
1
𝑦, we have 𝑥 + 2𝑦 = 2𝑛 + 2(2𝑚 + 1) = 2(𝑛 + 2𝑚 + 1), which is an even number, so 𝑥𝑅
1
𝑦 holds.
However, for 𝑦𝑅
1
𝑥, we have 𝑦 + 2𝑥 = (2𝑚 + 1) + 2(2𝑛) = 2(𝑚 + 2𝑛) + 1, which is an odd number, so 𝑦𝑅
1
𝑥 does
not hold.
Having found a counterexample such that (𝑥, 𝑦) ∈ 𝑅
1
but (𝑦, 𝑥) ∈ 𝑅
1
, we conclude that 𝑅
1
is not symmetric .
Q.E.D.
(3) transitive
Proof:
To verify transitivity, we need to check whether 𝑥𝑅
1
𝑧 whenever 𝑥 𝑅
1
𝑦 and 𝑦𝑅
1
𝑧 for all 𝑥, 𝑦, 𝑧 ∈ Z.
We can show this by contradiction. Assume that 𝑥 𝑅
1
𝑦 and 𝑦𝑅
1
𝑧 hold, but 𝑥𝑅
1
𝑧 does not hold. It implies that 𝑥 + 2𝑧
is an odd number. Note that since 2𝑧 must be even, then 𝑥 must be an odd number. For 𝑥𝑅
1
𝑦 to hold, 𝑥 + 2𝑦 must
be even, and when 𝑥 is odd, 2𝑦 must also be odd, which is impossible as 2𝑦 must be even for any integer 𝑦.
Therefore, our assumption is wrong, and we have shown that whenever 𝑥𝑅
1
𝑦 and 𝑦𝑅
1
𝑧 hold, 𝑥𝑅
1
𝑧 must also hold.
Hence, we conclude that 𝑅
1
is transitive .
Q.E.D.
(b) Determine correctness of a statement.
Answers:
The statement is not correct.
The logical fallacy is at the statement “Take an arbitrary 𝑏 such that 𝑎𝑅𝑏.” The statement assumes that such 𝑏 exists,
which is not necessarily true. Symmetry only ensures that if 𝑎𝑅𝑏 holds, then 𝑏𝑅𝑎 must also hold, but it does not ensure
that 𝑎𝑅𝑏 alone must hold.
Page 10 of 10
Page 10 of 10
This is the solutions that was submitted for COMP2121 (subclass 1B) Assignment 1 by the author.
The assignment was scored 93/100. The answers of question 2 were incorrect and are excluded in this document. As a result of copyright issues, the official solutions cannot be provided in this document. You are advised to consult other when in doubt.
Please note that there are often more than one way to solve the problems and the solutions provided here are not guaranteed to be the most optimal approach. They are provided for reference only.
This document will receive no further updates.
See also
-
COMP2121_1B-Assignment2
Assignment 2 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
-
COMP2121_1B-Assignment3
Assignment 3 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
-
CCCH9044-Individual-Essay
The 3000-word individual essay for the course CCCH9044.
-
CCGL9042-Question-Bank
The question bank for CCGL9042 in-class quizzes.
-
CCHU9094-Essay
Read the student submission of the essay to CCHU9094. This work has been graded A.
-
CCST9064-Video-Essay
The final video essay submitted for CCST9064 group project. Python code for Manim included.