Propositional logic is a branch of logic concerned with the logical relationships between statements and their combinations. It represents statements by symbols and connects them using operators corresponding to expressions such as “not,” “and,” and “or.” Unlike first-order logic, it does not analyze statements into objects, predicates, and quantifiers. Its standard classical interpretation assigns each statement exactly one of two truth values: true or false. Propositional systems also include nonclassical alternatives with different interpretations or inference rules. (plato.stanford.edu)
Language and connectives
The syntax of a propositional language specifies its well-formed formulas. Propositional variables, commonly written (p,q,r), are atomic formulas. If (A) and (B) are formulas, expressions such as (\neg A), ((A\land B)), and ((A\to B)) are also formulas. Repeated application of these formation rules generates arbitrarily complex expressions. Parentheses distinguish structures that might otherwise be ambiguous. Some languages additionally include constants (\top) and (\bot), representing truth and falsity. (cs.cmu.edu)
The principal logical connectives have the following classical meanings:
| Connective | Notation | Truth condition |
|---|---|---|
| Negation | (\neg A) | True exactly when (A) is false |
| Conjunction | (A\land B) | True exactly when both components are true |
| Disjunction | (A\lor B) | True when at least one component is true |
| Material implication | (A\to B) | False exactly when (A) is true and (B) is false |
| Biconditional | (A\leftrightarrow B) | True exactly when the components have matching truth values |
Disjunction here is inclusive; exclusive OR instead requires exactly one true component. (plato.stanford.edu)
Material implication is particularly important to distinguish from everyday conditionals. It is equivalent to (\neg A\lor B), so it is true whenever its antecedent is false. It does not, by itself, assert causation, temporal order, or any substantive connection between antecedent and consequent. Translating ordinary language therefore requires attention to which aspects of meaning the formalization preserves. (plato.stanford.edu)
Semantics and truth tables
Classical semantics begins with a valuation assigning true or false to every propositional variable. The truth conditions of the connectives extend this assignment to compound formulas. A truth table displays all assignments relevant to a formula; with (n) distinct variables, there are (2^n) rows. For example: (plato.stanford.edu)
| (p) | (q) | (p\land q) | (p\to q) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | F | T |
| F | F | F | T |
A tautology is true under every valuation, as with (p\lor\neg p). A contradictory formula, such as (p\land\neg p), is false under every valuation. A contingent formula is true under some valuations and false under others. A formula is satisfiable if at least one valuation makes it true; several formulas are jointly satisfiable if one valuation makes all of them true. (forallx.openlogicproject.org)
Consequence and equivalence
Logical validity concerns truth preservation rather than the actual truth of particular premises. Writing (\Gamma\models A) means that every valuation satisfying all premises in (\Gamma) also satisfies (A). An invalid argument has a countervaluation: an assignment making every premise true and its conclusion false. Consequently, validity alone does not establish that an argument’s premises describe the world correctly. (plato.stanford.edu)
For example, (p) and (p\to q) entail (q), illustrating modus ponens. But (q) and (p\to q) do not entail (p): both premises remain true when (q) is true and (p) false. This invalid pattern is the fallacy of affirming the consequent. (cs.cmu.edu)
Two formulas are logically equivalent when they have identical truth values under every valuation. De Morgan’s laws, for instance, equate (\neg(A\land B)) with (\neg A\lor\neg B). Such equivalences connect propositional reasoning with Boolean algebra and permit transformations that preserve truth conditions. (plato.stanford.edu)
Proof systems
Semantic consequence is distinguished from derivability, written (\Gamma\vdash A). A formal proof derives a conclusion through explicitly permitted rules. Systems studied in proof theory include axiomatic calculi, natural deduction, sequent calculi, and tableaux. They provide different presentations of deductive reasoning rather than different truth tables. (openlogicproject.org)
A proof system is sound when derivability implies semantic consequence, and complete when semantic consequence implies derivability. Standard classical propositional calculi satisfy both properties. Thus truth-table validity and formal provability agree, although constructing a proof and enumerating valuations can involve very different amounts of work. (forallx.openlogicproject.org)
Normal forms and computation
Every classical propositional formula has an equivalent conjunctive normal form: a conjunction of clauses, each a disjunction of literals. A literal is a variable or its negation. There is also an equivalent disjunctive normal form, consisting of a disjunction of conjunctions. Negation together with conjunction and disjunction is functionally complete: these connectives can express every finite Boolean truth function. (plato.stanford.edu)
The Boolean satisfiability problem, or SAT, asks whether a formula has a satisfying valuation. Exhaustive truth-table enumeration supplies a terminating algorithm, establishing decidability. Nevertheless, SAT is NP-complete, making it central to computational complexity. Search procedures such as DPLL combine branching with propagation of forced assignments. Inference can also be tested through satisfiability: a finite collection of premises entails (A) exactly when their conjunction with (\neg A) is unsatisfiable. (cs.cmu.edu)
Applications and scope
In computer science, propositional formulas describe logic gates and switching circuits, and support automated reasoning. In artificial intelligence, they can encode facts, rules, and planning constraints in a knowledge base. Their limitations arise from treating atomic statements as unanalyzed units: general claims about all objects require richer languages. Modal logic adds operators for necessity and possibility, while intuitionistic logic provides a nonclassical propositional system in which classical principles such as unrestricted excluded middle are not generally derivable. (plato.stanford.edu)