# Thread: Predicate logic - Tautology?

1. ## Predicate logic - Tautology?

I'm struggling a bit with these formulas, whether they are tautologies or not;

1) $\displaystyle \forall x P(x) \wedge \exists x (P(x) \to Q(x)) \to \forall x Q(x)$

2) $\displaystyle \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)$

Any help/tips on where to start/solve these would be greatly appreciated!

2. Hmmm....

3. Originally Posted by jokke22
2) $\displaystyle \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)$
A. $\displaystyle \exists y \forall x R(x,y)\;\;\;\;.$ B. $\displaystyle \forall x \exists yR(x,y)$
Suppose that $\displaystyle R(x,y)$ reads “x is causes y”.
Then the A statements reads: Something is caused by everything.
The B statement reads: Everything causes something.
Now does A imply B?

4. Originally Posted by jokke22
2) $\displaystyle \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)$
1. $\displaystyle \vdash \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)$
2. $\displaystyle \exists y \forall x R(x,y) \vdash \forall x \exists yR(x,y)$ (by deduction theorem)
3. $\displaystyle \forall x R(x, c) \vdash \forall x \exists yR(x,y)$ (by rule EI, existential instantiation)
4. $\displaystyle \forall x R(x, c) \vdash \exists yR(x,y)$ (by generalization theorem)
5. $\displaystyle R(x, c) \vdash \exists yR(x,y)$ (by generalization theorem)
6. $\displaystyle \forall y \neg R(x,y) \vdash \neg R(x,c)$ (contraposition)
7. $\displaystyle \neg R(x,c) \vdash \neg R(x,c)$ (quantifier axiom)

Thus, (2) is tautology.

5. Originally Posted by aliceinwonderland
1. $\displaystyle \vdash \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)$
2. $\displaystyle \exists y \forall x R(x,y) \vdash \forall x \exists yR(x,y)$ (by deduction theorem)
3. $\displaystyle \forall x R(x, c) \vdash \forall x \exists yR(x,y)$ (by rule EI, existential instantiation)
4. $\displaystyle \forall x R(x, c) \vdash \exists yR(x,y)$ (by generalization theorem)
5. $\displaystyle R(x, c) \vdash \exists yR(x,y)$ (by generalization theorem)
6. $\displaystyle \forall y \neg R(x,y) \vdash \neg R(x,c)$ (contraposition)
7. $\displaystyle \neg R(x,c) \vdash \neg R(x,c)$ (quantifier axiom)

Thus, (2) is tautology.
That is thorough! Thank you!

Those rules any site which shows "all" used in predicate logic? My school book is missing out on some of them.

As for A), struggling hard myself, any help/suggestion on this as well?

6. Originally Posted by jokke22
1) $\displaystyle \forall x P(x) \wedge \exists x (P(x) \to Q(x)) \to \forall x Q(x)$
1.$\displaystyle \{\forall x P(x), \exists x (P(x) \to Q(x)) \} \vdash \forall x Q(x)$.
2.$\displaystyle \{\forall x P(x), \exists x( \neg P(x) \vee Q(x) \} \vdash \forall x Q(x)$.
3. $\displaystyle \{\forall x P(x), \exists x \neg P(x) \vee \exists x Q(x) \} \vdash \forall x Q(x)$.
4. $\displaystyle \{\forall x P(x), \neg \forall x P(x) \vee \exists x Q(x) \} \vdash \forall x Q(x)$.
5. $\displaystyle \{\forall x P(x), \exists x Q(x) \} \vdash \forall x Q(x)$.

Note.
Since $\displaystyle \{\exists x Q(x) \} \vdash \forall x Q(x)$ is not valid, 5 is not valid.
3 uses the rule of union for existential quantifier (link).