APPLI DISCRETE STRUC
APPLI DISCRETE STRUC COT 3100
Popular in Course
Popular in OTHER
This 4 page Class Notes was uploaded by Carlo Monahan on Friday September 18, 2015. The Class Notes belongs to COT 3100 at University of Florida taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/206632/cot-3100-university-of-florida in OTHER at University of Florida.
Reviews for APPLI DISCRETE STRUC
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/18/15
A Guide to Proof Writing 437 A Guide to Proof Writing by Ron Morash University of MichiganiDearborn Toward the end of Section 15 the text states that there is no algorithm for proving theorems H H Such a procedure does not exist77 This is true but does not mean that proofwriting is purely an art so that only those with exceptional talent and insight can possibly write proofsi Most proofs that students are asked to write in elementary courses fall into one of several categories each calling for a systematic approach that can be demonstrated imitated and eventually masteredi We present some of these categories and techniques for working within them organized as follows This material supplements that found in the text and is intended to help get you started creating your own proofsi Also studying the material in this Guide will help you understand better the proofs you rea i ll Deducing conclusions having the form For every I if 131 then Qzi77 lili Direct proof lilili Propositions having no hypothesis lili2i Propositions having one or more hypotheses liliSi Disproving false propositions having conclusions of the form VIPI A Qz lili4i The tactic of division into cases lili5i Proving equality of sets 12 lndirect proof 121 Proof by contrapositive 122 Proof by contradiction 123 Deriving conclusions of the form 4 or T 2 Remarks on additional methods of proof 21 Deducing conclusions having the form For every I there exists y such that Pz y 22 Proof by mathematical induction 1 Deducing conclusions having the form For every I if 131 then Qzi77 Many de ning properties in mathematics have the form VIP A representing the idea All P7s are Q7si77 Cf Examples 17 19 and 22 in Section 13 of the text Some de nitions involving this form are i A set A is a subset of a set B In symbols A Q B if and only if VIKI E A A z E This is read in words A is a subset of B if and only if for every z E z E A then I 6 Bi77 Less formally A is a subset of B if and only if every element of A is also an element of Bi Cf De nition 4 in Section 16 of the text ii A function f is onetoone f is onetoone if and only if for every 11 and 12 in the domain of f E fzl fz2 then 11 12 Cf De nition 5 in Section 18 of the text iii A relation R on a set A is symmetiic R is symmetric if and only if for every I y E A E z y E R then y I E Ri Cf De nition 4 in Section 71 of the text Many mathematical propositions that students are asked to prove have as their conclusion a statement involving a de nition of the form just described Some examples are a Prove that for all sets A and B A Q A U Bi b Prove that for all sets X Y and Z if X E Y then X N Z E Y N Z c Prove that for every function f whose domain and codomain are subsets of the set of real numbers if f is strictly increasing cf De nition 6 in Section 17 then f is onetoonei d Prove that for all relations R1 and R2 on a set A if R1 and R2 are symmetric then the relation R1 R2 is symmetric Note that the desired conclusion in each of the propositions a7d is a statement involving one of the de nitions i7iiii Furthermore propositions b c and d each have a hypothesis a statement we are allowed to assume true and whose assumed truth presumably will play a role in deriving the conclusion We begin our study of proofwriting methods by considering the very broad category known as direct proof 438 A Guide to Proof Writing 1 1 Direct proof An argument in which we prove a proposition in its originallystated form is called a direct proof Some forms of direct proof are discussed in Section 15 of the text In the sections of this Guide that follow we present various techniques for creating direct proofs Attempting to write a direct proof of a proposition is usually our rst line of attack Direct proof contrasts with indirect proof in which we prove a proposition by proving a different but logically equivalent form of the original proposition We will introduce indirect proofs later but will focus in Examples 1711 on various approaches to direct proo s 111 Propositions having no hypothesis Direct proofs of propositions like a having no hypothesis tend to be simpler in their structure than the proofs that are required for propositions b7d Examples 1 and 2 demonstrate proofs for this simpler case Example 1 Prove Proposition a For all sets A and B A Q A U B Solution The proof proceeds as follows Let A and B be arbitrary sets To prove A Q A U B let I be an arbitrarily chosen element of A Note We are assuming that z E A We must prove that z E A U B By the de nition of union77 this means we must prove that either I E A or z E B Since we know I E A by our assumption the desired conclusion I E A or z E B follows immediately I Letls dissect the proof in Example 1 and analyze what we did Our starting point assume I E A is an application of one of the most widelyused approaches to proofwriting known as the choose method The basic approach to deriving a conclusion of the form VIPz A is to begin by choosing an arbitrary object giving it a speci c name such as 177 for which it is assumed that 131 is true Our goal is to deduce that must consequently also be true In Example 1 131 is the assumption 1 E A77 and is the desired conclusion I E A U B77 We make the following additional observations 0 The object I is a xed but arbitrarily chosen element of the universe of discourse of 131 and We do not assign any speci c value to I rather we give the name I to a generic object that is assumed to satisfy the propositional function and use that name to keep track of the object as we proceed through the steps of the proof The power of this approach is that any conclusion we draw about this 1 applies to every object a for which the assumption Pa is true This is valid by the rule of universal generalization see Table 2 of Section 15 0 In the rst part of a proof of a conclusion of the form VIPr A called the settingup77 of the proof we choose I assume 131 is true and then write out what it would mean for to be true in our example to prove I E A U B we must prove that either I E A or z E E Learning the process of setting up a proof in this category provides a fairly standardized predictable and almost mechanical beginning of a prospective direct proof Furthermore once we have written out these details the remainder of the proofithe path from the assumption 131 to the desired conclusion Qziis sometimes obvious 0 In the proof in Example 1 the path from what we assumed ie z E A to the conclusion ie z E A U B was obvious In our proof we stated that the conclusion follows immediately77 But was there something more than just common sense77 to justify that conclusion Yes The rule of inference p A p V 4 Law of Addition is the underlying logical tool that justi es this step This rule and other rules of inference are stated in the text in Table l of Section 15 In the sample proofs that follow we will make explicit reference to the rules of inference used in an increasingly less obvious way as the proofs become more complex even though it is common practice to apply these rules only implicitly that is without speci c mention To become pro cient at writing proofs you need to know how to use these rules of inference and when to use them Example 2 Prove that for all sets X and Y X N Y UX E Y Discussion Let X and Y be arbitrary sets To prove X N Y UX E Y let a be an arbitrarily chosen element of X N Y U We could also say Assume a E X N Y U X We must prove a E Y This concludes the settingup of the proof Now we must gure out how to get from the assumption to the conclusion To do that we begin by analyzing what our assumption means SiIEe a E X N Y UX we know that a E X and a E Y U X The latter in turn tells us that either a E Y or a E X that is either a E Y or a X Note that the preceding sentence makes the rst mention of the desired A Guide to Proof Writing 439 conclusion a E Y Now can we infer the conclusion a E Y from the known either a E Y or a X This would require a rule of inference 17 V q A p the converse of the Law of Addition This is not a valid inference since 17 V q A p is not a tautology so this approach does not work Note however that not only do we know either a E Y or a X from our assumption but we also know that a E X Thus what we know from our assumption has the form 17 V q q Notez p is a E Y and q is a X so t is a E X Does Table l in Section 15 give us a conclusion that follows from this premise It does The Law of Disjunctive Syllogism 17 V q g A p enables us to draw the conclusion p that is a E Y the desired conclusion M2 As stated in Table l the roles of p and q are reversed from what we have here but that is of no consequence I Before moving on we rewrite the preceding proof leaving out explanatory comments What remains provides a representative view of what a typical proof looks like Let X and Y be arbitrary sets To prove X Y UX E Y assume a E X N Y UX We must prove a E Y By our assumption we know a E X and a E Y U X therefore a E X and either a E Y or a E X Thus we know that either a E Y or a X but we also know that a E X so a X is false Hence we conclude a E Y as desired At this point you may wish to try some relevant exercises in the text such as Exercises 12ac and l4abc in Section 17 You should nd the principles from Examples 1 and 2 helpful in attempting these exercises 112 P quot39 having one or more h potheses As we work through the steps of a prospective proof the tools at our disposal in moving toward a desired conclusion are 0 the assumptions we are entitled to make at the outset in setting up the proof 0 assumed axioms and previouslyproved theorems if any and 0 rules of inference from logic such as p A qu used in Example 1 and qu A q A p used in Example 2 See Table l in Section 15 for additional rules of this type In addition to these most propositions we are asked to prove contain 0 one or more hypotheses statements whose truth is to be assumed in the proof and which we expect will be used as part of the argument leading to the conclusion Example 3 provides our rst instance of a proposition in which a hypothesis is to be assumed in deriving a conclusion of the form VIPz A Example 3 Prove Proposition b For all sets X Y and Z if X E Y then X N Z E Y N Z Proof Let X Y and Z be sets such that X E Y To prove X N Z E Y N Z assume I E X N Z To prove I E Y N Z we must prove I E Y and b E Z This marks the end of setting up the proof Now we must return to our assumption and the hypothesis and begin to analyze what they mean and what information we can draw from them By our assumption we know that b E X and b E Z so in particular I E Z one of our two desired conclusions Furthermore since I E X part of our assumption and since X E Y here we are for the rst time bringing in the hypothesis we may conclude that b E Y our other desired conclusion I The following feature of the proof in Example 3 is very important In setting up the argument at the outset we applied the choose method to the desired conclusion not the hypothesis Thus our initial statement was assume I E X N Z A common mistake by beginning students is to begin with assume I E X erroneously focusing at the start of the proof on the hypothesis rather than on the desired conclusion Note that we did not employ the hypothesis until the very end of the proofl In the last sentence of the proof in Example 3 we concluded I E Y from knowing I E X and X E Y Let us consider why this conclusion is justi ed The truth of X E Y means that the proposition VIKI E X A I E Y is true Thus in particular the proposition 1 E X A b E Y is true where b is the speci c object we are working with in the proof Since I E X is true and the if then statement I E X A b E Y is true the truth of b E Y follows from the rule of inference modus ponens cf Table l in Section 15 of the text Note once again that a rule of inference has played an important though implicit role in a proof
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'