# 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)$

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

• that parentheses are not necessary, is the exact content of associativity :) Jul 3 '15 at 18:37
• 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. 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.

• @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$) Jul 3 '15 at 19:34