Study if the set of formulas $\Phi$ is satisfiable.

122 Views Asked by At

Let $\Phi = \{ \exists x (P(x) \lor Q(x)), \, \exists x \forall y R(x,y),\, \forall x \forall y (R(x,y) \rightarrow (P(x)\land \neg Q(x)))\}$, and in case it is, give a model for $\Phi$.

Let $A = \{ a,b \}$, $P^\mathcal{A}(a) = 1$, $Q^{\mathcal{A}}(a)=0$, $P^\mathcal{A}(b)=1$, $Q^\mathcal{A}(b)=0$ and $R^\mathcal{A}(i, j) = 1$ for $i,j \in A$. That (I believe) would be a model for $\Phi$ and hence, $\Phi$ is satisfiable. Let's check it: $$\exists x (P(x) \lor Q(x))$$ Yes, $x = a$ or $x = b$ satisfy that formula. $$\exists x \forall y R(x,y)$$ Yes, in fact, $\forall x \forall y R(x,y)$ $$\forall x \forall y (R(x,y) \rightarrow (P(x)\land \neg Q(x)))$$ Yes. $R(x,y)=1$ in the model for all $x$ and for all $y$. So we only need to check that the conclusion also holds for every $x$ and for every $y$. If $x = a$, then $P(a) \land \neg Q(a) = 1$ in the model, since $P(a) = 1$ and $\neg Q(a) = 1$. If $x = b$, $P(b) \land \neg Q(b) = 1$ in the model, since again, $P(b) = 1$ and $\neg Q(b) = 1$.

So $A$ with the interpretation I gave is a model for $\Phi$. Is this reasoning correct? Thank you!

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, that works!

Note that $a$ and $b$ are exactly alike in their properties, so a simpler model would have been to have just 1 object $a$, that has property $P$, but not property $Q$, and that stands in relation $R$ to itself.