notesonly.in

One notebook for every subject — open it anywhere.

Log in

Propositional and Predicate Logic: Complete Beginner's Guide

EngineeringTry the interactive 3D model →

Propositional logic studies statements that are either true or false — propositions — and how they combine with AND, OR, and NOT. Predicate logic extends this with predicates (statements about objects, like "x is even") and quantifiers: "for all" and "there exists". Together they are the formal language of mathematical reasoning.

Logic is the operating system of rigorous thought in computer science. Digital circuits are physical embodiments of propositional formulas, database queries are predicate logic in disguise, and every program correctness proof is written in these symbols.

Key Concepts

  • Proposition: a declarative sentence with a definite truth value, e.g. "7 is prime" (true).
  • Connectives: NOT, AND, OR, IMPLIES, IF-AND-ONLY-IF — building compound statements from simpler ones.
  • Truth table: lists a formula's value for every combination of its variables' truth values.
  • Tautology / contradiction: always true (P OR NOT P) or always false (P AND NOT P), regardless of inputs.
  • Quantifiers: "for all x, P(x)" means P holds for every x; "there exists x, P(x)" means for at least one x — order matters.

Formulas

  • De Morgan's laws: NOT (P AND Q) ≡ (NOT P) OR (NOT Q); NOT (P OR Q) ≡ (NOT P) AND (NOT Q) — negation flips AND to OR.
  • Implication: "P implies Q" ≡ "(NOT P) OR Q" — false only when P is true and Q is false.
  • Contrapositive: "P implies Q" ≡ "(NOT Q) implies (NOT P)" — always the same truth value.
  • Quantifier negation: NOT ("for all x, P(x)") ≡ "exists x, NOT P(x)" — "not all birds fly" means "some bird does not fly".

Worked Example

Verify De Morgan's law — NOT (P AND Q) equals (NOT P) OR (NOT Q) — with a 4-row truth table:

  1. P=T, Q=T: NOT(P AND Q) = F; (NOT P) OR (NOT Q) = F OR F = F. Match.
  2. P=T, Q=F: NOT(P AND Q) = T; F OR T = T. Match.
  3. P=F, Q=T: NOT(P AND Q) = T; T OR F = T. Match.
  4. P=F, Q=F: NOT(P AND Q) = T; T OR T = T. Match.

All 4 rows agree, so the formulas are logically equivalent — proved by exhaustive checking, which is exactly what truth tables are for.

Common Misconceptions

  • "If P then Q" means P causes Q. Implication is truth-functional: "if the moon is cheese, then 2+2=5" is vacuously true — no causation implied.
  • "For all x exists y" equals "exists y for all x". "Everyone has someone who loves them" differs from "someone loves everyone" — order changes meaning.
  • Logic is about opinions. Formal logic cares only about form: a valid argument's conclusion follows from its premises regardless of topic.

Real-World Applications

  • Digital circuits: AND/OR/NOT gates implement connectives; chip verification checks formula equivalence.
  • Databases: SQL WHERE clauses are predicate-logic formulas over tables.
  • Program verification: preconditions and postconditions are logical formulas proved about code.
  • AI: expert systems and Prolog reason with predicates and quantifiers.

Propositional logic is a precise algebra of true and false; predicate logic adds objects and quantities. From truth tables to quantifiers, these tools turn fuzzy reasoning into calculation — the foundation beneath circuits, databases, and every proof in computer science.

Related blogs