This set tests propositional and predicate logic, the starting point of every Discrete Mathematics course. You will work through truth tables, logical equivalences, tautologies and contradictions, negating quantified statements, translating English into predicate logic and spotting valid and invalid rules of inference. The questions match the level of GATE CS, university semester exams and UGC NET, and they also help in placement aptitude rounds that include logical reasoning.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Logical connectives and truth tables
- Tautology, contradiction and contingency
- Logical equivalences and functional completeness
- Quantifiers and their negation
- Translating English statements to predicate logic
- Rules of inference and common fallacies
Discrete Mathematics MCQs with answers and explanations
Q1. Which formula is logically equivalent to p → q?
a) ¬p ∨ q
b) p ∨ ¬q
c) ¬p ∧ q
d) q → p
Q2. What is the contrapositive of 'If a number is divisible by 6, then it is even'?
a) If a number is even, then it is divisible by 6
b) If a number is not even, then it is not divisible by 6
c) If a number is not divisible by 6, then it is not even
d) A number is divisible by 6 and it is not even
Q3. How many distinct Boolean functions (distinct truth tables) can be defined on 3 propositional variables?
a) 8
b) 64
c) 256
d) 512
Q4. Which of the following is a tautology?
a) (p → q) → (q → p)
b) (p ∨ q) → (p ∧ q)
c) (q ∧ (p → q)) → p
d) (p ∧ (p → q)) → q
Q5. What is the negation of ∀x (P(x) → Q(x))?
a) ∀x (P(x) ∧ ¬Q(x))
b) ∃x (P(x) ∧ ¬Q(x))
c) ∃x (¬P(x) → ¬Q(x))
d) ∃x (¬P(x) ∧ Q(x))
Q6. From the premises p → q and ¬q, a student concludes ¬p. Which rule of inference is used?
a) Modus ponens
b) Disjunctive syllogism
c) Modus tollens
d) Hypothetical syllogism
Q7. In how many rows of its truth table is p → (q ∧ r) true?
a) 3
b) 4
c) 7
d) 5
Q8. Let S(x): x is a student, M(y): y likes mathematics, and F(x, y): y is a friend of x. Which formula expresses 'Every student has a friend who likes mathematics'?
a) ∀x (S(x) → ∃y (F(x, y) ∧ M(y)))
b) ∀x (S(x) ∧ ∃y (F(x, y) → M(y)))
c) ∃y ∀x (S(x) → (F(x, y) ∧ M(y)))
d) ∀x ∃y (S(x) ∧ F(x, y) ∧ M(y))
Q9. Which implication is valid for every predicate P(x, y) over every non-empty domain?
a) ∀y ∃x P(x, y) → ∃x ∀y P(x, y)
b) ∀x ∃y P(x, y) → ∃y ∀x P(x, y)
c) ∃x ∀y P(x, y) → ∀y ∃x P(x, y)
d) ∃x P(x, x) → ∀x P(x, x)
Q10. Which single connective is functionally complete on its own?
a) AND
b) OR
c) XOR
d) NAND
Q11. p ↔ q is logically equivalent to which formula?
a) (p ∧ q) ∨ (¬p ∧ ¬q)
b) (p ∧ ¬q) ∨ (¬p ∧ q)
c) (p ∨ q) ∧ (¬p ∨ ¬q)
d) (p → q) ∨ (q → p)
Q12. Let p: you pass and s: you skip the exam. How is 'You will pass unless you skip the exam' best written?
a) p → ¬s
b) ¬s → p
c) s → p
d) ¬p → ¬s
Q13. Which of the following is a contradiction?
a) (p → q) ∧ (q → p)
b) p ∨ ¬(p ∧ q)
c) (p ∧ q) → p
d) (p ∨ q) ∧ ¬p ∧ ¬q
Q14. Given the premises p ∨ q and ¬p ∨ r, which conclusion follows by resolution?
a) q ∨ r
b) q ∧ r
c) p ∨ r
d) ¬q → ¬r
Q15. Over the domain {1, 2, 3}, which statement is TRUE?
a) ∃y ∀x (x + y = 4)
b) ∀x ∃y (x + y = 4)
c) ∀x ∀y (x + y ≤ 5)
d) ∃x ∃y (x + y = 7)
Q16. p → (q → r) is logically equivalent to which formula?
a) (p → q) → r
b) (p ∨ q) → r
c) (p ∧ q) → r
d) p ∧ q ∧ ¬r
Q17. An argument concludes p from the premises p → q and q. What is this?
a) The fallacy of affirming the consequent
b) Modus ponens
c) The fallacy of denying the antecedent
d) A valid hypothetical syllogism
Q18. A formula F is satisfiable but not valid. What can be said about ¬F?
a) ¬F is a contradiction
b) ¬F is also satisfiable but not valid
c) ¬F is a tautology
d) ¬F is unsatisfiable whenever F has two or more variables
Quick revision notes
- p → q ≡ ¬p ∨ q; it is false only when p is true and q is false.
- Contrapositive ¬q → ¬p is equivalent to p → q; the converse and inverse are not.
- Number of Boolean functions on n variables = 2^(2^n).
- ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x).
- ∃x ∀y P(x,y) → ∀y ∃x P(x,y) is valid; the reverse is not.
- Modus ponens: p, p → q ⊢ q. Modus tollens: ¬q, p → q ⊢ ¬p.
- NAND alone and NOR alone are functionally complete.
- 'All S are M' uses ∀x (S(x) → M(x)); 'some S is M' uses ∃x (S(x) ∧ M(x)).
Frequently asked questions
What is the difference between a tautology and a valid argument?
A tautology is a single formula that is true under every assignment. An argument is valid when the conjunction of its premises implies the conclusion, that is, when (premises) → conclusion is a tautology.
Why is ∀x combined with → but ∃x combined with ∧?
∀x (S(x) → P(x)) restricts the claim to elements satisfying S. Writing ∃x (S(x) → P(x)) would be made true by any element that is not S, so the existential form uses ∧ to require an element that is S and also P.
Which sets of connectives are functionally complete?
{¬, ∧}, {¬, ∨}, {¬, →}, {NAND} and {NOR} are all functionally complete. {∧, ∨} is not, because it cannot express negation, and → alone is not, because it cannot produce the constant false.
Comments
Post a Comment