1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ @PeterForeman : Disjunction is associative... $\endgroup$ – Eric Towers Jun 17 '19 at 17:29
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So it's true that, in general, the associative law does not hold? Are there cases where they do hold? $\endgroup$ – BigBear Jun 17 '19 at 17:43
  • 1
    $\begingroup$ @WilsonGuo: It would be more right to say that what you're calling "the associative law" is not the same as what most other people use that name about. Your (vastly extended) "associative law" does not hold in general. $\endgroup$ – hmakholm left over Monica Jun 17 '19 at 22:07

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.