Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$p \land \lnot q \lor q \land \lnot r \lor \lnot p \lor r $ $\equiv$$(p \lor \lnot p) \land (\lnot q \lor q) \land (\lnot r \lor r)$

Is this move "legal"? Or can you only apply the associative property on like operators?

share|cite|improve this question
Hard to judge about move, since left-hand side is unreadable. – André Nicolas Jan 16 '13 at 1:13
You are also applying a commutative property at the same time, which makes this even harder to follow. – Code-Guru Jan 16 '13 at 1:18
up vote 4 down vote accepted

Associativity applies only when the connectives involved are exclusively $\land$ or exclusively $\lor$:

$$p \land q \land r \equiv (p \land q)\land r \equiv p \land (q\land r)$$

$$p \lor q \lor r \equiv (p \lor q)\lor r \equiv p \lor (q\lor r)$$

Because of associativity of $\lor$ and $\land$, parentheses are not necessary to define expressions like those above.

Your statement, however:

$$p \land \lnot q \lor q \land \lnot r \lor \lnot p \lor r \tag{given}$$

has mixed connectives, and so associativity does not apply across all possible groupings.

Please note: as stated, your (given) expression is not well-defined without parentheses. That is, without parentheses, it is ambiguous; it can be read any number of ways, most of which are not equivalent. Does it mean connect from left to right?:

$$(((((p\land \lnot q) \lor q) \land) \lnot r)\lor\lnot p) \lor r\;?\tag{1}$$

Or does it mean this?

$(p \land \lnot q) \lor (q \land \lnot r) \lor (\lnot p \lor r)\;?\tag{2}$

or any number of other possible ways of grouping with parentheses?

In general, when you have an expression like $(2)$ above, you need to apply the Distributive Laws to distribute over another connective:

For example $$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$$ $$p \lor (q\land r) \equiv (p \lor q) \land (p\lor r)$$

share|cite|improve this answer
Does boolean logic have a mathematically defined "order of operations"? Programming languages typically define one (which they call "precedence") for boolean operators, but I'm not certain if this comes from some mathematical definition or not. – Code-Guru Jan 16 '13 at 1:25
In theory, there is an order of precendence defined, but I have seen at least two different, mutually contradictory versions of it (one rates $\vee$ higher, the other $\wedge$). – Johannes Kloos Jan 16 '13 at 2:17
Associativity, by itself, is NOT sufficient for defining expressions like p^(q^r) where the rule of replacement is NOT restricted, and the structure in question has more than one operation. If you have the rule of replacement, and you deal with ({0, 1}, ^) as a structure, then you can drop all parentheses. But, if you deal with ({0, 1}, ^, v), and you drop parentheses as liberally as you want, then 1^(0v0) is ambiguous, since from 0v0=0 we can derive 1^(0v0)=1^0=0, and since it is true that 1=1v0, it would come as valid to derive that 1^(0v0)=1v0^(0v0)=1v(0^(0v0))=1v0=1. – Doug Spoonwood Jan 17 '13 at 1:51
@amWhy: Lovely answer +1 – Amzoti May 8 '13 at 2:40

No, mixed expressions like this are not associative; instead, they obey distributive laws: $$ (a\wedge b)\vee c \equiv (a\vee c) \wedge (b \vee c) $$ and $$ a \wedge (b\vee c) \equiv(a\wedge b) \vee (a \wedge c). $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.