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$
2
  • $\begingroup$ How can $T \vee \neg q \equiv T$ In my book it says $T \vee q \equiv T$ $\endgroup$ 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$
6
  • $\begingroup$ How can the negation disappear in $(\neg p \vee p) \vee q$? $\endgroup$ Jun 4 '15 at 16:25
  • $\begingroup$ It doesn't disappear, $\neg p \vee p \equiv T$, that is, is always true. $\endgroup$ Jun 4 '15 at 16:27
  • $\begingroup$ I meant the negation of $q$ $\endgroup$ Jun 4 '15 at 16:31
  • $\begingroup$ Is it clear now? Do you get the "next step"? $\endgroup$ Jun 4 '15 at 16:31
  • 1
    $\begingroup$ No, it was a typo. But both are true. $\endgroup$ 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.