1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can $T \vee \neg q \equiv T$ In my book it says $T \vee q \equiv T$ $\endgroup$ – Aziz Soldier Jun 4 '15 at 16:23
  • 1
    $\begingroup$ 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.$ $\endgroup$ – abel Jun 4 '15 at 17:14
2
$\begingroup$

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

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

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 !

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.