A propositional formula is built from atomic propositions using logical connectives. Unlike a first-order formula, it has no quantifiers over individuals. A Boolean valuation interprets its atoms as truth values and evaluates its connectives recursively.
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.
A subformula occurrence specifies a particular position in the syntax tree of a formula. Two occurrences can contain the same logical formula while being different nodes. Replacement of one occurrence does not necessarily replace the others.
Subformula replacement is the operation of replacing one specified subformula occurrence by another logical formula. Its preservation of well-formedness is the subformula replacement theorem.
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.
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.
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.
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.
A conjunction containing each of a specified finite collection of Boolean variables exactly once, either positively or negated. It is satisfied by exactly one Boolean valuation of those variables. The minterms for all valuations are mutually exclusive and collectively exhaustive, so they can encode an arbitrary finite table of values.
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.
If , eliminate the letters private to by
Every assignment satisfying satisfies one disjunct of . If an assignment satisfies , change only the eliminated letters to its witnessing assignment. The modified assignment satisfies and hence , whose letters were unchanged. Thus , and the propositional completeness theorem gives the two derivations. The interpolant uses only common letters; an empty common vocabulary is handled by logical truth constants.

Ancestors (6)

  1. Propositional logic
  2. Mathematical logic
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

A propositional formula is a type of mathematical expression used in propositional logic, which deals with propositions that can be either true or false. Propositional formulas are constructed using propositional variables (which represent simple statements), logical connectives, and parentheses to define the structure of the formula.