Which of the following formulas are true:
A.(∀x∀y (P(x,y)=>P(y,x)))=>∀z P(z,z)
B. ∀x∀y (P(x,y)=>(P(y,x)=>∀z P(z,z)))
C. (∀x P(x))=> ∃y P(y)
D. none of the above
My Question is How do we approach problems like that?? the only thing coming to my head is to turn them into CNF, so for example from (A) we'll get:
(∀x∀y(¬P(x,y)∨P(y,x)))=>∀z P(z,z)
(∃x∃y(P(x,y)∧¬P(y,x)))∨∀z P(z,z)
Eventually I will have from (A) the following two rules:
1) P(c1,c2)∨P(z,z)
2) ¬P(c2,c1)∨P(z,z)
Does this Mean that A is Not Valid because I can't reach (True) from the above two Rules??
To prove that a formula is 'true' ... by which I assume they mean 'valid' ... i.e. always true, you can negate the statement, and show that that leads to a contradiction. So, if you use the resolution method: negate the statement, put into CNF, get the clauses, and see if you can resolve it to the empty clause. If so, then that negation of the original statement was a contradiction, meaning that the original statement itself was valid.
For, for example, take the third statement. Negated:
$\neg (\forall x \ P(x) \to \exists y \ P(y))$
which is equivalent to:
$\forall x \ P(x) \land \neg \exists y \ P(y)$
and thus to:
$\forall x \ P(x) \land \forall y \ \neg P(y)$
this gives two clauses:
$P(x)$
and
$\neg P(y)$
and they immediately resolve to the empty clause, meaning that $\forall x \ P(x) \to \exists y \ P(y)$ is valid ('true')
Now to demonstrate that some statement is not valid, simply provide a counterexample.
For example, for the first one, take as your domain a single object $a$, and have it not stand in relation $P$ to itself. Then $\forall x \forall y (P(x,y) \to P(y,x))$ is (vacuously) true, but $\forall z \ P(z,z)$ is false, and hence $\forall x \forall y (P(x,y) \to P(y,x)) \to \forall z \ P(z,z)$ is false.