BCS Discrete Mathematics 2 — Questions and Answers
Question 1: In propositional logic, which law states that P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)?
- Absorption law
- De Morgan's law
- Distributive law (Correct answer)
- Associative law
Correct answer: Distributive law
The distributive law in propositional logic allows OR to distribute over AND (and vice versa), giving P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).
Question 2: What is the greatest common divisor (GCD) of 48 and 36?
- 6
- 9
- 12 (Correct answer)
- 18
Correct answer: 12
Using the Euclidean algorithm: GCD(48, 36) = GCD(36, 12) = GCD(12, 0) = 12.
Question 3: Which of the following is a valid tautology?
- P ∧ ¬P
- P ∨ Q
- P → P (Correct answer)
- P ∧ Q
Correct answer: P → P
P → P (P implies P) is always true regardless of the truth value of P, making it a tautology.
Question 4: How many ways can 5 distinct books be arranged on a shelf?
- 25
- 60
- 120 (Correct answer)
- 720
Correct answer: 120
The number of permutations of 5 distinct objects is 5! = 5×4×3×2×1 = 120.
Question 5: In graph theory, what is a Hamiltonian path?
- A path that visits every edge exactly once
- A path that visits every vertex exactly once (Correct answer)
- The shortest path between two vertices
- A path that returns to the starting vertex
Correct answer: A path that visits every vertex exactly once
A Hamiltonian path visits every vertex in a graph exactly once; it does not need to return to the starting vertex.
Question 6: What does the principle of mathematical induction require as its two steps?
- Base case and recursive case
- Base case and inductive step (Correct answer)
- Hypothesis and conclusion
- Axiom and theorem
Correct answer: Base case and inductive step
Mathematical induction requires proving a base case (e.g., n=1 is true) and an inductive step (if true for n=k, then true for n=k+1).
Question 7: Which set operation produces elements that are in either set A or set B but not in both?
- Union (A ∪ B)
- Intersection (A ∩ B)
- Symmetric difference (A △ B) (Correct answer)
- Difference (A − B)
Correct answer: Symmetric difference (A △ B)
The symmetric difference A △ B contains all elements that belong to A or B but not to their intersection, formally (A ∪ B) − (A ∩ B).
BCS Discrete Mathematics 2
In propositional logic, which law states that P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)?