Questions
3 questions per paper
Difficulty
Medium
Importance
High weightage in Discrete Mathematics papers
Overview
Propositional and Predicate Logic form the mathematical foundation of digital circuits, algorithm design, and database query languages. Mastering these concepts is essential for competitive and university exams as they provide the formal framework for evaluating the validity of arguments and system operations. The core goal is to transition from natural language reasoning to precise, rule-based symbolic manipulation.
Propositional Logic and Truth Tables
Propositional logic deals with declarative statements that are either true or false. Truth tables provide a systematic method to determine the truth value of a compound statement based on its constituent propositions and logical connectives.
- Negation (~p): Inverts the truth value
- Conjunction (p ∧ q): True only if both are true
- Disjunction (p ∨ q): True if at least one is true
- Implication (p → q): False only if p is true and q is false
- Biconditional (p ↔ q): True if both have the same truth value
- Number of rows in truth table = 2^n where n is the number of variables
Logical Equivalences
Logical equivalences are statements that have the same truth value in every possible scenario. These laws allow for the simplification of complex boolean expressions, which is a common task in both logical theory and digital logic simplification.
- De Morgan's Laws: ~(p ∧ q) ≡ ~p ∨ ~q and ~(p ∨ q) ≡ ~p ∧ ~q
- Commutative Laws: p ∧ q ≡ q ∧ p
- Associative Laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
- Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
- Double Negation: ~~p ≡ p
- Contrapositive equivalence: (p → q) ≡ (~q → ~p)
Predicate Logic and Quantifiers
Predicate logic extends propositional logic by introducing variables and quantifiers to represent statements about objects within a domain. This allows for the expression of general statements about sets of items rather than individual fixed values.
- Universal Quantifier (∀x P(x)): True if P(x) is true for all x in the domain
- Existential Quantifier (∃x P(x)): True if there exists at least one x in the domain where P(x) is true
- Negation of Universal: ~∀x P(x) ≡ ∃x ~P(x)
- Negation of Existential: ~∃x P(x) ≡ ∀x ~P(x)
- Predicates return a boolean value based on inputs
Formula Sheet
p → q ≡ ~p ∨ q
p ↔ q ≡ (p → q) ∧ (q → p)
~∀x P(x) ≡ ∃x ~P(x)
~∃x P(x) ≡ ∀x ~P(x)
Exam Tip
Always verify the Contrapositive (~q → ~p) when dealing with complex implications, as it is logically identical to the original statement and often easier to prove.
Common Mistakes
- Misinterpreting the truth value of the implication (p → q), specifically thinking it is false when the antecedent p is false.
- Neglecting the domain of discourse when applying quantifiers, which changes the truth value of the entire expression.
- Applying De Morgan's laws incorrectly by failing to negate the individual components along with the connective.
More Revision Notes
Ready to test yourself?
Play topic-wise Propositional & Predicate Logic questions in Aspirant Arcade — gamified MCQ practice.
Download Free