Show that the formula is satisfiable

59 Views Asked by At

The formula is: $$P(f(a),g(b))\to R(h(a,b,c))\lor P(f(a),g(b)))$$

Here, $a,b$ are constants, $P,R$ are relations and $f,g,h$ are functions.

Now, if we assume that $P(f(a),g(b)) = t$ then it's easy to easy that the formula is true, but how do I deal with the case where $P(f(a),g(b)) = f$?

1

There are 1 best solutions below

0
On BEST ANSWER

An implication $A \to B$ is equivalent to $\neg A \vee B$. Therefore, your forumla can be transformed to

$$\neg P(f(a),g(b)) \vee R(h(a,b,c)) \lor P(f(a),g(b))$$

The formula is always true, since $\neg P(f(a),g(b)) \vee P(f(a),g(b))$ is a tautology and true in all interpretations.