Propositional Logic is the study of how whole statements (propositions) combine under logical connectives to yield valid or invalid inferences. A proposition is treated as having exactly one of two truth values—true or false—without analyzing internal structure like subjects, predicates, or quantifiers. The scope is intentionally limited: it models reasoning patterns based on operators such as NOT, AND, OR, IMPLIES, and IFF.
Because it ignores what propositions are “about,” Propositional Logic is often described as a logic of truth-functions. In this setting, the truth of a compound statement depends only on the truth values of its parts. This makes it a foundational entry point for Formal Reasoning and a standard bridge into Mathematical Logic and Discrete Mathematics.
The basic symbols of Propositional Logic include propositional variables (typically p, q, r) and connectives such as ¬ (negation), ∧ (conjunction), ∨ (disjunction), → (material implication), and ↔ (biconditional). Parentheses or precedence rules determine how formulas are parsed so that every expression is a well-formed formula (WFF). A common precedence order is ¬ strongest, then ∧, then ∨, then →, then ↔.
Even small formulas can express complex conditions; for example, (p → q) ∧ (q → r) captures a chain of implications. Converting formulas to standard forms like CNF or DNF is routine in proof and computation. These syntactic disciplines support systematic transformations used in Boolean Algebra and in automated theorem provers.
The semantics of Propositional Logic assigns each propositional variable a truth value in {T, F}, then evaluates compound formulas by truth tables. Each connective has a fixed rule: for instance, p ∧ q is true only when both are true, while p → q is false only when p is true and q is false. A formula is a tautology if it is true under every assignment, and a contradiction if false under every assignment.
Truth tables grow exponentially: with n distinct variables there are 2n possible valuations. For n = 10 variables, that is 210 = 1,024 rows; for n = 20 variables, 220 = 1,048,576 rows. This exponential blow-up is one reason practical tools use smarter techniques than full enumeration, especially in SAT Solving and modern verification pipelines.
An argument in Propositional Logic is valid when, in every valuation where all premises are true, the conclusion is also true. Proof systems capture validity syntactically through rules such as Modus Ponens (from p and p → q infer q), Modus Tollens, and introduction/elimination rules for ∧ and ∨. A sound system proves only valid statements; a complete system can prove every valid statement.
Normal forms provide standardized targets for reasoning and computation. Conjunctive Normal Form (CNF) is a conjunction of clauses, each clause being a disjunction of literals, and it underlies many decision procedures. Transformations like eliminating → and ↔, pushing negations inward (via De Morgan’s laws), and distributing ∨ over ∧ are common steps in moving from arbitrary formulas to CNF for Automated Theorem Proving.
The central computational task in Propositional Logic is satisfiability: whether there exists an assignment making a formula true. The SAT problem was the first shown NP-complete (Cook–Levin, 1971), and it remains a benchmark for complexity and practical optimization. While worst-case complexity is daunting, modern SAT solvers routinely handle instances with millions of variables and clauses in industrial settings, especially when structure and heuristics are favorable.
Applications are widespread: hardware design uses propositional encodings to check that circuits satisfy specifications, and software engineering uses SAT/SMT workflows to detect bugs and prove properties. Propositional abstractions also appear in configuration management and planning, where constraints are naturally expressed as Boolean conditions. The tight connection between formulas and circuits—where ∧, ∨, and ¬ correspond to gates—makes Propositional Logic a compact language for reasoning about digital systems and for linking to Computational Complexity concepts.
A common misconception is that p → q means “p causes q” or expresses real-world implication in a causal or temporal sense. In Propositional Logic, → is material implication with a precise truth condition: it is false only in the case T → F, and true otherwise, including when p is false. This can feel unintuitive, but it is what makes implication truth-functional and compatible with truth-table semantics.
Another myth is that Propositional Logic is “too simple to matter” outside textbooks. In reality, SAT-based methods are core to modern verification and optimization, and SAT is NP-complete, indicating expressive power and computational hardness rather than triviality. It is also mistaken to think truth tables are always the practical method; with 2n valuations, tables become infeasible quickly (for n = 30, there are 1,073,741,824 rows), motivating proof systems, normal forms, and solver heuristics.
Finally, some assume Propositional Logic can express all of mathematics or all natural-language reasoning. Without quantifiers (∀, ∃) and predicates, it cannot directly represent statements like “every number has a successor” or “some person is a doctor.” Those require richer systems such as first-order logic, though propositional fragments remain essential building blocks within larger formalisms and are often used as approximations in practice.