Editing First-order logic (section)

===Evaluation of truth values===
{{unsourced section|date=July 2023}}

A formula evaluates to true or false given an interpretation and a '''variable assignment''' μ that associates an element of the domain of discourse with each variable. The reason that a variable assignment is required is to give meanings to formulas with free variables, such as <math>y = x</math>. The truth value of this formula changes depending on the values that ''x'' and ''y'' denote.

First, the variable assignment μ can be extended to all terms of the language, with the result that each term maps to a single element of the domain of discourse. The following rules are used to make this assignment:
* ''Variables''. Each variable ''x'' evaluates to ''μ''(''x'')
* ''Functions''. Given terms <math>t_1, \ldots, t_n</math> that have been evaluated to elements <math>d_1, \ldots, d_n</math> of the domain of discourse, and a ''n''-ary function symbol ''f'', the term <math>f(t_1, \ldots, t_n)</math> evaluates to <math>(I(f))(d_1,\ldots,d_n)</math>.

Next, each formula is assigned a truth value. The inductive definition used to make this assignment is called the [[T-schema]].
* ''Atomic formulas (1)''. A formula <math>P(t_1,\ldots,t_n)</math> is associated the value true or false depending on whether <math>\langle v_1,\ldots,v_n \rangle \in I(P)</math>, where <math>v_1,\ldots,v_n</math> are the evaluation of the terms <math>t_1,\ldots,t_n</math> and <math>I(P)</math> is the interpretation of <math>P</math>, which by assumption is a subset of <math>D^n</math>.
* ''Atomic formulas (2)''. A formula <math>t_1 = t_2</math> is assigned true if <math>t_1</math> and <math>t_2</math> evaluate to the same object of the domain of discourse (see the section on equality below).
* ''Logical connectives''. A formula in the form <math>\neg \varphi</math>, <math>\varphi \rightarrow
\psi</math>, etc. is evaluated according to the [[truth table]] for the connective in question, as in propositional logic.
* ''Existential quantifiers''. A formula <math>\exists x \varphi(x)</math> is true according to ''M'' and <math>\mu</math> if there exists an evaluation <math>\mu'</math> of the variables that differs from <math>\mu</math> at most regarding the evaluation of ''x'' and such that φ is true according to the interpretation ''M'' and the variable assignment <math>\mu'</math>. This formal definition captures the idea that <math>\exists x \varphi(x)</math> is true if and only if there is a way to choose a value for ''x'' such that φ(''x'') is satisfied.
* ''Universal quantifiers''. A formula <math>\forall x \varphi(x)</math> is true according to ''M'' and <math>\mu</math> if φ(''x'') is true for every pair composed by the interpretation ''M'' and some variable assignment <math>\mu'</math> that differs from <math>\mu</math> at most on the value of ''x''. This captures the idea that <math>\forall x \varphi(x)</math> is true if every possible choice of a value for ''x'' causes φ(''x'') to be true.

If a formula does not contain free variables, and so is a sentence, then the initial variable assignment does not affect its truth value. In other words, a sentence is true according to ''M'' and <math>\mu</math> if and only if it is true according to ''M'' and every other variable assignment <math>\mu'</math>.

There is a second common approach to defining truth values that does not rely on variable assignment functions. Instead, given an interpretation ''M'', one first adds to the signature a collection of constant symbols, one for each element of the domain of discourse in ''M''; say that for each ''d'' in the domain the constant symbol ''c''<sub>''d''</sub> is fixed. The interpretation is extended so that each new constant symbol is assigned to its corresponding element of the domain. One now defines truth for quantified formulas syntactically, as follows:
* ''Existential quantifiers (alternate)''. A formula <math>\exists x \varphi(x)</math> is true according to ''M'' if there is some ''d'' in the domain of discourse such that <math>\varphi(c_d)</math> holds. Here <math>\varphi(c_d)</math> is the result of substituting  ''c''<sub>''d''</sub> for every free occurrence of ''x'' in φ.
* ''Universal quantifiers (alternate)''. A formula <math>\forall x \varphi(x)</math> is true according to ''M'' if, for every ''d'' in the domain of discourse, <math>\varphi(c_d)</math> is true according to ''M''.
This alternate approach gives exactly the same truth values to all sentences as the approach via variable assignments.