Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that following is a tautology because I've checked its truth table. I am now attempting to prove that it is a tautology by using the rules of logic, which is more difficult. How should I proceed?

$(p\land(p\implies q))\implies q$

$(p\land(\lnot p \lor q))\implies q$

$(p\land \lnot p) \lor (p\land q) \implies q$ This step is where I'm getting stuck at. I know that $(p\land \lnot p)$ is false. So it seems to me that the truth value of everything to the left of the $\implies$ operator depends on the truth value of $(p\land q)$ So what I want to do is this:

FALSE $\lor (p\land q) \implies q$ which reduces to

$(p\land q) \implies q$

Is my thinking correct so far? If so, then I want to rewrite $(p\land q) \implies q$ as

$\lnot(p \land q) \lor (p \land q)$ by using the identity $p\implies q \equiv \lnot p \lor q$ Am I on the right track?

share|improve this question
    
Everything looks good for your first question. I would think that $(p\land q)\implies q$ is more fundamental than the identity you used. –  Jonas Meyer Jan 17 '11 at 6:52
    
You are correct! –  lampShade Jan 17 '11 at 7:27
add comment

4 Answers

up vote 3 down vote accepted

Use De Morgan's law on $\neg(p\land q)$ near the end. This should give you a disjunction which should easily be seen as tautological by the law of excluded middle. Also, remember that $(p\land q)\implies q\equiv \neg(p\land q)\lor q$, not $\neg(p\land q)\lor(p\land q)$ as you wrote.

share|improve this answer
    
This is the essential step. Thanks for all the help! I have it now. –  lampShade Jan 17 '11 at 7:26
add comment

Your reasoning is correct so far. It seems to me that since $a\to b$ is equivalent to $\lnot a\lor b$, then $(p\land q)\to q$ is equivalent to $\lnot(p\land q)\lor q$, which is different from what you wrote in the last line. To continue, I guess you want to use that $\lnot(p\land q)$ is equivalent to $\lnot p\lor \lnot q$.

share|improve this answer
add comment

$$ \begin{align} (p\land(p\rightarrow q))\rightarrow q &\Longleftrightarrow (p\land(\neg p\lor q))\rightarrow q\\ &\Longleftrightarrow ((p\land \neg p)\lor (p\land q))\rightarrow q\\ &\Longleftrightarrow (F\lor (p\land q))\rightarrow q & \text{Negation law}\\ &\Longleftrightarrow \neg(F\lor (p\land q))\lor q\\ &\Longleftrightarrow (T\land \neg(p\land q))\lor q \\ &\Longleftrightarrow (T\land(\neg p\lor \neg q))\lor q &\text{DeMorgan's law}\\ &\Longleftrightarrow (\neg p\lor \neg q)\lor q &\text{Domination law}\\ &\Longleftrightarrow \neg p\lor (\neg q\lor q) \\ &\Longleftrightarrow \neg p\lor T\\ &\Longleftrightarrow T\\ \end{align} $$

share|improve this answer
    
I edited your post to put it in the LaTeX form we use here. To see how I did it, click on the text right after "edited" above this comment. By the way, welcome to the site! –  Rick Decker Sep 22 '12 at 19:32
add comment

Using natural deduction notation

Modus ponens: $$\backslash\!\!\!\!\!{A}$$ $$\overline{B}$$ $$\overline{A\to B}$$ If from the assumption $A$ can deduce $B$, then $A\to B$ is deducible.

Law of Conjunction: $$A\wedge B$$ $$\overline{\qquad A \qquad}$$ and $$A\wedge B$$ $$\overline{\qquad B \qquad}$$ and If $A\wedge B$ holds, then both $A$ and $B$ also holds.

To prove the statement using ND, start by breaking up the first implication - and you soon figure out what to do. (If there is any doubt just ask.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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