Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

To parenthesize, or not to parenthesize (that is the question)

  1. Feb 12, 2005 #1

    honestrosewater

    User Avatar
    Gold Member

    I'm trying to find the clearest, most efficient notation for predicate logic. I especially want to avoid being bogged down in parentheses or other grouping symbols, but, of course, not at the expense of clarity or consistency. Has anyone found a happy medium?

    For example, in writing the following, I spent a ridiculous amount of time double-checking my parentheses.

    [tex]\exists ! x (Px) \equiv (\exists x (Px)) \wedge (\forall x \forall y ((Px \wedge Py) \implies x=y))[/tex]

    Negate the whole statement twice [tex](\neg (\neg p) \equiv p)[/tex]:
    [tex]\neg (\neg (\exists x (Px)) \wedge (\forall x \forall y ((Px \wedge Py) \implies x=y))))[/tex]

    Distribute the inner negation [tex](\neg (p \wedge q) \equiv \neg p \vee \neg q)[/tex]:
    [tex]\neg (\neg (\exists x (Px)) \vee \neg(\forall x \forall y ((Px \wedge Py) \implies x=y)))[/tex]

    Substitute the negated existential [tex](\neg (\exists x (Px)) \equiv \forall x (\neg Px))[/tex]:
    [tex]\neg (\forall x (\neg Px) \vee \neg(\forall x \forall y ((Px \wedge Py) \implies x=y)))[/tex]
     
  2. jcsd
  3. Feb 12, 2005 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you are encountering a predicament some of us have also done. namely we began the study of predicate logic, and propositional calculus and symbolic logic in general, as a means of clarifying the truth of statements. For this lots of parentheses are needed.

    Then at some point we found that human beings are not greatly aided in understanding statements merely because those statements are totally precise. I.e. they can still be puzzlingly unclear, even if entirely correct.

    Thus eventually, in communication of mathematics to humans, one stops using much predicate calculus, and attempts the classical art of writing words that convey ones meaning more strikingly.


    But you are no doubt still fascinated by this logical exercise, and perhaps for some reason, such as the desire to comunicate with machines. But I offer this remark, from experience.

    It was 1960, as a Freshman at Harvard, when I first noted, with some disdain, that the grader could not realize that the arguemnts in my homework were actually correct, if i wrote the statements out in predicate calculus. It is too hard to follow for many people.

    So I quit, and seldom use it today, although one would often dearly like to be able to express say continuity vs uniform continuity of a function this way in a class.


    another instance from experience comes from having student homework graded by machine. The student often thinks the machine is wrong, but the machine in my experience never was. Rather the stduent had always left out a parentheses, which the human grader understands and supplies mentally.

    For me personally, your expression should have a parentheses right at the beginning, surrounding the existentially quantified expression. Leaving it out makes the statement harder to follow at least for me.
     
    Last edited: Feb 12, 2005
  4. Feb 12, 2005 #3

    honestrosewater

    User Avatar
    Gold Member

    I think (blank) spaces should be used as grouping symbols, just as they are in this sentence. I'm not entirely sure how that would work (great, new project), but I'd bet it's already been done.
    Thanks for the advice.
    I'm not sure how to say this- the distinction between logic and math gets harder to see everyday- I guess you could say I'm interested in formal systems and interpretations. That is, I'm mostly interested in math as a language. I'm especially interested in the relationship between the what and how of meaning, and I expect to be spending lots of time with logics.
    Yeah, I'm missing a left parenthesis "(" after the second negation in the second statement.
    Where did you learn that notation? I've seen the same thing said in at least a dozen different ways, and I haven't used any notation enough to guess at the reasoning behind the choice of any of them.
     
  5. Feb 12, 2005 #4

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    well i read principles of mathematics in high school, then articles by various logicians, such as in world of mathematics, then studied out of willard van orman quine's books as a college freshman, then read loomis advanced calculus, audited lectures of paul cohen, perused his book on the continuum mhypothesis, then much later taught out of patrick suppes book. i have also perused the huge tome of russell and whitehead, which really turned me off.

    they spend as i recall hundreds of pages on such matters as whether 0 = 1 or 1+1 = 2.

    if the distinction between math and logic seems vague to you, then may i suggest you are not a mathematician but a logician, which you seem to confirm. to a mathematician, few mathematical questions of significance have much to do with logic.

    logical question to be sure are difficult, but they have a different focus, and a different appeal. actually i know a very strong number theorist who is interested in some difficult matters of computability, related to logic.

    as to your last question, doesn't it just seem uniform practice to use parentheses on existential quantifiers if you use them on universal ones?
     
    Last edited: Feb 12, 2005
  6. Feb 12, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ack, I'm turning into a logician. :cry:
     
  7. Feb 12, 2005 #6

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you are just broad minded.
     
  8. Feb 12, 2005 #7

    honestrosewater

    User Avatar
    Gold Member

    I guess I'll have to try to scrounge up a copy of that principles of math book you keep recommending. :smile: I presume you're talking about Quine's "Mathematical Logic"- I only read parts of that. I read his "Elementary Logic" and was pretty bored (though that's not necessarily his fault). I do love how he only uses negation, conjunction, and the existential quantifier. I didn't like Suppes either, from the little I read of it. I like Machover (the book I'm waiting for- have you read it?). I'll use Copi's "Intro to Logic" too, considering its reputation.
    There's a tiny book on PDEs-"Intro to PDEs" by Arne Broman, IIRC- that I "read" -though I barely understood a word of it- just because it was so concise, well-organized, and all-around beeyoutiful.
    I would write [tex]\forall x (Px)[/tex] if it were alone. I add the parentheses for compound propositions. Eh, I guess [tex]\exists !x (Px)[/tex] isn't really alone. It's relatively alone, er, whatever- I'm experimenting.

    What would you say is the difference between logic and math? What is it about a question that makes you say, "Yay, that's a math question" vs. "No thanks, that's a logic question"?

    BTW, I agree- logicians are broader-minded than mathematicians. :tongue2:
    Edit: Or did you mean he's always thinking about broads? Or that he thinks like a broad?
     
    Last edited: Feb 13, 2005
  9. Feb 13, 2005 #8

    honestrosewater

    User Avatar
    Gold Member

    In case anyone cares, if there's a way to use blank spaces as grouping symbols, it isn't obvious. However, you can use overlining or underlining and hash marks; the former for grouping, the latter for negation. The lines nest by stacking. For instance,
    [tex][(p \vee q) \Leftrightarrow \neg (\neg p \wedge \neg q)][/tex] would look something like
    ----------------
    -----_____--+--
    -___-____+___+
    p V q <=> p ^ q
    but not so fugly. I'll test it out for a while (on paper) and see how it compares. I've decided to embrace grouping symbols now anyway.
     
  10. Feb 13, 2005 #9
    You can always generate syntax trees as we do for expressions. It also can be used to develop an efficient system to parse a predicate logic expression. (Syntax trees are used at compiler levels to parse expression trees) I believe this should be feasible and should be clear enough, more-so since the precedence and associativity for the logic operators are defined just as the for arithmetic operators.

    -- AI
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: To parenthesize, or not to parenthesize (that is the question)
  1. A question (Replies: 3)

  2. A question (Replies: 8)

  3. A question (Replies: 5)

  4. A question (Replies: 8)

Loading...