Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

Question

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$:

$$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$

But when I try to show it without a truth table (with just transformations), I end up in a loop between that and:

$$\lnot Q \land (\lnot Q \lor R)$$

Is there a way to show this is true without using a truth table? What am I missing?!

Thanks in advance!

Answer 1

\begin{align*} \neg Q \vee (\neg Q\wedge R) &= (\neg Q\wedge 1) \vee (\neg Q\wedge R) \\ &= \neg Q \wedge (1\vee R) \\ &= \neg Q \wedge 1 \\ &= \neg Q \end{align*}

Answer 2

$Q\implies\lnot Q \wedge R\implies\lnot Q$ Contradiction!

Answer 3

Assume that Q is true. Then it follows that $\lnot$Q is false, and ($\lnot$Q$\land$R) is false also. So, ¬Q∨(¬Q∧R) is false.

Assume that Q is false. Then $\lnot$Q is true, and thus so is ¬Q∨(¬Q∧R).

Since Q is either true or false, and since in either case the equality here ¬Q∨(¬Q∧R)=¬Q, it follows that ¬Q∨(¬Q∧R)=¬Q in all cases.

Answer 4

If you don't mind using order theory, you can show it without any reference to true or false. Let $\leq$ be an order with $A \vee B \geq A$ and $A \wedge B \leq A$. Then, $\neg Q \vee (\neg Q \wedge R) \geq \neg Q$ and $\neg Q \wedge (\neg Q \wedge R) \leq \neg Q$. If the two expressions are equal, you can see that they must equal $\neg Q$.

Answer 5

When it comes to showing that logical statements are independent of certain variables I like to cycle through them and show it this way. Notice that you've shown that your statement is independent of the truth or falsity of $R$ so I'll take that approach here.

Let's suppose $R = T$, then

$$\neg Q\vee(\neg Q\wedge R) = \neg Q\vee(\neg Q\wedge T) = \neg Q\vee (\neg Q)= \neg Q.$$

Likewise if $R = F$, then

$$\neg Q\vee(\neg Q\wedge R) = \neg Q\vee(\neg Q\wedge F) = \neg Q\vee F = \neg Q.$$

Thus no matter what the truth value of $R$ is we get $\neg Q$ so we are forced to conclude that $\neg Q\vee(\neg Q\wedge R) = \neg Q.$

Answer 6

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $Here is yet another way to calculate this:

$$\calc \lnot Q \lor (\lnot Q \land R) \;\equiv\; \lnot Q \calcop\equiv{both $\;X \lor Y \equiv Y\;$ and $\;\lnot X \lor Y\;$ are alternative ways to write $\;X \Rightarrow Y\;$} \lnot (\lnot Q \land R) \lor \lnot Q \calcop\equiv{DeMorgan} Q \lor \lnot R \lor \lnot Q \calcop\equiv{excluded middle; simplify} \true \endcalc$$