Showing tautology without a truth table.

Question

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?

Aaron Maroja · Answer 1 · 2015-06-04T16:30:18.757

2

$$ \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.

edited Jun 04 '15 at 16:30

answered Jun 04 '15 at 15:56

Aaron Maroja

17,571

How can the negation disappear in $(\neg p \vee p) \vee q$? – Aziz Soldier Jun 04 '15 at 16:25
It doesn't disappear, $\neg p \vee p \equiv T$, that is, is always true. – Aaron Maroja Jun 04 '15 at 16:27
I meant the negation of $q$ – Aziz Soldier Jun 04 '15 at 16:31
Is it clear now? Do you get the "next step"? – Aaron Maroja Jun 04 '15 at 16:31
Okay so $T \vee \neg q \equiv T$ and $T \vee q \equiv T$ is the same? – Aziz Soldier Jun 04 '15 at 16:34
1

No, it was a typo. But both are true. – Aaron Maroja Jun 04 '15 at 16:51

score 2 · Answer 2 · answered Jun 04 '15 at 15:58

2

$$ 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$$

answered Jun 04 '15 at 15:58

abel

29,170

How can $T \vee \neg q \equiv T$ In my book it says $T \vee q \equiv T$ – Aziz Soldier Jun 04 '15 at 16:23
1

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 04 '15 at 17:14

score 1 · Answer 3 · answered Jun 04 '15 at 16:00

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 !

Showing tautology without a truth table.

3 Answers3