Why do ¬, ∀ and ∃ have the same precedence? The Next CEO of Stack OverflowWhy do the sequent calculus NOT left and NOT right rules work?grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)Operator precedence in propositional logicSemantic natural language processing - from texts to logical expressions? Universal knowledge base?Precedence of satisfiability operatorWhy does soundness imply consistency?Can proof by contradiction work without the law of excluded middle?SAT Solver Front-End: Strategy to order QuantifiersTrying to understand interpretation and denotation in FOLUnderstanding a Single Step in the Model Checking Algorithm
How can I run a deployer module after the commit?
How does a dynamic QR code work?
magento 2 Incompatible argument type: Required type: MagentoFrameworkRegistry
Obtaining database information and values in extended properties
Best way to load image from list python script
Mathematica command that allows it to read my intentions
Car headlights in a world without electricity
How seriously should I take size and weight limits of hand luggage?
How to use `glossaries` together with `ProvidesPackage`
Do Iron Man suits sport waste management systems?
Is it possible to create a QR code using text?
How to coordinate airplane tickets?
Horrendous Scope of Text
What is the difference between NTP and validity in Smith's "Logic: The Laws of Truth"?
That's an odd coin - I wonder why
Why do I get "Binary file matches" with grep -I?
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
How to ignore Spotlight index for a volume contain another macOS
How to install cross-compiler on Ubuntu 18.04?
Avoiding the "not like other girls" trope?
Can compressed videos be decoded back to their uncompresed original format?
How badly should I try to prevent a user from XSSing themselves?
Does int main() need a declaration on C++?
Find the majority element, which appears more than half the time
Why do ¬, ∀ and ∃ have the same precedence?
The Next CEO of Stack OverflowWhy do the sequent calculus NOT left and NOT right rules work?grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)Operator precedence in propositional logicSemantic natural language processing - from texts to logical expressions? Universal knowledge base?Precedence of satisfiability operatorWhy does soundness imply consistency?Can proof by contradiction work without the law of excluded middle?SAT Solver Front-End: Strategy to order QuantifiersTrying to understand interpretation and denotation in FOLUnderstanding a Single Step in the Model Checking Algorithm
$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?
logic first-order-logic notation
$endgroup$
|
show 4 more comments
$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?
logic first-order-logic notation
$endgroup$
27
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland 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
|
show 4 more comments
$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?
logic first-order-logic notation
$endgroup$
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?
logic first-order-logic notation
logic first-order-logic notation
edited Mar 22 at 7:35
Raphael♦
58k24143317
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
284
27
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland 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
|
show 4 more comments
27
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland 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
27
27
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland C$ and have people understand what you mean.
$endgroup$
– David Richerby
Mar 21 at 15:29
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland C$ and have people understand what you mean.
$endgroup$
– David Richerby
Mar 21 at 15:29
7
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
$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
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
$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
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
$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
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
$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
|
show 4 more comments
2 Answers
2
active
oldest
votes
$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
add a comment |
$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
|
show 4 more comments
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105880%2fwhy-do-%25c2%25ac-%25e2%2588%2580-and-%25e2%2588%2583-have-the-same-precedence%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
add a comment |
$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
add a comment |
$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$
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.
edited Mar 22 at 6:13
answered Mar 22 at 5:15
LarsHLarsH
1627
1627
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
add a comment |
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
1
1
$begingroup$
Thank you, I understand it now!
$endgroup$
– Phil
Mar 22 at 10:26
$begingroup$
Thank you, I understand it now!
$endgroup$
– Phil
Mar 22 at 10:26
1
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
$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
add a comment |
$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
|
show 4 more comments
$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
|
show 4 more comments
$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$
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 $-$.)
edited Mar 21 at 17:49
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
4,44011537
$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
|
show 4 more comments
$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
$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$
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$
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
$begingroup$
See rule 5 at cs.odu.edu/~cs381/cs381content/logic/pred_logic/construction/…
$endgroup$
– LarsH
Mar 22 at 5:22
1
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
$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
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
$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
|
show 4 more comments
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105880%2fwhy-do-%25c2%25ac-%25e2%2588%2580-and-%25e2%2588%2583-have-the-same-precedence%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
27
$begingroup$
I would be very wary of ideas of precedence in first-order logic. Don't think you can write $forall x,Alor B$ or $Alor Bland 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