Logic: propositional and predicate

In short

Propositional (sentential) logic treats whole statements as atoms joined by connectives — not, and, or, if-then, if-and-only-if — and asks whether a form is a tautology, a contradiction or contingent, and whether an argument is valid. Predicate (first-order, quantificational) logic looks inside the statement at individuals, predicates, relations and the quantifiers "all" and "some", so it can validate arguments propositional logic cannot. It is core to BA Philosophy logic papers under UGC CBCS, to UGC-NET Paper 1 reasoning and Philosophy Paper 2, and to CUET-PG; the same material appears as Discrete Mathematics ("propositional and first-order logic") in GATE CS, and in CLAT/judiciary legal-reasoning sections. Employers use it in software testing and SQL conditions, in rule engines at Indian banks and insurers, in SAT/model-checking tools at chip-design centres (Intel, NVIDIA, Synopsys, Cadence in Bengaluru, Noida, Pune), and in any interview question about boolean conditions.

Explained

1. Propositions, connectives and well-formed formulas

• A proposition is a declarative sentence with exactly one truth value, T or F. Questions, commands, exclamations and open sentences ("x > 3") are not propositions.
• Simple (atomic) propositions are symbolised by p, q, r…; compound ones are built with connectives. Propositional logic is two-valued, truth-functional and extensional: the value of a compound depends only on the values of its parts.
• The five standard connectives, with Indian textbook notation (Copi) in brackets:
  • Negation ¬p (~p) — "not p"; unary.
  • Conjunction p ∧ q (p·q) — true only when both are true.
  • Disjunction p ∨ q — inclusive "or": false only when both are false. Exclusive or (p ⊻ q) is a separate connective, true when exactly one holds.
  • Material implication p → q (p ⊃ q) — false only when p is T and q is F; p is the antecedent, q the consequent.
  • Biconditional p ↔ q (p ≡ q) — true when both have the same value.
• Scope and brackets: the main connective decides the formula's kind. Precedence ¬ > ∧ > ∨ > → > ↔; → is right-associative. p ∨ q ∧ r reads p ∨ (q ∧ r), so brackets are safer.
• Well-formed formula (wff): every atom is a wff; if A, B are wffs so are ¬A, (A∧B), (A∨B), (A→B), (A↔B) — nothing else is.
• Paradoxes of material implication: a false antecedent or a true consequent makes p → q true ("If the moon is cheese, Delhi is in India" is true). → captures truth-functional dependence, not causation or relevance — the standard answer to this exam question.

2. Truth tables, status of formulas and validity

• A formula with n distinct atoms needs 2ⁿ rows; list values in a fixed order so no row is missed.
• Tautology (logically true) — T in every row; contradiction (logically false) — F in every row; contingent (contingency) — at least one T and one F.
• Satisfiable = true in at least one row (has a model); unsatisfiable = contradiction. A formula is a tautology iff its negation is unsatisfiable.
• Logical equivalence A ≡ B: same column in every row, i.e. A ↔ B is a tautology. Logical implication A ⊨ B: no row has A true and B false.
• Validity of an argument: premises P₁…Pₙ, conclusion C is valid iff (P₁∧…∧Pₙ) → C is a tautology, equivalently iff P₁∧…∧Pₙ∧¬C is unsatisfiable. Soundness (in the ordinary sense) adds that the premises are in fact true.
• Consistency of a set of propositions: some single assignment makes all of them true.
• Decision procedures: (a) full truth table, (b) reduced/shorter truth-table method — assume the conclusion false and the premises true and look for contradiction, (c) truth trees (semantic tableaux) — decompose until every branch closes, (d) natural deduction (proof, not a decision procedure for invalidity), (e) resolution on CNF.
• Propositional logic is decidable — the truth table always terminates — but the table grows as 2ⁿ, which is why SAT solvers exist; SAT was the first problem proved NP-complete (Cook, 1971).

3. Equivalences, implication forms and valid argument forms

• Standard equivalences (replacement rules): Double negation ¬¬p ≡ p; De Morgan ¬(p∧q) ≡ ¬p∨¬q and ¬(p∨q) ≡ ¬p∧¬q; Commutation, Association; Distribution p∧(q∨r) ≡ (p∧q)∨(p∧r); Material implication p→q ≡ ¬p∨q; Transposition p→q ≡ ¬q→¬p; Exportation (p∧q)→r ≡ p→(q→r); Tautology/Idempotence p∨p ≡ p; Material equivalence; Absorption; Identity and Domination (p∧T ≡ p, p∨T ≡ T).
• Duality: interchanging ∧ with ∨ and T with F turns an equivalence into its dual.
• Four related conditionals: given p→q — converse q→p, inverse ¬p→¬q, contrapositive ¬q→¬p. Only the contrapositive is equivalent to the original; converse and inverse are equivalent to each other.
• Necessary and sufficient: in p→q, p is sufficient for q and q is necessary for p. "Only if" introduces the consequent: "p only if q" = p→q. "Unless" = "if not": "p unless q" = ¬q→p ≡ p∨q.
• Valid elementary argument forms (rules of inference): Modus ponens (p→q, p ⊢ q); Modus tollens (p→q, ¬q ⊢ ¬p); Hypothetical syllogism (p→q, q→r ⊢ p→r); Disjunctive syllogism (p∨q, ¬p ⊢ q); Constructive dilemma ((p→q)∧(r→s), p∨r ⊢ q∨s); Destructive dilemma; Simplification, Conjunction, Addition, Absorption.
• Formal fallacies: affirming the consequent (p→q, q ⊢ p) and denying the antecedent (p→q, ¬p ⊢ ¬q) — both invalid; also illicit disjunctive syllogism when "or" is read exclusively without warrant.
• Natural deduction uses nine such rules of inference (Copi's list, which does not include Destructive Dilemma — that is a further valid form, derivable from the nine) plus ten replacement rules, with Conditional Proof (assume the antecedent, derive the consequent, discharge) and Indirect Proof / reductio (assume ¬C, derive a contradiction). Every assumption must be discharged before the proof ends.

4. Normal forms, resolution and adequate sets

• A literal is an atom or its negation; a clause is a disjunction of literals.
• DNF (disjunctive normal form) — a disjunction of conjunctions of literals; read off the T rows of the truth table. CNF — a conjunction of clauses; read off the F rows (negated) or get it by eliminating → and ↔, pushing ¬ inwards by De Morgan, then distributing.
• Principal/full (canonical) forms: every disjunct of the full DNF (a minterm) mentions every variable once; the number of minterms equals the number of models.
• Resolution: from clauses (A ∨ x) and (B ∨ ¬x) infer (A ∨ B). To prove an argument valid, convert premises and the negated conclusion to CNF and derive the empty clause (⊥). This is refutation-complete and is the engine of Prolog and of SAT/SMT tools.
• Functional completeness (adequacy): {¬, ∧, ∨} is adequate; so are {¬, ∧}, {¬, ∨}, {¬, →}. NAND (Sheffer stroke, p ↑ q) and NOR (Peirce arrow, p ↓ q) are each adequate on their own — the basis of universal gates in digital electronics. {∧, ∨} is not adequate (cannot express negation).
• Propositional logic is sound and complete (every provable formula is a tautology and every tautology is provable) and consistent.

5. Predicate logic: symbols, quantifiers and translation

• Why it is needed: "All MPs are citizens; Gandhi is an MP; so Gandhi is a citizen" is valid but, treated as three atoms p, q, r, is invalid in propositional logic. Predicate logic analyses the internal structure.
• Vocabulary: individual constants a, b, c (named objects); individual variables x, y, z; predicates F, G (one-place = properties) and R, L (two- or more-place = relations); function symbols f(x) in full first-order logic; the identity sign =; quantifiers.
• Quantifiers: universal ∀x (also (x)) — "for every x"; existential ∃x — "for at least one x". They are interdefinable: ∀xFx ≡ ¬∃x¬Fx.
• Standard translation patterns (the most examined item):
  • All S are P: ∀x(Sx → Px) — a conditional, never a conjunction.
  • No S is P: ∀x(Sx → ¬Px) ≡ ¬∃x(Sx ∧ Px).
  • Some S are P: ∃x(Sx ∧ Px) — a conjunction, never a conditional.
  • Some S are not P: ∃x(Sx ∧ ¬Px).
  • Only S are P: ∀x(Px → Sx).
  • All except S are P: ∀x(¬Sx → Px) (usually with ∀x(Sx → ¬Px) if "except" is exclusive).
• Scope, bound and free variables: a quantifier binds the variable in its scope; a variable not bound is free. A formula with a free variable is open (not true or false by itself); a formula with none is closed = a sentence. In ∀x(Fx → Gy), y is free.
• Nested quantifiers — order matters: ∀x∃y L(x,y) ("everyone loves someone") is weaker than ∃y∀x L(x,y) ("someone is loved by everyone"). ∃y∀x ⊨ ∀x∃y, not the converse. Mixing like quantifiers (∀x∀y, ∃x∃y) can be reordered freely.
• Identity and numerical claims: "exactly one F" = ∃x(Fx ∧ ∀y(Fy → y = x)); "at least two F" = ∃x∃y(Fx ∧ Fy ∧ x ≠ y). Russell's theory of definite descriptions analyses "the F is G" as ∃x(Fx ∧ ∀y(Fy→y=x) ∧ Gx).
• Semantics: an interpretation (model) fixes a non-empty domain of discourse and assigns objects to constants, sets to one-place predicates, sets of pairs to relations. A formula is valid if true in every interpretation, satisfiable if true in some. Standard first-order logic assumes a non-empty domain, which is why ∀xFx → ∃xFx comes out valid.

6. Predicate rules, quantifier equivalences and the big results

• Quantifier Negation (QN): ¬∀xFx ≡ ∃x¬Fx; ¬∃xFx ≡ ∀x¬Fx. Push the ¬ inwards and flip each quantifier: ¬∀x∃yR(x,y) ≡ ∃x∀y¬R(x,y).
• Distribution: ∀ distributes over ∧ and ∃ over ∨ — ∀x(Fx∧Gx) ≡ ∀xFx ∧ ∀xGx; ∃x(Fx∨Gx) ≡ ∃xFx ∨ ∃xGx. The crossed cases are not equivalences: ∀xFx ∨ ∀xGx ⊨ ∀x(Fx∨Gx) but not conversely; ∃x(Fx∧Gx) ⊨ ∃xFx ∧ ∃xGx but not conversely.
• Four quantifier rules of natural deduction, with their restrictions:
  1. UI (Universal Instantiation): from ∀xFx infer Fa for any constant — unrestricted.
  2. EI (Existential Instantiation): from ∃xFx infer Fa only for a new constant not occurring earlier in the proof or in the conclusion. Do EI before UI when both are available.
  3. EG (Existential Generalisation): from Fa infer ∃xFx — unrestricted.
  4. UG (Universal Generalisation): from Fa infer ∀xFx only if a is arbitrary — not introduced by EI and not free in any undischarged assumption.
• Proving invalidity: you cannot do it by failing to find a proof; you must give a counter-model — a small finite domain (often {1, 2}) with predicate extensions making the premises true and the conclusion false.
• Prenex normal form: every first-order formula is equivalent to one with all quantifiers in front; Skolemisation then removes ∃ for resolution theorem-proving.
• Metatheory to quote in exams: first-order logic is sound and complete (Gödel's completeness theorem, 1930) and compact; it is undecidable in general (Church and Turing, 1936) but semi-decidable — a valid formula will be proved eventually, an invalid one may loop. Monadic (one-place-predicate) first-order logic is decidable. Gödel's incompleteness theorems (1931) concern formal arithmetic, not first-order logic itself — a very common confusion.
• Limits and extensions: first-order logic cannot quantify over predicates (second-order logic can) and cannot express "most"; necessity and possibility need modal logic; three-valued, fuzzy and intuitionistic logics drop bivalence or excluded middle. Classical logic also assumes existential import issues away by requiring non-empty domains.

Key points

• Proposition — a declarative sentence with exactly one truth value; questions and open sentences are excluded.
• Truth-functionality — a compound's value is fixed by its components' values; this is why → is *material* implication.
• Material implication — p→q is false only in the single case T→F; equivalently ¬p∨q.
• 2ⁿ rows — a truth table over n atoms; 2^2ⁿ distinct truth functions of n variables.
• Tautology / contradiction / contingent — true in all rows, false in all rows, mixed.
• Validity — impossible for premises to be true with the conclusion false; equivalently premises ∧ ¬conclusion is unsatisfiable.
• Contrapositive — the only one of converse, inverse and contrapositive equivalent to p→q.
• Modus ponens and modus tollens — valid; affirming the consequent and denying the antecedent — formal fallacies.
• De Morgan's laws — negation turns ∧ into ∨ and ∨ into ∧, negating both parts.
• CNF / DNF — conjunction of clauses / disjunction of conjunctions; DNF reads off the true rows, CNF off the false rows.
• Resolution — refutation method: negate the conclusion, convert to CNF, derive the empty clause.
• NAND and NOR — each alone functionally complete, hence "universal gates".
• All S are P = ∀x(Sx→Px); Some S are P = ∃x(Sx∧Px) — conditional for "all", conjunction for "some".
• Quantifier Negation — ¬∀ ≡ ∃¬ and ¬∃ ≡ ∀¬.
• Quantifier order — ∃y∀x implies ∀x∃y, never the reverse.
• EI restriction — instantiate an existential to a brand-new constant; UG restriction — never generalise on a constant obtained by EI.
• Counter-model — the only way to prove a predicate-logic argument invalid; use a two-element domain.
• Metatheory — propositional logic decidable; first-order logic sound, complete, compact but undecidable (semi-decidable).

Formulas and examples

Example 1 — truth table and models of (p ∨ q) ∧ (¬q ∨ r). n = 3, so 8 rows.

Four models out of eight, so the formula is contingent and satisfiable. Full DNF = (p∧q∧r) ∨ (p∧¬q∧r) ∨ (p∧¬q∧¬r) ∨ (¬p∧q∧r) — four minterms, matching the four T rows.

Example 2 — valid versus fallacious conditional reasoning. "If the GST return is filed late, a late fee applies. A late fee applies. So the return was filed late." Let p = filed late, q = late fee. Form: p→q, q ⊢ p — affirming the consequent. Counterexample row: p = F, q = T → premises p→q = T and q = T, conclusion p = F. Premises true, conclusion false, so invalid. Now modus tollens: p→q, ¬q ⊢ ¬p. Test (p→q) ∧ ¬q → ¬p by the short method: assume conclusion ¬p false, so p = T; premise ¬q true, so q = F; then p→q = T→F = F, so a premise fails. No row makes premises true with the conclusion false — valid.

Example 3 — CNF conversion and a resolution refutation. Prove p→q, q→r, ¬r ⊢ ¬p. Clauses: (1) ¬p ∨ q, (2) ¬q ∨ r, (3) ¬r, and the negated conclusion (4) p.

• Resolve (1) and (2) on q → (5) ¬p ∨ r.
• Resolve (5) and (3) on r → (6) ¬p.
• Resolve (6) and (4) on p → ⊥ (empty clause).

The negation of the conclusion is inconsistent with the premises, so the argument is valid. The same result by natural deduction: 1, 2 give p→r by hypothetical syllogism; with ¬r, modus tollens gives ¬p.

Example 4 — symbolisation and quantifier negation. Domain: people. Sx = x is a student, Lx = x is a lecture, A(x,y) = x attends y, E(z) = z is an exam, P(x,z) = x passes z. "Every student who attends all lectures passes some exam": ∀x[(Sx ∧ ∀y(Ly → A(x,y))) → ∃z(Ez ∧ P(x,z))]. Its negation, driven inwards by QN and ¬(A→B) ≡ A∧¬B: ∃x[Sx ∧ ∀y(Ly → A(x,y)) ∧ ∀z(Ez → ¬P(x,z))] — "some student attends every lecture and passes no exam." Also note "No student passed" = ¬∃x(Sx ∧ Qx) ≡ ∀x(Sx → ¬Qx) — the two standard forms of the E proposition.

Example 5 — proving a predicate argument invalid by counter-model. Claim: ∀x(Fx → Gx), ∃x Gx ⊢ ∃x Fx. Take domain D = {1, 2}, extension of F = { } (empty), extension of G = {1}.

• ∀x(Fx→Gx): no object is F, so every conditional has a false antecedent — true.
• ∃x Gx: 1 is G — true.
• ∃x Fx: nothing is F — false.

Premises true, conclusion false in this interpretation, so the argument is invalid. (Swapping the second premise with the conclusion — ∀x(Fx → Gx), ∃x Fx ⊢ ∃x Gx — gives a valid argument by EI, UI, modus ponens and EG.)

Where it is used

• Software and IT services (TCS, Infosys, Wipro, Cognizant, Accenture India): writing and simplifying boolean conditions, SQL WHERE clauses with AND/OR/NOT and NULL-aware three-valued logic, De Morgan refactoring of if statements, and decision-table test design in QA.
• Chip design and formal verification (Intel, NVIDIA, Qualcomm, Synopsys, Cadence, Texas Instruments in Bengaluru, Noida, Hyderabad): SAT/SMT solvers, model checking and assertion-based verification rest on CNF and resolution; NAND/NOR universality underlies gate-level design.
• AI, data and rule engines: Prolog and Datalog, knowledge graphs and ontologies (OWL/description logics), credit-approval and claims rule engines in Indian banks, NBFCs and insurers, and policy rules in UPI/KYC compliance checks.
• Law and public examinations: CLAT and judicial-service legal-reasoning sections, and drafting — statutory conditions turn on "and"/"or", "only if", "unless" and "provided that"; necessary-versus-sufficient condition analysis is a standard legal-reasoning skill.
• Teaching and research: BA/MA Philosophy logic papers, UGC-NET Philosophy, and the Discrete Mathematics paper of GATE CS; also the aptitude and logical-reasoning rounds of banking (IBPS), SSC and campus placement tests.
• Mathematics and engineering proof work: precise statement of theorems with ∀/∃, proof by contraposition and by contradiction, and the ε-δ definitions in analysis, which are nested-quantifier statements.

Interview questions

• Q: What is the difference between propositional and predicate logic? A: Propositional logic treats statements as indivisible atoms joined by connectives; predicate logic analyses their inner structure into individuals, predicates and quantifiers, so it validates arguments such as "all men are mortal; Socrates is a man; so Socrates is mortal" that propositional logic cannot.
• Q: When is p → q false? A: Only when p is true and q is false; in all three other combinations it is true, which is why it is called *material* implication.
• Q: Is p → q equivalent to its converse? A: No. It is equivalent only to its contrapositive ¬q → ¬p; the converse q → p is equivalent to the inverse ¬p → ¬q.
• Q: How do you prove an argument valid using a truth table, and how do you shorten it? A: Show that (premises) → conclusion has T in every row; the short way is to assume the conclusion false and the premises true and show that this assignment is impossible.
• Q: What is the difference between validity and truth? A: Validity is a property of the inference — the conclusion cannot be false if the premises are true; truth is a property of the individual statements. A valid argument can have false premises, and an invalid one can have a true conclusion.
• Q: Why is {NAND} functionally complete? A: ¬p = p↑p, p∧q = (p↑q)↑(p↑q) and p∨q = (p↑p)↑(q↑q), so every truth function can be built from NAND alone — hence it is a universal gate.
• Q: Translate "Only graduates are eligible." A: ∀x(Ex → Gx) — "only" makes the mentioned class the consequent, not the antecedent.
• Q: Does ∀x∃y L(x,y) imply ∃y∀x L(x,y)? A: No. "Everyone loves someone" does not give one person loved by everyone; the implication runs the other way only.
• Q: Negate "Some students passed all papers." A: ∃x(Sx ∧ ∀y(Py → Passed(x,y))) becomes ∀x(Sx → ∃y(Py ∧ ¬Passed(x,y))) — every student failed at least one paper.
• Q: How do you show a predicate-logic argument is invalid? A: Give a counter-model — a non-empty domain, usually of one or two elements, with predicate extensions that make all premises true and the conclusion false.
• Q: What is the restriction on Existential Instantiation, and why? A: The instantiating constant must be new to the proof and absent from the conclusion; otherwise you would wrongly assume the existing object is one already named, allowing invalid derivations.
• Q: Is first-order logic decidable? A: No — Church and Turing showed validity in first-order logic is undecidable; it is semi-decidable, since a sound and complete proof system will eventually prove any valid formula. Propositional logic is decidable, though SAT is NP-complete.
• Q: What does Gödel's completeness theorem say, and how is it different from incompleteness? A: Completeness (1930) says every first-order logical truth is provable in the system; incompleteness (1931) says any consistent, sufficiently strong formal theory of arithmetic has true arithmetical sentences it cannot prove — a claim about arithmetic, not about logic itself.

Common mistakes

• Translating "All S are P" as ∀x(Sx ∧ Px) and "Some S are P" as ∃x(Sx → Px) — the first says everything is both S and P, the second is trivially satisfied by any non-S.
• Confusing a conditional with its converse, and inferring p from p→q and q (affirming the consequent) or ¬q from p→q and ¬p (denying the antecedent).
• Botching the negation of a conditional: ¬(p→q) is p ∧ ¬q, not ¬p → ¬q and not p → ¬q.
• Applying De Morgan without negating both components, or forgetting to flip the quantifier when moving ¬ across ∀/∃.
• Reversing nested quantifiers, or scoping wrongly — ∀x(Fx) → Gx leaves x free and is not a sentence at all.
• Violating the EI/UG restrictions: instantiating an existential to a constant already in use, or universally generalising on a constant introduced by EI.
• Claiming invalidity because no proof was found, instead of constructing a counter-model; and offering an empty domain, which classical predicate logic does not allow.
• Reading "or" as exclusive by default, treating "unless" as "and", or mixing up necessary with sufficient conditions in legal and verbal reasoning questions.

Related topics

Syllogisms · Critical reasoning: arguments and inferences · Set theory and Boolean algebra · Informal fallacies · Modal and many-valued logics · Philosophy of language and meaning.