BSCS Discrete Mathematics and Logic 1 — Questions and Answers
Question 1: What is a proposition in propositional logic?
- A mathematical equation
- A statement that is either true or false (Correct answer)
- A function with boolean output
- A conditional branch in code
Correct answer: A statement that is either true or false
A proposition is a declarative statement that has a definite truth value — it is either true or false, not both.
Question 2: What does the logical connective ¬ (NOT) do?
- Combines two propositions with AND
- Negates the truth value of a proposition (Correct answer)
- Implies one proposition from another
- Checks equivalence of two propositions
Correct answer: Negates the truth value of a proposition
The NOT operator negates a proposition: if P is true, ¬P is false, and vice versa.
Question 3: What is the cardinality of the set {a, b, c, d}?
- 3
- 4 (Correct answer)
- 5
- 2
Correct answer: 4
The cardinality of a set is the number of elements it contains; {a, b, c, d} has 4 elements.
Question 4: Which of the following represents a tautology?
- P ∧ ¬P
- P ∨ Q
- P ∨ ¬P (Correct answer)
- P → Q
Correct answer: P ∨ ¬P
P ∨ ¬P is always true regardless of P's value — it is a tautology known as the Law of Excluded Middle.
Question 5: What is the Pigeonhole Principle?
- If n items are put into n+1 containers, at least one container has more than one item
- If n+1 items are put into n containers, at least one container has more than one item (Correct answer)
- Every set has at least one subset
- A recursive function must have a base case
Correct answer: If n+1 items are put into n containers, at least one container has more than one item
The Pigeonhole Principle states that if n+1 items are placed into n containers, at least one container must hold at least two items.
Question 6: What is a bijection (bijective function)?
- A function where every output has multiple inputs
- A one-to-one and onto (surjective and injective) function (Correct answer)
- A function mapping integers to real numbers
- A function with no inverse
Correct answer: A one-to-one and onto (surjective and injective) function
A bijection is both injective (one-to-one) and surjective (onto), establishing a perfect pairing between domain and codomain.
BSCS Discrete Mathematics and Logic 1
What is a proposition in propositional logic?