Associativity and De Morgan's for more than 2 literals

Question

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.

Answer 1

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

Answer 2

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.