2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Yes; $(A∧B∧C)$ is an abbreviation for $(A∧(B∧C))$ or, equivalently : $((A∧B)∧C))$, as your proof shows. $\endgroup$ Jan 17 '15 at 10:15
  • $\begingroup$ No, take a look at the formation rules. Also, the rule of uniform substitution would fail if (A∧B∧C) were meaningful. $\endgroup$ Jan 17 '15 at 19:25
  • $\begingroup$ @DougSpoonwood Could you please elaborate on that? Thank you. $\endgroup$ Jan 19 '15 at 3:12
  • $\begingroup$ @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. $\endgroup$ Jan 19 '15 at 3:35
  • $\begingroup$ 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. $\endgroup$ Jan 19 '15 at 3:57
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 19 '15 at 4:03
  • $\begingroup$ This answer combined with Doug Spoonwood's note that the only logical operator used should be ($\land$ XOR $\lor$) answers my question completely. $\endgroup$ Jan 19 '15 at 5:19
  • $\begingroup$ @Doug Nowhere did I imply that expressions combining $\lor$ and $\land$ without parentheses are meaningful. $\endgroup$
    – Lord_Farin
    Jan 19 '15 at 6:07
-2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – MJD
    Jan 19 '15 at 4:42
  • $\begingroup$ 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? $\endgroup$ Jan 19 '15 at 5:09
  • $\begingroup$ @MJD By substitution I meant exactly that: plugging in a formula as if it was a complete logical "block". $\endgroup$ Jan 19 '15 at 5:12
  • $\begingroup$ @AndreyPortnoy I'm not sure. $\endgroup$ Jan 19 '15 at 18:08

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.