Logic is the grammar of every proof you will ever write, and in Discrete Mathematics it is the topic that rewards precision over memory. Get the truth tables, the equivalences, and the quantifier rules exactly right, and a whole family of GATE questions becomes mechanical.
This is one of the densest sub-areas in the Discrete Mathematics question bank, so the return on understanding it properly is high. Let us build it from propositions up to formal inference, with the worked steps the exam actually asks for.
Propositional logic: statements and connectives
A proposition is a declarative statement that is either true or false, never both. "7 is prime" is a proposition. "Solve this equation" is not. We combine propositions with five connectives:
Negation (not, written not p): flips the truth value.
Conjunction (and, p and q): true only when both are true.
Disjunction (or, p or q): true when at least one is true.
Implication (if p then q, p to q): the one students misread. It is false in exactly one case, when p is true and q is false.
Biconditional (p if and only if q): true when p and q have the same truth value.
Here p is the antecedent or hypothesis, and q is the consequent or conclusion.
Truth tables, tautology and contradiction
A truth table lists every combination of inputs and the resulting output. This is the truth table for the two connectives students get wrong most often, implication and biconditional:
p | q | p to q | p iff q |
|---|---|---|---|
T | T | T | T |
T | F | F | F |
F | T | T | F |
F | F | T | T |
Read the third and fourth rows of the implication column carefully. When the hypothesis is false, the implication is vacuously true. This is the single most tested fact in the topic.
From a truth table we classify any compound formula:
A tautology is true in every row. The classic example is p or not p, the law of excluded middle.
A contradiction is false in every row, such as p and not p.
A contingency is neither, its value depends on the inputs.
Two formulas are logically equivalent when they have identical truth tables. That is written with the equivalence sign, and it is the engine of every simplification below.
Logical equivalences you must know
These are the laws you should be able to apply without deriving them each time:
Law | Equivalence |
|---|---|
De Morgan's | not (p and q) is equivalent to not p or not q |
De Morgan's | not (p or q) is equivalent to not p and not q |
Implication | p to q is equivalent to not p or q |
Contrapositive | p to q is equivalent to not q to not p |
Double negation | not (not p) is equivalent to p |
Distributive | p and (q or r) is equivalent to (p and q) or (p and r) |
The implication law, that p to q rewrites as not p or q, is the one that unlocks the most problems. Whenever an implication appears inside a larger formula, convert it first and the rest usually falls out by De Morgan's.
Implication: converse, inverse and contrapositive
Given the implication p to q, three related statements are built by swapping and negating:
Converse: q to p.
Inverse: not p to not q.
Contrapositive: not q to not p.
The examiner's favourite fact: an implication is logically equivalent to its contrapositive, and the converse is equivalent to the inverse. An implication is not equivalent to its converse, and confusing the two is a standard trap. If you can recite that one sentence, you will not lose those marks.
Predicate logic: quantifiers and their negation
Propositional logic cannot express "every integer has a successor" because it treats a whole statement as one atom. Predicate logic adds predicates and quantifiers. A predicate P(x) becomes a proposition once x is fixed or quantified.
The universal quantifier, for all x P(x), asserts P holds for every x in the domain.
The existential quantifier, there exists x P(x), asserts P holds for at least one x.
The rule you must never fumble is the negation of quantifiers:
not (for all x P(x)) is equivalent to there exists x not P(x).
not (there exists x P(x)) is equivalent to for all x not P(x).
In words, pushing a negation inward flips the quantifier and negates the predicate. So the denial of "all swans are white" is not "no swan is white", it is "there exists a swan that is not white". Nested quantifiers negate the same way, one layer at a time, flipping each quantifier as the negation moves right.
Rules of inference: a worked validity proof
An argument is valid when the conclusion follows from the premises by the rules of inference, regardless of whether the premises are actually true. The rules you must know are modus ponens (from p to q and p, conclude q), modus tollens (from p to q and not q, conclude not p), hypothetical syllogism (from p to q and q to r, conclude p to r), and disjunctive syllogism (from p or q and not p, conclude q).
Here is a validity proof that chains two of them. Premises:
p to q
not q
p or s
Show that s follows.
From premises 1 and 2, apply modus tollens to get not p.
From premise 3 and not p, apply disjunctive syllogism to get s.
The conclusion s is derived, so the argument is valid. In the exam you will be given premises like these and asked whether a stated conclusion follows, and this is the exact procedure: name the rule at each step, do not hand-wave.
How propositional and predicate logic are tested in GATE
GATE CS tests this area three ways. First, pure truth-table evaluation, asking whether a formula is a tautology or how many rows are true. Second, logical-equivalence and simplification questions that hinge on De Morgan's and the implication law. Third, quantifier questions, either translating an English sentence into symbols or negating a nested quantified statement. The rules of inference appear as short validity checks.
The topic connects straight into the rest of Discrete Mathematics. Once you can reason about relations and functions symbolically, the same quantifier machinery describes them, which is why our Discrete Mathematics learn module sequences logic before those topics. When you want to drill just this area, work the quantifiers practice set and the tautology and validity set from previous years.
Practise it, do not just read it
Logic is confirmed on questions, not on a single read of the rules. Learn the implication truth table cold, keep contrapositive and converse cleanly apart, and negate one nested quantified statement by hand until it feels routine.
Work the previous-year quantifiers practice set and tautology and validity set with worked solutions.
For Discrete Mathematics inside the whole GATE CS syllabus, GATE Guidance by Sanchit Sir sequences logic alongside set theory, relations and graph theory.
Browse the wider CS Fundamentals category for the neighbouring topics.
Master the truth tables, the equivalences, and the quantifier negation rules, and this stops being a topic you second-guess and becomes marks you count on.
