Chapter 7, Tutorial 4
PL: Syntax and Semantics
[Gold]

We have been using PL now for some time. But we have yet to say exactly what counts as a sentence of this language. It is time to spell this out. Let's begin with a few preliminary considerations. These will give the basic idea of PL sentence construction.

  1. We cannot define a PL sentence as we did before in SL, we cannot start with the atomic sentence and use connectives to build molecular ones. Why not?
    • Answer: the "atoms" of PL are not themselves sentences. For example, take the sentence '(^x)(Ax>Bx)'. We will build this sentence by starting with the atoms 'Ax' and 'Bx', combining these with the horseshoe to give 'Ax>Bx' and finally adding the quantifier.
    • But 'Ax', 'Bx', and 'Ax>Bx' are not sentences! Because they contain a variable 'x' instead of a name, they do not express complete thoughts. For instance, 'Ax' says that "x has property A" which is a little like saying "_____ has mumps". It is not a complete sentence.
    • So, 'Ax', 'Bx', and 'Ax>Bx' are incomplete sentences. We will call them "formulas" of PL.
    • To make a formula like these into sentences, we must either replace variables with a name or add a quantifier.
    • Thus we will make the sentence '(^x)(Ax>Bx)' by building it up from atoms ('Ax' and 'Bx') using a truth functional connective and a quantifier. When each variable has a quantifier, the formula is also a sentence.
  2. So, we construct sentences from formulas:
    • First, we take , 'Ax', 'Da', 'Rxa', 'Bxyz', etc. as our atomic formulas.
    • Then we build more complex formulas adding truth functional connectives or quantifiers. For example, we may build '~Ax', '(Da&Bxyz)', '(%x)Rxa', etc. These are new formulas.
    • We may keep on building by adding more truth functional connectives and quantifiers to formulas already constructed. For example: '~Ax>(%x)Rxa' or '(^y)(Da&Bxyz)' count as more complex formulas of PL.
    • Only when a PL formula has a quantifier for each instance of a variable does it count as a sentence of PL. Of our examples just above, only '(%x)Rxa' is a sentence.
  3. This is all a bit vague. We will make these syntactical definitions more precise beginning on the next page.

But first, try your hand at the following. Which of these count as formulas of PL? (We drop outside parentheses as with SL.)

  1. (^a)Pa
  2. Pyv(^x)Px
  3. Px(^x)Tx
  4. Px&(^x)Tx
  5. (^x)Px&(^x)Tx
  6. (^x)(Px&(^x)Tx)
  7. (^x)[Px>(%y)Lyx]
  8. (^x)[Px>(%y)(Lxy&Rx]
  9. (^x)[Px>(%y)(Lxy&Rx)]
  10. (^x)[Px>%y(Lxy&Rx)]

And which of the following are sentences of PL?

  1. (^x)(%y)Lxy
  2. (^x)Lxy&(%y)Lyy
  3. (^x)(%y)Lxy&(%y)Lyy
  4. (^x)[(%y)Lxy&~(%y)~Lyx]