Propositional Logic & Predicate Logic — Complete Guide for GATE CS

Propositional Logic & Predicate Logic — Complete Guide for GATE CS

The formal language of reasoning — for GATE CS, ISRO CS, UGC NET, and placement interviews

Last Updated: April 2026

Key Takeaways 📌

• Propositional Logic deals with statements that are either true or false, connected by logical connectives (AND, OR, NOT, implication, biconditional). It is the foundation of digital circuits, Boolean algebra, and program verification.
• Predicate Logic (First-Order Logic) extends propositional logic by introducing variables, quantifiers (∀, ∃), and predicates — making it expressive enough to reason about mathematical structures, databases, and formal proofs.
• GATE CS tests: truth tables, tautology/contradiction identification, logical equivalences, CNF/DNF conversion, satisfiability, and predicate logic inference (Universal Instantiation, Modus Ponens, resolution).
• ISRO and UGC NET additionally test formal proof construction and translation of English sentences into predicate logic.
• The practical payoff: logic is the theoretical basis for SQL WHERE clauses, program verification (pre/post-conditions), digital circuit design, and TOC (automata theory uses formal languages built on logical predicates).

Table of Contents

1. What is Propositional Logic?
2. Logical Connectives — Symbols, Definitions, Truth Tables
3. Compound Propositions and Truth Tables
4. Tautology, Contradiction, and Contingency
5. Logical Equivalences — Laws of Logic
6. Normal Forms — CNF and DNF
7. Propositional Inference Rules
8. Satisfiability and Resolution
9. Limitations of Propositional Logic
10. What is Predicate Logic (First-Order Logic)?
11. Predicates, Variables, and Quantifiers
12. Translating English to Predicate Logic
13. Scope, Binding, and Free/Bound Variables
14. Inference Rules in Predicate Logic
15. Worked GATE-Level Examples
16. Common Mistakes
17. Quick Reference — Formulas and Equivalences
18. Frequently Asked Questions
19. Next Steps

1. What is Propositional Logic?

Propositional Logic is the branch of formal logic that studies propositions — declarative statements that are unambiguously either true (T) or false (F), never both, never neither.

Examples of propositions:

• “The number 7 is prime.” → True
• “All even numbers are divisible by 4.” → False
• “Delhi is the capital of Maharashtra.” → False

Non-examples (not propositions — no truth value):

• “Close the door.” → A command, not a statement.
• “What is 2 + 2?” → A question.
• “x > 5” → Truth depends on the value of x; this is a predicate (covered later).

Propositions are denoted by lowercase letters: p, q, r, s, … Each proposition has a truth value: T (true) or F (false).

Why it matters for GATE CS: Propositional logic is directly tested (2–4 marks per year), appears in digital logic (Boolean algebra is propositional logic over {0,1}), and is the semantic foundation of SQL WHERE clauses and programming language conditional expressions. The question “Is this formula a tautology?” is one of the most-repeated GATE CS question patterns.

2. Logical Connectives — Symbols, Definitions, and Truth Tables

Propositions are combined using logical connectives to form compound propositions. There are five standard connectives:

2.1 Negation (NOT) — ¬p

The negation of p is true when p is false, and false when p is true.

Reading: “not p”, “it is not the case that p”

2.2 Conjunction (AND) — p ∧ q

True only when both p and q are true.

Reading: “p and q”

2.3 Disjunction (OR) — p ∨ q

True when at least one of p or q is true. This is inclusive OR.

Reading: “p or q (or both)”

2.4 Implication (Conditional) — p → q

The most misunderstood connective. Read as “if p then q.” It is false only when p is true and q is false. When the premise p is false, the implication is vacuously true regardless of q.

Reading: “p implies q”, “if p then q”, “p only if q”

Intuition for vacuous truth: The statement “If it rains, I will carry an umbrella” is not violated on a day when it does not rain, regardless of what you carry.

Important forms derived from p → q:

• Converse: q → p (not logically equivalent to p → q)
• Inverse: ¬p → ¬q (not logically equivalent to p → q)
• Contrapositive: ¬q → ¬p (logically equivalent to p → q — this is very frequently tested in GATE)

2.5 Biconditional — p ↔ q

True when p and q have the same truth value (both true or both false).

Reading: “p if and only if q”, “p iff q” Key identity: p ↔ q ≡ (p → q) ∧ (q → p)

2.6 Exclusive OR — p ⊕ q

True when exactly one of p or q is true. Note: p ⊕ q ≡ ¬(p ↔ q).

3. Compound Propositions and Truth Tables

A compound proposition is built from atomic propositions using connectives. A truth table lists the truth value of the compound proposition for every possible combination of truth values of its atomic propositions.

For n atomic propositions, a truth table has 2ⁿ rows.

Example: Construct the truth table for (p ∨ q) → (p ∧ ¬q)

Since the formula is false for some truth value assignments, it is a contingency (neither a tautology nor a contradiction).

Operator Precedence (highest to lowest):

1. ¬ (negation)
2. ∧ (conjunction)
3. ∨ (disjunction)
4. → (implication)
5. ↔ (biconditional)

So p ∨ q → r means (p ∨ q) → r, not p ∨ (q → r).

4. Tautology, Contradiction, and Contingency

GATE testing pattern: You are given a formula and asked whether it is a tautology, contradiction, or neither. The efficient method is to try to find a falsifying assignment (an assignment that makes the formula false). If none exists, it is a tautology. If every assignment falsifies it, it is a contradiction.

Commonly tested tautologies — memorise these:

• p ∨ ¬p (Law of Excluded Middle)
• ¬(p ∧ ¬p) (Law of Non-Contradiction)
• (p → q) ↔ (¬q → ¬p) (Contrapositive equivalence)
• (p → q) ∧ (q → r) → (p → r) (Hypothetical Syllogism)
• (p ∧ (p → q)) → q (Modus Ponens as a tautology)
• p → (q → p) (Weakening)
• (p → q) ↔ (¬p ∨ q) — the implication-to-disjunction equivalence

5. Logical Equivalences — Laws of Logic

Two compound propositions A and B are logically equivalent (A ≡ B) if they have identical truth values for every possible combination of truth values of their components. Equivalently, A ↔ B is a tautology.

Complete Table of Standard Equivalences

Identity Laws:

• p ∧ T ≡ p
• p ∨ F ≡ p

Domination Laws:

• p ∨ T ≡ T
• p ∧ F ≡ F

Idempotent Laws:

• p ∨ p ≡ p
• p ∧ p ≡ p

Double Negation:

• ¬(¬p) ≡ p

Commutative Laws:

• p ∨ q ≡ q ∨ p
• p ∧ q ≡ q ∧ p

Associative Laws:

• (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
• (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive Laws:

• p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
• p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

De Morgan’s Laws (extremely frequently tested in GATE):

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q

Absorption Laws:

• p ∨ (p ∧ q) ≡ p
• p ∧ (p ∨ q) ≡ p

Negation Laws:

• p ∨ ¬p ≡ T
• p ∧ ¬p ≡ F

Implication Equivalences:

• p → q ≡ ¬p ∨ q
• p → q ≡ ¬q → ¬p (Contrapositive)
• ¬(p → q) ≡ p ∧ ¬q

Biconditional Equivalences:

• p ↔ q ≡ (p → q) ∧ (q → p)
• p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
• ¬(p ↔ q) ≡ p ⊕ q

Exportation Law:

• (p ∧ q) → r ≡ p → (q → r)

6. Normal Forms — CNF and DNF

Normal forms provide canonical representations of logical formulas — particularly important in automated theorem proving, SAT solvers, and GATE CS questions on logic simplification.

6.1 Disjunctive Normal Form (DNF)

A formula is in DNF if it is a disjunction (OR) of conjunctions (AND) of literals.

• Form: (L₁ ∧ L₂ ∧ …) ∨ (L₃ ∧ L₄ ∧ …) ∨ …
• Each literal is either a variable (p) or its negation (¬p).
• Each conjunction clause is called a minterm.

Example: (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ ¬r) is in DNF.

DNF corresponds directly to a truth table: Each row where the formula is TRUE contributes one minterm. If p=T, q=F makes the formula true, the corresponding minterm is p ∧ ¬q.

6.2 Conjunctive Normal Form (CNF)

A formula is in CNF if it is a conjunction (AND) of disjunctions (OR) of literals.

• Form: (L₁ ∨ L₂ ∨ …) ∧ (L₃ ∨ L₄ ∨ …) ∧ …
• Each disjunction clause is called a maxterm (or clause).

Example: (p ∨ q) ∧ (¬p ∨ r) ∧ (q ∨ ¬r) is in CNF.

CNF corresponds to rows where the formula is FALSE: Each row where the formula is FALSE contributes one maxterm. If p=F, q=F makes the formula false, the corresponding maxterm is p ∨ q (which is false exactly when p=F and q=F).

6.3 Converting to CNF — Step-by-Step

Converting any formula to CNF:

1. Eliminate biconditionals: Replace p ↔ q with (p → q) ∧ (q → p).
2. Eliminate implications: Replace p → q with ¬p ∨ q.
3. Push negations inward using De Morgan’s laws and double negation until negations appear only on atomic variables (this is called Negation Normal Form, NNF).
4. Distribute ∨ over ∧ using the distributive law: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C).

Example — Convert (p → q) → r to CNF:

Step 1: Eliminate outer implication: ¬(p → q) ∨ r Step 2: Eliminate inner implication: ¬(¬p ∨ q) ∨ r Step 3: De Morgan on ¬(¬p ∨ q): (p ∧ ¬q) ∨ r Step 4: Distribute ∨ over ∧: (p ∨ r) ∧ (¬q ∨ r)

Result (CNF): (p ∨ r) ∧ (¬q ∨ r) ✓

7. Propositional Inference Rules

Inference rules allow us to derive new propositions (conclusions) from existing ones (premises). These are valid argument forms — the conclusion is guaranteed to be true whenever all premises are true.

Distinguishing valid inference from logical equivalence: Logical equivalence (≡) means two formulas have the same truth value in all situations. An inference rule (⊢) means the conclusion is true whenever the premises are true — but the conclusion and premises need not be equivalent.

8. Satisfiability and Resolution

8.1 Satisfiability (SAT)

A formula is satisfiable if there exists at least one truth assignment that makes it true. It is unsatisfiable if no such assignment exists (i.e., it is a contradiction).

• Tautology → always satisfiable (true under all assignments)
• Contradiction → unsatisfiable
• Contingency → satisfiable (but not under all assignments)

The Boolean Satisfiability Problem (SAT) asks: given a propositional formula (typically in CNF), is there a satisfying assignment? SAT was the first problem proven to be NP-complete (Cook-Levin theorem, 1971) — a connection between propositional logic and computational complexity that appears in both Discrete Mathematics and Algorithms in GATE CS.

8.2 Resolution Proof Method

Resolution is a proof technique used in automated theorem proving and logic-based AI. To prove that a set of clauses S is unsatisfiable, you repeatedly apply the resolution rule until the empty clause (⊥) is derived.

Resolution Rule: Given clauses (A ∨ p) and (B ∨ ¬p), derive the resolvent (A ∨ B). When A and B are both empty, the resolvent is ⊥.

Proof by Refutation: To prove that a formula F follows from premises P₁, P₂, …, Pₙ:

1. Convert all premises and ¬F to CNF.
2. Collect all clauses.
3. Repeatedly apply resolution.
4. If you derive ⊥ (empty clause), then F follows from the premises.

Example: Prove q follows from {p, p → q}.

Convert to CNF:

• p → clause {p}
• p → q → clause {¬p, q}
• ¬q (negation of conclusion) → clause {¬q}

Resolve {¬p, q} and {¬q}: get {¬p} Resolve {p} and {¬p}: get {} = ⊥

Therefore, q is provable from {p, p → q}. ✓

9. Limitations of Propositional Logic

While powerful for reasoning about fixed statements, propositional logic has critical limitations:

1. Cannot reason about objects and their properties. The statement “All students who study hard pass the exam” cannot be expressed in propositional logic with a finite set of propositions (you would need one proposition per student).
2. No quantification. It has no way to say “for all x” or “there exists an x.”
3. Cannot express mathematical induction. Statements like “For all natural numbers n, n² ≥ n” require a universal quantifier over an infinite domain.
4. Cannot capture the structure of relations. “A is taller than B” requires a two-argument predicate Taller(A, B).

These limitations motivated the development of Predicate Logic (First-Order Logic).

10. What is Predicate Logic (First-Order Logic)?

Predicate Logic, also called First-Order Logic (FOL), is an extension of propositional logic that introduces:

• Predicates — functions that map objects to truth values (e.g., Prime(7), Enrolled(Alice, CS101))
• Variables — ranging over a domain of objects (e.g., x, y, n)
• Quantifiers — ∀ (for all) and ∃ (there exists)
• Constants — specific named objects (e.g., Alice, 0, π)
• Functions — mapping objects to objects (e.g., father(x), successor(n))

Together, these features allow predicate logic to express the vast majority of mathematical statements and database queries — making it the standard formal language for mathematics, computer science theory, and relational databases.

“First-Order” refers to the fact that quantifiers range over objects (individuals) in the domain, not over predicates or sets of objects. Quantification over predicates themselves is called Second-Order Logic.

11. Predicates, Variables, and Quantifiers

11.1 Predicates

A predicate is a property or relation. P(x) means “x has property P.” The truth value of P(x) depends on what x refers to.

• P(x) = “x is even”: P(4) = T, P(7) = F
• Enrolled(x, y) = “student x is enrolled in course y”: Enrolled(Alice, CS101) = T

An n-ary predicate takes n arguments. P(x) is unary, R(x, y) is binary, etc.

11.2 Quantifiers

Universal Quantifier — ∀ (for all)

∀x P(x) means “for every object x in the domain, P(x) is true.”

• Truth condition: P(x) must be true for every possible value of x in the domain.
• If the domain is {1, 2, 3, 4}: ∀x Even(x) is FALSE (since 1 and 3 are not even).

Existential Quantifier — ∃ (there exists)

∃x P(x) means “there exists at least one object x in the domain such that P(x) is true.”

• Truth condition: P(x) must be true for at least one value of x.
• If the domain is {1, 2, 3, 4}: ∃x Even(x) is TRUE (x=2 works).

11.3 Negation of Quantifiers (De Morgan’s Laws for Quantifiers)

These are the most-tested predicate logic transformations in GATE CS:

General rule: To negate a quantified formula, push the negation inward, flipping each ∀ to ∃ and each ∃ to ∀, until the negation reaches the predicate.

11.4 Nested Quantifiers

Quantifiers can be nested, and the order of different quantifiers matters.

• ∀x ∃y Loves(x, y): “Every person loves someone.” (For each person, there is some person they love — possibly a different one for each.)
• ∃y ∀x Loves(x, y): “There is someone who is loved by everyone.” (A single person loved by all.)

These two are not equivalent — the order of ∀ and ∃ changes the meaning. However, two universal quantifiers or two existential quantifiers can be swapped:

• ∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y)
• ∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y)

12. Translating English to Predicate Logic

Translation is tested in UGC NET CS and ISRO CS, and indirectly in GATE CS (understanding the meaning of quantified formulas).

Useful patterns:

Critical mistake alert: “Some A are B” uses ∧ (not →): ∃x (A(x) ∧ B(x)). The formula ∃x (A(x) → B(x)) is almost always true (it is satisfied by any x for which A(x) is false), so it captures nearly nothing. Always use ∧ with ∃.

Example translations:

“Every student who submits the assignment on time receives full marks.”

• Let S(x) = “x is a student”, T(x) = “x submits the assignment on time”, F(x) = “x receives full marks”.
• Translation: ∀x ((S(x) ∧ T(x)) → F(x))

“There exists a prime number that is even.”

• Let P(x) = “x is prime”, E(x) = “x is even”.
• Translation: ∃x (P(x) ∧ E(x)) — and this is TRUE (x = 2).

13. Scope, Binding, and Free/Bound Variables

The scope of a quantifier is the part of the formula to which it applies.

• In ∀x (P(x) → Q(x)), the scope of ∀x is the entire formula P(x) → Q(x).
• A variable x is bound if it is within the scope of a quantifier that binds it.
• A variable x is free if it is not bound by any quantifier.

In ∀x (P(x) ∧ Q(x, y)):

• x is bound (by ∀x)
• y is free (no quantifier binds it)

A formula with no free variables is called a sentence (or closed formula) — it has a definite truth value for a given interpretation. A formula with free variables is called an open formula — its truth value depends on what the free variables are assigned.

GATE application: Questions sometimes give a formula and ask which variables are free or bound, or ask for the truth value of a formula after substituting values for free variables.

14. Inference Rules in Predicate Logic

Predicate logic inherits all propositional inference rules and adds four quantifier-specific rules:

14.1 Universal Instantiation (UI)

From ∀x P(x), conclude P(c) for any specific constant c.

Example: From ∀x (x > 0 → x² > 0), conclude 5 > 0 → 5² > 0.

14.2 Universal Generalisation (UG)

From P(c) for an arbitrary constant c (not constrained by any assumptions), conclude ∀x P(x).

Caution: c must be truly arbitrary — not a specific chosen constant and not a constant introduced in a hypothesis.

14.3 Existential Instantiation (EI)

From ∃x P(x), introduce a new constant c (a fresh name) and assert P(c).

Example: From ∃x Prime(x) ∧ Even(x), we may say: let c be such a value; then Prime(c) ∧ Even(c).

14.4 Existential Generalisation (EG)

From P(c) for some specific constant c, conclude ∃x P(x).

Example: From Prime(2) ∧ Even(2), conclude ∃x (Prime(x) ∧ Even(x)).

15. Worked GATE-Level Examples

Example 1 (GATE CS pattern — Tautology check)

Question: Which of the following is a tautology?

(A) (p ∧ q) → p (B) p → (p ∧ q) (C) p ∨ (q → p) (D) (p → q) → p

Solution:

(A) (p ∧ q) → p: This says “if both p and q are true, then p is true.” The only way an implication is false is if the premise is true and conclusion is false. Here, if p ∧ q is true, then p must be true (by simplification). So this is always true — a tautology. ✓

(B) p → (p ∧ q): Try p = T, q = F: premise p is T, conclusion p ∧ q = F. The implication is F. Not a tautology. ✗

(C) p ∨ (q → p): q → p ≡ ¬q ∨ p. So p ∨ ¬q ∨ p ≡ p ∨ ¬q. Try p = F, q = T: F ∨ F = F. Not a tautology. ✗

(D) (p → q) → p: Try p = F, q = T: (F → T) = T; then T → F = F. Not a tautology. ✗

Answer: (A)

Example 2 (GATE CS pattern — Logical equivalence)

Question: Which of the following is logically equivalent to ¬(∀x P(x) → ∃y Q(y))?

Solution:

Recall: ¬(A → B) ≡ A ∧ ¬B.

So: ¬(∀x P(x) → ∃y Q(y)) ≡ ∀x P(x) ∧ ¬(∃y Q(y))

Now apply De Morgan for quantifiers: ¬(∃y Q(y)) ≡ ∀y ¬Q(y)

Result: ∀x P(x) ∧ ∀y ¬Q(y)

Reading: “Every x satisfies P, and no y satisfies Q.”

Example 3 (GATE CS pattern — CNF conversion)

Question: Convert p → (q ∧ r) to CNF.

Solution:

Step 1: Eliminate implication: p → (q ∧ r) ≡ ¬p ∨ (q ∧ r)

Step 2: Distribute ∨ over ∧: (¬p ∨ q) ∧ (¬p ∨ r)

Result (CNF): (¬p ∨ q) ∧ (¬p ∨ r) ✓

This is already in CNF — two clauses, each a disjunction of literals.

Example 4 (GATE CS pattern — Inference)

Question: From the premises:

1. ∀x (Student(x) → Attends(x, Lectures))
2. Student(Priya)

Conclude: Attends(Priya, Lectures)

Solution:

From premise 1, apply Universal Instantiation with c = Priya: Student(Priya) → Attends(Priya, Lectures)

Now apply Modus Ponens with premise 2 (Student(Priya)): Conclusion: Attends(Priya, Lectures) ✓

Example 5 (GATE CS pattern — Contrapositive)

Question: The statement “If a graph is bipartite, then it has no odd-length cycle” is equivalent to which of the following?

(A) If a graph has no odd-length cycle, then it is bipartite. (B) If a graph has an odd-length cycle, then it is not bipartite. (C) If a graph is not bipartite, then it has an odd-length cycle. (D) A graph is bipartite if and only if it has an odd-length cycle.

Solution:

Original: p → q where p = “bipartite”, q = “no odd-length cycle”

Contrapositive: ¬q → ¬p = “if a graph has an odd-length cycle, then it is not bipartite.”

Answer: (B) ✓

Note: (A) is the converse, (C) is the inverse. Neither is logically equivalent to the original. (D) is the biconditional, which makes the opposite claim.

16. Common Mistakes

Mistake 1 — Confusing implication with biconditional. p → q is not the same as p ↔ q. The implication is one-directional. Many students incorrectly conclude that if q is true, then p must be true — this is the fallacy of “affirming the consequent.” Modus Ponens goes forward (p, p→q ⊢ q), not backward.

Mistake 2 — Forgetting that p → q is vacuously true when p is false. When p is false, p → q is true regardless of q. This surprises students who expect a false premise to make the implication “unknown.” In classical two-valued logic, there is no “unknown” — only T and F.

Mistake 3 — Using ∃x (A(x) → B(x)) to mean “some A are B.” The correct form is ∃x (A(x) ∧ B(x)). The implication form ∃x (A(x) → B(x)) is trivially true whenever any object fails to be A (since a false premise makes the implication true).

Mistake 4 — Swapping the order of ∀ and ∃ in nested quantifiers. ∀x ∃y P(x,y) and ∃y ∀x P(x,y) are generally not equivalent. The first says “for each x, there is some y” (the y can depend on x). The second says “there is a single y that works for all x simultaneously.”

Mistake 5 — Incorrectly applying De Morgan’s law to quantifiers. ¬(∀x P(x)) is ∃x ¬P(x), not ∀x ¬P(x). When pushing a negation past a quantifier, flip the quantifier (∀ ↔ ∃) and negate the predicate.

Mistake 6 — Confusing converse, inverse, and contrapositive. Only the contrapositive (¬q → ¬p) is logically equivalent to p → q. The converse (q → p) and inverse (¬p → ¬q) are equivalent to each other, but not to the original implication.

Mistake 7 — Treating CNF and DNF conversion as purely mechanical without checking. After conversion, verify your result by checking that every clause satisfies the CNF/DNF definition. A common error is stopping the distribution step too early and leaving a non-clause structure inside a conjunction.

17. Quick Reference — Formulas and Equivalences

Standard Logical Equivalences

Quantifier Negation (De Morgan for Predicate Logic)

Inference Rules Summary

Key Tautologies to Memorise

• p ∨ ¬p (Excluded Middle)
• p → (q → p) (Weakening)
• (p → q) ∧ (q → r) → (p → r) (Transitivity)
• (p ∧ (p → q)) → q (Modus Ponens tautology)
• (p → q) ↔ (¬q → ¬p) (Contrapositive)

18. Frequently Asked Questions

Q1. What is the difference between propositional logic and predicate logic?

Propositional logic works with atomic propositions (fixed statements with fixed truth values) and connectives. It cannot express “for all” or “there exists” — so it cannot reason about properties of individual objects. Predicate logic introduces predicates (properties and relations applied to variable objects) and quantifiers (∀ and ∃), making it expressive enough for mathematics, programming language semantics, and database query logic. Propositional logic is a special case of predicate logic where there are no variables and no quantifiers.

Q2. Why is the implication p → q true when p is false?

The implication p → q makes a conditional guarantee: if the condition p is met, then q will hold. If p is false — the condition is never triggered — the guarantee is never tested and therefore never violated. In formal logic, we define p → q as ¬p ∨ q, which gives it exactly this truth behaviour. This “vacuous truth” is not a bug or arbitrary convention; it is necessary for the mathematical system to behave consistently. If we defined p → q as false when p is false, then every universally quantified statement “∀x (A(x) → B(x))” would become unworkable (any element outside A would falsify it).

Q3. How does GATE CS typically test propositional and predicate logic?

GATE CS logic questions fall into four main types: (1) Tautology/equivalence identification — given a formula or pair of formulas, identify which is a tautology or which pair is logically equivalent; (2) CNF/DNF conversion — convert a given formula or identify which of the given formulas is the CNF/DNF of a given truth table; (3) Inference validity — given premises and a conclusion, determine whether the conclusion follows logically; (4) Predicate logic translation and quantifier manipulation — negate a quantified formula, determine the equivalence of two quantified formulas, or identify the meaning of a given formula. Questions are 1 or 2 marks and typically 2–4 appear per year.

Q4. What is the connection between propositional logic and digital circuits?

Boolean algebra — the mathematics of digital circuits — is essentially propositional logic restricted to the domain {0, 1} where 0 = F and 1 = T. AND gates correspond to ∧, OR gates to ∨, NOT gates to ¬, NAND gates to ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan), and XOR gates to p ⊕ q. The laws of propositional logic (De Morgan’s, distributive, absorption) are exactly the laws used to simplify Boolean expressions and minimise circuit complexity. K-map minimisation (covered in CS_11) is a graphical technique for applying these equivalences efficiently.

Q5. What is the significance of SAT being NP-complete for GATE CS?

Cook’s theorem (1971) proved that the Boolean Satisfiability Problem (SAT) — asking whether a propositional formula has a satisfying assignment — is NP-complete. This means every problem in NP can be polynomially reduced to SAT. SAT was the first NP-complete problem identified. For GATE CS, this matters because NP-completeness (covered in CS_30 — Algorithms) is tested by asking students to prove a new problem is NP-complete by reducing a known NP-complete problem (often SAT or 3-SAT) to it. Understanding SAT as a logic problem clarifies both why it is hard and why it is the canonical NP-complete problem.

Q6. Is predicate logic decidable?

Propositional logic is decidable — there is a finite procedure (truth tables) to determine whether any given propositional formula is a tautology. First-Order Predicate Logic is undecidable — there is no general algorithm that can determine whether an arbitrary first-order formula is a tautology (this is Church’s theorem, and it connects to the undecidability of the Halting Problem). However, FOL is semi-decidable: if a formula is a tautology, a theorem prover will eventually find a proof; but if it is not, the prover may run forever. This decidability distinction appears in GATE CS’s Theory of Computation section (Turing machines and decidability — CS_68).

Q7. What is the connection between predicate logic and SQL?

SQL’s WHERE clause is directly based on predicate logic. A SQL query like SELECT * FROM Students WHERE GPA > 3.5 AND Major = ‘CS’ applies a predicate (GPA > 3.5 ∧ Major = ‘CS’) to each row object x in the Students relation. Relational algebra — the formal foundation of SQL (covered in CS_48) — is defined in terms of predicates and set operations that correspond directly to existential and universal quantification. JOIN operations correspond to existential quantification over tuples. Understanding predicate logic gives deep insight into why SQL queries behave the way they do, particularly for complex subqueries with EXISTS and NOT EXISTS.

19. Next Steps

• 👉 CS_02 — Sets, Relations & Functions — The set-theoretic companion to logic
• 👉 CS_03 — Graph Theory — Logic applied to graph structures
• 👉 CS_08 — Discrete Mathematics Formula Sheet — Rapid-revision reference for all of Discrete Maths
• 👉 CS_62 — Finite Automata (TOC) — Where logic meets formal language theory
• 👉 Back to Discrete Mathematics Hub
• 👉 Back to CS/IT Main Hub