Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my discrete mathematics class we wrote down the truth table for some Boolean functions and in that table they go in the following order:

¬, ∧, ∨, →, ~, ⊕, |, ↓

So, I assumed that this is the order I need to use when evaluating formulas, and all was fine until there appeared an expression (x ⊕ yz) . Normally, I would take conjunction of y and z, then apply exclusive or. However, when I type this into WolframAlpha, it always takes "xor" first, and only then conjunction no matter what the order is.

I really hope someone could give me the right precedence. I'm almost sure that first 4 operations are in the correct order, but what about exclusive or, Sheffer stroke, and Pierce arrow?

Thank you!

EDIT:

I looked through my notes, and in fact we agreed on the order in the class, I can't believe I missed that...Anyway, the order is as follows:

  1. ¬
  2. ∧, |, ↓
  3. ⊕, ~

In groups 2 and 5 I guess the associativity is from left to right.

Maybe this will help someone.

share|improve this question
    
I'm guessing Wolfram|Alpha is following Mathematica's conventions. I don't know about its precedence table though. Maybe you could check out mathematica.SE –  user2468 Apr 5 '12 at 21:15
    
Operation precedence is not a needed concept. One might argue that the correct precedence is none at all. Just write things in Polish (prefix), or Reverse Polish (postfix) notation. It's not like you'd stop doing Boolean Algebra if you did this. As Henning Makholm alludes to in his answer, operation precedence varies significantly between different contexts. So, who's the author using the symbols, and what have they indicated about how they use symbols? –  Doug Spoonwood Apr 6 '12 at 13:55
1  
@DougSpoonwood Thank you for asking "what have they indicated about how they use symbols?" This made me go through my notes again, and it turns out we did write down the order! See my edit. –  user825089 Apr 6 '12 at 16:35
add comment

1 Answer

up vote 2 down vote accepted

There is no really settled consensus about what the precedence of these operation symbols ought to be. Mostly that is considered to be not a methematical question, but purely one of presentation -- how many parentheses can you omit and still have a reasonable expectation that your reader will understand the same formula you thought you were writing?

When one uses multiplicative notation for conjunction (that is, just writing the conjuncts next to each other with no punctuation) it is natural to treat is as binding stronger than the operations that are written with symbols -- including $\neg$, so $\neg ab$ almost always means $\neg(a\land b)$. (When negation is written with an overline, its scope is of course unambiguous).

It is not unusual to extend this to conjunction written with an explicit $\land$ at least as far as the interaction between $\land$ and other binary operations go (but $\neg a \land b$ always means $(\neg a)\land b$). However there are also many authors who don't want to depend on such conventions and insist on disambiguating parentheses whenever $\land$ and $\lor$ are used together).

Since $\to$ is not associative, it presents special problems. In computer science and fields influenced by it, $a\to b\to c$ almost always meas $a\to (b\to c)$, but there are also logicians who write $a\to b\to c$ for $(a\to b)\to c$ -- perhaps reasoning that $a\to(b\to c)$ could equivalently be written as $a\land b \to c$ -- and yet others who prefer all nested implications to be fully parenthesized.

I wouldn't depend on any particular conventions for $\sim$, $\oplus$, $|$ or $\downarrow$, or among these and $\to$ or $\lor$. Err in the direction of too many parentheses. If is uncommon to have see formulas that contain more than one of these anyway, so it's no great burden to always parenthesize them.

Biimplication, when written $\leftrightarrow$, usually has the lowest precedence of all. I assume that what you write $\sim$ is the same operator, but I wouldn't bet on the convention extending to there.

Programming languages and other pieces of software that have to make some sense of formulas typed by a user (such as Wolfram Alpha) will usually have some particular rules that they use to unravel unparenthesized expressions, but it is not usually worth the trouble trying to memorize them -- they might well be different in the next programming language over anyway.

share|improve this answer
1  
To perhaps clarify things here, → doesn't pose special problems just because it's not associative, but because it usually happens in a system which has more associative than non-associative operations, or in a system where the authors (implicitly) put more weight on associative operations than non-associative operations (a phrase like "not both" for the Sheffer stroke at least seems to imply a use of conjunction). If we considered operation precedence in a system with 6 operations, only one of which associated, a non-associative operation doesn't present any special problems. –  Doug Spoonwood Apr 6 '12 at 14:14
    
@Henning Makholm Thank you for your input. In fact, I never had any problems with implication and equivalence, because the disambiguating brackets were always there. This is the first time I wasn't sure about. However, thanks to Doug Spoonwood, I looked through my notes again, and found the order we agreed upon in my class. But as you said, there probably isn't any convention though. –  user825089 Apr 6 '12 at 16:42
    
Yet it still remains a mystery for me, why not make one unified rule. Mathematics is pretty formal discipline, I would say. It would be just easier for everyone. And if we need to alter the "execution flow", we should just use brackets as in ordinary arithmetic. –  user825089 Apr 6 '12 at 16:46
1  
@user825089 I don't think it practical to make one unified rule, because there exist several distinct mathematical and logical traditions (perhaps "schools" serves as a better term here), who already have their conventions. There doesn't seem any sufficient reason to prefer one convention over another, and even if one unique convention existed, we could easily come with another one which basically functions in the same way. Different authors have used different symbols for logical connectives (K, ^, &, AND all for logical conjunction). The difference in notation here does not affect formality. –  Doug Spoonwood Apr 6 '12 at 18:03
2  
Mathematical formality does not arise because of uniformity. Formality happens because of adherence to the rules and axioms given, which definitively do allow for variation (or "diversity" if you prefer that term). –  Doug Spoonwood Apr 6 '12 at 18:06
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.