Faculty of Information and Communication Technology
FORMATIVE ASSESSMENT 1
MODULE NAME:
Discrete Structures / History of Computing and Info Models
I declare that I am familiar MODULE CODE:
DCT115D DCTF15D HSP115D
with, and will abide to the
Examination rules of Tshwane Duration: 2 hours Examiner:
University of Technology Date: August 2022 Ms. L Cronjé
Total Marks: 62
Full Marks: 60
(2 bonus marks) Moderator:
Total pages: 9 pages Ms. E Rynners
_____________________ Student number
Signature
Surname: Initials: Mark (%):
Instructions:
• Answer ALL questions, show all steps.
• Use the spaces provided to answer each question.
• Write legibly in blue or black PEN.
• Round to 2 decimal places, where applicable
• See Appendix for formulas and tables for logical
equivalences and rules of inference
Question 1 Logic and proofs [30]
1.1 Write down the logical expression of the following circuit: (6)
1.2 Using propositional equivalences, prove that: ¬[(𝑥 ∧ 𝑦) ∨ (¬𝑥 ∧ 𝑦)] ≡ ¬𝑦
(Show one step per line with a reason for the step) (6)
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 2
1.3 A set of premises and a conclusion is given. Use the rules of inference to deduce the conclusion
from the premises, giving a reason for each step. (8)
(i) 𝑆 ∧ ¬𝑃 → 𝑄
(ii) 𝑆
(iii) ¬𝑅 → ¬𝑄
(iv) ¬𝑃
(v) ∴ 𝑅 ∨ 𝐿
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 3
1.4 Prove, using Mathematical induction, for any 𝑛 ≥ 1, that
𝑛
5 + 8 + 11 + ⋯ + (2 + 3𝑛) = 2 [10 + 3(𝑛 − 1)] (10)
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 4
Question 2 Sets, functions and matrices [32]
2.1 Calculate the following
9
2.1.1 ( ) (2)
3
(𝑤−1)!
2.1.2 (3)
(𝑤+3)!
2.2 How many subsets of 6 elements can be made up of the set of lower case letters, ∴ {a, b, c, …, z}(4)
2.3 If 𝑓(𝑥) = 3√𝑥 − 1, find the inverse 𝑓 −1 (𝑦) (4)
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 5
1−𝑥
2.4 If 𝑓(𝑥) = and 𝑔(𝑥) = 𝑥 2 find 𝑓 ∘ 𝑔 and 𝑔 ∘ 𝑓 (4)
2
8
2.5 Write the following in expanded form and calculate: ∑𝑚=5(𝑚2 − 10) (4)
2.6 Write out the binomial expansion of: (5 − 𝑥)3 and calculate. (4)
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 6
1 −1 3 −1 4 2 0 −1
2.7 Given the following matrices: 𝐴 = [ ],𝐵 = [ ],𝐶 = [ ],
3 −2 2 −4 1 1 5 3
1 0 1 1
𝐷 = [0 1] , 𝑎𝑛𝑑 𝐸 = [1 0], find:
1 0 1 1
2.7.1 𝐴 − 3𝐵 (2)
2.7.2 𝐶𝐴 (3)
2.7.3 Meet of D and E (2)
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 7
Appendix
Logical Equivalences
Given any statement variables p, q, and r, a tautology t and a contradiction c, the following logical
equivalences hold.
1. Commutative laws: 𝑝⋀𝑞 ≡ 𝑞⋀𝑝 𝑝⋁𝑞 ≡ 𝑞⋁𝑝
2. Associative laws: (𝑝⋀𝑞)⋀𝑟 ≡ 𝑝⋀(𝑞⋀𝑟) (𝑝⋁𝑞)⋁𝑟 ≡ 𝑝⋁(𝑞⋁𝑟)
3. Distributive laws: 𝑝⋀(𝑞⋁𝑟) ≡ (𝑝⋀𝑞)⋁(𝑝⋀𝑟) 𝑝⋁(𝑞⋀𝑟) ≡ (𝑝⋁𝑞)⋀(𝑝⋁𝑟)
4. Identity laws: 𝑝⋀𝒕 ≡ 𝑝 𝑝⋁𝒄 ≡ 𝑝
5. Negation laws: 𝑝⋁¬𝑝 ≡ 𝒕 𝑝⋀¬𝑝 ≡ 𝒄
6. Double negative law: ¬(¬𝑝) ≡ 𝑝
7. Idempotent laws: 𝑝⋀𝑝 ≡ 𝑝 𝑝⋁𝑝 ≡ 𝑝
8. Universal bound laws: 𝑝⋁𝒕 ≡ 𝒕 𝑝⋀𝒄 ≡ 𝒄
9. De Morgan’s laws: ¬(𝑝⋀𝑞) ≡ ¬𝑝⋁¬𝑞 ¬(𝑝⋁𝑞) ≡ ¬𝑝⋀¬𝑞
10. Absorption laws: 𝑝⋁(𝑝⋀𝑞) ≡ 𝑝 𝑝⋀(𝑝⋁𝑞) ≡ 𝑝
11. Negations of t and c: ¬𝒕 ≡ 𝒄 ¬𝒄 ≡ 𝒕
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 8
Rules of Inference
Modus Ponens 𝑝→𝑞 Elimination a. 𝑝⋁𝑞 b. 𝑝⋁𝑞
𝑝 ¬𝑞 ¬𝑝
∴𝑞 ∴𝑝 ∴𝑞
Modus Tollens 𝑝→𝑞 Transitivity 𝑝→𝑞
¬𝑞 𝑞→𝑟
∴ ¬𝑝 ∴𝑝→𝑟
Generalization a. 𝑝 b. 𝑞 Proof by Division 𝑝⋁𝑞
∴ 𝑝⋁𝑞 ∴ 𝑝⋁𝑞 into Cases 𝑝→𝑟
Specialization a. 𝑝⋀𝑞 b. 𝑝⋀𝑞 𝑞→𝑟
∴𝑝 ∴𝑞 ∴𝑟
Conjunction 𝑝 Contradiction ¬𝑝 → 𝒄
𝑞 Rule ∴𝑝
∴ 𝑝⋀𝑞
𝑛
𝑛
(𝑎 + 𝑏) = ∑ ( ) 𝑎𝑛−𝑘 𝑏 𝑘
𝑛
𝑘
𝑘=0
DCT115D/DCTF15D/HSP115D FA1 2022 Semester 2 – August 2022 9