21
$\begingroup$

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

  • 0
    The compound proposition in plaintext above in better typesetted form is here: http://mathbin.net/560262010-11-28
  • 0
    I've edited the proposition so it looks exactly like the one you link at. Note the difference between `\Rightarrow` ($\Rightarrow$) and `\rightarrow` ($\rightarrow$). The latter is the usual connective, the former is "logical implication"; as I understand it, people who work in Mathematical Logic make a clear distinction between the two (and get endlessly annoyed by those who don't...)2010-11-28
  • 2
    @Arturo: we certainly care about the difference between the two, but the notation varies greatly from one author to another, so that $\Rightarrow$ is often used as a connective. In the most common setting of first-order logic, Goedel's completeness theorem implies that it's pretty safe to ignore the difference.2010-11-29
  • 0
    @Arturo: The book that I'm currently reading (Kenneth Rosen's 'Discrete mathematics and it's applications' (6e) uses $\rightarrow$ to represent logical implication.2010-11-29
  • 0
    @CarlMummert I never realized the two symbols are not the same, what is the difference in their meaning?2017-03-16
  • 0
    @Ovi: some authors use $\rightarrow$ for the logical connective (which could appear in a formula) and $\Rightarrow$ for logical implication at the meta level. Of course, in first-order logic, for sentences $\phi$ and $\psi$, we have $\phi \models \psi$ if and only if $\phi \vdash \psi$ if and only if $\vdash \phi \to \psi$, so in that notation $\phi \Rightarrow \psi$ is equivalent to $\phi \to \psi$ being logically valid.2017-03-16

7 Answers 7