[SL02] Well-formed formula

§1. The language of SL

To define the language of SL, we need to specify the symbols or the vocabulary of SL. These are the basic building blocks out of which more complicated expressions are to be constructed. There are three kinds of symbols in SL :

1. Sentence letters : A, B, C, etc. These capital letters are used to translate sentences. If we run out of sentence letters we can always add subscripts to them to make new ones, e.g. A1 , B274, etc..

2. Five sentential connectives :

    ~ (tilde, or the negation sign)
    & (ampersand, or the conjunction sign)
    ∨ (the wedge, or the disjunction sign)
    → (the arrow)
    ↔ (the double-arrow)

3. Open and close brackets : ( )

§2. Construction of WFFs

The set of sentence letters, connectives, and brackets constitutes the set of symbols of SL. An expression of SL is simply any string of one or more symbols of SL:

  1. ABCDF&&&&(())))→ABCB12356A
  2. P
  3. (P&Q)
  4. ~~(P&Q))

Now we come to syntax, the rules that tell us which of the expressions of SL are grammatical, and which are not. A grammatical expression is called a well-formed formula (WFF). A WFF of SL is any expression of SL that can be constructed according to these rules of formation :

Rules of formation for SL

  1. All sentence letters are WFFs.
  2. If φ is a WFF, then ~φ is a WFF.
  3. If φ and ψ are WFFs, then (φ&ψ), (φvψ), (φ→ψ), (φ↔ψ) are also WFFs.
  4. Nothing else is a WFF.

Some comments on these rules :

  • The first rule tells us that symbols such as "A", "B", "C" are all WFFs.
  • "φ" in rule 2 is a Greek symbol, which nowadays is pronounced by many English speakers as "phi" (as in "Hifi"). (Note: this is probably not the correct ancient Greek pronuciation!) It is a variable that stands for any arbitrary thing. What rule 2 tells us is that whatever φ is, if it is a WFF, then when you add "~" to the front of φ you will end up with a new and longer WFF. So from rule 1, we know that "A" is a WFF. Then we can apply rule 2 to "A" to infer that "~A" is also a WFF. If we apply rule 2 again, then we can see that "~~A" is also a WFF.
  • "ψ" in rule 3 is a Greek symbol pronounced as "psi" (as in "psychology"). It is also a variable. Consider the formula "(P&~P)". This is a WFF because "P" is a WFF according to rule 1, so "~P" is also a WFF. Combining them according to rule 3 then, "(P&~P)" is also a WFF.
  • However, even though "~P" is a WFF, "(~P)" is not, because as we can see from rule 3, any WFF that contains a pair of brackets must have at least one of the four other connectives inside.
  • As you can see, the negation sign always connect to one single WFF to make a longer WFF, and is called a one-place connective. Whereas all other connectives connect two WFFs to make a new one and are called binary or 2-place connectives. Notice that all these connectives combine with WFFs to make new WFFs. A WFF is like a sentence which is why these connectives are called “sentential connectives”.

Are these expressions WFF?

  1. P
  2. ~~~~~~~~~~(P&Q)
  3. (P∨Q∨R)
  4. (~(P&S))
  5. (~P)
  6. ((P↔Q))
  7. ~(~G&~(~P&~Q))
  1. Suppose a WFF contains only three symbols. How many sentence letters would there be in this WFF? Is it possible for the WFF to contain the connective "&"?
  2. How many symbols are there in the longest WFF in SL?
  3. How many occurrences of binary and 1-place connectives are there in "~(~~(~P&Q)∨S)"?

§3. Grammatical categories

Here are some useful terms for talking about WFFs and their parts. If φ and ψ are WFFs, then :

  • (φ&ψ) is a conjunction where φ and ψ are the first and second conjunct respectively.
  • (φvψ) is a disjunction where φ and ψ are the two disjuncts.
  • (φ→ψ) is a conditional sentence where φ is the antecedent and ψ the consequent. Note that it is a mistake to say that ψ is the conclusion as this conditional sentence need not be an argument.
  • (φ↔ψ) is a biconditional sentence.
  • ~φ is the negation of φ.

So for example :

  • "(P&Q)" is a conjunction.
  • "((P&Q)∨(R↔Q))" is a disjunction.
  • "~(P→(Q∨S))" is the negation of "(P→(Q∨S))".
  • "~(P&Q)" is the antecedent of "(~(P&Q)→((P&S)↔Q))".

§4. Scope

By the scope of a connective α in a WFF φ we mean the shortest WFF in φ that contains α. Examples :

  1. The scope of “&” in “~(P&Q)” is “(P&Q)”. “&” is of course contained in the whole WFF, but it is not the shortest WFF that contains it. “&Q” is a shorter expression that contains “&” but it is not a WFF.
  2. The scope of “&” in “(~(~P&Q)→P)” is “(~P&Q)”.

§5. Main connective

The main connective in a WFF φ is the connective that has the widest scope. Here are some examples where the main connectives are highlighted in red:

  1. ~(P&Q)
  2. ~~~(P&Q)
  3. ~(~P&(P&Q))
  4. (~(~P&Q)P)
  5. ~(~(~P&Q)↔P)
  6. ((~M&N)&R)
  7. (~(~M&N)&R)

You will probably realize that we can use the main connective of a WFF to define whether it is a negation, a biconditional or a conditional, a disjunction or a conjunction.

Answer the following questions :

  1. Which is the first conjunct of "((P&Q)&R)"?
  2. Which is the second disjunct of "((P∨Q)&R)"?
  3. Which is the second disjunct of the first conjunct of "((P∨Q)&R)"?
  4. Suppose the antecedent of a conditional is a disjunction where both disjuncts are "P", and the consequent is the negation of the antecedent. What does this conditional look like?
  5. Give an example of a conjunctive WFF where the first conjunct is the negation of the second conjunct.
previous tutorial next tutorial


© 2004-2024 Joe Lau & Jonathan Chan