7
$\begingroup$

In propositional logic the order of precedence I have found for the logical connectives is

  1. $\neg$
  2. $\land$
  3. $\lor$
  4. $\Rightarrow$
  5. $\Leftrightarrow$

Where do I have to put the exclusive or $\dot\lor$ in the above list?

Note: I also asked this question on this the German forum matheboard.de two days ago. Because I did not get an answer there and because I also did not find an answer in the internet, I also want to ask this question here. I hope, this is okay.

$\endgroup$
3
$\begingroup$

The exclusive-or can be thought of as "compound connective": a connective that involves $\lor$, $\land$ and $\lnot$ in any one of its forms: $$p \dot\lor q \equiv (p \lor q) \land \lnot(p \land q)\equiv (p \lor q)\land (\lnot p \lor \lnot q) \equiv (p \land \lnot q) \lor (\lnot p \land q)$$

Then the table of precedence you've posted covers exclusive-or, implicitly at least, as can be seen in the "expanded" versions of the exclusive-or.

$\endgroup$
  • $\begingroup$ For example: Where do I have to put the parentheses in the statement $A \lor B \,\dot\lor\, C \land D$? $\endgroup$ – Stephan Kulla Aug 7 '14 at 15:35
  • $\begingroup$ That is ambiguous, if I've ever seen ambiguous. $\endgroup$ – Namaste Aug 7 '14 at 15:40
  • 1
    $\begingroup$ Based on the reasoning here, I'd be inclined to suggest it's last in your list, following the biconditional, since it can be thought of as the negation of the biconditional. So for your example, $(A \lor B)\dot\lor(C\land D)$. But this is just speculation. $\endgroup$ – Namaste Aug 7 '14 at 15:51
  • $\begingroup$ Would you agree, if we say, that there is no clear answer to this question? $\endgroup$ – Stephan Kulla Aug 7 '14 at 15:53
  • $\begingroup$ Yes, I'd agree with that!. $\endgroup$ – Namaste Aug 7 '14 at 15:54
2
$\begingroup$

'Exclusive or' ($\;\mathop{\dot \lor}\;$) is the negation of equivalence ($\;\Leftrightarrow\;$): $$ (p \mathop{\dot \lor} q) \;\Leftrightarrow\; \lnot(p \Leftrightarrow q) $$ Therefore personally I prefer to write equivalence as $\;\equiv\;$ and 'exclusive or' as $\;\not\equiv\;$, to make the duality clear in the symbols.

And when using those symbols, of course, I prefer to use the same precedence for both operators, and write e.g. $\;A \lor B \;\not\equiv\; C \land D\;$ without any parentheses.

Finally, note that not only is $\;\equiv\;$ associative, but also $\;\not\equiv\;$ is associative, and they are even mutually associative, so that we can write: $$ p \not\equiv q \;\equiv\; \lnot(p \equiv q) $$ without ambiguity.


On the same topic, I also dislike the precedence difference between $\;\land\;$ and $\;\lor\;$, as shown in your table. One reason is the strong duality between both (which is hidden even more in boolean algebra notation). But more importantly, a convention which makes $\;A \land B \lor C\;$ different from $\;A \land (B \lor C)\;$ can only lead to confusion, and instead it should be our goal as math writers to make the job as easy as possible on the math readers.

Therefore personally I never write $\;A \land B \lor C\;$, but instead always $\;(A \land B) \lor C\;$.

All of the above I did not invent myself, but I learned it from Dijkstra/Feijen/Scholten/Gries/Schneider. See the article E.W. Dijkstra, "The notational conventions I adopted, and why" (on-line), and also the books E.W. Dijkstra and C.S. Scholten, "Predicate Calculus and Program Semantics" and D. Gries and F.B. Schneider, "A Logical Approach to Discrete Math".


And all this goes to show that precedence is a convention: one can get used to any convention, there are arguments for and against each one, and you don't "have to" put every operator in a specific place in the precedence list.

In case of doubt for a specific operator, you can always use parentheses so that the reader does not have to worry. Dijkstra also taught me to use more whitespace around lower precedence operators, as in $$ p \;\equiv\; q \;\equiv\; p \land q \;\equiv\; p \lor q $$ That also helps the reader in parsing, by suggesting the precedence.

$\endgroup$
  • $\begingroup$ I like brackets as well. However note when we use the + and notation for or and and, it becomes clear that we can do algebraic tricks. e.g. a•b + a•c ≡ a ( b + c ), just like regular algebra. $\endgroup$ – ctrl-alt-delor Nov 5 '15 at 21:47
  • $\begingroup$ @richard Yes. But note that in that case we also have $\;(a+b) • (a+c) \;\equiv\; a + (b•c)\;$ which is really unclear and counter-intuitive, which for me shows that using $\;+\;$ and $\;•\;$ for 'or' and 'and' is more trouble than it seems worth at first sight. $\endgroup$ – MarnixKlooster ReinstateMonica Nov 5 '15 at 22:10
  • $\begingroup$ Sorry my example was bad, I realised as I slept (following posting it). What I should have said is 1+1=2=1, 1+0 =1, 0+0=0, 0•0=0, 0•1=0, 1•1=1. Except for 2=1 it is like regular algebra. $\endgroup$ – ctrl-alt-delor Nov 6 '15 at 21:55

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.