Well-formed formula
A syntactic object defined by formal grammar rules.
A well-formed formula (WFF or wff) is a finite sequence of symbols from a given alphabet, constructed according to the defined grammar of a formal language. In mathematical logic, propositional logic, and predicate logic, formulas are syntactic objects that can be given semantic meaning through interpretation, and they are central to the representation of proofs and truth conditions.
- field
- Mathematical logic, propositional logic, predicate logic
- known_for
- Fundamental syntactic unit in formal languages
- pronunciation
- Pronounced 'woof', 'wiff', 'weff', or 'whiff'
- key_uses
- Propositional logic and predicate logic such as first-order logic
- distinction
- Distinction between vague 'property' and inductively defined well-formed formula has roots in Weyl's 1910 paper
Lore & Background
In predicate logic, the definition of a formula depends on a signature specifying constant, predicate, and function symbols with arities. Terms are defined recursively from variables, constants, and function applications. Atomic formulas are formed from equality of terms or predicate symbols applied to terms. The set of formulas is the smallest set containing atomic formulas closed under negation, conjunction, disjunction, and existential or universal quantification. A formula with no quantifiers is quantifier-free; an existential formula starts with existential quantifiers followed by a quantifier-free formula.
Reader's Guide
Well-formed formulas are the foundational syntactic objects of formal logic, enabling precise reasoning in propositional and predicate logic. Their inductive definition ensures that every formula has a unique parse tree, which is essential for defining truth conditions and proof systems. The distinction between a formula as an abstract sequence of symbols and its physical token instances allows for the possibility of formulas too long to be written in the physical universe. The concept of a closed formula (sentence) with no free variables is crucial for determining truth values under interpretation. Properties such as validity (true for every interpretation) and satisfiability (true for some interpretation) are defined for formulas, and decidability applies when an effective method exists for determining truth under substitutions of free variables. The formal grammar of well-formed formulas underpins automated theorem proving, programming language syntax, and the study of computability.
Did You Know?
- The abbreviation wff is pronounced 'woof', 'wiff', 'weff', or 'whiff'.
- A formula may in principle be so long that it cannot be written at all within the physical universe.
- The distinction between the vague notion of 'property' and the inductively defined notion of well-formed formula has roots in Weyl's 1910 paper.
- In propositional calculus, precedence rules (e.g., ¬ most binding, then →, ∧, ∨) are conventions used to simplify written representation.
More in Sets And Logic 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record