Why do ¬, ∀ and ∃ have the same precedence?Why 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
Lay out the Carpet
How do I go from 300 unfinished/half written blog posts, to published posts?
How easy is it to start Magic from scratch?
Where does the Z80 processor start executing from?
How to check is there any negative term in a large list?
Would a high gravity rocky planet be guaranteed to have an atmosphere?
Escape a backup date in a file name
What can we do to stop prior company from asking us questions?
System.debug(JSON.Serialize(o)) Not longer shows full string
Two monoidal structures and copowering
What does "I’d sit this one out, Cap," imply or mean in the context?
Sort a list by elements of another list
How does buying out courses with grant money work?
when is out of tune ok?
Sequence of Tenses: Translating the subjunctive
How does Loki do this?
How did Doctor Strange see the winning outcome in Avengers: Infinity War?
Avoiding estate tax by giving multiple gifts
Pole-zeros of a real-valued causal FIR system
Valid Badminton Score?
Is expanding the research of a group into machine learning as a PhD student risky?
Is oxalic acid dihydrate considered a primary acid standard in analytical chemistry?
India just shot down a satellite from the ground. At what altitude range is the resulting debris field?
What is paid subscription needed for in Mortal Kombat 11?
Why do ¬, ∀ and ∃ have the same precedence?
Why 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
edited Mar 22 at 7:35
Raphael♦
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
edited Mar 22 at 7:35
Raphael♦
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
26
$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
3
$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
edited Mar 22 at 7:35
Raphael♦
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 22 at 7:35
Raphael♦
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 22 at 7:35
Raphael♦
58k24143317
edited Mar 22 at 7:35
Raphael♦
58k24143317
edited Mar 22 at 7:35
Raphael♦
58k24143317
58k24143317
asked Mar 21 at 15:00
PhilPhil
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 21 at 15:00
PhilPhil
284
asked Mar 21 at 15:00
PhilPhil
284
284
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
26
$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
3
$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
26
$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
3
$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
26
26
$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
3
3
$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.
answered Mar 22 at 5:15
LarsHLarsH
1627
$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 $-$.)
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
$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
);
);
Phil is a new contributor. Be nice, and check out our Code of Conduct.
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.
answered Mar 22 at 5:15
LarsHLarsH
1627
$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.
answered Mar 22 at 5:15
LarsHLarsH
1627
$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.
answered Mar 22 at 5:15
LarsHLarsH
1627
$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.
answered Mar 22 at 5:15
LarsHLarsH
1627
edited Mar 22 at 6:13
answered Mar 22 at 5:15
LarsHLarsH
1627
answered Mar 22 at 5:15
LarsHLarsH
1627
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 $-$.)
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
$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 $-$.)
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
$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 $-$.)
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
$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 $-$.)
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
edited Mar 21 at 17:49
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
answered Mar 21 at 15:14
Discrete lizard♦Discrete lizard
4,44011537
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
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
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
26
$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
3
$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