Associative Law for Boolean Logic

Question

The associative law states that for the logic formula:

$$(A \wedge B) \wedge C = A \wedge (B \wedge C)$$

$$(A \vee B) \vee C = A \vee (B \vee C)$$

I asked myself would the associative law hold for multiple operators, so I tested it out on $(A \wedge B) \vee C $ vs $A \wedge (B \vee C) $. This turned out to not be true once I did I truth table. For the first formula as long as C is true the entire thing is true even if A is not true, while for the second, A must be true in order for the logic formula to hold true.

My question is are there times when the associative law still works when I have multiple operators and not just two (e.g. $A \wedge B \wedge C \vee D\vee E$). How can I tell immediately whether or not the associative law is applicable? Are there operators (such as $\downarrow$) that work with the associative law even when I have different operators in the same formula?

Answer 1

Apart from conjunction and disjunction, other associative operations are the biconditional $\leftrightarrow$ and the exclusive-or $\oplus$, where $a\oplus b$ is defined as $(a\land\lnot b)\lor (\lnot a\land b)$, i.e., $a\oplus b$ is true if and only if exactly one of $a$ and $b$ is true. The conditional $\rightarrow$ is not associative.

To your broader question, I'd say it's not entirely clear what it means to say that the associative law applies to 'multiple operators': typically, it's only applied to iterations of the same operator.

In your example with $(a\land b)\lor c$ and $a\land (b\lor c)$, you can replace $a\land b$ with $f(a,b)$, and $a\lor b$ with $g(a,b)$. Your suggestion is then that associativity would require that $g(f(a,b), c)$ is equivalent to $f(a, g(b,c))$. However, it's not entirely clear that this is what associativity should mean in this context; and even if it does, you can't expect it to hold in general.

Answer 2

This is analogous to the situation with addition and multiplication. Both are associative by themselves. However, multiplication distributes over addition. You can't have combined associativity with both of them together. That is, for example, it is not true in general that $(a+b)*c = a+(b*c).$ In fact, what is true is that $(a+b)*c = (a*c)+(b*c).$ Same thing happens with Boolean logic $\wedge$ and $\vee.$

Associativity only holds if you have an expression with just one kind of binary operator in the expression. You can not combine two kinds of associative operators together in general, as demonstrated by the addition ($+$) and multiplication ($*$) example.

Of course, there can be special examples where you can combine operators and still have associativity. For example, suppose we define the operator $a\circ b:=0$ which is clearly associative (check). Then $(a*b)\circ c = a*(b\circ c) = 0$ for all $a,b,c.$