subformler

Subformler, in logic and formal linguistics, refers to the subformulas of a given formula. A subformula is any formula that occurs inside another formula, following the recursive structure of the formula’s syntax. The concept is used to analyze the components that make up a complex expression and to study how these components interact within logical derivations.

Formally, if φ is a formula, then every atomic formula appearing in φ is a subformula of φ. If ψ is a subformula of φ, and φ is constructed from ψ and possibly other subformulas using logical connectives such as not (¬), and (∧), or (∨), implies (→), or biconditional (↔), then the constituent subformulas involved in that construction are also subformulas of φ. The formula φ itself is typically included as a subformula, while the term proper subformula refers to a subformula that is strictly smaller than φ (i.e., not equal to φ).

Subformulas are central in proof theory because many proof systems aim to preserve the subformula property: every formula appearing in a deduction of a target formula φ is a subformula of φ. This restriction can simplify proof search, help ensure termination, and influence the complexity of automated reasoning.

Applications of the subformula concept include automated theorem proving, model checking, and the analysis of logical syntax. It also aids in the study of formula simplification, interpolants, and the structure of proofs across various logics, including propositional, first-order, and modal systems. See also: subformula, proper subformula, formula, logic, proof theory.