Logical equivalence rule: prove a tautology

Question

For the tautology

"(¬Q)→(R→¬(P∧Q))"

how can I show that this is equivalent With the tautology

(Q or (¬Q))
By logical equivalence rules? Would this be easier to do by using a truth table, de morgan Law etc?

Answer 1

A truth-table takes $8$ rows ... which is pretty doable.

Using logical equivalence rules is probably a bit quicker though. Start with rewriting the implications as disjunctions:

$$\neg Q \rightarrow (R \rightarrow \neg (P \land Q)) \Leftrightarrow$$

$$Q \lor (\neg R \lor \neg (P \land Q))$$

$$...$$

Answer 2

As Mauro also said, try using $P \rightarrow Q \equiv \lnot P \lor Q$ along with associativity and distributivity.

$$\begin{align} (\lnot Q) \rightarrow (R \rightarrow \lnot(P\land Q)) &\equiv Q \lor (\lnot R \lor (\lnot P \lor \lnot Q)) \\ &\equiv Q \lor (\lnot Q \lor (\lnot R \lor \lnot P))\\ &\equiv( Q \lor \lnot Q )\lor (Q \lor (\lnot R \lor \lnot P)) \end{align}$$

which is a tautology since $Q \lor \lnot Q$ is a tautology.

Answer 3

$\neg Q\to (R\to\neg(Q\wedge P))$ will be a tautology if it is held to be true for all evaluations of $P,R,$ and $Q$.   Let us look at both evaluations for $Q$.

• Assume $Q$; that $Q$ evaluates as $\top$ (true).   Then by substitution the implication is $\neg\top\to(R\to\neg(\top\wedge P))$, which is an implication whose antecedant is false.

• Assume $\neg Q$; that $Q$ evaluates as $\bot$ (false).   Then by substitution the implication is $\neg\bot\to(R\to\neg(\bot\wedge P))$, which is an nested implication whose consequent is an implication whose consequent is true.

Therefore what can we say?