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.
A logical formula or a collection of formulas is unsatisfiable when no permitted interpretation makes all of it true. The permitted interpretations come from the chosen semantics: Boolean valuations for propositional logic, or structures and variable assignments for first-order logic. Unsatisfiability is therefore a semantic property; a refutation is a syntactic proof of that property.
For example, is unsatisfiable because neither truth value of makes both parts true. The logical formula is satisfiable, although it is false in the valuation assigning false to both letters. Thus being false in one interpretation does not establish unsatisfiability. In classical propositional logic, is valid exactly when is unsatisfiable. Likewise, exactly when is unsatisfiable. This turns entailment questions into searches for countermodels or contradiction certificates.
A logical variable is a symbol whose value is supplied by the semantics of a logical language. A propositional variable receives a truth value under a Boolean valuation. An individual variable of first-order logic receives an element of a structure under an assignment. These are different kinds of variable and should not be identified.

Ancestors (5)

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

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.