Quiz. Semantic Entailment (FOL) [0016]

  • November 22, 2025

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:

\[ \begin {align*} I &= \{a \mapsto \alpha , b \mapsto \beta \} \\ I &= \{f(\alpha ) \mapsto \beta , f(\beta ) \mapsto \alpha \} \\ I &= \{p(\beta , \alpha ) \mapsto \top , p(\beta , \beta ) \mapsto \top \} \end {align*} \]

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))\)

Solution. 

  • November 22, 2025
  1. \(p(f(b), f(x))\) evaluates to \(\top \) because \(f(b) = f(\beta ) = \alpha \) and \(f(x) = f(\alpha ) = \beta \), and \(p(\alpha , \beta ) = \top \).
  2. \(p(f(x), f(b))\) evaluates to \(\top \) because \(f(x) = f(\alpha ) = \beta \) and \(f(b) = f(\beta ) = \alpha \), and \(p(\beta , \alpha ) = \top \).
  3. \(p(a, f(x))\) evaluates to \(\bot \) because \(a = \alpha \) and \(f(x) = f(\alpha ) = \beta \), and \(p(\alpha , \beta ) = \bot \).