Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proofs Using Quantifiers


Date: 10/17/2001 at 19:02:46
From: Melanie
Subject: Proofs Using Quantifiers

We're doing proofs, and I have no idea how to do this one:

GIVEN :(UPSIDEDOWN Ex)Ax ARROW (UPSIDEDOWN Ax)Bx
       (UPSIDEDOWN Ex)Cx ARROW (UPSIDEDOWN Ex)Dx
         An (SYMBOL FOR AND) Cn

PROVE: (UPSIDEDOWN Ex)(Bx AND Dx)


Date: 10/17/2001 at 20:47:07
From: Doctor Achilles
Subject: Re: Proofs Using Quantifiers

Hi Melanie,

Thanks for writing to Dr. Math.

Let me start with a few logical symbols. Some of the concepts here 
will probably be review, but it'll make sure we're on the same page.

p, q, r, s, and t are logical sentences. They can be true or false.

^ is the symbol for and. (p ^ q) is true if p is true AND q is true.

u is the symbol for or. (p u q) is true if p is true OR if q is true 
OR if both p and q are true.

-> is the symbol for if, then. (p -> q) is read "if p, then q". 
(p -> q) is true if p is false OR if q is true.

<-> is the symbol for if and only if. (p <-> q) is true if p and q are 
BOTH true, or if they are BOTH false.

a, b, c, d, e, ..., m, and n are constants. They refer to particular 
objects.  w, x, y, and z are variables; they refer to some unspecified 
object or other.

A capital letter such as A, B, C, or D refers to some property of an 
object. For example, B could refer to the property of being blue.  
When you put a capital letter in front of a constant, you are saying 
that that object has the property. So Bn means "object n is blue."

When you put a capital letter in front of a variable, you have to have 
a quantifier in front of it.

A backward E is the symbol for existence. For the purposes of this 
answer I'll just use a regular E. (Ex)Bx is read "There exists some x 
such that x is blue," or, more to the point, "something is blue."

An upside-down A is the symbol for a universal. For the purposes of 
this answer I'll just use a capital V. (Vx)Bx is read "For all x, x is 
blue," or, more to the point, "everything is blue."

You are given:

1)  (Ex)Ax -> (Vx)Bx
2)  (Ex)Cx -> (Ex)Dx
3)  An ^ Cn

One easy thing to get from line (3) is that An is true (since An and 
Cn are BOTH true, then An by itself must be true).

4)  An

Now if object n has property A, then it's pretty easy to see that 
SOMETHING has property A:

5)  (Ex)Ax

Line (1) tells us that if we know (Ex)Ax, then we are entitled to 
(Vx)Bx. Well, since we just proved (Ex)Ax in line (5), let's get what 
we're owed from line (1).

6)  (Vx)Bx

Okay, we just proved that EVERYTHING has the property B. Now let's go 
back to line (3) and get that other piece of information out of it:

7)  Cn

Just as before, since object n has the property C, then SOMETHING has 
the property C:

8)  (Ex)Cx

Line (2) tells us that if we have (Ex)Cx, then we are entitled to 
(Ex)Dx. So let's get what we're entitled to:

9)  (Ex)Dx

Okay, so we just proved that SOMETHING has the property D, there may 
be more than one thing with the property D, but we can be assured that 
there is at least one. Let's call that thing "m" (just for right now).

10) Dm

Now, we know from line (6) that EVERYTHING has the property B. In 
particular, object m has the property B:

11) Bm

Let's put lines (10) and (11) together with an and:

12) (Bm ^ Dm)

So m has the property B and the property D, and we can say with 
confidence that SOMETHING has the property B and the property D.

13) (Ex)(Bx ^ Dx)

And that's it.

For a review of how to do derivations without quantifiers, check out 
this url (on this page I use an n for and instead of a ^, so be aware 
of that when reading the page):

   Mathematical Logic
   http://www.mathforum.org/dr.math/problems/chin.2.9.01.html   

Here's a quick list for your reference of the things you can do to a 
quantifier (again, I use a regular E for existential and a V for 
universal).

EI: Existential introduction. If you have a concrete case, say An,  
    then you are entitled to an existential case, i.e. (Ex)Ax. There 
    are NO restrictions on introducing existentials

EE: Existential elimination. If you have an existential, say (Ex)Cx, 
    you can ASSUME a concrete case, i.e. Cm.  HOWEVER, there are two 
    restrictions: First, the concrete case CANNOT be something you 
    have seen before, so in this case m has to be a new letter that 
    hasn't appeared in your derivation yet. Second, you have made a 
    new assumption, the only thing you can take out of the assumption 
    is something that does not contain the letter m. So for example in 
    the problem above, (Bm ^ Dm) couldn't have been our final 
    conclusion, but only an intermediate step in the derivation, but 
    it was legitimate for us to take out (Ex)(Bx ^ Dx), since that has 
    no m's in it.

VE: Universal elimination. If you have a universal, say (Vx)Dx, you 
    are entitled to ANY instance you want. So you can say Dn, even if 
    n is something you've seen before. There are NO restrictions on 
    eliminating universals.

VI: Universal introduction. If you have a concrete case, say Bm, then 
    you are entitled to (Vx)Bx ONLY IF the letter m DOES NOT appear in 
    ANY assumption. Universal introduction is RARELY used, so be very 
    careful that the concrete object you're talking about is not in 
    ANY assumption before you use it.

Try going back through the derivation above and seeing which rule was 
used at each step. This will give you practice with the rules.

I hope all this helps. If this is unclear or you have other questions 
about math, please write back.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/