# Associative law with logical connectives **URL:** \ **Category:** Factual Questions\ **Created:** [February 26, 2016, 7:14pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237 "2016-02-26T19:14:48Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![D18](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@D18](https://boards.straightdope.com/u/D18)\ **Post date:** [February 26, 2016, 7:14pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/1 "2016-02-26T19:14:48Z")
As always, not homework; looking for some help with self-study. And as always, I realize this is a very basic question. The associative law when using logical connectives says: P AND (Q AND R) = (P AND Q) AND R So does this mean: P AND (Q AND R) = (P AND Q) AND R = P AND Q AND R The reference I’m using (How to Prove It by Velleman) doesn’t say so explicitly, but I don’t see why it wouldn’t. And I’m assuming that the same would hold true for P OR (Q OR R). ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [February 26, 2016, 7:41pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/2 "2016-02-26T19:41:26Z")
> [@D18](#): > > The associative law when using logical connectives says: > > P AND (Q AND R) = (P AND Q) AND R > > So does this mean: > > P AND (Q AND R) = (P AND Q) AND R = P AND Q AND R Yes: Once you know that P AND (Q AND R) = (P AND Q) AND R, the parentheses are no longer necessary, since P AND Q AND R has the same value regardless of how you interpret/evaluate it. I hope that answers your question; I’m not sure whether I understood it correctly. ---
**Author:** ![D18](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@D18](https://boards.straightdope.com/u/D18)\ **Post date:** [February 26, 2016, 7:51pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/3 "2016-02-26T19:51:57Z")
Yes, thank you, as always. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [February 26, 2016, 9:57pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/4 "2016-02-26T21:57:15Z")
I would answer this as follows. The AND connective (let me write it as &) is defined as a binary connective. Therefore, at the beginning, P & Q & R is undefined. However, once you have that (P & Q) & R = P & (Q & R), it is customary to extend the binary operation to a ternary, quarternary, …, n-ary operation for all finite n. This cannot, of course, be done for non-associative operations. For example, if x stands for the vector cross product in three dimensions, u x v x w is meaningless. You must specify (u x v) x w or u x (v x w). ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [February 26, 2016, 11:14pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/5 "2016-02-26T23:14:04Z")
> [@D18](#): > > … > So does this mean: > > P AND (Q AND R) = (P AND Q) AND R = P AND Q AND R > … I’d spin this part a bit differently. The statement “P AND Q AND R” is operationally ambiguous. You don’t know how to compute the value. The statements “P AND (Q AND R)” and separately “(P AND Q) AND R” are each operationally unambiguous. You \*do \*know how to compute their values. Conveniently the associative principle applies and therefore we know P AND (Q AND R) = (P AND Q) AND R Which implies that when working with “P AND Q AND R” the \*answer \*is well-defined, but the \*process to get to the answer \*is not. That is a dangerously sloppy foundation to build math on. The typical solution is we define a rule which says “inadequately parenthesized expressions are evaluated in this \ order of operator precedences, and between operators of equal precedence in [left-to-right | right-to-left] order.” Once you’ve decided what rule you or your book is using, then, _and only then_, can you compute the value of any expression. Before that you’re just guessing. Sometimes, as with idealized realizations of simple associative operators, all the possible guesses turn out to be the same answer which also happens to be the right answer. But that’s luck, not skill. IOW, don’t count on it. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [February 26, 2016, 11:27pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/6 "2016-02-26T23:27:04Z")
Late add since edit timed out: We just did a thread I can’t now quickly find on some stupid arithmetic “puzzle” making the rounds of Facebook which mixes + - \* / with no parenthesis. All the controversy about the correct answer comes from folks ignoring, forgetting, or never having learned the ambiguity resolution rule I mentioned above. The answer is undefined when there’s no agreement on what the rule _is_. Anybody with any arithmetic skills knows what rule \*ought to be \*applied. All the problems arise when \*ought to be \*just _isn’t_. ---
**Author:** ![Frylock](https://avatars.discourse-cdn.com/v4/letter/f/ce7236/32.png) [@Frylock](https://boards.straightdope.com/u/Frylock)\ **Post date:** [February 26, 2016, 11:54pm UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/7 "2016-02-26T23:54:25Z")
With respect and apologies, I think all the answers given so far are either wrong or unhelpful. OP, _for your purposes_ the answer is “no, because in the version of logic you’re learning, ‘P AND Q AND R’ is not a valid expression.” It can’t be equal to the other two expressions–because it can’t be equal to anything, because in the language of propositional logic (that you’re learning in your class) it doesn’t _mean_ anything. (I am making assumptions about what the predicate logic you’re learning is like, but based on my experience with lots of textbooks etc, I think the assumption is really safe.) There are definitely ways, later on, to formalize the idea of, as was mentioned above, a tertiary (and 4-ary and so on) conjunction. But in your course, you’re learning the binary one. And with the binary one, you have to have those parentheses. On Edit: I missed **LSLGuy** ’s response above. He’s got the right idea IMO. ---
**Author:** ![TATG](https://avatars.discourse-cdn.com/v4/letter/t/50afbb/32.png) [@TATG](https://boards.straightdope.com/u/TATG)\ **Post date:** [February 27, 2016, 2:08am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/8 "2016-02-27T02:08:00Z")
> [@D18](#): > > The reference I’m using (How to Prove It by Velleman) doesn’t say so explicitly, but I don’t see why it wouldn’t. Well, some editions of that book do say so explicitly (from page 21): > [@Velleman](#): > > Notice that because of the associative laws we can leave out parentheses in formulas of the forms P ∧ Q ∧ R and P ∨ Q ∨ R without worrying that the resulting formula will be ambiguous, because the two possible ways of filling in the parentheses lead to equivalent formulas. > [@Frylock](#): > > OP, _for your purposes_ the answer is “no, because in the version of logic you’re learning, ‘P AND Q AND R’ is not a valid expression.” It can’t be equal to the other two expressions–because it can’t be equal to anything, because in the language of propositional logic (that you’re learning in your class) it doesn’t _mean_ anything. Strictly speaking, P ∧ (Q ∧ R) usually won’t be a well formed formula, because it is a conjunction that lacks outer parenthesis. The convention is, I guess, “drop parenthesis when doing so is unambiguous, or if you are in a class, don’t drop them, unless they are the outer-parenthesis or we tell you that you can”. I don’t think Velleman actually defines well formed formula, in any case. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [February 27, 2016, 4:11am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/9 "2016-02-27T04:11:53Z")
> [@TATG](#): > > Well, some editions of that book do say so explicitly (from page 21): Good catch! > [@](#): > > I don’t think Velleman actually defines well formed formula, in any case. Probably because Velleman isn’t presenting an in-depth study of formal logic for its own sake, being more concerned for its use in mathematical reasoning and proofs (I assume, not having read that particular book.) ---
**Author:** ![TATG](https://avatars.discourse-cdn.com/v4/letter/t/50afbb/32.png) [@TATG](https://boards.straightdope.com/u/TATG)\ **Post date:** [February 27, 2016, 4:17am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/10 "2016-02-27T04:17:57Z")
> [@Thudlow\_Boink](#): > > Probably because Velleman isn’t presenting an in-depth study of formal logic for its own sake, being more concerned for its use in mathematical reasoning and proofs (I assume, not having read that particular book.) You assume correctly. ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [February 27, 2016, 6:16am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/11 "2016-02-27T06:16:28Z")
To be sure, everything said in all the above posts about the use of parentheses and order-of-operations in propositional logic, happen to apply exactly the same way to ordinary arithmetic, where the operations of addition and multiplication are involved. Thus, for example, + and \* (using \* for multiply) are binary operators, and a+b+c or a_b_c are well-defined _only_ by the conventions we have about when parentheses can be omitted and implied. Even the above remark about the custom of omitting the outermost parentheses applies similarly. I like to call this the “crosswalk rule”. In California law (and maybe other states), there is an explicit law that a crosswalk exists, whether marked or not, wherever two streets meet at right angles. Thus, the explicit crosswalk markings may be omitted at such intersections, but pedestrians are drivers are expected to know that _there is a crosswalk there_. Similarly, in an expression like 3_a_[sup]2[/sup] + _a_ + 7, the student should understand that _every term has a coefficient_ even if there is no coefficient written. We have the understanding that a coefficient of 1 may be left implied, but there is still a coefficient there! The same with parentheses. We should have an understanding that, in an expression like a+b+c, the parentheses ((a+b)+c) _are there_ even if they aren’t written. Our convention allows us to leave them implied in certain cases, _but the parentheses are there whether you see them or not_. ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [February 27, 2016, 6:33am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/12 "2016-02-27T06:33:06Z")
@ **D18** : Once you get through the associative laws for ∧ and ∨ do you then discuss the distributive laws? (Or do you jump straight into De Morgan’s various Rules?) I wondered once how far you could go with the analogies between conventional arithmetic and propositional logic. In arithmetic, we have commutative and associative laws for both addition and multiplication. In propositional logic, we have commutative and associative laws for both ∧ and ∨ In arithmetic, we then have a _distributive law of multiplication over addition_ which tells us: a \* ( b + c ) = ( a \* b ) + ( a \* c ) Is there a similar distributive law in propositional logic? I don’t remember ever seeing such a thing mentioned in any class or textbook. There is some tendency to see disjunction ( ∨ ) as analogous to addition, and conjunction ( ∧ ) as analogous to multiplication. So is conjunction distributive over disjunction? I.e., is a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ) So I played with it a bit, and figured it out, and discovered the surprise answer. See if you can work it our for yourself! [spoiler]To my surprise, I found that conjunction and disjunction are _each distributive over the other_ (suitable emoticon not found)! Thus, a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ) and also a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) Whoda thunk it?[/spoiler] ---
**Author:** ![D18](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@D18](https://boards.straightdope.com/u/D18)\ **Post date:** [February 29, 2016, 1:42am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/13 "2016-02-29T01:42:30Z")
Interesting discussion, guys! Thank you. Sorry I didn’t get back to the thread till now. **TATG** :smack: As **Thudlow** said, good catch! Apologies for asking a question I could have answered with some more careful reading, but hopefully y’all enjoyed weighing in on the topic regardless. The specific context that lead to the question is I got a line like: (x ∈A ∧ x ∈B) ∧ (x ∈A ∧ x ∈C) So I wasn’t clear on whether I could reduce that to: (x ∈A ∧ x ∈B ∧ x ∈C) using the associative law and the idempotent law. So the answer is yes, I think! 😉 **Senegoid** , yes, Velleman does invoke the distributive law for logical connectives, and one of the exercises is to demonstrate its validity using truth tables and presents it in the way you did. I’ll have to try to figure out how it is derived, as you suggested. ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [February 29, 2016, 2:27am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/14 "2016-02-29T02:27:24Z")
> [@D18](#): > > **Senegoid** , yes, Velleman does invoke the distributive law for logical connectives, and one of the exercises is to demonstrate its validity using truth tables and presents it in the way you did. I’ll have to try to figure out how it is derived, as you suggested. I’m not sure there is any such thing as “how to derive” such a fundamental law, _other_ than simply using truth tables to enumerate all the cases. In arithmetic, the various commutative, associative, and distributive laws are fundamental axioms, meaning that they are not derived from more fundamental rules. I think the same must be true for the commutative, associative, and distributive laws in propositional logic too. ETA: What about De Morgan’s various Rules? Are they fundamental (that is, derivable only by using truth tables to enumerate all possible cases), or are they algebraically derivable from the more fundamental rules? ---
**Author:** ![TATG](https://avatars.discourse-cdn.com/v4/letter/t/50afbb/32.png) [@TATG](https://boards.straightdope.com/u/TATG)\ **Post date:** [February 29, 2016, 3:32am UTC](https://boards.straightdope.com/t/associative-law-with-logical-connectives/747237/15 "2016-02-29T03:32:19Z")
> [@D18](#): > > (x ∈A ∧ x ∈B ∧ x ∈C) using the associative law and the idempotent law. So the answer is yes, I think! 😉 I don’t think that is enough (unless you play fast and loose with the laws). You could do it if you use the commutative law. > [@Senegoid](#): > > I’m not sure there is any such thing as “how to derive” such a fundamental law, _other_ than simply using truth tables to enumerate all the cases. One can derive them from other fundamental laws. (Well, we haven’t said what a fundamental law is. But if you want all the laws of classical propositional logic, you only need a finite set of laws. And there will be many such sets (and sets that are non-redundant in the sense that there have no unnecessary laws.)) > [@Senegoid](#): > > In arithmetic, the various commutative, associative, and distributive laws are fundamental axioms, meaning that they are not derived from more fundamental rules. One can derive associativity (of either multiplication or addition) from a few axioms of PA (none of which are associativity, of course). > [@Senegoid](#): > > ETA: What about De Morgan’s various Rules? Are they fundamental (that is, derivable only by using truth tables to enumerate all possible cases), or are they algebraically derivable from the more fundamental rules? This is a different sense of fundamental. On this definition I’d guess either every tautology is fundamental, or none is.