2
$\begingroup$

I'm learning about disjunctive normal form and the algebra of propositions. The text is Discrete Mathematics with Graph Theory, 3rd Edition by Goodaire and Parmenter (it wasn't highly recommended on Amazon but it is what BSU has chosen).

In the examples is this implication, $p \rightarrow (q \wedge r)$ which they use to demonstrate how to show in disjunctive normal form using both truth tables and algebra. I'm lost on the algebra. Please help me understand where it's coming from.

$ \begin{align} [p\rightarrow (q\wedge r)] &\Leftrightarrow [(\neg p) \vee (q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q)\vee ((\neg p)\wedge (\neg q)) \vee (q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q \wedge r) \vee ((\neg p)\wedge q \wedge (\neg r)) \vee \\ & \hspace{20pt}((\neg p )\wedge (\neg q) \wedge r) \vee ((\neg p) \wedge (\neg q) \wedge (\neg r)) \vee \\ & \hspace{20pt} (p \wedge q \wedge r) \vee ((\neg p)\wedge q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q \wedge r) \vee ((\neg p)\wedge q \wedge (\neg r)) \vee \\ & \hspace{15pt}((\neg p )\wedge (\neg q) \wedge r) \vee ((\neg p) \wedge (\neg q) \wedge (\neg r)) \vee (p \wedge q \wedge r)] \end{align} $

I'm fine up to the first logical equivalance. However, on the second, I'm lost. I'm not sure which one of the properties they've discussed was used in this algebra. Is a distributive property being used?

$\endgroup$
3
$\begingroup$

What is being done, here, in the second equivalence is using the equivalence of $$\lnot p \equiv \lnot p\land T \equiv (\lnot p \land (\underbrace{q\lor \lnot q}_{\large \text{true}})) \underbrace{\equiv}_{\large \text{DL}} (\lnot p \land q) \lor (\lnot p \land \lnot q)$$

So $$\color{blue}{\lnot p} \lor \color{red}{(q\land r)} \equiv \color{blue}{(\lnot p \land q) \lor (\lnot p \land \lnot q)}\lor \color{red}{(q\land r)}$$

So yes, in a sense, the distributive law (DL) is being used, as well as the tautologies $\lnot p \equiv (\lnot p \land T)$ and $q \lor \lnot q = T$.

The same approach is being used in the second equivalence, which makes use of the tautology $r \lor \lnot r$, etc.

$\endgroup$
  • $\begingroup$ Thank you. I can see things more clearly now. I'm working a bit on the $\lnot p \equiv p \land T$ but I think I'm getting it. It started to make sense with truth tables. What's quite irritating is that I cannot find, in the text, the foundation for this "trick" they've used. $\endgroup$ – Andrew Falanga Feb 5 '14 at 14:38
  • $\begingroup$ @Andrew Falanga - The trick is simple: $p \land T$ is equivalent to $p$ simply because of truth-table for $\land$. If you write the table for a two sentence letters formula, you can see that the presence of $T$ "cancels" the two rows : $T-F$ and $F-F$; so the two remaining rows gives you respectively : $T$ for the row $T-T$ and $F$ for the row $F-T$, and this amount to saying that the result has the same truth-value as $p$. The same for $p \lor F \equiv p$. $\endgroup$ – Mauro ALLEGRANZA Feb 5 '14 at 16:02
  • $\begingroup$ @Andrew Falanga - the other trick to be used is : $T \equiv (p \lor \lnot p)$ and $F \equiv (p \land \lnot p)$. The reason is the same, and it is obvious. $\endgroup$ – Mauro ALLEGRANZA Feb 5 '14 at 16:05
  • $\begingroup$ @MauroALLEGRANZA I would agree it's obvious once you've learned it. I think I've got it though. Just to be sure. My text has this logical equivalence: $(p \land 1) \equiv p$. This seems to be the one being used, only instead of $p$ it's $(\lnot p \land 1) \equiv \lnot p$. This is because, if $\lnot p$ is true, then paring it with a tautology means you have $\lnot p$. Maybe my wording is wrong, but do I have it? $\endgroup$ – Andrew Falanga Feb 5 '14 at 22:37
  • $\begingroup$ @Andrew Yes, you've got it! Pairing ("and-ing") any statement whatsoever with a tautology is equivalent to that same statement. $\endgroup$ – Namaste Feb 5 '14 at 22:43
1
$\begingroup$

He has used the following "tricks" (check them with truth-tables) :

$$p \equiv (p \land T)$$

and

$$T \equiv (q \lor \lnot q)$$

So, you have the following chain of equivalences :

$$[(\lnot p) \lor (q \land r)] \equiv [(\lnot p \land T) \lor (q \land r)] \equiv [(\lnot p \land (q \lor \lnot q)) \lor (q \land r)] $$

Now, if you "distribute" $\lnot p$, you will get the second equivalence.

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