predicate first order logic satisfiability

80 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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."