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$

6 Answers 6

Reset to default
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, 2014 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, 2014 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, 2014 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, 2016 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, 2014 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, 2014 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$
    – A. Thomas Yerger
    Jun 23, 2014 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, 2014 at 2:36
  • $\begingroup$ Oh you're right. Whoops. Thanks for the clarification. I misread what was in front of me. $\endgroup$
    – A. Thomas Yerger
    Jun 23, 2014 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, 2014 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.