first-order logic

(redirected from First-order language)

first-order logic

(language, logic)
The language describing the truth of mathematical formulas. Formulas describe properties of terms and have a truth value. The following are atomic formulas:

True False p(t1, where t1,..,tn are terms and p is a predicate.

If F1, F2 and F3 are formulas and v is a variable then the following are compound formulas:

F1 ^ F2 conjunction - true if both F1 and F2 are true,

F1 V F2 disjunction - true if either or both are true,

F1 => F2 implication - true if F1 is false or F2 is true, F1 is the antecedent, F2 is the consequent (sometimes written with a thin arrow),

F1 <= F2 true if F1 is true or F2 is false,

F1 == F2 true if F1 and F2 are both true or both false (normally written with a three line equivalence symbol)

~F1 negation - true if f1 is false (normally written as a dash '-' with a shorter vertical line hanging from its right hand end).

For all v . F universal quantification - true if F is true for all values of v (normally written with an inverted A).

Exists v . F existential quantification - true if there exists some value of v for which F is true. (Normally written with a reversed E).

The operators ^ V => <= == ~ are called connectives. "For all" and "Exists" are quantifiers whose scope is F. A term is a mathematical expression involving numbers, operators, functions and variables.

The "order" of a logic specifies what entities "For all" and "Exists" may quantify over. First-order logic can only quantify over sets of atomic propositions. (E.g. For all p . p => p). Second-order logic can quantify over functions on propositions, and higher-order logic can quantify over any type of entity. The sets over which quantifiers operate are usually implicit but can be deduced from well-formedness constraints.

In first-order logic quantifiers always range over ALL the elements of the domain of discourse. By contrast, second-order logic allows one to quantify over subsets.

["The Realm of First-Order Logic", Jon Barwise, Handbook of Mathematical Logic (Barwise, ed., North Holland, NYC, 1977)].
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
Briefly, states are models of a first-order language called a domain language.
Consider a first-order language with two sorts, a and [beta].
A genuinely tenseless and nonmodal language can be expressed in a first-order language. Natural language has the power of explicit quantification over times and worlds.
Modern modal logic originated as a branch of philosophical logic in which the concepts of necessity and possibility were investigated by means of a pair of dual operators ([] and [diamond]) that are added to a propositional or first-order language. The field owes much of its flavor and success to the introduction in the 1950s of the "possible-worlds" semantics in which the modal operators are interpreted via some "accessibility relation" connecting possible worlds.
The language of folk theology tends to be first-order language similar to the language of prayer, worship, witness, and exhortation, while the language of academic theology is usually second-order language, language in which the first order language is scrutinized.
Begin with a standard, first-order language whose logical terminology is {V, &, [similar to], [exists], [for every]}.
From the beginning, Moggi [1989] took pains to stress that monads could be applied to a first-order language, independent of the machinery required for a higher-order language.
Rather, we have here a concrete, vivid, first-order language in which the man is depicted mainly in terms of his service to a community.
It can be argued that in order to interpret an expression of a formal first-order language in a given structure(11) it should not be necessary to 'step out' of that structure and survey the whole universe of sets.
Genealogical constructions, explanations and normative critiques all depend upon the first-order languages that we care about, the languages through which others can appear to us or not.

Full browser ?