Answer to Question #325559 in Discrete Mathematics for Abbas

Question

Determine whether (p ∧ (p → q)) →q is a tautology using laws of logic.

Answer 1

At first, we remind that logical implication $\rightarrow$ can be rewritten via a logical disjunction. Namely, $a\rightarrow b=\bar{a}\lor b$ for two statements $a,b$. Thus, the expression can be rewritten as: $(p\land(p\rightarrow q))\rightarrow q=\overline{(p\land(\bar{p}\lor q))}\lor q$. Remind De Morgan’s laws (they belong to laws of logic): $\overline{p\land q}=\bar{p}\lor\bar{q}$, $\overline{p\lor q}=\bar{p}\land\bar{q}$. From them we get: $\overline{(p\land(\bar{p}\lor q))}\lor q={(\bar{p}\lor\overline{(\bar{p}\lor q))}}\lor q={\bar{p}\lor{({p}\land \bar{q})}}\lor q={\bar{p}\lor q\lor{({p}\land \bar{q})}}$. We point out that $\overline{\bar{p}\lor q}={({p}\land \bar{q})}$. Thus, we have a disjunction of the statement $\overline{p}\lor q$ and its negation. Therefore, the expression is a tautology.