Formula (mathematical logic)

Formula (mathematical logic)

In mathematical logic, a formula is a type of abstract object a token of which is a symbol or string of symbols which may be interpreted as any meaningful unit (i.e. a name, an adjective, a proposition, a phrase, a string of names, a string of phrases, etcetera) in a formal language. Two different strings of symbols may be tokens of the same formula. It is not necessary for the existence of a formula that there be any tokens of it. The exact definition of a formula depends on the particular formal language in question. [Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic]

A fairly typical definition (specific to first-order logic) goes as follows: Formulas are defined relative to a particular formal language and "relation symbols", where each of the function and relation symbols comes supplied with an arity that indicates the number of arguments it takes.

Then a term is defined recursively as
#A variable,
#A constant, or
#"f"("t"1,...,"t""n"), where "f" is an "n"-ary function symbol, and "t"1,...,"t""n" are terms.

An atomic formula is one of the form:
#"t"1="t"2, where "t"1 and "t"2 are terms, or
#"R"("t"1,...,"t""n"), where "R" is an "n"-ary relation symbol, and "t"1,...,"t""n" are terms.

Finally, the set of formulae is defined to be the smallest set containing the set of atomic formulae such that the following holds:
# egphi is a formula when phi is a formula;
#(phi land psi) and (phi lor psi) are formulae when phi and psi are formulae;
#exists x, phi is a formula when "x" is a variable and phi is a formula;
#forall x, phi is a formula when x is a variable and phi is a formula (alternatively, forall x, phi could be defined as an abbreviation for egexists x, egphi).

If a formula has no occurrences of exists x or forall x, for any variable x, then it is called "quantifier-free". An "existential formula" is a string of existential quantification followed by a quantifier-free formula.

ee also

*Well-formed formula


*cite book | author = Hinman, P. | title = Fundamentals of Mathematical Logic | publisher = A K Peters | year = 2005 | id = ISBN 1-568-81262-0

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Structure (mathematical logic) — In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it. Universal algebra studies structures that generalize the algebraic structures such as… …   Wikipedia

  • Theory (mathematical logic) — This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation). In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. Usually… …   Wikipedia

  • Sentence (mathematical logic) — This article is a technical mathematical article in the area of predicate logic. For the ordinary English language meaning see Sentence, for a less technical introductory article see Statement (logic). In mathematical logic, a sentence of a… …   Wikipedia

  • Literal (mathematical logic) — In mathematical logic, a literal is an atomic formula (atom) or its negation. The definition mostly appears in proof theory (of classical logic), e.g. in conjunctive normal form and the method of resolution. Literals can be divided into two types …   Wikipedia

  • Absoluteness (mathematical logic) — In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures (also called models). Theorems about absoluteness typically show that each of a large syntactic class of formulas is… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • Formula — For other senses of this word, see formula (disambiguation). In mathematics, a formula (plural: formulae[1] or formulas[1]) is an entity constructed using the symbols and formation rules of a given logical language. In science, a formula is a… …   Wikipedia

  • Formula (disambiguation) — Generally, a formula is A set form of words in which something is defined, stated, or declared, or which is prescribed by authority or custom to be used on some ceremonial occasion (Oxford English Dictionary). It is a diminutive form of the word… …   Wikipedia

  • Logic and the philosophy of mathematics in the nineteenth century — John Stillwell INTRODUCTION In its history of over two thousand years, mathematics has seldom been disturbed by philosophical disputes. Ever since Plato, who is said to have put the slogan ‘Let no one who is not a geometer enter here’ over the… …   History of philosophy

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”