Propositional Logic

The five standard connectives are conjunction (AND, symbolized ∧), disjunction (OR, ∨), negation (NOT, ¬), material implication (IF...THEN, →), and biconditional (IF AND ONLY IF, ↔). These connectives combine atomic propositions—statements that are either true or false—into compound propositions whose truth values are fully determined by truth tables. Propositional logic does not include quantifiers, which are introduced in first-order predicate logic.

Propositional logic underpins digital circuit design, where logic gates (AND, OR, NOT gates) physically implement Boolean functions in processors and memory. It is also the basis for SAT (satisfiability) solving, which is used in formal verification of software and hardware, automated theorem proving, and artificial intelligence planning. Modern SAT solvers can handle propositional formulas with millions of variables.

Propositional logic deals only with whole propositions and their connectives, while first-order (predicate) logic introduces variables, predicates, and quantifiers such as ∀ (for all) and ∃ (there exists). This allows first-order logic to express statements like 'every person is mortal,' which propositional logic cannot represent. Propositional logic is decidable—any valid formula's truth can be determined mechanically—whereas first-order logic is only semi-decidable.

A truth table enumerates every possible combination of truth values for the input propositions and shows the resulting truth value of the compound expression for each combination. For a formula involving n distinct atomic propositions, the table requires exactly 2 to the power of n rows. For example, a formula with variables P and Q needs 4 rows: (T,T), (T,F), (F,T), and (F,F).