Which of the first-order formulae are true in S?

38 Views Asked by At

$S=(U, [.]), S=\{0,1,2\}, [P]=\{0,1\}, [R]=\{(0,0), (0,1), (1,2)\}$

a) $(\exists x~\exists y.R(x,y))\implies (\forall x.P(x))$

b) $\exists x~\exists y.(R(x,y) \implies \forall x.P(x))$

I think a) is false, because $P(x)$ can be true or false, so the right side of implication has to be false for the entire statement is true, and this is possible by setting $x=2$ and $y=2$.

I think b) is also true because similarly, we can select $R(x,y) = (2,2)$ so false implies anything is false.

Is my reasoning correct?

1

There are 1 best solutions below

0
On

Yes, that is okay.   It demonstrates the importance of quantifier scope.

The conditional, $\exists x\exists y~R(x,y)~\to~\forall x~P(x)$, is false because the antecedant, $\exists x\exists y~R(x,y)$, is true while the consequent, $\forall x~P(x)$, is false.

The existential $\exists x~\exists y~\big(R(x,y)\to\forall x~ P(x)\big)$, is true because the bound conditional, $R(x,y)\to\forall x~ P(x)$ is true for any pair where $R(x,y)$ is false, and there does exist such a pair.