Examine whether a formula is satisifable.

43 Views Asked by At

Let $S$ be a structure $S = \langle\mathbb{N}, p, q\rangle $ where

$\langle a,b\rangle \in p \iff a + b \ge 6 \\ \langle a,b\rangle \in q \iff b = a+2$

Examine whether formulas are satisifable while valuation $v$ is $v(y)=7, v(z) = 1$

$$1. \forall x\ p(x,y) \to \exists q(x,y)$$ $$2. \forall x\ p(x,y) \to \forall q(x,y)$$

Please help me with that :).

1

There are 1 best solutions below

6
On BEST ANSWER

Well the definitions are not exactly what I'm used to. But I think what this question is asking is if the structure $S$ satisfies these formulas under the valuation $v(y)=7$, $v(x)=1$ (assuming "$v(z)=1$" is a typo). Notation-wise, we are trying to show that $S \vDash (\forall x p(x, y) \rightarrow \exists x q(x, y))(v)$.

Solving this problem is a matter of breaking down the problem in a step by step way (kinda like using the different derivative rules in calculus) by using the definition to derive an equivalent condition that we can verify from what is given whether or not it is satisfied. The crucial formula satisfaction rules for this problem are as follows:

Given $L$-formulas $\varphi$ and $\phi$:

  1. $S \vDash \varphi \rightarrow \phi(v) : \iff S \nvDash \varphi(v)$ or $S \vDash \phi(v)$

  2. $S \vDash \forall x \phi(v) : \iff S \vDash \phi(v[a|x])$ for all $a \in S$.

  3. $S \vDash \exists x \phi(v) : \iff S \vDash \phi(v[a|x])$ for some $a \in S$.

  4. $S \vDash P(x_1, \dots, x_n)(v)$ (where $P$ is an $n$-ary relation symbol) $: \iff (v(x_1), \dots, v(x_n)) \in P^S$

(where $P^S \subseteq S^n$ is the relation that corresponds to $P$ in the structure $S$).

Hopefully that notation is clear with you and if not, I would love to adapt my notation with whatever reference you're using. Anyway, I'll do the first problem and you can do the second one.

Check out how the definition provides a circuit from condition to equivalent condition that solves the problem.

\begin{align*} S \vDash (\forall x p(x, y) \rightarrow \exists x q(x, y))(v) & \iff \text{ $S \nvDash (\forall x p(x, y))(v)$ or $S \vDash (\exists x q(x, y))(v)$}. \end{align*} So it suffices to verify whether $S \nvDash (\forall x p(x, y))(v)$ or $S \vDash (\exists x q(x, y))(v)$. In other words, if one of those conditions are met, then our argument shows the given formula is satisfied, and otherwise satisfaction fails. We will start with checking the first condition $S \nvDash (\forall x p(x, y))(v)$, even though it fails, just because it exposes the thought process more. \begin{align*} S \vDash (\forall x p(x, y))(v) & \iff S \vDash p(x, y)(v[a|x]), & \text{ for all $a \in \mathbb{N}$} \\ & \iff v[a|x](x)+v[a|x](y) \geq 6, & \text{ for all $a \in \mathbb{N}$}\\ & \iff a+7 \geq 6, \\ \end{align*} Since in $S$, we find $a+7 \geq 6$, for all $a \in \mathbb{N}$, we find $S \vDash \forall x p(x, y)$.

Now we must check to see if $S \vDash (\exists x q(x, y))(v)$. We find \begin{align*} S \vDash (\exists x q(x, y))(v) & \iff S \vDash q(x, y)(v[a|x]), & \text{ for some $a \in \mathbb{N}$}\\ & \iff v[a|x](x)=v(y)+2, & \text{ for some $a \in \mathbb{N}$} \\ & \iff a=7+2, & \text{ for some $a \in \mathbb{N}$} \\ \end{align*} and notice that in $S$, this condition holds when $a=9$, since $9=7+2$, naturally.

Hope that helps!

UPDATE 1: Note that I made notation edits so that my notation is consistent.

UPDATE 2: Reorganized the structure of this response a bit, so that hopefully it's less confusing.