Propositional

Propositional refers to propositions—statements that can be either true or false—and is most commonly encountered in propositional logic, also called sentential logic. This branch of logic abstracts away the internal structure of statements and studies how truth-values combine under logical connectives.

A propositional formula is built from propositional variables (for example p, q, r) and logical connectives such as negation (not), conjunction (and), disjunction (or), implication (if... then), and biconditional (if and only if). Semantics assign each variable a truth value and define the value of complex formulas via truth tables. For instance, p ∧ q is true exactly when both p and q are true; p → q is false only when p is true and q is false.

Syntactically, a proof system provides rules to derive formulas. Modus ponens is a central rule: from p and p → q, infer q. Propositional logic can be formalized in various systems, including Hilbert-style, natural deduction, and sequent calculus. The formulas that are true under every interpretation are called tautologies; those that are true under at least one interpretation are satisfiable.

Propositional logic is distinct from predicate logic, which adds quantifiers and the internal structure of propositions through predicates and variables. It underpins areas such as digital circuit design, automated theorem proving, and formal verification. Its decision problems, such as tautology and satisfiability, are well-studied and decidable, with computational complexity that reflects the size of the formulas involved.