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

11
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 28, 2014 at 20:48
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This isn't clear. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .