Prove if a set of first order logic formulas is satisfiable

960 Views Asked by At

How can I prove if a set of first order logic formulas is satisfiable or not?

For example, if I have the following set:

$\{∃x∀y¬R(y,x),∀yR(y,y)\}$

1

There are 1 best solutions below

9
On BEST ANSWER

Hint

For unsatisfiability, you can try to find a contradiction.

The first premise implies, for some $a$:

$∀y¬R(y,a)$.

Then, instantiating both the above formula and the second premise with $a$, we get :

$¬R(a,a)$ and $R(a,a)$

a contradiction.