1
$\begingroup$

I have problems to understand how to think of satisfiability in predicate logic.

For example why is $ \forall x (p(x) \vee \neg p(x)) $ valid, but

$ \forall x p(x) \vee \forall x\neg p(x) $ only satisfiable?

And $ ( \forall x (p(f(x)) \rightarrow \neg p(f(x)))) \land p(c) $ satisfiable, but

$ ( \forall x (p(f(x)) \rightarrow \neg p(f(x)))) \land p(f(c)) $ not?

$c$ is a constant, $p$ a predicate and $f$ a function.

$\endgroup$
2
$\begingroup$

It will help to rewrite the relevant expressions in natural language. Let's look at the first two. The first says "For every $x$, either $p(x)$ holds or $p(x)$ fails." This should obviously be true, without any other information: everything is either true or false, so for any specific object $x$ and any specific property $p$ either $x$ has $p$ or $x$ doesn't have $p$.

The second, however, says "Either every $x$ has property $p$ or every $x$ fails to have property $p$." Basically, this is saying that all objects look the same (at least as far as property $p$ is concerned). And this is clearly not always true: e.g. in the natural numbers, take $p$ to be evenness: some numbers are even, so $\forall x(\neg p(x))$ fails, but some numbers are odd, so $\forall x(p(x))$ fails too.

I suspect a lot of the confusion is coming from "algebraic" intuition - specifically in the case of the first two, the idea that everything is distributive: that we can distribute the "$\forall$" over the "$\vee$." There are indeed various "algebraic" rules, but they're not necessarily the ones you'll think of immediately; before you have a solid understanding of them, you need to resist the temptation to "simplify in the obvious way."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.