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
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

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search