Showing tautology without a truth table.

Show that the conditional statement is a tautology without using a truth table.

$a)$ $(p \wedge q) \rightarrow p$

My suggestion would be getting rid of the implication first, so

$(p \wedge q) \rightarrow p \equiv \neg(p \wedge q) \vee p$

How should I continue hereafter?

$$p \wedge q) \rightarrow p \equiv \neg(p \wedge q) \vee p \equiv (\neg p \vee \neg q)\vee p \equiv (\neg p \vee p)\vee \neg q \equiv T \vee \neg q \equiv T$$

• How can $T \vee \neg q \equiv T$ In my book it says $T \vee q \equiv T$ – Aziz Soldier Jun 4 '15 at 16:23
• both $T \vee q \equiv T$ and $T \equiv \neg q \equiv T$ are true because $T \vee T \equiv T, T \vee F \equiv T.$ – abel Jun 4 '15 at 17:14

\begin{align}(p \wedge q) \to p &\equiv \neg(p \wedge q) \vee p \\&\equiv (\neg p \vee \neg q) \vee p \equiv \neg p \vee (\neg q \vee p) \\&\equiv (\neg p \vee p)\vee \neg q \equiv T \vee \neg q \equiv T \end{align}

Next step should be to use De Morgan's Law.

• How can the negation disappear in $(\neg p \vee p) \vee q$? – Aziz Soldier Jun 4 '15 at 16:25
• It doesn't disappear, $\neg p \vee p \equiv T$, that is, is always true. – Aaron Maroja Jun 4 '15 at 16:27
• I meant the negation of $q$ – Aziz Soldier Jun 4 '15 at 16:31
• Is it clear now? Do you get the "next step"? – Aaron Maroja Jun 4 '15 at 16:31
• No, it was a typo. But both are true. – Aaron Maroja Jun 4 '15 at 16:51

Well you are on the right track on getting rid of the implication.

Now you should see that for $\neg(p \wedge q) \vee p$

If $p$ is true and then we have $\neg(p \wedge q) \vee true$ which is true

Now if $p$ is false then we have $\neg(false \wedge q) \vee false$ which is $\neg(false) \vee false$ which is $true \vee false$ which is true.

Now you see that we don't even care about $q$ and that's why we don't need a truth table !