1
$\begingroup$

A link to the transcript of the manuscript: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html

My questions:

What does Dijkstra mean by:

"Do not introduce priority [precedence] rules that destroy symmetry. I remember how much more pleasant the predicate calculus became to work with after we had decided to give con- and disjunction the same binding power and thus to consider p ∧ q ∨ r an ill-formed formula."?

Specifically: can you illustrate how a precedence rule where conjunction has higher precedence than disjunction would destroy symmetry?

Then, what does he mean by (please note that he uses the "." operator to denote function application):

"As time went on, I learned to appreciate expressions built with operators as a way of avoiding functional notation. We can write the difference a−b as dif.(a, b) or exc.(b, a), where min and exc are functions of an ordered pair. (I believe that the notion of “function of 2 arguments” is now obsolete.) But we can also write the “curried” versions (min. a). b and (sub. b). a in which, for instance, sub is a higher-order function such that sub. b decreases its argument by b (so that sub.(−1) would be the successor function). Functions dif, exc, min and sub are different functions and as soon as the operation of functional composition enters the game, the distinctions are essential. But as long as we don’t do functional composition, the choice between the four options is irrelevant and writing the expression a−b is a lovely way of avoiding being overspecific."?

Specifically: what is the function exc, and how is it that a-b can represent both exc and min? Am I correct in understanding that min is the minimum function?

$\endgroup$
2
$\begingroup$
  1. Conjunction and disjunction are dual, but if conjunction has higher precedence than disjunction, then dual to p ∧ q ∨ r is (p ∨ q) ∧ r != p ∨ q ∧ r.

  2. As you can see exc is dif with its arguments flipped: exc(x, y) = y - x. min is probably short for "minus", not "minimum".

$\endgroup$
  • $\begingroup$ Thank you, it's beginning to click for me now. min is sub with its arguments flipped, and exc is dif with its arguments flipped. However, another question: what do you mean by "dual"? $\endgroup$ – user12330 Dec 24 '13 at 18:11
  • $\begingroup$ @twirlobite See en.wikipedia.org/wiki/… $\endgroup$ – Alexey Romanov Dec 24 '13 at 19:25
  • $\begingroup$ How is the dual of p ∧ q ∨ r then (p ∨ q) ∧ r? Are you missing negation signs? $\endgroup$ – user12330 Dec 24 '13 at 19:47
  • $\begingroup$ No: "In classical logic, the ∧ and ∨ operators are dual in this sense" $\endgroup$ – Alexey Romanov Dec 25 '13 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy