您在這裡

A hint on deciphering formulas' meanings

16 六月, 2015 - 15:42
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

Some formulas can get pretty hairy: ∀x :(∃y :(∀z : (likes (x, y)¬likes (y, z)))). The zeroth step is to take a breath, and read this in English: for every x, there's some y such that for every z, x likes y but y doesn't like z. Even so, how do we approach getting a handle on what this means? Given an interpretation, how do we know it's true?

The top-down way would be to read this formula left-to-right. Is the whole formula true? Well, it's only true if, for every possible value of x, some smaller formula is true (namely, " there exists a y such that forall z, likes (x, y) and ¬likes (y, z). "). (This is a formula with x free, that is, it's a statement about x.) And is that formula true? Well, precisely when we can find some y such that ... (and so on). This direct approach is hard to keep inside your head all at once.

Most people prefer approaching the problems in a bottom-up manner (or if you prefer, right-to-left or inside-out): First consider at the small inner bits alone, figure out what they mean, and only then figure out how they relate.

  • What does the innermost formula likes (x, y) ∧¬likes (y, z) mean, in English? That's not so bad: x likes y, and y dislikes z. A statement about three people called x, y, z.
  • Working outward, what does ∀z : (likes (x, y) ∧¬likes (y, z)) mean? Ah, not so bad either: x likes y, and y dislikes everybody. 6
  • Keep on going: ∃y :(∀z : (likes (x, y) ∧¬likes (y, z))) becomes "x likes some misanthrope".
  • Now it's clear: ∀x :(∃y :(∀z : (likes (x, y) ∧¬likes (y, z)))) is just "everybody likes some misanthrope".

Phew!