Associativity of logical connectives

Question

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator?

The implies operator ($\rightarrow$) does not have the associative property. That means that $(p \rightarrow q) \rightarrow r$ is not equivalent to $p \rightarrow (q \rightarrow r)$. Because of that, the question comes op how $p \rightarrow q \rightarrow r$ should be interpreted.

The proposition $p \rightarrow q \rightarrow r$ can be defined in multiple ways that make sense:

• $(p \rightarrow q) \rightarrow r$ (left associativity)
• $p \rightarrow (q \rightarrow r)$ (right associativity)
• $(p \rightarrow q) \land (q \rightarrow r)$

Which one of these definitions is used?

I could not locate any book/webpage that mentions about associativity of logical operators in discrete mathematics.

Please also cite the reference (book/reliable webpage) that you use to answer my question (as I'm planning to add this to wikipedia page about 'logical connectives').

Thanks.

PS: I got this question when I saw this problem: Check if following compound proposition is tautology or not:

$$ \mathrm{p} \leftrightarrow (\mathrm{q} \wedge \mathrm{r}) \rightarrow \neg\mathrm{r} \rightarrow \neg\mathrm{p}$$

Answer 1

When you enter $p \Rightarrow q \Rightarrow r$ in Mathematica (with p \[Implies] q \[Implies] r), it displays $p \Rightarrow (q \Rightarrow r)$.

That makes it plausible that the $\rightarrow$ operator is generally accepted as right-associative.

Answer 2

Some logical operators are associative: both $\wedge$ and $\vee$ are associative, as a simple check of truth tables verifies. Likewise, the biconditional $\leftrightarrow$ is associative.

However, the implication $\rightarrow$ is not associative. Compare $(p\rightarrow q)\rightarrow r$ and $p\rightarrow(q\rightarrow r)$. If all of $p$, $q$, and $r$ are false, then $p\rightarrow (q\rightarrow r)$ is true, because the antecedent is false; but $(p\rightarrow q\rightarrow r$ is false, because $r$ is false, but $p\rightarrow q$ is true. They also disagree with $p$ and $r$ are false but $q$ is true: then $p\rightarrow(q\rightarrow r)$ is true because the antecedent is false, but $(p\rightarrow q)$ is true, $r$ false, so $(p\rightarrow q)\rightarrow r$ is false.

Since they take different values at some truth assignments, the two propositions are not equivalent, so $\to$ is not associative.

Answer 3

The proposition $p \rightarrow q \rightarrow r$ can be defined in multiple ways that make sense:

• $(p \rightarrow q) \rightarrow r$ (left associativity)
• $p \rightarrow (q \rightarrow r)$ (right associativity)
• $(p \rightarrow q) \land (q \rightarrow r)$

Which one of these definitions is used?

1. A logician would read $$p \rightarrow q \rightarrow r$$ (in the absence of explicit parentheses) as $$p \rightarrow (q \rightarrow r);$$ however, in informal logic (including mathematics), $$p \Rightarrow q \Rightarrow r$$ is commonly read as $$(p \Rightarrow q) \;\text{ and }\; (q \Rightarrow r),$$ which isn't logically equivalent to $$p \Rightarrow (q \Rightarrow r).$$

2. On the other hand, $$p \Leftrightarrow q \Leftrightarrow r$$ is commonly read as $$(p \Leftrightarrow q) \;\text{ and }\; (q \Leftrightarrow r),$$ whereas a logician would read $$p \leftrightarrow q \leftrightarrow r$$ as $$p \leftrightarrow (q \leftrightarrow r),$$ which isn't logically equivalent to $$(p \leftrightarrow q) \;\text{ and }\; (q \leftrightarrow r).$$

   To wit: $$(p \Leftrightarrow q) \;\text{ and }\; (q \Leftrightarrow r)$$ asserts that $p,q,r$ all have the same truth value, while the truth assignment $(p,q,r)=$ (false, false, true) is actually admitted by both $$p \Leftrightarrow ( q \Leftrightarrow r)$$ and $$(p \Leftrightarrow q) \Leftrightarrow r.$$

Answer 4

Counter example: Suppose p, q, r are all false. Then (p=>q)=>r is false, and p=>(q=>r) is true.

Answer 5

I think $(p \rightarrow q) \land (q \rightarrow r)$ is the most useful interpretation of $p \rightarrow q \rightarrow r$. It corresponds to natural language when we say something like "A implies B, which implies C".

A related convention is $x \lt y \lt z$ meaning $x \lt y \land y \lt z$. The same three cases arise when $\lt$ is treated as a function yielding a boolean integer like in many programming languages.

Answer 6

Presumably $p \Rightarrow q \Rightarrow r$ means $(p \Rightarrow q) \Rightarrow r$, since the other option $p \Rightarrow (q \Rightarrow r)$ is equivalent to $(p \land q) \Rightarrow r$. That's similar to the laws of powering $p^{q^r} = p^{\left(q^r\right)}$ since $\left(p^q\right)^r = p^{qr}$.

Best practice is just not to put the reader into a state of ambiguity. Some mathematical writers dislike punctuation, but that's not an excuse for the rest of us to take advantage of it.

Since $\land$ and $\lor$ are associative, there's no ambiguity there, and it makes sense not to put parentheses. Sometimes one even thinks of an expression like $p \land q \land r$ as a conjunction $\land(p,q,r)$.

The latter convention is the case in proof complexity when one is measuring the depth of a formula. If a first-order quantified formula is translated to propositional logic, then $\forall$ will correspond to a conjunction, and $\exists$ to a disjunction; it makes sense not to penalize the formula for the size of the underlying universe.

An even more daring "convention" is having infinite conjunctions/disjunctions - this wouldn't make sense at all for $\Rightarrow$. So your textbook authors are at fault (even though having the $\Leftrightarrow$ bind weakly is a reasonable convention if not overused).

Answer 7

What basic principle(s) do you have when doing logic from scratch without any formation rules? I'll propose one which I think unobjectionable.

1. Try to keep things as simple as reasonable or make things as simple as reasonable.

When you work or play around with conditionals you probably will want to find the antecedent of the conditional so that you can detach something. p→(q→r) has a simpler antecedent than (p→q)→r, and consequently given a pseudo-formula it comes as simpler to find an antecedent of some form "p" in your axiom set than to find some form (p→q) in your axiom set to detach something from (p→q)→r. Consequently, p→(q→r) makes more sense than (p→q)→r.

Answer 8

Note that since it's not a binary operator, but a binary relation, associativity does not always yield the same semantics, of reducing composition pairings to a queue. Suppose $p \implies q \implies r.$ But if $r$ is false, $p \implies q$ being true does not imply $r$ is true. Likewise, $p \implies q$ can be false while $p \implies (r \implies q)$ is true, so $(p \implies (q \implies r)) \implies (p \implies q), (q \implies r)$ is not necessarily true. Finally, if $(p \implies q) \implies r$, and $p \implies (q \implies r),$ and $p \equiv F,$ we have no reason to think $q \implies r$, and $p \implies q$ can still be true, which would mean $r$ is true regardless of whether $p \implies r$.