Answer to Question #325554 in Discrete Mathematics for Abbas

Question

Determine whether (¬q ∧ (p → q)) → ¬p) 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:

$(\lnot q\land(p\rightarrow q))\rightarrow\lnot p=\lnot{(\lnot q\land(\lnot p\lor q))}\lor\lnot p$. Remind De Morgan’s laws (they belong to laws of logic): $\overline{a\land b}=\bar{a}\lor\bar{b}$, $\overline{a\lor b}=\bar{a}\land\bar{b}$ for two statements $a,b$. From them we get: $\lnot{(\lnot q\land(\lnot p\lor q))}\lor\lnot p=q\lor(\lnot(\lnot p\lor q))\lor\lnot p=\lnot q\lor( p\land \lnot q)\lor\lnot p$. The statement is not a tautology. Suppose that p and q are true. The expression is false in this case.