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

[honestrosewater]

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.

$$\exists ! x (Px) \equiv (\exists x (Px)) \wedge (\forall x \forall y ((Px \wedge Py) \implies x=y))$$

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

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

Substitute the negated existential $$(\neg (\exists x (Px)) \equiv \forall x (\neg Px))$$:
$$\neg (\forall x (\neg Px) \vee \neg(\forall x \forall y ((Px \wedge Py) \implies x=y)))$$

 

[mathwonk]

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.

 

[honestrosewater]

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.

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.

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.

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.

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.

Yeah, I'm missing a left parenthesis "(" after the second negation in the second statement.

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.

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.

 

[mathwonk]

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?

 

[Hurkyl]

Ack, I'm turning into a logician.

 

[mathwonk]

you are just broad minded.

 

[honestrosewater]

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.

I guess I'll have to try to scrounge up a copy of that principles of math book you keep recommending. 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.

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?

I would write $$\forall x (Px)$$ if it were alone. I add the parentheses for compound propositions. Eh, I guess $$\exists !x (Px)$$ 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?

 

[honestrosewater]

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,
$$[(p \vee q) \Leftrightarrow \neg (\neg p \wedge \neg q)]$$ 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.

 

[TenaliRaman]

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