I'm reviewing discrete math a second time (after it being over a decade since I took the course in college).

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$?

Rowsen's text just says "by the associative and commutative laws for disjunction".

What exactly are the associative step(s) involved in this transition? I understand the simple concept of commutative laws. Basically, I'm looking for a more rigorous explanation of how to arrive at this step than the one Rowsen supplies.

Also, regarding commutative, I would think that that the parentheses don't matter since all of the variables are connected by disjunctions only. Thus couldn't one also reason that $(\neg p \lor \neg q) \lor (p \lor q) \equiv \neg p \lor \neg q \lor p \lor q$? If so than it would seem easy to rearrange this by the commutative law. Then just add back the parentheses to get the desired result (in this case the goal being to arrive at $T \lor T$ by negation).

  • $\begingroup$ that parentheses are not necessary, is the exact content of associativity :) $\endgroup$
    – user251257
    Jul 3 '15 at 18:37
  • 1
    $\begingroup$ Would you be able to go from $(-p + -q) + (p + q)$ to $(-p + p) + (-q + q)$, using only the associative and commutative laws of addition; adding/removing/moving parenthesis, and switching the variables around? It's the same thing here. That is, I think your comment at the bottom is pretty much it. Maybe a few intermediate steps, depending on exactly what laws you have, but you've got the idea. $\endgroup$
    – pjs36
    Jul 3 '15 at 18:39

Answer 1: Either $\neg q$ or $q$ is true. So at least one of $\neg p \vee \neg q$ and $p \vee q$ is true, so expression 1 is a tautology. Also $\neg q \vee q$ is always true. so expression 2 is also a tautology, so they are equivalent.

Answer 2:

\begin{align*} (\neg p \vee \neg q) \vee (p \vee q) &\equiv (\neg p \vee (\neg q \vee (p \vee q)) \\ &\equiv \neg p \vee (\neg q \vee (q \vee p)) \\ &\equiv \neg p \vee ((\neg q \vee q) \vee p) \\ &\equiv \neg p \vee (p \vee (\neg q \vee q)) \\ &\equiv (\neg p \vee p) \vee (\neg q \vee q) \end{align*}

First, third and fifth by associative law, second and fourth by communative law.

  • $\begingroup$ Thanks, answer 2 is a nice breakdown as it shows the associative steps in a way that the book defines them (i.e. moving parentheses instead of my hand-waving way of just saying let's get ride of all the parentheses, rearrange, and add parentheses back in). However, based on the comments to my question, I assume my approach is acceptable as well? $\endgroup$
    – Matt
    Jul 3 '15 at 18:56
  • $\begingroup$ @Matt What is "acceptable" is a tricky question as it may depend on various factors. If you want to be more rigorous, you could try to do the following exercise: Every propositional formula $\phi$ can be converted in an equivalent formula of the form $((((\phi_1 \vee \phi_2) \vee \phi_3) \vee \ldots ) \vee \phi_n)$, where each $\phi_i$, $i=1, \ldots, n$, doesn't contain $\vee$ as a logical symbol. (Hint: Proceed by induction on the complexity of $\phi$) $\endgroup$ Jul 3 '15 at 19:34
  • $\begingroup$ @Stefan, thanks for the suggestion. I'll consider this when I get the the time. I'm reviewing discrete math to prepare for graduate level algorithms this fall. I haven't gotten to the review of induction yet. I agree about "acceptable" being tricky and why I asked this question in the first place to better the rigor of my understanding and not rely so much on intuition or hand waving. $\endgroup$
    – Matt
    Jul 3 '15 at 19:44

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.