Show a formula is satisfiable

517 Views Asked by At

Show that the following formula is satisfiable: $$(R(c)\land \forall x (R(x)\to R(f(x))))\to \forall xR(x)$$ here, $R$ is a relation and $f$ is a function.

Now, if $R(c)=f$ then it easy to show that the formula is indeed satisfiable. We left with showing that the formula is also satisfiable when $R(c)=t$.

So in that case, It's equivalent to show that the following formula is satisfiable: $$\forall x (R(x)\to R(f(x)))\to \forall xR(x)$$

But it seems to me that you cannot tell for sure. I tried to prove by contradiction, assuming the LHS is $f$ whereas the RHS is $t$, but it didn't work out.

What am I missing?

1

There are 1 best solutions below

1
On BEST ANSWER

"Satisfiable" doesn't mean that the formula must be true, just that it can be true. That is, it means there is some interpretation of $R$, $f$, and $c$ such that it is true. So you are free to choose an interpretation in which $R(c)$ is false, in which case as you observe the formula is trivially true.