5
$\begingroup$

I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀). This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?

$\endgroup$
  • 27
    $\begingroup$ I would be very wary of ideas of precedence in first-order logic. Don't think you can write $\forall x\,A\lor B$ or $A\lor B\land C$ and have people understand what you mean. $\endgroup$ – David Richerby Mar 21 at 15:29
  • 7
    $\begingroup$ As far as I can see, precedence of logical connectives and quantifiers can vary from author to author. I tend to write $\forall x.\ (p(x) \implies q(x))$ without parentheses, like several others. Some instead write $(\forall x.\ p(x)) \implies q$ without parentheses, using the opposite precedence. I learned to never take precedence for granted, and sometimes to use a few redundant parentheses to be sure to be understood by everyone. $\endgroup$ – chi Mar 21 at 19:23
  • 4
    $\begingroup$ @Kevin: I hope that's a joke. Prenex normal forms are available only in classical logic, but more importantly, they make statements harder to understand. $\endgroup$ – Andrej Bauer Mar 22 at 7:06
  • 4
    $\begingroup$ @Kevin "There's a formal definition", "there are explicit conventions", and "nobody will be confused" are three very different statements. $\endgroup$ – Raphael Mar 22 at 7:36
  • 1
    $\begingroup$ @chi And I read "$\forall x\,p(x)\Rightarrow q(x)$" as "Oh, god, somebody who thinks there are precedence rules in first-order logic, so I'm going to have to reverse-engineer what they think those rules are." $\endgroup$ – David Richerby Mar 22 at 9:51
3
$\begingroup$

I thought the order of precedence of operators and quantifiers was arbitrary

Certainly the rules of precedence could be set up in different ways, but some ways are more helpful and convenient than others, and there are principled reasons for this.

but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀).

Assuming you mean "strength" as a synonym for "precedence," the reason these three have the same precedence is that these operators are all prefix operators: as you said, their arguments are the next expressions to the right. ¬ takes the next expression as its single argument, and ∀ and ∃ each take the next two expressions. As long as you use only prefix operators, there is never ambiguity as to which operators govern which arguments: There is only one possible answer to "What's the argument of $\neg$ in $\neg \forall x \forall y P(x, y)$?" As such, precedence rules between these prefix operators would be unnecessary.

On the other hand, when you introduce infix operators such as ∧ (or mix in postfix operators), parsing becomes ambiguous without precedence rules or parentheses. For example, $\neg A \land B$ would be ambiguous because $\neg$ is a prefix operator and $\land$ is an infix operator. To fix this, we could just use parentheses, but in a complex expression this becomes cumbersome. Precedence rules, if agreed upon, allow us to be unambiguous with less notation. By following the rule "¬ will have precedence over ∧", we can write and read "$\neg A \land B$" and agree on what it means.

This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?

I think the chain of "leading" here is backwards. Because these three are prefix operators (their arguments are the next 1 or 2 expressions to the right), there's no ambiguity between them and thus no need for precedence rules.

$\endgroup$
  • 1
    $\begingroup$ Thank you, I understand it now! $\endgroup$ – Phil Mar 22 at 10:26
  • 1
    $\begingroup$ As long as you use only prefix operators, there is never ambiguity as to which operators govern which arguments And that's the beauty of Polish notation. $\endgroup$ – sgf Mar 22 at 11:48
17
$\begingroup$

Order of precedence is simply a notional convenience. There is no notion of strength here, just notation. All three operators are unary operators with notation "$\circ\ \cdot$", where $\circ$ denotes the operator symbol $\exists, \forall,\neg$ and $\cdot$ the operand. There can never be any ambiguity in which order to apply these operators: the operator to the right must always be applied to the operand first.

Hence, they have the same precedence among eachother if we consider only those three operators. (Note that there can be ambiguity if the unary operators have different position, e.g. $-x^2$, this could mean either $(-x)^2$ or $-(x^2)$ if there was no precendence between $^2$ and $-$.)

$\endgroup$
  • $\begingroup$ The real question is why you would want the quantifiers to bind so tightly, assuming that most statements will be in prenex normal form and therefore need parentheses. $\endgroup$ – Kevin Mar 21 at 23:11
  • $\begingroup$ Certainly ¬ is unary, but I don't understand why you say that ∃ and ∀ are unary operators. For example, wouldn't you say that $∀x P(x)$ is an expression, but $∀x$ is not? Maybe you just meant to say that they're all prefix operators, and that's why there's no need for precedence rules between them. $\endgroup$ – LarsH Mar 22 at 4:55
  • $\begingroup$ See rule 5 at cs.odu.edu/~cs381/cs381content/logic/pred_logic/construction/… $\endgroup$ – LarsH Mar 22 at 5:22
  • 1
    $\begingroup$ @LarsH Without domain specification, the quantifiers are unary. But even when we include the specification, this is usually in a subscript, e.g. $\forall_{x \in X} P(x)$. In that case, the operator remains unambiguous in this setting. $\endgroup$ – Discrete lizard Mar 22 at 6:44
  • 4
    $\begingroup$ $\forall$ and $\exists$ are not unary operators. They are binders, which is a feature of higher-order syntax. $\endgroup$ – Andrej Bauer Mar 22 at 7:07

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.