We can define a first order language as a tuple of 3 sets \(\langle \mathcal C, \mathcal F, \mathcal R\rangle \) where:

• Constants (\(\mathcal C\)): the set of constants in the language. E.g., \(\{a, b, c\}\)
• Function Symbols (\(\mathcal F\)): the set of function symbols in the language. E.g., \(\{f, g, h\}\)
• Relation Symbols (\(\mathcal R\)): the set of relation symbols in the language. E.g., \(\{R, S, T\}\)

Using BNF we can define the syntax as follows

Here the atom \(p\) represents an atomic predicate applied to terms \(t_1, \ldots , t_n\), where \(p \in \mathcal R\) with an arity of \(n\)

1. \(f(x)\)
2. \(p(x)\)
3. \(p(f(x))\)
4. \(p(p(x))\)
5. \(p(f(f(x)))\)

For quantifiers:

Each variable occurring within the formula \(F\) known as the scope is either:

• bound: if it is within the scope of a quantifier that binds it. E.g., in \(\forall x.\ P(x, y)\), the variable \(x\) is bound.
• free: if it is not bound by any quantifier within the formula. E.g., in \(\forall x.\ P(x, y)\), the variable \(y\) is free.

Consider the formula

1. Is the \(y\) bound or free?
2. Is the first occurrence of \(x\) bound or free?
3. Is the second occurrence of \(x\) bound or free?

We have 3 important classifications of formulas in First Order Logic (FOL) based on the nature of their variables:

• Closed Formula: A formula with no free variables. All variables in the formula are bound by quantifiers. E.g., \(\forall x.\ \exists y.\ p(x, y)\) is a closed formula.
• Open Formula: A formula with at least one free variable. E.g., \(p(x, y)\) is an open formula since both \(x\) and \(y\) are free.
• Ground Formula: A formula with no variables at all. E.g., \(p(a, b)\) is a ground formula if \(a\) and \(b\) are constants.

Consider the following formula

Is this formula closed, open, or ground?

In first order logic a Interpretation; similar to the case of propositional logic; is a mapping which assigns meaning to the syntax of the language. In this instance it's a mapping from constants, function symbols and predicate symbols to specific objects, functions and relations in a given domain. We can define an interpretation as a sort of piece wise function as follows:

Where \(D\) (sometimes also denoted as \(U\)) is the domain of discourse which is a non-empty set of objects over which the quantifiers range. Intuitively the domain of discourse represents what we wish to talk about in our interpretation. We can break this down into 3 parts:

• constants (\(c \in \mathcal C\)): are mapped to specific elements in the domain \(d \in D\). For example if \(c\) is the constant \("a"\) and \(D = \{1, 2, 3\}\), then \(I(a) = 1\) could be a valid mapping.
• function symbols (\(f \in \mathcal F\)): are mapped to functions that take elements from the domain and return elements in the domain. For example if \(f\) is a unary function symbol \("f"\) and \(D = \{1, 2, 3\}\), then \(I(f) = f_D\) where \(f_D(1) = 2\), \(f_D(2) = 3\), and \(f_D(3) = 1\) could be a valid mapping.
• relation symbols (\(p \in \mathcal R\)): are mapped to relations (or predicates) that take elements from the domain and return truth values \(\{\top , \bot \}\). For example if \(p\) is a binary relation symbol \("R"\) and \(D = \{1, 2, 3\}\), then \(I(R) = R_D\) where \(R_D(1, 2) = \top \), \(R_D(2, 3) = \bot \), and \(R_D(3, 1) = \top \) could be a valid mapping.

A structure \(\mathcal {M}\) for a first-order language \(\mathcal {L}\) consists of:

• A non-empty domain \(D\), which is the set of objects that the variables can refer to.
• An interpretation function \(I\) that assigns meanings to the non-logical symbols in \(\mathcal {L}\):
• For each constant symbol \(c\) in \(\mathcal {L}\), \(I(c)\) is an element of \(D\).
• For each n-ary function symbol \(f\) in \(\mathcal {L}\), \(I(f)\) is a function from \(D^n\) to \(D\).
• For each n-ary predicate symbol \(P\) in \(\mathcal {L}\), \(I(P)\) is a subset of \(D^n\).

A variable assignment \(\sigma \) for a structure \(S\) is a function that assigns each variable to an element of the domain \(D\) of the structure. That is, for each variable \(x\), \(\sigma (x) \in D\).

In First Order Logic, terms are evaluated based on an interpretation \(I\) and a variable assignment \(\sigma \) within a structure \(S\) denoted as \(\langle I, \sigma \rangle (t)\). The evaluation rules are as follows:

• If \(t\) is a constant symbol \(c\), then \(\langle I, \sigma \rangle (c) = I(c)\).
• If \(t\) is a variable \(x\), then \(\langle I, \sigma \rangle (x) = \sigma (x)\).
• If \(t\) is a function application \(f(t_1, t_2, \ldots , t_n)\), then \[ \langle I, \sigma \rangle (f(t_1, t_2, \ldots , t_n)) = I(f)(\langle I, \sigma \rangle (t_1), \langle I, \sigma \rangle (t_2), \ldots , \langle I, \sigma \rangle (t_n)) \]

Consider the following domain/universe of discourse, variable assignment, and interpretation:

• Universe \[ U \triangleq \{1, 2\} \]
• Variable assignment \[ \sigma \triangleq \{x\mapsto 2, y\mapsto 1\} \]
• Interpretation \[ \begin {align*} I & \triangleq \{a \mapsto 1, b \mapsto 2\} \\ I & \triangleq \{f(1, 1) \mapsto 2, f(1, 2) \mapsto 2, f(2, 1) \mapsto 1, f(2, 2) \mapsto 1\} \end {align*} \]

What is the evaluation of the following terms under the given interpretation and variable assignment?

1. \(f(a, y)\)
2. \(f(x, b)\)
3. \(f(f(x, b), f(a, y))\)

We evaluate formulas in first order logic under a structure which consists of a domain and an interpretation function. In addition, we need a variable assignment to evaluate formulas with free variables. To denote truth under a structure \(S\) and variable assignment \(\sigma \) we write:

• True: If a formula \(F\) evaluates to true under \(U, I, \sigma \) we write \[U, I, \sigma \models F\]
• False: If a formula \(F\) evaluates to false under \(U, I, \sigma \) we write \[U, I, \sigma \nvDash F\]

We can define semantic entailment inductively as follows:

Consider constants (free variables) \(a, b\) and a unary function \(f\), and a binary predicate \(p\). Let \(U = \{\alpha , \beta \}\) and interpretation function \(I\) be defined as follows:

Under the structure \(S = (U, I)\) and variable assignment \(\sigma = \{x \mapsto \alpha \}\) what do the following formulas evaluate to?

1. \(p(f(b), f(x))\)
2. \(p(f(x), f(b))\)
3. \(p(a, f(x))\)

In addition to evaluating atomic formulas, we can define the evaluation of complex formulas using logical connectives and quantifiers as follows:

For the proof rules of quantifiers we have two variants depending on whether we are dealing with free or bound variables:

In first order logic, the semantic argument method represents a proof by contradiction. The basic idea is as follows:

1. We assume that our formula \(F\) is not valid, i.e., \(\exists S, \sigma \nvDash F\)
2. Use the proof rules to derive a contradiction from this assumption.
3. If we can indeed derive a contradiction, we conclude that our initial assumption was false, and therefore \(F\) must be valid.

We can express the semantic argument method via the following inference rule:

So the idea here being that if we have a predicate and its negation both holding under the same interpretation and variable assignment, we can derive a contradiction. This allows us to conclude that our initial assumption (that the formula is not valid) must be false, thereby proving the validity of the formula.

Consider the following formula:

Using the semantic argument method, determine whether the formula \(F\) is valid.