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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.