BCS Discrete Mathematics 1 — Questions and Answers
Question 1: Which of the following is the correct definition of a bijective function?
- A function that is injective but not surjective
- A function that is both injective and surjective (Correct answer)
- A function that maps multiple inputs to the same output
- A function that is surjective but not injective
Correct answer: A function that is both injective and surjective
A bijective function is one that is both injective (one-to-one) and surjective (onto), establishing a perfect one-to-one correspondence between domain and codomain.
Question 2: What is the value of the expression ¬(P ∧ Q) when P = True and Q = False?
- True (Correct answer)
- False
- Undefined
- Both True and False
Correct answer: True
P ∧ Q = True ∧ False = False, and ¬False = True, so the expression evaluates to True.
Question 3: How many edges does a complete graph K_5 have?
- 5
- 8
- 10 (Correct answer)
- 20
Correct answer: 10
A complete graph K_n has n(n-1)/2 edges; for K_5, that is 5×4/2 = 10 edges.
Question 4: Which proof technique assumes the negation of what you want to prove and derives a contradiction?
- Direct proof
- Proof by induction
- Proof by contradiction (Correct answer)
- Proof by contrapositive
Correct answer: Proof by contradiction
Proof by contradiction (reductio ad absurdum) assumes ¬P is true and then logically derives a contradiction, thereby proving P must be true.
Question 5: What is the cardinality of the power set of a set with 4 elements?
- 4
- 8
- 16 (Correct answer)
- 12
Correct answer: 16
The power set of a set with n elements has 2^n subsets; for n=4, that is 2^4 = 16.
Question 6: Which of the following recurrence relations describes the Fibonacci sequence?
- F(n) = F(n-1) + F(n-2) (Correct answer)
- F(n) = 2·F(n-1)
- F(n) = F(n-1) × F(n-2)
- F(n) = F(n-1) - F(n-2)
Correct answer: F(n) = F(n-1) + F(n-2)
The Fibonacci sequence is defined by F(n) = F(n-1) + F(n-2) with base cases F(0)=0 and F(1)=1.
Question 7: A relation R on set A is said to be an equivalence relation if it is:
- Reflexive, symmetric, and transitive (Correct answer)
- Reflexive and transitive only
- Symmetric and transitive only
- Reflexive and antisymmetric
Correct answer: Reflexive, symmetric, and transitive
An equivalence relation must satisfy all three properties: reflexivity (aRa), symmetry (aRb ⟹ bRa), and transitivity (aRb ∧ bRc ⟹ aRc).
BCS Discrete Mathematics 1
Which of the following is the correct definition of a bijective function?