3
$\begingroup$

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!

$\endgroup$
10
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ (This is kind of a dirty trick, if you ask me.) $\endgroup$ – user21467 Jun 23 '14 at 2:29
  • $\begingroup$ How did you get the not Q and 1? I kind of get it but would like to be sure. Thank you! $\endgroup$ – user157000 Jun 23 '14 at 2:31
  • 1
    $\begingroup$ 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)$. $\endgroup$ – user21467 Jun 23 '14 at 2:38
  • $\begingroup$ 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'. $\endgroup$ – JorgeeFG May 11 '16 at 18:41
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ is this not part of the truth table? the point of the op is not to use the truth table. $\endgroup$ – abel Nov 28 '14 at 20:48
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This isn't clear. $\endgroup$ – Doug Spoonwood Jun 23 '14 at 2:09
1
$\begingroup$

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.

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

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

$\endgroup$
1
  • $\begingroup$ $ \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\;$. $\endgroup$ – MarnixKlooster ReinstateMonica Nov 28 '14 at 20:10
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.