Alessandro Cimatti Created 2026-10-31 Updated 2026-11-05
Alessandro Cimatti 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]
Armin Biere Created 2026-10-31 Updated 2026-11-05
Armin Biere 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]
Axiom-only complete propositional calculus 2026-10-31
Take precisely the propositional tautologies as axioms and supply no inference rules. A one-line proof then establishes exactly the valid propositional formulas, so this calculus is sound and complete for theoremhood. Its axiom set is decidable by finite truth tables. This construction does not by itself give strong completeness for consequence from arbitrary assumptions.
Balanced parentheses in propositional syntax 2026-10-25
Every propositional formula generated by a parenthesized grammar has equally many opening and closing parentheses. By structural induction, atomic formulas begin with equal zero counts; negation preserves them; and a parenthesized binary logical connective adds its two subformula counts and one parenthesis of each kind. An optional paired-parenthesis construction also adds one to both counts. This necessary syntactic invariant is useful for checking generated expressions, though equal counts alone do not guarantee correctly nested syntax.
Boolean formula Created 2026-10-06 Updated 2026-10-18
A Boolean formula is a finite expression built from Boolean variables and Boolean operations, equivalently a propositional formula with two-valued semantics. A Boolean valuation determines its truth value. In , logical negation acts only on , and the outer logical conjunction combines with . Occurrences of the same Boolean variable share one truth value. The Boolean satisfiability problem asks whether some Boolean valuation makes the Boolean formula true.
Boolean game 2026-10-24
A finite game represented succinctly by propositional logic. Each player controls a disjoint collection of Boolean variables and chooses their truth values. Together those choices determine a Boolean valuation. A player's goal is a propositional formula, with payoff one if satisfied and zero otherwise. The control sets normally form a set partition of all variables.
A pure strategy strategy profile is a Nash equilibrium if every unsatisfied player remains unsatisfied after every change to that player's controlled variables. Checking a candidate can therefore require solving a Boolean satisfiability problem, even though evaluating its current payoffs is easy.
Boolean valuation Created 2026-09-29 Updated 2026-10-14
A Boolean valuation assigns each primitive proposition a value in , equivalently , and extends recursively to every propositional formula using the classical logical connectives. The same primitive proposition always receives the same value within one Boolean valuation. For compound propositional formulas and ,Every other case receives the opposite value. Thus gives . A truth table varies the assignment; recursive evaluation computes one row. The truth-functional restriction means that changing what the primitive propositions describe, while retaining their values, cannot change the value of the compound propositional formula. See forall x: Calgary, chapter 9 and section 10.1.
Given a succinct Boolean game and a complete pure strategy strategy profile, determine whether it is a Nash equilibrium. The problem is co-NP-complete for goal propositional formulas, even with one player. This differs from existential equilibrium checking in a Boolean game, which searches for some qualifying Nash equilibrium.
A negative instance has a short complexity certificate: a currently unsatisfied player and new truth values for that player's controlled Boolean variables that make the goal true. Evaluating the current and changed propositional formulas takes polynomial time, proving membership in co-NP.
For hardness, given a propositional formula , let one player control and a fresh variable , with goal . The all-false candidate has payoff zero. It is a Nash equilibrium exactly when is an unsatisfiable Boolean formula, since any satisfying assignment permits an improvement by also setting true. This is a polynomial-time many-one reduction from unsatisfiability. The fresh guard ensures that the candidate loses independently of the input formula's value there.
co-NP 2026-10-24
The class of decision problems whose complements belong to NP. Equivalently, negative instances admit polynomially bounded witnesses verifiable in polynomial time. A problem is co-NP-complete when it is in co-NP and every problem in co-NP has a polynomial-time reduction to it. Unsatisfiability of a propositional formula is a basic example: its complement is the NP-complete Boolean satisfiability problem.
Counting complexity Created 2026-09-28 Updated 2026-11-05
Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation and a polynomial , a standard counting function isThe complexity class consists of these functions, equivalently the numbers of accepting computations of Nondeterministic Turing machines running in polynomial time. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.
For the propositional formula , the satisfying Boolean valuations are , and , so the answer is three. The associated decision problem asks only whether that count is positive. For a zero-one matrix, the permanent of a matrix counts perfect matchings in a bipartite graph. Testing whether any such perfect matching exists admits a polynomial-time algorithm, while counting them is -complete under polynomial-time Turing reductions.[ref]
De Morgan's laws Created 2026-09-28 Updated 2026-10-14
De Morgan's laws exchange logical conjunction and logical disjunction when a logical negation moves across them:Here denotes logical equivalence: the two propositional formulas agree under every Boolean valuation.[ref]
3.1 Propositional Logic. Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin; Discrete Mathematics: An Open Introduction, 3rd edition by Oscar Levin, §3.1, Logical Equivalence: definition, Example 3.1.3 and De Morgan's Laws box
A complete verification uses the four rows of a truth table. In input order , both sides of the first logical equivalence have output sequence ; both sides of the second have . A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing logical negation inward without changing AND to OR is wrong.
For the events in Boolean operations on events, the corresponding set identities areOne can prove these identities by checking an arbitrary set element : its two membership truth values obey De Morgan's laws. The same reasoning works for any two subsets of a common universal set.
De Morgan's laws shade the same set whether a compound event is complemented first or its component events are complemented first
. Details. For a nested program test, let mean “backup recent”, mean “backup verified”, and mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present givesThe transformed condition reads “backup stale or unverified, and no override”. Apply the second of De Morgan's laws at the outside, then the first at the inner logical conjunction. For it rejects; changing only to one makes it accept. With Boolean operands in Python,
not ((recent and verified) or override) and ((not recent) or (not verified)) and (not override) have the same result and inspect the operands in the same order, with the same skipped operands. Edmund Clarke Created 2026-10-31 Updated 2026-11-05
Edmund Clarke 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]
Endpoint-false disjunctive normal form 2026-10-31
A propositional formula false on the all-true and all-false Boolean valuations has a disjunctive normal form in which every minterm contains a positive literal and a negative literal. Grouping the positive propositional variables into and the negated propositional variables into the negation of a logical disjunction writes each minterm as . De Morgan's laws therefore give the negation of a logical conjunction of such logical implications. For a contradiction use .
Given two weighted formula utility representations with binary rational numbers as weights, decide whether their values agree on every Boolean valuation. This problem is co-NP-complete.
For membership, a valuation witnessing unequal values certifies non-equivalence. Evaluate all propositional formulas and add their weights exactly in polynomial time. For hardness, compare the one-rule base with the empty base. They are equivalent exactly when is an unsatisfiable Boolean formula. Thus even very small weighted rule bases express a universal equivalence question.
Given a Boolean game and a query propositional formula , decide whether some pure strategy Nash equilibrium satisfies . The problem is complete for the existential second level of the polynomial hierarchy.
For membership, existentially choose a Boolean valuation and universally check every player's every unilateral deviation. The goal must remain false under all such deviations for each player whose goal is currently false. Each individual check takes polynomial time.
For hardness, start with a two-block quantified Boolean formula . Give player 1 control of and the constant true goal. Give player 2 control of and goal , and use as the query. A queried Nash equilibrium exists exactly when some choice of leaves player 2 unable to falsify by changing . This is precisely the input quantified statement, and the construction is a polynomial-time reduction.
Finite-variable dependence of a propositional rule base Created 2026-10-25 Updated 2026-10-31
Every finite collection of finite propositional formulas mentions only finitely many Boolean variables. Two Boolean valuations agreeing on those variables satisfy exactly the same formulas. They therefore have the same value under any weighted formula utility representation using that collection.
This observation limits representation over infinite sets. On , the function indicating whether the selected subset is infinite cannot be represented by a finite rule base: if is the finite set of mentioned indices, and agree on all those indices but require values zero and one. Completeness claims for finite propositional rule bases must therefore specify a finite underlying set or restrict the functions represented.
Formation rule Created 2026-10-31 Updated 2026-11-05
A formation rule specifies how well-formed expressions can be constructed from simpler expressions in a formal language. The formal grammar of propositional formulas has rules for propositional variables, negation and binary logical implication.
Logical equivalence Created 2026-10-14 Updated 2026-10-25
Two propositional formulas are logically equivalent in classical propositional logic when they have the same truth value under every Boolean valuation. Identical output columns in a truth table prove logical equivalence; one differing row refutes it. De Morgan's laws give useful examples.
Logical formula Created 2026-10-31 Updated 2026-11-05
A logical formula is a finite expression constructed by the formation rules of a formal language. Propositional formulas combine propositional variables by logical connectives. First-order formulas additionally contain terms, atomic relations and quantifiers. A logical formula is a syntactic object; its truth is determined only after specifying a suitable interpretation and values for its free variables.
Maximal consistency in propositional logic 2026-10-31
A propositionally consistent theory is maximally consistent when every proper extension by a new propositional formula is inconsistent. It decides each propositional formula or its negation.
