# Associativity and De Morgan's for more than 2 literals

Do logical operators have meaning when used with more than 2 literals "associatively", e.g.: $(A \land B \land C)$?

I.e., are statements such as $(A \land B \land C)$ meaningful, as opposed to $((A \land B) \land C)$, which is meaningful?

If yes, is it possible to prove De Morgan's for any finite n by induction like so:

1. For $n = 2$, base De Morgan's applies: $\neg(A_{1} \lor A_{2}) \Leftrightarrow \neg A_{1} \land \neg A_{2}$.
2. Assume that for $n = k$, $\neg (A_{1}\lor A_{2}\lor \ldots \lor A_{k}) \Leftrightarrow (\neg A_{1}\land \neg A_{2} \land \ldots \land \neg A_{k})$.
3. Then for $n = k + 1$: $\neg (A_{1}\lor A_{2}\lor \ldots \lor A_{k} \lor A_{k+1}) \Leftrightarrow \neg ((A_{1}\lor A_{2}\lor \ldots \lor A_{k})\lor A_{k+1})\Leftrightarrow \neg (A_{1}\lor A_{2}\lor \ldots \lor A_{k}) \land \neg A_{k+1} \Leftrightarrow \neg A_{1} \land \neg A_{2} \land \ldots \land \neg A_{k} \land \neg A_{k+1}$
4. Therefore, $\neg (A_{1}\lor A_{2}\lor \ldots \lor A_{n}) \Leftrightarrow (\neg A_{1}\land \neg A_{2} \land \ldots \land \neg A_{n})$ is true for any finite n.

?

Thank you.

• Yes; $(A∧B∧C)$ is an abbreviation for $(A∧(B∧C))$ or, equivalently : $((A∧B)∧C))$, as your proof shows. Jan 17 '15 at 10:15
• No, take a look at the formation rules. Also, the rule of uniform substitution would fail if (A∧B∧C) were meaningful. Jan 17 '15 at 19:25
• @DougSpoonwood Could you please elaborate on that? Thank you. Jan 19 '15 at 3:12
• @DougSpoonwood I feel like it even though it is formally incorrect to use that kind of notation, it is still meaningful intuitively. For example, for both $\land$ and $\lor$ the truth table of an expression consisting of $n$ literals and $n-1$ operators of one kind is the same whatever the placement of parentheses is (out of $2^n$ possible variants). Therefore, the notation in this case is logically insignificant. Jan 19 '15 at 3:35
• No, it's logically significant, because if (A∧B∧C) is an expression, than the rule of uniform substitution fails. The rule of uniform substitution is important for having an axiomatic system of propositional logic. If say A∧B is meaningful (which you implied), and we have the rule of uniform substitution, then substituting B with CvD we obtain A∧CvD. Suppose A=0, C=0, D=1. Then [A∧(CvD)]=0, while [(A∧C)vD]=1. So, I started with an expression assumed as meaningful and deduced a contradiction, which renders either the expression or the rule of uniform substitution as not meaningful. Jan 19 '15 at 3:57

Certainly $\land$ and $\lor$ can be used meaningfully in this way. This is because we can prove (e.g. by truth tables, a straightforward exercise) that they are associative, i.e.:

$$A \land (B \land C) \iff (A \land B) \land C \qquad A \lor (B \lor C) \iff (A \lor B) \lor C$$

so that we can argue that it doesn't really matter whether we use parentheses or not. From there on, you have given a proper proof that De Morgan's laws generalise to these expressions.

Do note, however, that this does not apply to every logical operator out there. This question deals with associativity of $\to$; it is shown not to be associative:

$$A \to (B \to C) \not\iff (A \to B) \to C$$

• You can only use ∧ and ∨ in this way, if we have a system where the only binary expression is either ∧ or ∨ (but you can't have both around). Associativity only ensures that such expressions are meaningful when we have a pure semigroup. If we have two associative operations around, such as the two-valued logical operations "∧" and "∨", then an expression like A∧B∨C can be ambiguous. It's not associativity which makes such work, but rather that for any binary operations B$_1$, B$_2$, for all x, y, z, ((xB$_1$y)B$_2$z)=(xB$_1$(yB$_2$z)). Associativity is a special case of that. Jan 19 '15 at 4:03
• This answer combined with Doug Spoonwood's note that the only logical operator used should be ($\land$ XOR $\lor$) answers my question completely. Jan 19 '15 at 5:19
• @Doug Nowhere did I imply that expressions combining $\lor$ and $\land$ without parentheses are meaningful. Jan 19 '15 at 6:07

No. For example, (A$\land$B$\lor$C) is not meaningful, even though both $\land$ and $\lor$ associate.

If we have that for any binary operations B1, B2, for all x, y, z, ((xB1y)B2z)=(xB1(yB2z)), then we can drop parentheses as you've suggested. Thus, if we just have a semigroup, then we can drop all parentheses. But, if we have more than one binary operation, we can't drop parentheses.

Also, if (A∧B∧C) is an expression, than the rule of uniform substitution fails. The rule of uniform substitution is important for having an axiomatic system of propositional logic. If say A∧B is meaningful (which you implied), and we have the rule of uniform substitution, then substituting B with CvD we obtain A∧CvD. Suppose A=0, C=0, D=1. Then [A∧(CvD)]=0, while [(A∧C)vD]=1. So, I started with an expression assumed as meaningful and deduced a contradiction, which renders either the expression or the rule of uniform substitution as not meaningful.

• Surely the rule of uniform substitution applies only to wffs. You can replace $B$ with the complete wff $(C\lor D)$; you cannot replace it with the non-wff $C\lor D$ any more than you can replace it with the non-wffs $C\lor$ or $(C\lor D$.
– MJD
Jan 19 '15 at 4:42
• Thank you for your answer. Is it right then, that if ($\lor$ is used) XOR ($\land$ is used) multiple times within the initial expression AND we do not move the parentheses enclosing a substituted expression, then such usage would always be meaningful? Jan 19 '15 at 5:09
• @MJD By substitution I meant exactly that: plugging in a formula as if it was a complete logical "block". Jan 19 '15 at 5:12
• @AndreyPortnoy I'm not sure. Jan 19 '15 at 18:08