# Prove tautology without truth table (Stuck)

I'm trying to prove a formula that is tautology without using truth tables and i'm stuck... Here is what i tried:

Formula: $((p \land q) \land(p \to r) \land (q \to r)) \to r$

What i did:

1. $((p \land q) \land(p \to r) \land (q \to r)) \to r$
2. $((p \land q) \land(\lnot p \lor r) \land (\lnot q \lor r)) \to r$
3. $(\lnot p \land \lnot q) \lor (p \land \lnot r) \lor (q \lor \lnot r) \lor r$

And what should i do now ?

Try to make your formula false. To do it, $r$ shold be false (denote $r=0$ for short). But the predecessor should be true which means that all $p\wedge q$, $p\to r$ and $q\to r$ should be true. It is impossible because since $p\wedge q=1,$ then $p=1$ and $q=1$ and both implications $p\to r$, $q\to r$ are false.

I have shown that it is impossible to find a valuation for $p,q,r$ which makes our formula false.

You were a little quick going from:

1. $((p \land q) \land(\lnot p \lor r) \land (\lnot q \lor r)) \to r$

to:

1. $(\lnot p \land \lnot q) \lor (p \land \lnot r) \lor (q \lor \lnot r) \lor r$

And in fact you made some small mistakes ... so let's do that again:

1. $((p \land q) \land(\lnot p \lor r) \land (\lnot q \lor r)) \to r \Leftrightarrow \text{ (Implication)}$

2. $\neg ((p \land q) \land(\lnot p \lor r) \land (\lnot q \lor r)) \lor r \Leftrightarrow \text{ (DeMorgan)}$

3. $\neg (p \land q) \lor \neg(\lnot p \lor r) \lor \neg(\lnot q \lor r)) \lor r \Leftrightarrow \text{ (DeMorgan x 3)}$

4. $(\neg p \lor \neg q) \lor (p \land \neg r) \lor (q \land \neg r) \lor r$

So this is different from what you got! ... can you take it from here?

If not:

5. $(\neg p \lor \neg q) \lor (p \land \neg r) \lor (q \land \neg r) \lor r \Leftrightarrow \text{ (Association)}$
6. $\neg p \lor \neg q \lor (p \land \neg r) \lor (q \land \neg r) \lor r \Leftrightarrow \text{ (Commutation)}$
7. $\neg p \lor (p \land \neg r) \lor (q \land \neg r) \lor \neg q \lor r \Leftrightarrow \text{ (DeMorgan)}$
8. $\neg p \lor (p \land \neg r) \lor (q \land \neg r) \lor \neg (q \land \neg r) \Leftrightarrow \text{ (Complement)}$
9. $\neg p \lor (p \land \neg r) \lor \top \Leftrightarrow \text{ (Annihilation)}$
10. $\top$