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

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?!

\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*}

• (This is kind of a dirty trick, if you ask me.)
– user21467
Jun 23, 2014 at 2:29
• How did you get the not Q and 1? I kind of get it but would like to be sure. Thank you! Jun 23, 2014 at 2:31
• If you mean, why is it correct, I guess it depends on your context. It's often an axiom that $A\wedge 1 = A$. If you mean, how would someone come up with the idea of making that manipulation in this context, I guess it's analogous to factoring out the $x$ from something like $x+xy$ and getting $x(1+y)$.
– user21467
Jun 23, 2014 at 2:38
• It is old but I would like to add something for newcomers. Q ^ True = Q. (in propositional logic, Q ^ 1 = Q in Boole's Algebra). This is true because if Q = True, True ^ True is True. Then if Q = False, False ^ True remains false. So, Q ^ True = Q. In the second step, he extracts the Q using 'reverse distributive'. May 11, 2016 at 18:41

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.$

• is this not part of the truth table? the point of the op is not to use the truth table.
– abel
Nov 28, 2014 at 20:48

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

• This isn't clear. Jun 23, 2014 at 2:09

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.

• When $Q$ is false, how do you have that $\neg Q \wedge R$ is true? Is $R$ always true? Jun 23, 2014 at 2:24
• I don't have that if Q is false, then ¬Q∧R is true. I have that ¬Q∨(¬Q∧R) is true. Jun 23, 2014 at 2:36
• Oh you're right. Whoops. Thanks for the clarification. I misread what was in front of me. Jun 23, 2014 at 2:39

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$.

• \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)}}Another way to write this argument, using $\;\Rightarrow\;$ for $\;\le\;$ and $\;\Leftarrow\;$ for $\;\ge\;$: $$\calc \lnot Q \calcop\Rightarrow{weaken} \lnot Q \lor (\lnot Q \land R) \tag{0} \calcop\equiv{distribute; simplify} \lnot Q \land (\lnot Q \lor R) \calcop\Rightarrow{weaken} \tag{1} \lnot Q \endcalc$$ This ping-pong argument shows that $\;\ref 0 \;\equiv\; \ref 1\;$. Nov 28, 2014 at 20:10

\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$$