A propositional substitution maps each atomic propositional variable to a propositional formula and extends recursively through every logical connective. Replacements are simultaneous: a variable appearing inside a replacement formula is not replaced again in the same substitution step. Since propositional logic has no variable-binding quantifiers, this operation has no variable-capture problem.
Propositional theory Created 2026-10-07 Updated 2026-10-14
Propositional type 2026-10-07
A propositional type is a collection of propositional formulas to be jointly realized by a Boolean valuation. A valuation realizes it when every member is true and omits it when some member is false. For propositional omission arguments, the collection need not itself be consistent.
Propositional variable 2026-10-31
A propositional variable is an atomic symbol assigned a truth value by a Boolean valuation. A propositional formula is built from these symbols by logical connectives. The variables carry no quantifiers over individuals; their values may be chosen independently.
Propositional variable elimination Created 2026-10-14 Updated 2026-10-25
The displayed identity follows by testing the two possible truth values of . Existentially forgetting gives . Repeating this operation produces a propositional formula on a specified remaining vocabulary. Logical truth constants are needed if that vocabulary is empty.
For each , a propositional formula over specified variables can have exactly satisfying assignments and length . For , interpret a Boolean valuation as the binary number and test whether it is less than .
For every position with , use a conjunction asserting that all earlier bits equal and , leaving later bits unrestricted. Take the disjunction of these terms. Each satisfying assignment has a unique first differing position, so the terms are disjoint, and their counts sum to . Their combined length is . Use logical falsity and logical truth at the two endpoints. The count is over all variables, including those absent from an individual term or from the whole formula.
Replacing a designated subformula by a logically equivalent formula preserves logical equivalence of the surrounding propositional formulas. For any Boolean valuation the two expressions at the replaced node have the same truth value. Each logical connective preserves this agreement when its other inputs are unchanged. Induction from that node to the root proves agreement of the whole formulas under every valuation.
Search-to-decision reduction Created 2026-09-24 Updated 2026-11-05
A search-to-decision reduction reconstructs a valid witness by querying a procedure that answers only whether an appropriate witness exists. The reduction must specify how it restricts the original task after each answer and how many queries it uses.
For Boolean satisfiability, first ask whether the propositional formula is satisfiable. If it is, consider its Boolean variables in order. Tentatively fix the next variable to zero and ask whether a satisfying extension remains. Keep zero after a positive answer; after a negative answer, fix it to one. The previously satisfiable partial assignment must have an extension using one of those values, so this step preserves existence of an extension.
After all variables are fixed, the resulting assignment is a witness. There are at most decision queries, and each restricted propositional formula has size bounded by the original size. Thus a polynomial-time algorithm for deciding Boolean satisfiability would also give a polynomial-time algorithm for finding a satisfying assignment. The procedure proves this relation for the specified task rather than assuming arbitrary search specifications have the same reduction.
Semantic entailment 2026-10-31
A propositional formula semantically entails when every Boolean valuation satisfying satisfies . Equivalently, is an unsatisfiable Boolean formula. Deciding semantic entailment is co-NP-complete: a counterexample Boolean valuation certifies failure in polynomial time, while reduces unsatisfiability to semantic entailment.
Lengths of formulas logically equivalent to a fixed propositional formula form a nonempty subset of the natural numbers, so a minimum exists. With variables counted as atomic symbols and no truth constants, and are distinct shortest tautologies. A formula with no binary connective is a variable preceded by negations and cannot be a tautology. Thus minimization need not give a canonical representative.
Subformula 2026-10-25
A subformula is a constituent propositional formula in a formula's recursive construction, including the whole formula itself. For an atomic variable the only subformula is itself; for , add to the subformulas of ; for a binary connective, add the combined formula to the union of the two operands' subformulas. The set of distinct subformulas can have smaller cardinality than the number of occurrences in the abstract syntax tree when the same expression appears more than once.
Replacing one designated subformula occurrence in a propositional formula by another propositional formula preserves well-formedness. Induct on the context surrounding the occurrence: at the root the result is the replacement formula; under a connective apply the induction hypothesis to the affected child and rebuild the parent using its formation rule.
Tautology Created 2026-10-14 Updated 2026-10-25
A tautology is a propositional formula true under every Boolean valuation in classical propositional logic, such as the law of excluded middle . A primitive proposition is not a tautology, even if it represents a true statement. See forall x: Calgary, section 12.1.
Truth table Created 2026-09-29 Updated 2026-10-14
A truth table lists a propositional formula's value for every Boolean valuation of its distinct primitive propositions. With primitive propositions, there are rows: each independently receives T or F. Evaluate compound columns from their subexpressions using the classical rules for logical connectives. This is exhaustive checking, so a formula true on every row is valid in classical propositional logic.
For a computed example over the natural numbers, let mean that is an even number and mean . The choices realize respectively : all four possible inputs.
The logical implication and its contrapositive agree on every row; the converse implication differs on two rows. A truth table therefore checks equivalence or supplies a counterexample. Classical truth conditions are given in forall x: Calgary, section 31.2. These two-valued truth tables do not characterize validity in Intuitionistic propositional logic.
Truth value 2026-10-14
In classical propositional logic, a truth value is false or true, encoded by a bit as zero or one. A Boolean valuation assigns these values to primitive propositions and extends to compound propositional formulas through logical connectives.
A propositional formula with two blocks of quantified Boolean variables. Determining the truth of an existential-then-universal instance is a canonical complete problem for the existential second level of the polynomial hierarchy, . For completeness one may restrict the matrix to a disjunction of terms with at most three literals. The order of the quantifiers matters: the assignment to must work for every assignment to .
A finite rule base pairs propositional formulas with weights and sums the weights of the formulas satisfied by a Boolean valuation. Over a finite set , associate one Boolean variable to membership of each element. Any utility function is represented by giving each subset's minterm weight . Exactly one rule fires at each valuation, so at most rules suffice. This bound counts rules, not the symbols required to write all formulas.
For computational questions, the weight encoding matters. Binary rational numbers permit exact addition and comparison in polynomial time; unrestricted real constants do not specify an ordinary finite input encoding.
Yunshan Zhu Created 2026-10-31 Updated 2026-11-05
Yunshan Zhu coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]