[Math] Is $[p \land (p \to q)] \to q$ a tautology

discrete mathematicslogic

I am new to discrete mathematics, and I am trying to simplify this statement. I'm using a chart of logical equivalences, but I can't seem to find anything that really helps reduce this.

Which of these would help me to solve this problem? I realize I can covert $p \to q$ into $\lnot p \lor q$, but I'm stuck after that step. Any push in the right direction would be awesome.

Best Answer

Is it a tautology? Yes

Why? Just draw the truth table and see that the truth value of the main implication is always 'true'. Here, I say '0' is 'false' and '1' is true: \begin{array}{|c|c|c|c|c|} \hline p & q & p\to q & p\land(p\to q) & (p\land(p\to q))\to q \\ \hline 0 & 0& 1&0&1\\ \hline 0 & 1& 1&0&1\\ \hline 1 & 0& 0&0&1\\ \hline 1 & 1& 1& 1& 1\\ \hline \end{array}

Edit: you can also say \begin{align}p \land (p \to q) &\equiv p \land (\lnot p \lor q)\\ &\equiv (p \land \lnot p) \lor (p \land q )\\ &\equiv \text {false} \lor (p \land q)\\&\equiv p \land q, \end{align}

that implies $q $.

Edit 2: this inference method is called modus ponens, and it is the simplest one.

For instance, say $p = $ it rains, $g = $ I get wet.

So, if we know that the implication if it rains, then I get wet is true (that is, $p\to q $) and It rains ($p $), what can we infere? It is obvious that I get wet ($q $).

Note that, even though $p \land (p\to q) $ is not verified, as $p\land (p\to q) \to q$, the main implication is verified.

Related Question