MODULE: Sentential logic

TUTORIAL SL02: Well-formed formula in SL

SL02.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. A₁ , B₂₇₄, 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 : ( )

SL02.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&&&&(())))→ABCB₁₂₃₅₆A
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 pronounced as "phi" (as in "Hifi"). 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”.

SL02.3 Exercises

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 "&"? [Show answer]
   The WFF must contain only one sentence letter with two negation signs in front. A WFF that contains any binary connective must contain at least five symbols.
2. How many symbols are there in the longest WFF in SL? [Show answer]
   There is no longest WFF in SL! Any WFF can be made longer by adding a negation sign to the front.
3. Are these expressions WFF?

   • P [Show answer]
     Yes. All sentence letters are WFFs.
   • ~~~~~~~~~~(P&Q) [Show answer]
     Yes.
   • (P∨Q∨R) [Show answer]
     No. Should be either (Pv(QvR)) or ((PvQ)vR)
   • (~(P&S)) [Show answer]
     No. An extra pair of brackets
   • (~P) [Show answer]
     No. An extra pair of brackets
   • ((P↔Q)) [Show answer]
     No. An extra pair of brackets
   • ~(~G&~(~P&~Q)) [Show answer]
     Yes.

4. How many occurrences of binary and 1-place connectives are there in "~(~~(~P&Q)∨S)"? [Show answer]
   4 1-place and 2 binary

---

SL02.4 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))".

SL02.5 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)”.

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.

SL02.6 Exercises

Answer the following questions :

1. Which is the first conjunct of "((P&Q)&R)"? [Show answer]
   (P&Q)
2. Which is the second disjunct of "((P∨Q)&R)"? [Show answer]
   This is a trick question! The WFF is a conjunction so it does not have any disjuncts!
3. Which is the second disjunct of the first conjunct of "((P∨Q)&R)"? [Show answer]
   Q
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? [Show answer]
   ((PvP)->~(PvP))
5. Give an example of a conjunctive WFF where the first conjunct is the negation of the second conjunct. [Show answer]
   (~P&P), or (~Q&Q), or (~(P&S)&(P&S)), etc.

<< previous page

---

---