# First-order Logic - Also called predicate logic. - Extends the capabilities of PL to talk about Boolean propositions - Express properties about objects, their properties, and relations between objects - Language constructs for objects - Object constants $c_{1}, c_{2}, \ldots$, function constants $f_{1}, f_{2}, \ldots$ - Variables (for objects) and quantifiers $\forall, \exists$ - Relation symbols $R_{1}, R_{2}, \ldots$ ## Syntax - We fix infinite sets of: - Function constants $f_{1}, f_{2}, \ldots$, each with an arity (number of arguments) $k \in \mathbb{N}$ - Relation symbol $\mathrm{R}_{1}, \mathrm{R}_{2}, \ldots$, each with an arity $k \in \mathbb{N}$ - (Object) variables $x_{1}, x_{2}, \ldots, y_{1}, y_{2}, \ldots, z_{1}, z_{2}, \ldots$ - Terms are constructed as follows. - Each variable $x$ is a term. - If $t_{1}, \ldots, t_{k}$ are terms and $f$ is a function constant of arity $k$, then $f\left(t_{1}, \ldots, t_{k}\right)$ is a term. - (In particular, if $c$ is a function constant of arity 0 , then $c$ is a term by itself.) - For example, if alex and mother are function constants of arities 0 and 1 , then the following are terms: alex, mother (alex), mother(mother(alex)), mother $(x)$, Formulas are constructed as follows. - If $t_{1}, t_{2}$ are terms, then $\left(t_{1}=t_{2}\right)$ is a formula. - If $R$ is a relation symbol of arity $k$ and $t_{1}, \ldots, t_{k}$ are terms, then $R\left(t_{1}, \ldots, t_{k}\right)$ is a formula. - (In particular, if $R$ is a relation symbol of arity 0 , then $R$ is a formula by itself.) - If $\varphi_{1}, \varphi_{2}$ are formulas, then so are: $\neg \varphi_{1},\left(\varphi_{1} \wedge \varphi_{2}\right),\left(\varphi_{1} \vee \varphi_{2}\right),\left(\varphi_{1} \rightarrow \varphi_{2}\right)$, $\left(\varphi_{1} \leftrightarrow \varphi_{2}\right)$. - If $x$ is a variable and $\varphi$ is a formula, then so are: $\forall x \cdot \varphi$ and $\exists x \cdot \varphi$. - For example, if $R$ is a unary relation symbol, then the following are formulas: (unary $=1$-ary $=$ of arity 1 ) - $R(x), \quad \exists x \cdot R(x), \quad \exists x \cdot \forall y_{0}:(R(x) \vee(x=y))$ - The subformulas $\operatorname{Sub}(\varphi)$ of a formula $\varphi$ are all formulas that appear as a part of $\varphi$ : $\operatorname{Sub}\left(\varphi_{1} \circ \varphi_{2}\right)=\left\{\varphi_{1} \circ \varphi_{2}\right\} \cup \operatorname{Sub}\left(\varphi_{1}\right) \cup \operatorname{Sub}\left(\varphi_{2}\right)$ for $\circ \in\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ $ \begin{aligned} \operatorname{Sub}(\neg \varphi) &=\{\neg \varphi\} \cup \operatorname{Sub}(\varphi) \\ \operatorname{Sub}\left(R\left(t_{1}, \ldots, t_{k}\right)\right) &=\left\{R\left(t_{1}, \ldots, t_{k}\right)\right\} \\ \operatorname{Sub}\left(t_{1}=t_{2}\right) &=\left\{\left(t_{1}=t_{2}\right)\right\} \end{aligned} $ - An occurrence of a variable $x$ in a formula $\varphi$ is bound if it appears in a subformula of $\varphi$ of the form $\forall x . \psi$ or $\exists x . \psi$ - An occurrence of a variable is free if it is not bound - Free $(\varphi)$ denotes the set of all free variables of $\varphi$ : variables that have a free occurrence in $\varphi$ - For example, there is one bound and one free occurrence of $x$ and one bound occurrence of $y$ in the formula $\varphi=R_{1}(x) \vee \exists x . \forall y . R_{2}(x, y)$ ## Semantics - Instead of truth assignments, we consider interpretations $\left(I, \cdot^{\prime}\right)$ for the meaning of first-order logic formulas, consisting of: - a (possibly infinite) set 1 , called the domain; - a function . ', called the interpretation function, that: - assigns each function constant $f$ of arity $k$ to a function $f^{\prime}: l^{k} \rightarrow /$ (and thus assigns each object constant c to an object $c^{\prime} \in l$ ), - assigns each relation symbol $R$ of arity $k$ to a relation $R^{\prime} \subseteq I^{k}$ (and thus assigns each 0 -ary relation symbol $R$ to true, $\{()\} \subseteq ∂I^{0}$, or false, $\left.\emptyset \subseteq I^{0}\right)$, ![[Semantics first order logic example.png]] - We define when an interpretation $\left(1,^{\prime}\right)$ and a variable assignment $\mu:$ Free $(\varphi) \rightarrow I$ satisfy a formula $\varphi$, written $l, \mu \mid=\varphi$. $ \begin{aligned} x^{l, \mu} &=\mu(x) \\ (c)^{l, \mu} &=c^{\prime} \\ \left(f\left(t_{1}, \ldots, t_{k}\right)\right)^{l, \mu} &=f^{\prime}\left(\left(t_{1}\right)^{l, \mu}, \ldots,\left(t_{k}\right)^{l, \mu}\right) \\ I, \mu \models\left(t_{1}=t_{2}\right) & \text { iff }\left(t_{1}\right)^{\prime, \mu}=\left(t_{2}\right)^{l, \mu} \\ I, \mu \models R\left(t_{1}, \ldots, t_{k}\right) & \text { iff }\left(\left(t_{1}\right)^{\prime, \mu}, \ldots,\left(t_{k}\right)^{\prime, \mu}\right) \in R^{\prime} \\ I, \mu \models \neg \varphi & \text { iff } \quad l, \mu \not \models \varphi \\ I, \mu \models \varphi_{1} \wedge \varphi_{2} & \text { iff } \quad \text { both } I, \mu \models \varphi_{1} \text { and } I, \mu \models \varphi_{2} \\ I, \mu \models \varphi_{1} \vee \varphi_{2} & \text { iff } \quad \text { at least one of } I, \mu \models \varphi_{1} \text { and } I, \mu \models \varphi_{2} \\ I, \mu \models \exists x . \varphi & \text { iff } \quad \text { there is some } d \in I \text { such that } I, \mu^{\prime} \models \varphi \\ & \text { where } \mu^{\prime}=\mu \cup\{x \mapsto d\}, \\ I, \mu \models \forall x . \varphi & \text { iff } \quad l, \mu^{\prime} \models \varphi \text { for all } \mu^{\prime}=\mu \cup\{x \mapsto d\} \text { where } d \in I \end{aligned} $ ## The Power of FOL --- ## References