21.  WORKING WITH MULTIPLE QUANTIFIERS
Click on to review how to symbolize with quantifiers

You have already seen that often we work with more than one quantifier in an expression, as when we have (x)[Fx -> (Ey)Gy], which could be used to symbolize "For everyone, if that person is friendly then there is someone who is generous."  A key point is that the variable used with the quantifier must link with ("bind") a corresponding variable in the following parenthesis.  red flag This is why we must use different variables when there could be a question of meaning.

In derivations with more than one quantifier outside a parenthesis we instantiate (eliminate the quantifier) from the left and work inward.  We generalize (introduce a quantifier) at the left outward, but we may generalize on any name inside a parenthesis.

Study the following derivations carefully.

    (x)(Ey)(Fx -> Gy) |- (Ex)(y)(Fy -> Gx)
    1.  (x)(Ey)(Fx -> Gy)    / show (Ex)(y)(Fy -> Gx)
    2.  (Ey)(Fa -> Gy)        1,  UI
    3.  Fa -> Gb                2,  EI
    4.  (y)(Fy -> Gb)          3,  UG
    5.  (Ex)(y)(Fy -> Gx)    4,  EG

    (x)[(Fx v Gx) -> (Ey)(Gy & Hy)] |- (x)(Ey)(Fx -> Hy)
    1.  (x)[(Fx v Gx) -> Ey(Gy & Hy)]    / show (x)(Ey)(Fx -> Hy)
    2.  (Fa v Ga) -> (Ey)(Gy & Hy)         1,  UI
        3.  Fa                                        HCP
        4.  Fa v Ga                                3,  Add
        5.  (Ey)(Gy & Hy)                        2,4, MP
        6.  Gb & Hb                               5,  EI
        7.  Hb                                        6,  Simp
     8.  Fa -> Hb                                  3-7,  CP
     9.  (Ey)(Fa -> Hy)                           8,  EG
    10.  (x)(Ey)(Fx -> Ey)                     9,  UG

EXERCISES (ON YOUR OWN)

Provide derivations for each of the following.
1.  (Fa & Gb)-> (z)Hz, (x)(Fx & Gx) |- Hc
2.  [(Ex)Fx & (Ey)Gy] -> (z)(Hz), Fa & Gb |- Hc
3.  (x)(Ey)(Fx v Gy) -> (Ez)Hz |- (x)~Fx -> [(Ey)Gy -> (Ez)Hz]
4.  (Ex)(y)(Fx & Gy) -> (Ez)Hz |- (x)(Fx & Gx) -> [(Ez)Hz v (z)Gz]

Go to the answer key


USING DYADIC PREDICATES

Up until now we've been working primarily with what are called one-place (monadic) predicates, as when we have Fa symbolizing the idea that Al is a friend.  But we can have any number of names following a predicate variable in order to indicate a specific kind of relationship among them.  For instance, Fab might represent "Al is Bob's father" and Fabc might represent "Al finds Bob in California."  When we do this the predicate variable ("F" in our examples) is not assumed to have the same meaning as we change the number of names, and even if we were to use it to represent the idea of a father, we could not derive Fa from Fab, even though in our commonsense world if Al is Bob's father then we can say that he is a father.

We are going to work now with two-place (dyadic) predicates.  We'll set up a code for our examples:
            Sx: x is a student
            Tx:  x is a teacher
            Lxy:  x likes y
            a: Alice
            b: Barbara

    Alice likes Barbara.  Lab
    Barbara likes Alice.  Lba
    Everybody likes Alice.  (x)Lxa
    Alice likes somebody.  (Ex)Lax
    Everybody likes somebody.  (x)(Ey)Lxy
    Every student likes Barbara.  (x)(Sx -> Lxb)
    Some students like all the teachers.  (Ex)[Sx & (y)(Ty -> Lxy)]
    Some teachers do not like any students.  (Ex)[Tx & (y)(Sy -> ~Lxy)]
    Any teacher likes both Alice and Barbara.  (x)[Tx -> (Lxa & Lxb)]
    Only students like Alice.  (x)(Lxa -> Sx)

In symbolizing information there is a special point we need to keep in mind.  Let's say we have this story:

            Every student reads all the texts.  Some texts are difficult.   Therefore, there are students who read things that are difficult.

    If we symbolize the information as presented we have

           (x)[Sx -> (y)(Ty -> Rxy)], (Ex)(Tx & Dx) |- (Ex)[Sx & (Ey)(Dy & Rxy)]

    Testing for validity (as with a consistency tree), we would find that it is not valid.  Why?  The first premise expresses a conditional relationship that can be true even if there are no students, but the conclusion expects that there are students.  How should we symbolize?  If the situation being represented is supposed to assume the existence of students, then we should add another premise making this explicit.

           (x)[Sx -> (y)(Ty -> Rxy)], (Ex)Sx, (Ex)(Tx & Dx) |- (Ex)[Sx & (Ey)(Dy & Rxy)]

The derivation will go along just as before, keeping in mind the need to work with the main connective for inference rules and also the need to respect the new name rule.

    1.  (x)[Sx -> (y)(Ty -> Rxy)]        
    2.  (Ex)Sx                                 
    3.  (Ex)(Tx & Dx)                         /  (Ex)[Sx & (Ey)(Dy & Rxy)]
    4.  Sa                                        2,  EI   remember why we instantiate this expression first
    5.  Sa -> (y)(Ty -> Ray)               1,  UI
    6.  (y)(Ty -> Ray)                        4,5,  MP
    7.  Tb & Db                                 3,  EI
    8.  Tb -> Rab                               6,   UI
    9.  Tb                                         7,  Simp
    10.  Rab                                     8,9,   MP
    11.  Db                                       7,  Simp
    12.  Db & Rab                            10,11,   Conj
    13.  (Ey)(Dy & Ray)                     12,  EG
    14.  Sa & (Ey)(Dy & Ray)             4,13,  Conj
    15.  (Ex)[Sx & (Ey)(Dy & Rxy)]      14,  UG

EXERCISES (ON YOUR OWN) 

Symbolize and provide derivations.
1.  All students read (some) long novels.  Any novel is exciting.  Therefore, all students read (some) things that are exciting.
2.  No student reads every novel.  Al is a student.  Therefore, there are novels that Al does not read.
3.  Bob and Carol are students.  Don is a teacher.  Every teacher likes all students.  Therefore, Don likes Bob and Carol.
4.  If every student is ambitious, then there are individuals who take some hard courses.  No one takes any hard courses.  Therefore, there are some students who are not ambitious.
5.  Students and teachers like anything that is fun.  Any logic problem is fun.  Ted is a student.  Therefore, Ted likes all logic problems.  (Hint: symbolize "students and teachers" as a disjunction, not a conjunction.)

Go to the answer key
REVIEW EXERCISE (1 bonus point)

Copy and paste the following into an email message to me and submit your derivations.   Several of these are exercises dealing with what are called prenex forms--patterns in which all the quantifiers are to the left.  red flag Be careful to indent any subordinate proofs.

1.  (Ex)Ax  v  (Ex)Bx  |-  (Ex)(Ax v Bx)    [hint: you must use an indirect derivation]
2.  (Ex)(Ax & Bx) -> (x)(Cx & Dx)  |-  (x)(y)[(Ax & Bx) -> (Cy & Dy)]
3.  (x)(y)(Ez){Fxy ->  Gz) |- (Ex)(Ey)Fxy -> (Ex)Gx
4.  (x)(y)(z)[(Axy v Byx) -> Cyz], ~Cba |- Aab -> Bba