Simple Predicate Logic

Syntax

The formal system of PL is rather complicated, and in this course we shall not be studying the whole complete system. Rather, we shall only look at a simplified version of PL that we shall call "Simple Predicate Logic", or "SPL" for short. Let us now look at the syntax for SPL.

As far as the vocabulary of SPL is concerned, we have the sentence letters, brackets and sentential connectives from SL. But in addition there are also predicate letters, variables and the quantifier symbols "∃" and "∀". Strictly speaking, in order to avoid confusion we should use different letters for sentence letters and predicates. But in practice, since predicate letters are always accompanied by names or variables in a WFF, the context should make it clear whether a capital letter is used as a sentence letter or as a predicate. So for example, "P" in "(P&Qa)" is a sentence letter and "Q" is a predicate. However, we should avoid using the same letter both as a sentence letter and a predicate, such as "(Pa&P)".

The syntactic rules, or formation rules, for SPL are as follows :

Rules of formation:

1. All sentence letters are wffs. Any predicate letter followed by a single name is also a wff.

2. If φ is a wff, then ~φ is a wff.

3. If φ and ψ are wffs, then (φ&ψ), (φvψ), (φ→ψ), (φ↔ψ) are also wffs.

4. If φ is a wff that contains any name ω, but does not contain any quantifier, then the resulting expression that is obtained by replacing all occurrences of ω in φ by a variable β, and attaching "∃β" or "∀β" to the front, is also a wff.

5. Nothing else is a wff.

The only new rules that are added are rules #1 and #4. Rule #1 tells us that apart from sentence letters, expressions such as "Pa", "Qb", "Gc" are also wffs. We can then apply rules #2 and #3 to form new wffs such as "~~Pa", "~((Pa&S)↔(~Fb∨Ka))" which are not wffs in SL.

The only complicated rule is rule #4. It applies only to wffs that include at least one name but no quantifier. So it applies to expressions such as "Qa", "(~Pa→S)", "(Pa&Qa)", but not "Q" or "∃xFx". The rules says that we can pick a name in a wff from the first group, replace all the occurrences of that name by a single variable, and then add either an existential or universal quantifier to the front that contains that variable. Here are some examples:

From "Qa", we get generate wffs such as "∃xGx", "∀yGy".

From "(~Pa→S)", we get "∃y(~Py→S)" or "∀x(~Px→S)".

From "(Qa↔Qa)", we get "∃x(Qx↔Qx)", "∀z(Qz↔Qz)" (But not "∃x(Qx↔Qa)"!)

From "(~Qa→Qb)", we get "∃x(~Qx→Qb)", "∀z(~Qa→Qz)" (But not "∃x(~Qx→Qx)"!)

From "~((Pa&S)↔(~Fb∨Ka))", we can get :
"∃x~((Px&S)↔(~Fb∨Kx))",
"∃x~((Pa&S)↔(~Fx∨Ka))", etc.
(But not "∃x~((Px&S)↔(~Fb∨Ka))")

Construction trees

A complex wff in SPL is any wff that contains a quantifier or a connective. To show how a complex wff is constructed, we can draw a construction tree for that wff. A construction tree is a tree diagram with arrows linking wffs. Starting with non-complex wffs at the top, the diagram shows how a complex wff can be built up step-by-step using the formation rules of SPL. Here for example is a construction tree for "~(P&~Fa)" :

We started off with "P" and "Fa" which are not non-complex wffs. An arrow from X to Y indicates that Y can be constructed from X by applying one of the formation rules. Similarly, an arrow from X and Y to Z indicates that Z can be constructed from X and Y. By drawing a construction tree for a wff we show clearly how the formation rules are used to build up the wff. As a second example here is a construction tree for "~∀x(P&~Fx)" :

Of course, in this second example, we could have started off with "Fb" instead. So sometimes (not always) a wff can have more than one construction tree.

---

Exercises

Question 1 : Are these expressions wffs of SPL? Draw a construction tree for each of the wff. (Take "x", "y", "z" as variables and other small letters as names.)

1. (P&(P&~R))  [ANSWER]
2. ∃x(Mx↔~Qx)  [ANSWER]
3. ~∃x~(Ma↔~Qx)  [ANSWER]
4. ~(~∀xKx∨∃y~Qy) [ANSWER]
5. ∀x∀y(Qx&Py) [Show answer]
   Not a wff.
6. ∀x(Px&∀y~Ly) [Show answer]
   Not a wff.
7. ∃x(P→Qa) [Show answer]
   Not a wff.
8. ∀x∀yFxy [Show answer]
   Not a wff.
9. ((∀xKx&∀yQy)∨Ma)  [ANSWER]
10. (∀xKx&((∀yQy)∨Ma)) [Show answer]
    Not a wff.
11. (∀xKx&∀yQy∨Ma) [Show answer]
    Not a wff.
12. ~~~∃x~~~Gx  [ANSWER]
13. (~~~∃x~~~Gx&Hx) [Show answer]
    Not a wff.
14. ~~∃x(~Gx&Hx)  [ANSWER]
15. ∀x((Ga∨Bx)↔(Kb&Gx))  [ANSWER]
16. ∀x((Gx∨Bx)↔(Kx&Gx))  [ANSWER]
17. ∀x((Ga∨Ba)↔(Ka&Ga)) [Show answer]
    Not a wff.

Question 2 : Do wffs in SL have unique construction trees? In other words, given any wff in SL, is it true that there is only one single construction tree that can be drawn for the wff? Why or why not?

<< previous page

---

---