# 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

## 4 Answers

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9549977779388428, "perplexity_flag": "head"}