DS-Assignment
UNIVERSITY OF SINDH
FACULTY OF ENGINEERING AND TECHNOLOGY
DISCRETE STRUCTURES (SE24-316)
BSSW PART-I (MORNING/EVENING)
Instructions:
1. This assignment contains 10 marks, and each student should submit it individually.
2. Submit your handwritten assignment on or before 29 November 2024. Late submissions
will not be accepted.
3. Assignment should be quoted properly.
4. Assignment should be precise. Do not add extra irrelevant material.
5. The first page should include:
• Your full name
• Roll number
• Subject name
• Submission date
• Teacher name
• Department
6. Answer all questions in sequence. Draw tables, diagrams or graphs wherever required.
7. Clearly label and highlight important points.
DS- Assignment
Assignment:
1. Verify if the following equivalence holds using truth tables:
• (𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ 𝑟) ≡ (¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ 𝑟)
• (p → r) ∧ (q → r) ≡ (p ∨ q) → r
2. Express the statement "If the light is on, then the room is not dark" in symbolic logic. Also,
write its contrapositive, converse, and inverse.
3. Which of these are propositions? What are the truth values of those that are propositions?
• Do not pass go.
• What time is it?
• There are no black flies in Maine.
• 𝑥 + 7 = 10, where 𝑥 is a variable.
4. Construct a combinational circuit using OR gates, and AND gates that produces the output
((¬𝑝 ∨ ¬𝑟) ∧ ¬𝑞) ∨ (¬𝑝 ∧ (𝑞 ∨ 𝑟)) from the input bits p, q and r.
5. Write a detailed definition of the following concepts along with examples:
a. Injective function
b. Surjective function
c. Bijective function
6. Show that each of these conditional statements is a tautology by using truth tables.
a) [¬p ∧ (p ∨ q)] → q
b) [(p → q) ∧ (q → r)] → (p → r)
c) [p ∧ (p → q)] → q
d) [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r
7. Define power set and cartesian product of set with examples. Let 𝐴 and 𝐵 be sets, using the
truth tables show that
a. (A ∩ B) ⊆ A
b. A ⊆ (A ∪ B)
c. A − B ⊆ A
d. A ∩ (B − A) = ∅
e. A ∪ (B − A) = A ∪ B
8. What is meant by composition of functions and why it is used.
Show that (𝑓 ∘ 𝑔)(𝑥) ≠ (𝑔 ∘ 𝑓)(𝑥) using an example of two functions 𝑓(𝑥) 𝑎𝑛𝑑 𝑔(𝑥).
9. Find (𝑓 ∘ 𝑓), (𝑔 ∘ 𝑔), (𝑓 ∘ 𝑔) and (𝑔 ∘ 𝑓) for the following:
• 𝑓(𝑥) = √𝑥 and 𝑔(𝑥) = 𝑥 2 + 1
• 𝑓(𝑥) = 2𝑥 − 3 and 𝑔(𝑥) = 5𝑥 + 1
10. Explain symmetric, reflexive and equivalence relation with examples. Let 𝐴 = {1,2,3} and
𝑅 = {(1,1), (2,2), (3,3), (1,2), (2,1)}. Check if 𝑅 is:
i. Reflexive
ii. Symmetric
iii. Anti-Symmetric
iv. Transitive
v. Equivalence
