For past few days I have been practicing problems related to validity of statements written in First-Order Logic, and I am wondering that is there an algorithm to check the validity of following types of First-Order Logic because most of the times I used examples to check the validity, Or is there a universal example which can help me deduce the validity of following types of FOL:
How can I check the validity of the following FOL'S:
$1.\;\forall x \ P(x) \implies P(c)$
$2.\;\forall x \ (P(x) \implies P(c))$
$3.\;\exists x\ (P(x) \implies \forall x P(x))$
$4.\;(\forall x\ P(x)) \lor (\forall x\ Q(x)) \implies \forall x\ (P(x) \lor Q(x))$
$5.\;(\exists x\ P(x)) \land (\exists x\ Q(x)) \implies \exists x\ (P(x) \land Q(x))$
$6.\;\forall x\ (P(x) \lor Q(x)) \implies (\forall x \ P(x)) \lor (\forall x\ Q(x))$
$7.\;\exists x\ (P(x) \lor Q(x)) \implies (\lnot\forall x\ P(x)) \lor (\exists x\ Q(x))$
$8. \; \forall x \ (P(x) \implies Q(x)) \implies ((\forall x \ P(x)) \implies (\forall x \ Q(x)))$
$9. \; ((\forall x \ P(x)) \implies (\forall x \ Q(x))) \implies \forall x \ (P(x) \implies Q(x))$
$10. \; \exists x \ (P(x) \lor Q(x)) \implies (\exists x \ P(x) \implies \exists x \ Q(x))$
$11. \; (\forall x \ (\exists y \ P(x,y) \implies Q(x,y))) \implies \forall x \exists y \ Q(x,y)$
The method which I used is using examples:
Suppose $P(x):\text{"x is odd"} \quad Domain: Z$, then
$1.\;\forall x \ P(x) \implies P(c)\;$ Valid
Because LHS will always be false.
$2.\;\forall x \ (P(x) \implies P(c))\equiv \forall x \ P(x) \implies P(c)$ Valid.
$3.\;\exists x \ (P(x) \implies \forall x P(x))$ Valid.
$4.\;(\forall x\ P(x)) \lor (\forall x\ Q(x)) \implies \forall x\ (P(x) \lor Q(x))$ Valid
$6.\;\forall x\ (P(x) \lor Q(x)) \implies (\forall x \ P(x)) \lor (\forall x\ Q(x))$ Not Valid
Suppose $P(x): \text{"x is even"} \quad Q(x): \text{"x is odd"} \quad Domain: Z$
Then the statement says that $\text{"For all x if x is even or x is odd then if for all x P(x) is even or for all x P(x) is odd"}$
LHS is always true but RHS is always false. Hence, Not Valid indeed its a contradiction.
$8. \; \forall x \ (P(x) \implies Q(x)) \implies ((\forall x \ P(x)) \implies (\forall x \ Q(x)))$ Valid
Suppose $P(x):\text{"x is a girl"} \quad Q(x):\text{"x is intelligent"}$
Given statement says that:
"If for all x if x is a girl then she is intelligent then if all
the students in the class are girls then all the girls are intelligent i.e RHS says that whole class is intelligent"
LHS is always true and RHS is always true.
I am not able to deduce the validity of $5,7,9,10,11$.
Best Answer
The torturous chain of comments has reached a point where an attempt at an Answer seems appropriate.
Note again that the incompleteness theorem, in the guise of the unsolvability of the "decision problem", shows that it's impossible to give a perfect answer, in the form "To decide whether $\phi$ is valid do the following", where "the following" can be done in a mechanical way regardless of $\phi$ and always returns the right answer. But the OP has asked what I actually do to figure these things out, and I can attempt to answer that.
First recall that by definition $\phi$ is valid if it's true in any interpretation. (Newbies should note that there is a precise formal definition of "interpretation". For our purposes we can leave the notion informally "defined" by example; e.g. if I say "Let $x$ range over the integers, let $P(x)$ be $x=x$ and let $Q(x) $ be $x>x$" I have specified an "interpretation" for the language used in (7).)
So what do I do to try to decide whether $\phi$ is valid?
Note I do not start by looking for an interpretation where $\phi$ is true!
Because if I find an interpretation where $\phi$ is true that says nothing about whether $\phi$ is valid - there may or may not be some other interpretation where $\phi$ is false. (This is why your proofs that various things are valid are wrong; in each case you just give one interpretation where the formula is true, which proves nothing.)
What I do do is this:
I succeed or not.
(i) If I do find an interpretation where $\phi$ is false, I'm done: $\phi$ is not valid.
(ii) If I cannot find an interpretation where $\phi$ is false, I ask myself why not. When I get lucky, looking for what goes wrong when I try to "falsify" $\phi$ allows me to prove that it's impossible to give an interpretation where $\phi$ is false; when that happens I've proved that $\phi$ is valid.
Three examples:
Formula (1): This seems "obvious" to me. Yes, it's valid, but your explanation "Because LHS will always be false." is wrong. LHS is false in the one interpretation you're considering, but to use that sentence to explain why $\phi$ is valid you'd have to show that LHS is false in every interpretation, which of course is not so.
But (1) is obviously valid: If $P(x)$ is true for every $x$ (that is, for every $x$ in the domain of some interpretation) then $P(x)$ is true for $x=c$.
Formula (7): I look for an interpretation where (7) is false. Looking at truth tables, this means I need an interpretation where $\exists x(P(x)\lor Q(x))$ is true, $\forall xP(x)$ is true and $\exists xQ(x)$ is false. An obvious way to make $\forall xP(x)$ true and $\exists xQ(x)$ false is to say $P(x)$ is $x=x$ and $Q(x)$ is $x>x$; I get lucky that with that interpretation $\exists x(P(x)\lor Q(x))$ is true, and I'm done: I have an interpretation where (7) is false, so (7) is not valid.
Formula (3): This seems to me like the most interesting example, because it looks wrong at first: How can $P(x)$ imply $\forall xP(x)$? But in fact this explains why $\exists x P(x)\implies\forall xP(x)$ is not valid, and that's not the same as (3). In fact it turns out that (3) is valid:
First I say to myself that using the same letter in both (nested) quantifiers may lead to confusion over what "$x$" means in an informal discussion. Since $\forall xP(x)$ is equivalent to $\forall yP(y)$ (technicality: and neither contains a free variable), (3) is equivalent to
3': $\exists x(P(x)\implies \forall yP(y))$.
Can we find an interpretation where (3') is false? Hmm. The negation of (3') is
$\lnot$3': $\forall x(P(x)\land \exists y(\lnot P(y)))$.
Since $\forall x$ does distribute over $\land$ and there is no $x$ free in $\forall yP(y)$, this is equivalent to
$(\lnot 3')'$: $\forall xP(x)\land \exists y(\lnot P(y))$
And $(\lnot 3')'$ is obviously false in every interpretation: If we can find $y$ such that $\lnot P(y)$ is true then $\forall xP(x)$ is false, since $x=y$ gives a counterexample.
Digression: That last bit shows why I changed one of the $x$'s to $y$ at the start: If I hadn't done that then expressing what I mean by "$x=y$ is a counterexample" would have been trickier.
So $\lnot$(3) is false in every interpretation, so (3) is true in every interpretation: (3) is valid.
Edit: I wrote all that out to illustrate the utility of the heuristic above. Of course one can give a simpler and probably more intuitive explanation of why (3') is valid:
In a given interpretation $\forall yP(y)$ is true or false. If it's true then $P(x)\implies \forall yP(y)$ is true regardless of $x$.
Suppose otoh that $\forall yP(y)$ is false in our interpretation. Choose $y$ so that $P(y)$ is false; then if $x=y$, $P(x)$ is false, so $P(x)\implies\forall yP(y)$ is again true. Since it's true for some $x$ in the interpretation it follows that $\exists x(P(x)\implies\forall yP(y))$ is true.