# How should I proceed in proving this tautology?

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?

-
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

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.

-
This is the essential step. Thanks for all the help! I have it now. –  lampShade Jan 17 '11 at 7:26

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

-

\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}

-
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

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.)

-