ࡱ> '` 0bjbj{P{P 4::9|."""""""$H8lr$ Q^hjjjjjj$h<"rrr"""""r "" v"rh""""" 0E@ "l0"1@1""1"" Srrrr Q Q Qđ Q Q Q6"""""" Chapter One Notes The Foundations: Logic and Proofs Based on: Discrete Math & Its Applications - Kenneth Rosen CSC125 - Spring 2010  HYPERLINK "http://faculty.kutztown.edu/rieksts/125/text/chap01.doc" As MS document 1.1 - Propositional Logic Concepts:: Proposition Propositional variables Propositional logic (calculus) Logical connectives (operators) ( ( ( ( ( ( Compound propositions Logical operations Negation (p not p Conjunction p ( q p and q Disjunction p ( q p or q (or both) Exclusive Or p ( q p xor q Conditional (implication) p ( q if p, then q (p implies q) Converse of p ( q is q ( p (p ( q) The converse does not necessarily follow. Example: If it rains then the streets are wet true If the streets are wet then it rained false Contrapositive of p ( q is (q ( (p The contrapositive does necessarily follow. If it rains then the streets are wet true If the streets are not wet then it did not rain true Inverse of p ( q is (p ( (q The inverse does not necessarily follow. Example: If it rains then the streets are wet true If it does not rain then the streets are not wet false Biconditional p ( q if p, then q and if q, then p p implies q and q implies p p if and only if q p iff q Truth tables p  (p T  F F  T p  qp ( qp ( qp ( qp ( qp ( q T  T T T F T T T  F F T T F F F T F T T T F F F F F F T T Bitwise And, Or, Xor And 0 0 1 1 0 1 0 1 0 0 0 1 Or 0 0 1 1 0 1 0 1 0 1 1 1 Xor 0 0 1 1 0 1 0 1 0 1 1 0 How many Boolean operations? x yf0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f150 000000000111111110 10000111100001111100011001100110011110101010101010101 Natural language, logic and ambiguity 1.2 - Propositional Equivalences Introduction:: From truth tables we can see that there are compound propositions that are equivalent to each other. In other words, whenever the first proposition is true, so is the second. And whenever the first is false, the second is also false. For example: p  q(p(p (q p ( q T  T F T T T  F F F F F T T T T F F T T T p  q(p(q (p ( (qp ( q((p ( q) T  T F F  F T F T  F F T  T F T F T T F T F T F F T T T F T Compare the above to Tables 3 and 4 on pp. 22 & 23 of Rosen. These are examples of important equivalences which we will study. Before we do, we need to learn some terminology. Tautology a proposition that is always true Example: p ( (p Contradiction (inconsistency) a proposition that is always false Example: p ( (p Contingency a proposition that is neither a tautology nor a contradiction, i.e., it is sometimes true and sometimes false. Example: p ( q For verification of these examples, look at Table 1, p. 22 and Table 7, p. 10. Logical Equivalences:: p & q are logically equivalent if p ! q is a tautology In that case we can write: p a" q Truth tables can be used to establish whether or not p & q are logically equiv. DeMorgan's Laws  Table 2 {on quiz } Tables of important logical equivs. Table 6 {on quiz} Table 7 involving conditionals {on quiz} Table 8 involving biconditionals {on quiz} Constructing New Logical Equivalences:: Given a small set of logical equivalences, we can derive new ones in a step by step process. Examples 6!8, pp. 26-27 illustrate how this is done. This process of derivation of new propositions from old is very useful and forms the basis of a lot of work in automated theorem proving. 1.3 - Predicates and Quantifiers Predicate logic predicate (propositional function) variable truth value of propositional function n-place predicate or n-ary predicate Quantifiers quantification - expresses extent to which a predicate is true over a range of elements predicate calculus domain OR domain of discourse OR universe of discourse universal quantifier (xP(x) counterexample one single x for which P(x) is false existential quantifier (xP(x) establishing example one single x for which P(x) is true See Table 1, p. 34 uniqueness quantifier (!xP(x) {or (1xP(x) } quantifiers with restricted domains precedence of quantifiers (xP(x) ( Q(x) a" ((xP(x)) ( Q(x) !a" (x(P(x)) ( Q(x)) binding variables variable within scope of quantifier is bound variable not within scope of quantifier is free Logical equivalences (x(P(x) ( Q(x)) a"(xP(x) ( (xQ(x), if same domain is used throughout Negating quantified expressions (DeMorgan's Laws) ((x P(x) a" (x(P(x) ((xP(x) a" (x(P(x) Quantifiers related to ( and ( (xP(x) operates like a super ( Let domain be {1,2,3} (xP(x) a" P(1) ( P(2) ( P(3) (xP(x) operates like a super ( Let domain be {1,2,3} (xP(x) a" P(1) ( P(2) ( P(3) That is why the negation laws above are called DeMorgan's Laws ((x P(x) a" ((P(1) ( P(2) ( P(3)) a" (P(1) ( (P(2) ( (P(3) a" (x(P(x) And ((xP(x) a" ((P(1) ( P(2) ( P(3)) a" (P(1) ((P(2) ( (P(3) a" (x(P(x) See Table 2, p. 41 Translating to & from English Let T(x) represent "x is tall" Everyone is tall:: (x T(x) It is not true that everyone is tall:: ((x T(x), is the same as Someone is not tall:: (x(T(x) Someone is tall:: (x T(x) It is not true that someone is tall:: ((x T(x), is the same as No one is tall:: (x(T(x), which is the same as Everyone is not tall {although this is ambiguous; see below} Ambiguity and subtlety of natural languages It is important to realize that one of the difficulties in translating back and forth from English (or any other natural language) to symbolic logic comes from the fact that some expressions are used in more than one way, logically speaking. In addition it is difficult to disambiguate because closely related expressions are used to express subtle nuances of meaning. Everyone is not tall is a good example. It can be taken to mean no one is tall, as we took it to mean above. (x(T(x) Or it can be taken to mean not everyone is tall ((x T(x) or someone is not tall (which is logically equivalent) (x (T(x) That meaning comes out clearly in the following interchange. Person A: Everyone is tall. Person B: No, everyone is not tall. Attempts to disambiguate by changing our wording lead to other problems. We could try to express (x(T(x) as everyone is short, but that changes the meaning. If we have a basketball team where the heights range from 5'9" to 6'6", we can say everyone is not tall; but we could not say everyone is short. We could make up new words and say everyone is untall, but that is not likely to be welcomed by the general population of English speakers. It soon becomes pretty clear that there is no cleancut solution to the translation problem. In fact, that is one of the reasons for using symbolic logic to eliminate the ambiguity inherent and widespread in natural language. Read the examples below to see how prevalent ambiguity and subtlety are in our use of "the king's English." Everyone goes No, everyone does not Everyone stays away Everyone does not go Everyone is going Everyone is not going Everyone is so not going Someone goes No, someone does not go Some do not go Some stay away Everyone thinks Everyone is unthinking Everyone does not think Everyone is thoughtful Everyone is not thoughtful Everyone is thoughtless Someone thinks Someone does not think Some is thoughtless Someone is thoughtless Everyone is caring Everyone is uncaring Everyone is not caring Not everyone is caring Everyone is careless Everyone is careful Everyone is not careful Not everyone is careful Not everyone is careless Quick Summary Realizing that there will still be ambiguous cases, here are some rules of thumb (x D(x) everyone does (x (D(x) everyone does not; i.e., for everyone does not is true ((x D(x) not everyone does; i.e., for some does not is true (x D(x) someone does (x (D(x) someone does not; there is someone who does not ((x D(x) no one does Equivalences ((x D(x) a" (x (D(x) No one does is the same as everyone does not ((x D(x) a" (x(D(x) Not everyone does is the same as someone does not 1.4 - Nested Quantifiers Think of quantification as loops Example 2 Order of Quantifiers Does not matter if all of same type Example 3 Very important when of mixed type Examples 4 & 5 Let domain be {1,2,3} (x (y P(x,y) a" (y(x P(x,y) a" P(1,1) ( P(1,2) ( P(1,3) ( P(2,1) ( P(2,2) ( P(2,3) ( P(3,1) ( P(3,2) ( P(3,3) (x (y P(x,y) a" (y(x P(x,y) a" P(1,1) ( P(1,2) ( P(1,3) ( P(2,1) ( P(2,2) ( P(2,3) ( P(3,1) ( P(3,2) ( P(3,3) (x (y P(x,y) a" (P(1,1) ( P(1,2) ( P(1,3)) ( (P(2,1) ( P(2,2) ( P(2,3)) ( (P(3,1) ( P(3,2) ( P(3,3)) In other words, for x = 1, (y P(x,y) ( for x = 2, (y P(x,y) ( for x = 3, (y P(x,y) (x (y P(x,y) a" (P(1,1) ( P(1,2) ( P(1,3)) ( (P(2,1) ( P(2,2) ( P(2,3)) ( (P(3,1) ( P(3,2) ( P(3,3)) In other words, either for x = 1, (y P(x,y) ( for x = 2, (y P(x,y) ( for x = 3, (y P(x,y) Similarly, (y (x P(x,y) a" (P(1,1) ( P(2,1) ( P(3,1)) ( (P(1,2) ( P(2,2) ( P(3,2)) ( (P(1,3) ( P(2,3) ( P(3,3)) In other words, either for y = 1, (x P(x,y) ( for y = 2, (x P(x,y) ( for y = 3, (x P(x,y) Therefore, (x (y P(x,y) `" (y (x P(x,y) `" (x (y P(x,y) See Table 1, p. 53 Translating mathematical statements Examples 6 & 7 Translating nested quantifiers into English Examples 9 & 10 Translating English into logical expressions Examples 11 & 13 Negating nested quantifiers Example 14 ((x (y (xy = 1) a" (x ( (y (xy = 1) a" (x (y ( (xy = 1) a" (x (y (xy `" 1) Example 15 ( (w (a (f (P(w,f) ( Q(f,a)) (w ((a (f (P(w,f) ( Q(f,a)) (w (a ((f (P(w,f) ( Q(f,a)) (w (a (f ((P(w,f) ( Q(f,a)) (w (a (f ((P(w,f) ( (Q(f,a)) Doubly quantified expression examples: Let W(x,y) be the statement student x watched Eagles game y, where the domain for x consists of all students in this class and the domain for y consists of all Philadelphia Eagles games last season. Express each proposition in English. 1. $x $y W(x,y) A student from this class watched an Eagles game last season. 2. ($x $y W(x,y) No student from this class watched an Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" (x ($y W(x,y) a" (x (y (W(x,y) Note: Equivalent to #18 {For all students and all Eagles games, it not true that any student watched any game} 3. $x "y W(x,y) A student from this class watched every Eagles game last season. 4. ($x "y W(x,y) No student from this class watched every Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" (x ((y W(x,y) a" (x $y (W(x,y) Note: Equivalent to #16 5. "y $x W(x,y) Every Eagles game last season was watched by a student in this class. 6. ("y $x W(x,y) Not every Eagles game last season was watched by a student in this class. Here are equivalent forms, by DeMorgan's Law a" $y ((x W(x,y) a" $y (x (W(x,y) Note: Equivalent to #17 7. "x $y W(x,y) Every student from this class watched an Eagles game last season. 8. ("x $y W(x,y) Not every student from this class watched an Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" $x ($y W(x,y) a" $x "y (W(x,y) Note: Equivalent to #14 {A student from this class did not watch any Eagles games last season; OR: It is not true that every student watched an Eagles game last season} 9. $y "x W(x,y) There is an Eagles game last season that every student watched. 10. ($y "x W(x,y) None of the Eagles games last season were watched by every student. Here are equivalent forms, by DeMorgan's Law a" "y ("x W(x,y) a" "y (x (W(x,y) Note: Equivalent to #15 11. "x "y W(x,y) Every student from this class watched every Eagles game last season. 12. ("x "y W(x,y) Not every student from this class watched every Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" $x ((y W(x,y) a" $x $y (W(x,y) Note: Equivalent to #13 13. $x $y (W(x,y) A student from this class who missed an Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" $x ((y W(x,y) a" ((x (y W(x,y) Note: Equivalent to #12 {There is a student from this class who did not watch every Eagles game last season; OR: Not every student from this class watched every Eagles game last season.} 14. $x "y (W(x,y) A student from this class did not watch any Eagles games last season. Here are equivalent forms, by DeMorgan's Law a" $x ($y W(x,y) a" ((x $y W(x,y) Note: Equivalent to #8 {Not every student from this class watched an Eagles game last season; OR: It is not true that every student watched an Eagles game last season} 15. "y $x (W(x,y) No Eagles game was watched by every student in this class. Here are equivalent forms, by DeMorgan's Law a" (y ((x W(x,y) a" ($y (x W(x,y) Note: Equivalent to #10 16. "x $y (W(x,y) Every student from this class missed an Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" "x ("y W(x,y) a" ($x "y W(x,y) Note: Equivalent to #4 {No student watched every Eagles game last season; OR: For every student, there is an Eagles game they did not watch} 17. $y "x (W(x,y) There is an Eagles game that no one watched. Here are equivalent forms, by DeMorgan's Law a" $y ($x W(x,y) a" ("y $x W(x,y) Note: Equivalent to #6 18. "x"y (W(x,y) No student watched any Eagles game last season. Here are equivalent forms, by DeMorgan's Law a" "x ($y W(x,y) a" ($x $y W(x,y) Note: Equivalent to #2 Every student in this class missed watching every Eagles game last season. 1.5 Rules of Inference Valid arguments in propositional logic p ! q p . ( q Definitions: argument - sequence of propositions premises - all the propositions in the sequence except the final one conclusion - the final proposition in the sequence argument form - sequence involving propositional variables valid - an argument form is valid if conclusion follows from premises, no matter what values the variables have. conclusion follows from premises - conclusion is true if all premises are true Rules of inference for propositional logic Study Table 1 Examples 1, 3, 4, 5 Using rules of inference to build arguments Example 6 Hypotheses: H1: (p ( q H2: r ( p H3: (r ( s H4: s ( t Argument: 1: (p ( q H1 2: (p Simp (1) 3: r ( p H2 4: (r MT (2,3) 5: (r ( s H3 6: s MP (4,5) 7: s ( t H4 8: t MP(6,7) Example 7 Hypotheses: H1: p ( q H2: (p ( r H3: r ( s Argument: 1: p ( q H1 2: (q ( (p Contrapos (1) 3: (p ( r H2 4: (q ( r HypSyl (2,3) 5: r ( s H3 6: (q ( s HypSyl (4,5) Resolution ((p ( q) ( (~p ( r)) ! (q ( r) Clause - disjunction of variables or their negations Resolvent - conclusion of application of resolution rule Fallacies Affirming the conclusion Denying the hypothesis Rules of inference for quantified statements Study Table 2 Examples 12 & 13 Example 12 Premises: P1: (x (D(x) ( C(x)) P2: D(Marla) Argument: 1: (x (D(x) ( C(x)) P1 2: D(Marla) ( C(Marla) UI (1) 3: D(Marla) P2 4: C(Marla) MP (2,3) Example 13 Hypotheses: P1: (x (C(x) ( (B(x)) P2: (x (C(x) ( P(x)) Argument: 1: (x (C(x) ( (B(x)) P1 2: C(a) ( (B(a) EI (1) 3: C(a) Simp (2) 4: (x (C(x) ( P(x)) P2 5: C(a) ( P(a) UI (4) 6: P(a) MP (3,5) 7: (B(a) Simp (2) 8: P(a) ( (B(a) Conj (6,7) 9: (x (P(x) ( (B(x)) EG (8) Combining rules of inference for propositions and quantified statements Universal modus ponens Universal modus tollens Summary of Valid Rules of Inference (Valid Argument Forms) Modus Ponens p p ! q ( q Modus Tollens (q p ! q ( (p Hypothetical Syllogism p ! q q ! r ( p ! r Disjunctive Syllogism p ( q (p . ( q Addition p . ( p ( q Simplification p ( q ( p Conjunction p q ( p ( q Resolution p ( q (p ( r ( q ( r Universal Instantiation (x P(x) ( P(c) for any element c Universal Generalization P(c) for an arbitrary c ( (x P(x) Existential Instantiation (x P(x) ( P(c) for some element c Existential Generalization P(c) for some element c ( (x P(x) Universal Modus Ponens (x (P(x) ! Q(x)) P(a), where a is any element in the domain ( Q(a) Universal Modus Tollens (x (P(x) ! Q(x)) (Q(a), where a is any element in the domain ( (P(a) Summary of Fallacies (Invalid Argument Forms) Affirming the conclusion q p ! q ( p Denying the hypothesis (p p ! q ( (q Unwarranted addition p . ( p ( q Unwarranted simplification p ( q ( p Unwarranted Universal Generalization P(c) for a particular c ( (x P(x) Existential Instantiation (x P(x) ( P(c) for a particular element c Universal Affirming the conclusion (x (P(x) ! Q(x)) Q(a), where a is any element in the domain ( P(a) Universal Denying the Hypothesis (x (P(x) ! Q(x)) (P(a), where a is any element in the domain ( (Q(a) 1.6 Introduction to Proofs Terminology Theorem statement that can be proven to be true. Propositions, facts, results less important true statements. Proof valid argument that establishes truth of a theorem. Axiom, postulate a statement taken to be true, though not proven (e.g., Appendix 1) Lemma intermediate result proven, then used in proof of a theorem. Corollary a theorem that can be established directly as the result of another theorem Conjecture statement thought to be true, but not proven to be, E.g., Collatz Conjecture, twin primes conjecture, Goldbach's conjecture Definitions Even integer n is even if ( integer k, s.t., n = 2k. Odd integer n is odd if ( integer k, s.t., n = 2k+1. Rational number real number r is rational if ( integers p,q, q `" 0, s.t., r = p/q. Irrational number real number r is irrational if it is not rational. FOREWORD: QUANTIFIERS, UI, UG Quantifiers  yes or no? :: p. 76  use of UI followed by UG requires choice of arbitrary element.  this is not the same as choosing any specific element. Fallacious proof To Prove: All integers are even. Proof: UI: Choose any element of the domain, say 44. Proof step: 44 = 2*22; therefore 44 is even. UG: Since true of element chosen, it is true for all elements; therefore all integers are even! Analysis: The UI/UG combination requires choice of arbitrary element; choosing a specific element, even if chosen at random, does not satisfy that requirement. 34oru̼iXE?2h)L2h_CJKHaJ h_CJ%hX`hB*CJOJQJaJph hh0JCJOJQJaJ4jh0h0B*CJOJQJUaJph(jhB*CJOJQJUaJphhB*CJOJQJaJph%hX`hAB*CJOJQJaJphh8B*CJOJQJaJph%hX`h8B*CJ,OJQJaJ,phhlB*CJ,OJQJaJ,phh8B*CJ,OJQJaJ,ph4o 0 ; G S l   < c  gdgdK6gdD4gdRgd_gd$a$gd@  0 ; G S T c l        yncյ[hCJaJ jhxCJaJ jhxCJaJ jhxCJaJ jhxCJaJ jhxCJaJ jhxCJaJhxCJaJhD4CJaJhRhD4CJ aJ hD4CJhRhD4CJ$OJQJaJ$ hRCJh_h8CJOJQJaJh@_CJOJQJaJh,h_CJ#  * + , / 0 2 ; H I J M N P b p q r t u w $ 𿴿}} jhK6CJaJhhK6CJaJ jhCJaJhhCJaJ jhCJaJ jhK6CJaJhK6CJaJ jhxCJaJ jhxCJaJ jhxCJaJhxCJaJhD4CJaJhCJaJ1 $ T  K ` o  I j $IfgdqgdRgdD4gdK6gd N [ \ ` f g h j k l m w    ' ( xj jhphRCJ$aJ$ jhphRCJ$aJ$hphRCJ$aJ$hRhRCJ aJ hRhD4CJ aJ hRCJ jhK6CJaJ jhK6CJaJ jhK6CJaJhhK6CJaJ jhCJaJhh6CJaJhCJaJhK6CJaJ% yy $Ifgdq}kd$$Ifl0t t0644 laytq yy $Ifgdq}kd#$$Ifl0t t0644 laytq }}ttttttt $IfgdqgdR}kd$$Ifl0t t0644 laytq    )FUVWXYZ[\g緬hy{CJaJh"{hy{CJaJhRhR>*CJaJhRCJaJh@_hRCJ aJ hRCJ jhphRCJ$aJ$ jhphRCJ$aJ$ jhphRCJ$aJ$hphRCJ$aJ$ jhphRCJ$aJ$4  $Ifgdqkd5$$Ifl@֞d4 44 t0644 laytq#(-2 $Ifgdq23:  $Ifgdqkd$$Ifl@֞d4 44 t0644 laytq:=BGLQV $IfgdqVW[  $Ifgdqkd$$Ifl@֞d4 44 t0644 laytq[^chmrw $Ifgdqwx|  $Ifgdqkd$$Ifl@֞d4 44 t0644 laytq| $Ifgdq gdRkdE$$Ifl@֞d4 44 t0644 laytq )FS]g $Ifgd"{ $Ifgdq $IfgdRgdR  /0123456789:;<=>TUVWXYZ[\]^_`abcyz˾h)L2h CJKHaJ h CJh@_hD4CJ aJ hRCJhphy{CJ$aJ$h"{hy{CJaJhy{CJaJH $Ifgd"{Ff# $Ifgdq !#%')+-/02468:< $IfgdqFf $Ifgd"{Ff <>@BDFHJLNPRTUWY[]_acegikmoq $IfgdqFf $Ifgd"{qsuwyz'3-.69<CI $Ifgd5[D $IfgdT+gdx'gd gdD4gdRFf $Ifgd"{$'3 -.9:<=?@AEFTXY\^_uwy{ɺ}uguu_uu_uu_h4^uCJ$aJ$ jhph5[DCJ$aJ$h5[DCJ$aJ$ jhph5[DCJ$aJ$ jhph5[DCJ$aJ$hph5[DCJ$aJ$h4^uCJaJhx'CJaJ hx'CJh.hx'CJ OJQJaJ hx'CJ OJQJaJ h CJh hx'CJOJQJaJh CJOJQJaJh,h CJ%IJQTY`eH????? $IfgdT+kda$$Ifl@rd4 4 t044 layt5[Defmpu|H????? $IfgdT+kd$$Ifl@rd4 4 t044 layt5[DH????? $IfgdT+kd$$Ifl@rd4 4 t044 layt5[DH????? $IfgdT+kdt$$Ifl@rd4 4 t044 layt5[D  "&?ENQ[_ejtw̨̝̗ h4^uCJ jh4^uCJ$aJ$ jhph4^uCJ$aJ$ jh4^uCJ$aJ$ jh4^uCJ$aJ$hph4^uCJ$aJ$ hx'CJhmCJ$aJ$h4^uCJ$aJ$h5[DCJ$aJ$hph5[DCJ$aJ$9HC::: $IfgdT+gdx'kd%$$Ifl@rd4 4 t044 layt5[D $Ifgd4^u $IfgdT+ $Ifgd5[D  $IfgdT+kd$$Ifl@֞A l* t0644 layt} ' $Ifgd4^u $IfgdT+'(/  $IfgdT+kd $$Ifl@֞A l* t0644 layt}/27>FKS $IfgdT+STX  $IfgdT+kd!$$Ifl@֞A l* t0644 layt}X[`dlqy $IfgdT+yz~  $IfgdT+kd"$$Ifl@֞A l* t0644 layt}~ $IfgdT+ gd4^ukd#$$Ifl@֞A l* t0644 layt}]iyhNfHvwgd4gdgdZgdx'gd4^u]iru  (*8:Gxy6 ִ޴ִ֣֩֩vhhx'6CJaJ hCJh.hx'CJ OJQJaJ hx'CJ OJQJaJ hZCJ jhZCJaJhZhx'6CJaJ jhZCJaJ jhZCJaJhZCJaJhx'CJaJh4^uhx'6CJaJ hx'CJh4^uCJaJ, LNfv=GkuvwskeVhWht!CJ OJQJaJ ht!CJh}CJaJhWh}CJ OJQJaJ hG^ h}h}CJOJQJh}CJOJQJaJh,h}CJh)L2h}CJKHaJ h}CJ h4CJh.hx'CJ OJQJaJ hx'CJ OJQJaJ hx'CJhCJaJ hCJhx'CJaJh4CJaJ CMtSir8f j gd*Xgdt!gd}iklr8jl&(*<>JLN`bprt ` h j ζz j"h}CJ$OJQJht!56CJaJht!ht!56CJaJ jht!CJaJht!ht!CJaJh*XCJH*aJh*Xh*XCJOJQJaJ j$h*XCJ$OJQJ j"ht!CJ$OJQJh}CJaJh*XCJaJht!CJaJ+j !(!!!!!."p""""#R##$^$$$$H%p%%%%&`&gd=gdCgdt!gdlygd} (!!!!!!!!!!!!!!!!!"" "*","."0"2"j"l"""""˦˳ˠvg˳g˳g jhlyCJ OJQJaJ  jht!CJ OJQJaJ ht!CJ OJQJaJ hWht!CJ OJQJaJ ht!CJ j$hlyCJ$OJQJ j"hlyCJ$OJQJ jhlyCJaJhlyCJaJ j"h}CJ$OJQJh}CJaJhmgh}CJ$OJQJ jh}CJaJ'"""""""# #V#X#t#v#x####$$$.$0$>$@$B$N$P$R$f$h$t$v$x$z$$$$$$$$$$$$$$$$$$$$%%%%%$%&%(%*%8%:%<%>%H%޷ j"hlyCJ$OJQJ jhlyCJaJ jhlyCJ OJQJaJ  j$hlyCJ$OJQJ jhlyCJ OJQJaJ hlyCJaJhlyhlyCJaJBH%n%p%%%%%&&&E&F&G&K&z&{&|&}&~&&&&&&&&&&&&&'T'\'''())ļwĴqih;gCJaJ hgCJ jhgCJaJ j"hgCJ$OJQJ j$h=CJ$OJQJ jh=CJaJ j"h=CJ$OJQJh=CJaJhgCJaJhWh=CJ OJQJaJ h=CJ OJQJaJ h=CJh*XhCCJOJQJaJhJCJOJQJaJ&`&&&&'T'\''()r){)))))3*P*u*}***<,D,---gd\pgd*YLgd;ggdggd=))E)S)r)s)t)u)v)))))))))))))u*}*******++<,D,----ztlf h2[CJh\pCJaJ h\pCJh*YLCJaJ h*YLCJh;gh;g6CJaJ jh;gCJaJ j"h;gCJ$OJQJ h;gCJ j$hgCJ$OJQJhghg6CJaJ jhgCJaJ j"hgCJ$OJQJhgCJaJh;gCJaJhgh;g6CJaJ$----- .!.;.C.Q.j.z......./!/)/9/Q/f/~/////gd2[gd\p-..0.;.C...!/)/~//W0f0s0t000000011&1'1(1S1[1f1g111111111111Ʒrrrjh,CJaJ j$hDCJ$OJQJhDhD6CJaJh\phD6CJaJ jhDCJaJ j"hDCJ$OJQJhDCJaJhWhDCJ OJQJaJ hDCJ OJQJaJ hDCJh\pCJaJ h\pCJ h2[CJh2[h2[6CJaJh2[CJaJ(/// 0$0=0W0f0t000$1d1}11111&2223N33334"4gdwgd,gdDgd\p1122222*2,2@2B2`2b22222222222233F3L3N3~333334"4J4L45"5ʾʾʸwowohwCJaJhWhwCJ OJQJaJ hwCJ OJQJaJ hwhwCJOJQJaJh,hwCJh)L2hwCJKHaJ hwCJh,h,6CJaJh,6CJaJ j"h,CJ$OJQJh,CJaJ j$h,CJ$OJQJ jh,CJaJ'"4L44445"5P5`5506X6h6687`7p778`889"999 :0::::gdw"5P5`5b5d5h5j55555555555555555666666*6,6F6H6J6X6h6j6l6p6r66666666666666666 7 77ǼǼǼǼǼǼǼ㠔㠼㠼㠼㠼hwCJ OJQJaJ  jhwCJ OJQJaJ  j$hwCJ$OJQJhlyhwCJaJ jhwCJ OJQJaJ  j"hwCJ$OJQJhwCJaJ hwCJhVhwCJOJQJaJ:77 7"72747N7P7R7`7p7r7t7x7z7777777777778888886888:8J8L8N88888888888899"9$9&9*9,9h!)hwCJaJ jhwCJaJ jhwCJ OJQJaJ  j$hwCJ$OJQJ j"hwCJ$OJQJ hwCJhwCJ OJQJaJ hlyhwCJaJ jhwCJ OJQJaJ hwCJaJ7,9T9V9X9h9j9l9~99999999999999999V:X:l:n::::::::::::::$;&;(;8;:;<;N;P;j;l;n;~;;;; j$hwCJ$OJQJ hwCJh!)hwCJaJ jhwCJaJ j"hwCJ$OJQJhlyhwCJaJ jhwCJ OJQJaJ hwCJ OJQJaJ  jhwCJ OJQJaJ hwCJaJ7:R;;;<<<=(=P=`====0>R>b>>>>(?H?n?????@%@gdYrGgdw;;;;;;;;;<<&<(<<<><V<X<l<n<p<<<<<<<<<<<<<<====(=N=P=`=޷ުޟުޟުގުށށުށުގufh*XhwCJOJQJaJhwCJOJQJaJ j$hwCJ$OJQJ hwCJh!)hwCJaJ jhwCJaJ j"hwCJ$OJQJhL3hw6CJaJhwCJ OJQJaJ  jhwCJ OJQJaJ hwCJaJhlyhwCJaJ jhwCJ OJQJaJ (`=====.>0>R>b>>>>>&?(?J?L?N?R?T?p?r?v?x?z?|?????????????@ @ @ @ @@@@@@&@'@)@*@+@-@.@Ŷݫݕݕݫݕݕݠݫݕݠݫݕݠݕ݊ݠݫݕ jhwCJaJ j$hwCJaJ j"hwCJaJ jhwCJaJhWhYrGCJ OJQJaJ hYrGCJ OJQJaJ hYrGCJ hwCJhwCJaJhWhwCJ OJQJaJ hwCJ OJQJaJ 6.@8@9@C@D@F@G@I@J@K@U@V@`@a@c@d@f@g@i@j@r@s@}@~@@@@@@@@@@@@@@@@@@AAA/A{h|z6CJaJh{u.h|z6CJaJh|zCJaJhWh|zCJ OJQJaJ h|zCJ OJQJaJ h|zCJhYrGCJaJ jhwCJaJ jhwCJaJ j$hwCJaJ j"hwCJaJ jhwCJaJhwCJaJ,%@B@_@|@@@@@AAB^BBCBCDCCD`DDDfEEEE2FFFGgd|zgdw/A0AkAlAAAAAABBBB B BBBBB^B`BBBC C"C$C&C(C*C.C0C2CC@CBCDCFCѵ~ob~ jh@mh|z5CJhH^h|zCJOJQJaJhh|zCJOJQJaJh|z5CJOJQJaJhXh|zCJOJQJaJh|zCJOJQJaJhXh|z5CJ OJQJaJ h]h|z56CJh|z56CJ h|zCJhlh|zCJaJh|zCJaJh-h|z6CJaJ&FCCD^D`DbDfDhDjDlDnDpDrDtD~DDDDDDDDDDDDDDDDDEEEE²²yyjah|z56CJhH^h|zCJOJQJaJh|z5CJOJQJaJhXh|zCJOJQJaJ jh@mh|z5CJhXh|z5CJ OJQJaJ  j"h|z5CJ OJQJaJ hDdh|z5CJ h|z5CJhVh|zCJOJQJaJh|zCJOJQJaJ h|zCJh|zCJOJQJaJ"EEEEEEEEEEEE2F4FFFFFFFGGGG G GGGGGG GGGG>H@HBHϳϏϳϏvg` h|z5CJhVh|zCJOJQJaJh|zCJOJQJaJ jh@mh|z5CJhH^h|zCJOJQJaJhh|zCJOJQJaJ h|zCJh|z5CJOJQJaJhXh|zCJOJQJaJh|zCJOJQJaJhXh|z5CJ OJQJaJ h|z56CJh]h|z56CJ%GGGG@HHHHI^II.JRJTJJ,KKKK@LbLL*MlMMM NbNNOgd|zBHFHHHJHLHNHPHRHTH^H`HbHfHhHjHnHpHrHtH~HHHHHHHHHIIIIIIII^I`III.Jɼ٭ɼ٭٠٠٭٠vghH^h|zCJOJQJaJhh|zCJOJQJaJh]h|z56CJh|z56CJ h|zCJh|z5CJOJQJaJhXh|zCJOJQJaJ jh@mh|z5CJhXh|z5CJ OJQJaJ h|zCJOJQJaJ j"h|z5CJ OJQJaJ hDdh|z5CJ(.J0J2J4J6J8J:J>JLJNJPJRJTJVJJJ,KKKKKKKKKKKK³¦‚vg`VF j"h|z5CJ OJQJaJ hDdh|z5CJ h|z5CJhVh|zCJOJQJaJh|zCJOJQJaJhH^h|zCJOJQJaJhh|zCJOJQJaJ h|zCJh|z5CJOJQJaJhXh|zCJOJQJaJh|zCJOJQJaJhXh|z5CJ OJQJaJ  jh@mh|z5CJh]h|z56CJh|z56CJKKKKKKKKKKKKKKKKKK@LBLDLFLHLJLNLPLRL\L^L`LbLLL(M*MlMnMpMrMtMvM˻ˮwhhH^h|zCJOJQJaJhh|zCJOJQJaJh]h|z56CJh|z56CJ h|zCJh|z5CJOJQJaJ jh@mh|z5CJ j"h|z5CJ OJQJaJ hXh|z5CJ OJQJaJ hDdh|z5CJhXh|zCJOJQJaJh|zCJOJQJaJ(vMxM|M~MMMMMMMMN NbNNNNNNNNNNNNNNNNNNNNNNNNOO2O4O6O\P³˜xkxkȳ jh@mh|z5CJhDdh|z5CJ h|z5CJhVh|zCJOJQJaJh|zCJOJQJaJhH^h|zCJOJQJaJhh|zCJOJQJaJ h|zCJh|z5CJOJQJaJhXh|zCJOJQJaJhXh|z5CJ OJQJaJ h|zCJOJQJaJ*O4OO\PPPQQQQQzRRSXSSSS2TTU&U(UUUXVVVW8Wgd|z\PPPPPPPPPPPPPPQQQQQQQQQQQQQQQQQQQQxRzRRSSɺɭɏɺɭɏvghVh|zCJOJQJaJh|zCJOJQJaJ jh@mh|z5CJhH^h|zCJOJQJaJhh|zCJOJQJaJh|z5CJOJQJaJhXh|zCJOJQJaJh|zCJOJQJaJhXh|z5CJ OJQJaJ h]h|z56CJh|z56CJ h|zCJ&SSSS S"S$S&S(S*S4S6S8SS@SBSDSFSHSJSTSVSXSSSSSSSSSSSSSSSS2T4TTҶަҶҙ~Ҷҙohh|zCJOJQJaJh]h|z56CJh|z56CJ h|zCJh|z5CJOJQJaJ j$h|z5CJ OJQJaJ hXh|zCJOJQJaJ jh@mh|z5CJh|zCJOJQJaJhXh|z5CJ OJQJaJ hDdh|z5CJ h|z5CJ)TTUUUU U UUUUU U"U$U&U(U*UUUUVVXVZV^V`VbVdVfVɹ낭vg`VhDdh|z5CJ h|z5CJhVh|zCJOJQJaJh|zCJOJQJaJhh|zCJOJQJaJh|z5CJOJQJaJhXh|zCJOJQJaJh|zCJOJQJaJhXh|z5CJ OJQJaJ  jh@mh|z5CJh]h|z56CJh|z56CJ h|zCJhH^h|zCJOJQJaJfVhVjVlVvVxV|VVVVVVVVVVVVVVWWWWWW"W$W&W(W2W4W6W8W:W*CJaJhd>*CJaJhdCJaJhWhdCJ OJQJaJ hdCJ OJQJaJ hdCJ hG^ hdhdCJOJQJ( gg.g8gHgbgghQhhhiRiZiiiiiiii jj$j0j@jPjcjrjjgddjjjj j!j,j-j0j>j@jEjFjHjIjUjVjjjkjwjxjjjjjjjjjjjjjjkkkkkkk#k%k,k-k9k:kk?kTkUkWkXkdkekgkhkkkkkkkkkkhdCJ OJQJaJ hdCJ jhdCJaJhHWhdCJOJQJaJhdCJOJQJaJ jhdCJaJhdCJaJ jhdCJaJCjjjjjjjjj kk%k4kOk_kykkkkkl.llmm2mfmmmngddkkkkkkkllll.l0lr\rlrrrrrss2sXsssssstt tgd[lgd-Mpppq qqqr rrrrr>r@rLrZr\rfrhrjrvrrrrrrrrrrrrrs sssss"s$s0s2sXsZsssssh-M>*CJaJ jh-MCJaJ j\h-MCJaJh-MCJaJh;h-M>*CJaJhh-MCJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJhWh[lCJ OJQJaJ h[lCJ OJQJaJ 1ssssssssssssssttttttttttt t3t4tBtCtHtJtKtNtStTtVtWtjtktvtwttttttǾ⭡Ǿ⭡ǂ⭡ jh-M>*CJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJ j\h-MCJaJh-M>*CJaJh;h-M>*CJaJ jh;h-M>*CJaJhh-MCJaJh-MCJaJ jh-MCJaJ. t3tCtNtWtjtwt~tttttttttuu,u?uYuvuuuuuuuvVvgd-Mtttttttttttttttttttttttttttuuuu uuuu+u,u?u@uXuYu^uuuvuȽ⦝zȽnzȽ❑ j"h-M>*CJaJ j\h-MCJaJ jh-M>*CJaJh;h-M>*CJaJh-M>*CJaJ jh-M>*CJaJ jh-MCJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJhh-MCJaJh-MCJaJ jh-MCJaJ+vu{u|u}u~uuuuuuuuuuuuuuuuuvv&vTvVv`vbvdvfvrvtvvvvvvvvwTwVw`wŽצŽםŽ{m{ם j"hsh-MCJaJhsh-MCJaJ j$h-MCJaJh;h-M>*CJaJh-M>*CJaJ j$h-M>*CJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJhh-MCJaJ j"h-MCJaJ j\h-MCJaJh-MCJaJ*VvtvvvvVwnwwwwTxnx~xxx.y*CJaJh-M>*CJaJ jh-M>*CJaJ j"hsh-MCJaJhsh-MCJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJhh-MCJaJh-MCJaJ j\h-MCJaJ$dyyyyyyyyyyyyyyyy z zz z%z&z1z2z7z8z;zz?zRzSzmznzszuzvzyz~zzzzzzzzzzzzzzӽӦӽ۽ӦӒӽ۽Ӧӽ۽Ӧ jh-M>*CJaJ jh-MCJaJh-M>*CJaJ j\h-MCJaJh;h-M>*CJaJhh-MCJaJ jh-MCJaJh-MCJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJ3Rznzyzzzzzzz{"{I{\{{ ||||}.}}}}~~$~,~_~~gdBDgd-Mzzzzzz{{{{!{"{'{({H{I{\{]{{{{| |*|~||||||||}} }}.}8}:}}}}}ȽⱨȽx⨜Ƚxl jh-M>*CJaJ j"hsh-MCJaJhsh-MCJaJ j\h-MCJaJh;h-M>*CJaJh-M>*CJaJ j$h-M>*CJaJhHPh-MCJ aJ h-MCJ aJ h-MCJ OJQJaJ h-MCJhh-MCJaJh-MCJaJ j"h-MCJaJ*}}}}}}}}}~~~#~$~,~X`kltxˀ̀ՀրހŻΨΑΨ΅ynyyeynyyhBD5CJaJ j$hBDCJaJh,mEhBD6CJaJh,mEhBD5CJaJhBDCJaJhWhBDCJ OJQJaJ hBDCJ OJQJaJ hG^ hBDhBDCJOJQJhVVhBDCJ hBDCJhBDCJaJ h-MCJhh-MCJaJ jh-MCJaJh-MCJaJ'~~1vX`lt6FjԂ 0t6>Ogd"Sgd-gdBD  $46FZԂ 0rtz҃56>rs܄݄ynn薇nnh,mEhBDCJaJh,mEhBD56CJaJhWhBDCJ OJQJaJ hBDCJ OJQJaJ hWh"SCJ OJQJaJ h"SCJ OJQJaJ h"SCJ j$h-CJaJh-6CJaJh-CJaJhBD5CJaJ hBDCJhBDCJaJhBD6CJaJ+Os~݄BPh%hQhZhahehnhhhViailiii1$5$7$8$H$`gd"S 1$5$7$8$H$gd"Sgd"SgdBDABRV[{hh%h,hPhQhYhZh`hahehihmhnhohyhhhhhhhhh˿ͮvhvhhvWvhW hBDh"SCJ KHOJQJaJ h"SCJKHOJQJaJ hBDh"SCJKHOJQJaJhBDh"SCJKHaJhBDh"SCJKHaJhBDh"SCJKHaJ hBDh"SCJKHOJQJaJh"SCJ OJQJaJ U h"SCJhhBD56CJaJhBDCJ OJQJaJ h,mEhBDCJaJhBDCJaJ"A correct proof using UI/UG: Prove: The sum of two odd integers is even. Proof: UI: Let: a = 2k + 1, where k is any integer b = 2 l + 1, where l is any integer Comment: Since we are using the definition of odd integer and k & l are any arbitrary integers, this sets the stage allowing us to use UG later in the proof. Then: Then: a + b = 2k + 1 + 2 l + 1 = 2(k + l +1) Let: m = k + l +1 Then: a + b = 2m, which is even by definition. UG: For all odd integers, a & b, a + b is even. Comment: We can apply UG here because a and b were chosen to be arbitrary odd integers. By using a representation which adheres strictly to the definition of odd integer, our representation fits all odd integers. And therefore, anything we derive as true of a and b is also true of all odd integers. Mathematicians shorthand: Because the above proof process is used so often, mathematicians usually omit mentioning all of the things that are obvious by virtue of their frequent use. Thus, the above proof can be stated much more succinctly, as below. 1. Prove: The sum of two odd integers is even. Proof: Let: a = 2k + 1 b = 2l + 1 Then: a + b = 2k + 1 + 2 l + 1 = 2(k + l +1) ( EVEN PROOF METHODS Direct Proof Direct proofs start with a proposition (mathematical fact) known to be true and proceed, step by step, to derive the conclusion directly. The above proof is a good example of direct proof. It starts with the definition of odd integer and then uses laws of arithmetic to derive other facts, leading eventually to the desired conclusion. Indirect Proof Proof by Contraposition Proof by contraposition can be used when the proposition to be proved is of the form: p ( q. Recall that the Law of Contraposition states that p ( q is equivalent to (q ( (p. Sometimes the latter is easier to prove than the former. A proof by contraposition proceeds by showing that if (q is true, then (p must also be true. Here is Example #3 from Rosen, p. 78. Prove: For integer n: 3n + 2 is odd ( n is odd. Prove contrapositive: For integer n: n is even ( 3n + 2 is even. Proof: Let: n = 2k (definition of even integer) Then: 3n+2 = 6k+2 = 2(3k+1) ( EVEN Indirect Proof - Proof by Contradiction Proof by contradiction is based upon the axiom that every proposition must be either True or False (Rosen, p. 1). Therefore, if we show that a proposition cannot be false, then it must be true. Here is Example #10 from Rosen, p. 80. Prove: (2 is irrational. Proof by contradiction: Assume: (2 is rational. Then: There exist integers p & q, q `" 0, s.t., (2 = p/q. WOLG, we assume p & q have no common factors since, any common factors can be eliminated by expressing p/q in lowest terms. By the laws of arithmetic: ((2)2 = (p/q)2 2 = p2/q2 2q2 = p2 Thus: p2 is even By Exercise 16 (to be done later): p is even By definition: p = 2k, for some integer k. Therefore: 2q2 = (2k)2= 4k2 q2 = 2k2 And so: q2 is even; and q is even. q = 2l for some l. But we now have a contradiction: Since p = 2k and q = 2l, they have a common factor, namely 2. x Therefore: our assumption that (2 is rational is false; and we have proven that: (2 is irrational. This proof can also be written in an abbreviated form, as below. Prove: (2 is irrational. Proof by contradiction: Assume: (2 is rational. Then: There exist integers p & q, q `" 0, s.t., (2 = p/q, with no common factors for p & q. By the laws of arithmetic: ((2)2 = (p/q)2 2 = p2/q2 2q2 = p2 (p is even, i.e., p = 2k, for some integer k. Then: 2q2 = (2k)2= 4k2 q2 = 2k2 (q is even, i.e., q = 2 l, for some integer l. Therefore: p and q have a common factor, namely 2. x Therefore: (2 is irrational. Mistakes in proofs: Division by zero Example #15, p. 83 Logical fallacies Affirming the conclusion, Example #16, pp. 83-84 Denying the hypothesis, Example #17, p. 84 Begging the question (circular reasoning), Example #18, p. 84 1.7 Proof Methods and Strategies PROOF METHODS Exhaustive Proof Examine all of a relatively small number of cases; show true to all. Prove: The only consecutive perfect powers less than 100 are 8 & 9. {Example 2, p. 87} Exhaustive proof: List all powers < 100: N N2 N3 N4 N5 N6 N7 1 1 1 1 1 1 1 2 4 8 16 32 64 3 9 27 81 4 16 64 5 25 6 36 7 49 8 64 9 81 Examine this list. The only consecutive integers in that list are 8 & 9. Proof by Cases: Use when no obvious way to prove for all values, but can individual cases readily provable. Caveat: Make sure all cases are considered. Prove: n2 e" n, for all integers. {Example 3, p. 88} Proof, by cases: Integers naturally fall into 3 categories: negative, zero, and positive. Case 1: n < 0. Then n = -k, for some k e" 1. And n2 = (-k)2 = k2 e" 1 > 0 > n. So n2 e" n. Case 2: n = 0. Then n2 = 02 = 0 = n. So n2 e" n. Case 3: n > 0. Then n e" 1. And n*n e" 1*n. So n2 e" n. Exhaustive Proof Errors 1. Draw a conclusion for some, but not all instances. No matter how many instances are considered, no conclusion is warranted unless all instances are considered. Mathematicians sometimes call this the " HYPERLINK "http://www.math.niu.edu/~rusin/known-math/96/smallnums" Law of Small Numbers". Example 8, p. 90. 2. Attempt proof by cases, but omit some cases. Example 9, p. 90. Existence Proofs - Constructive Provide an element a such that P(a) is true. Show: There is a positive integer that can be written as the sum of cubes of positive integers in two different ways. {Example 10, p. 91} Proof: 1729 = 103 + 93 = 123 + 13 Existence Proofs - Nonconstructive Prove that (xP(x) is true. Often this is done via proof by contradiction. I.e., derive a contradiction from ((xP(x). Show: There exist irrational numbers x and y such that xy is rational. {Example 11, p. 91} Proof: We know (2 is irrational. Consider (2(2. Either it is rational or irrational. Case 1: (2(2 is rational. Then let x = (2 and y = (2. Case 2: (2(2 is irrational. Then let x = (2(2 and y = (2. So xy = ((2(2)(2= (2(2*(2= (22= 2. So either in case 1 or in case 2 we have xy rational, though x and y are both irrational. Although we do not know which case meets the specification, we know that one must. Exercise: Use the calculator to determine which of the two cases meets the specification. Uniqueness Proofs There are two parts to uniqueness proofs: Existence: Show element with desired property exists. Uniqueness: Show (x `" y, x does not have desired property; or, show if x and y both have desired property, then x = y. Show: For odd integers a & b, a `" b, (! integer c, s.t. |a  c| =|b  c|. {Exercise 15, p. 103} Proof: Existence: We show existence constructively. WOLG, assume a > b. If |a c| = |b c|, then either a c = b c or a c = c b. But a c = b c ( a = b, so a c = c b. Reworking the equation: a c = c b a + b = 2c c = (a + b)/2 Finally, we know c is an integer since a+b, the sum of two odd integers, is even. Uniqueness: Solutions of linear equations are unique. Forward and Backward Reasoning: Start with what you want to prove and working backward derive the premises. If that succeeds, we construct the proof by reversing the reasoning steps. Caveat: This only works if at each step we produce statements that are equivalent, and therefore reversible. Examples 14 & 15, p. 95 illustrate this process. Adapting existing proofs: Often a known proof can be adapted to prove a similar (or parallel) conclusion. This is illustrated in Example 16, p. 96. Also, in  HYPERLINK "http://faculty.kutztown.edu/rieksts/125/hw/answers/1-6.html" 1.6 homework answers, the proof of Exercise 1 was adapted in the proofs of Exercises 2 and 6. Proof strategy in action On p. 97 Rosen presents many strategies for generating hypotheses and conjectures and for seeking proofs or counterexamples. Among others, this includes "trying it on for size," the method applied to  HYPERLINK "http://faculty.kutztown.edu/rieksts/125/hw/answers/1-6.html" Exercise 7 of 1.6hhhhhhh?iAiVi`iaikilimiiiiiiiiiiiiiiiiiiiiiiijjjjȷȫȚ򚷚剚xg hBDhyVCJKHOJQJaJ hBDhyVCJ KHOJQJaJ hBDh"SCJKHOJQJaJ hBDh"SCJKHOJQJaJh"SCJ OJQJaJ hBDh"SCJ KHOJQJaJ h"SCJaJhBDh"S5CJaJh"S5CJaJhBDh"SCJKHaJh"SCJKHOJQJaJ(iiiiijBkRklktkVl_lllllllllmmm$m,mgdBD`gdgdgd"S 1$5$7$8$H$gd"Sj*j,j:j;j@jAjkkkkBkJkQkRklktkUlVl_l`lalilllllllll˾˴~si]N]NhlhCJ OJQJaJ hCJOJQJaJhCJOJQJhlhCJaJhCJaJhcuhCJOJQJaJhCJOJQJaJ hCJhBDh"SCJKHaJh"SCJKHaJh"Sh"SCJKHaJ h"SCJhBDh"SCJKHaJh"SCJKHOJQJaJh"SCJ OJQJaJ h"SCJaJllllllmmmm#m$m,m}n~nnnnn o oooIoJo_oôω|vpfYfLfLf jhR~(CJKHaJhhR~(CJKHaJhR~(CJKHaJ hR~(CJ hBDCJhBDhCJKHaJhCJKHaJhWhBDCJ OJQJaJ hBDCJ OJQJaJ h"SCJhWh"SCJ OJQJaJ h"SCJ OJQJaJ hCJ j ahlhCJ$OJQJhlhCJ OJQJaJ hCJOJQJaJ,m~nnnn\o'p0p`pipppppppqqAqIqhrzr 1$5$7$8$H$gd]#gd]#gd`gd-gd- 1$5$7$8$H$gdR~(gdR~(gdBD 1$5$7$8$H$gd_o`obocodoeooooo&p'p0p7pTpUp_p`pippppppppppppp q qqqɽɽɓ{o{o_Y hCJ j ahlh-CJ$OJQJhCJOJQJaJhaflCJOJQJaJh-CJOJQJaJh-CJOJQJhlh-CJaJ jh-CJKHaJh-CJaJh-CJOJQJaJ h-CJhBDhR~(CJKHaJ jhR~(CJKHaJhR~(CJKHaJ jhR~(CJKHaJ"q@qAqIqfrhrzrrrrrrrss s>sssssRtStutvtxtyt|t}ttttttttttttttt߼߉zzzmzzmzzmzmzzmzh]#CJH*OJQJaJh-h]#CJOJQJaJh]#CJOJQJh]#CJOJQJaJh-h]#CJaJ" jhclh]#CJOJQJaJh]#CJOJQJaJhBDh]#CJKHaJh]#CJKHaJ h]#CJhWhBDCJ OJQJaJ hBDCJ OJQJaJ *zrrrrs(s>sstStstttttttttu$u6u@uMuiu}uuv"v`gd]#gd]#ttttttttttttt&u'u(u+u/u0u2u4u5u6u7u8u9uu?u@uNuOuPuQuhuiujunuoupuyuzu{u|u}uuuuuuv׷צ׎׷h]#CJOJQJh]#CJ KHOJQJaJ h]#h]#CJ KHOJQJaJ hBDh]#CJ KHOJQJaJ hyVh]#CJOJQJaJh]#CJOJQJaJh-h]#CJOJQJaJh]#CJH*OJQJaJ2vvv v"v$vLvNvvvvvvwxwwwwwwwxxxxNxxxxxDyFyJyLyRyTyZy\y^y`ydylynyrytyvyྴĐtttth]#CJH*OJQJaJh-h]#CJOJQJaJh-h]#CJaJh]#CJOJQJaJhBDh]#CJKHaJh]#CJKHaJ h]#CJ" jhclh]#CJOJQJaJh]#CJOJQJh]#CJOJQJaJ%h 4h]#B*CJ$OJ QJ aJ$ph,"vvvvxwwwwwx8xNxxy@y`yvyyy zzz{&{\{l{gdBDgdD`gd]# 1$5$7$8$H$gd]#gd]#vyzy|y~yyyyyyzzz zzzzzz z"z$z&z,z0z2z4z6zbzdzfzzzzzzzz{{~~ta%h 4h]#B*CJ$OJ QJ aJ$phh]#CJOJQJ hBDhDCJ KHOJQJaJ hDhDCJ KHOJQJaJ h]#CJH*OJQJaJh-h]#CJOJQJaJh]#CJOJQJaJ j ahlhDCJ$OJQJhDCJH*OJQJaJh-hDCJOJQJaJhDCJOJQJaJ&{{{({*{J{\{l{|{{{{{ |||"|=|D|H|R|f|g|h||||||||||||||̝yrl`h]CJ OJQJaJ h]CJ hG^ h,Ph,PCJOJQJ h,PCJhBDhBDCJaJh;CJaJhBDCJaJhWhBDCJ OJQJaJ h;CJ OJQJaJ hBDCJ OJQJaJ hBDCJ h]#CJ" jhclh]#CJOJQJaJh]#CJOJQJh]#CJOJQJaJ#l{{{{{ |;|g|||||||}}}`}j}}}}}`gdvOgdvO 1$5$7$8$H$gdvO 1$5$7$8$H$gdMgdMgd]gd,PgdBD||}}}_}`}a}i}j}q}}}}}}}}}}~~~~~~~~~ ~ ~ ~ ~ ~~~~~~Ÿ{{na{na{na{na{na{nhvOhvOCJOJQJhvOCJH*OJQJaJhvOCJOJQJhvOCJOJQJaJhvOCJaJhvOCJOJQJaJhvOhvOCJKHaJ hvOCJhUhvOCJKHaJhBDhMCJKHaJhMCJKHaJhMhMCJ$OJQJaJ$ hMCJhWh]CJ OJQJaJ &}}~"~3~>~G~M~S~Y~`~f~o~~~~~9eo0Xj&`gd7gd7 1$5$7$8$H$gd7 1$5$7$8$H$gdvOgdvO~~f~o~s~~~~~89@KNdefnovwVݺuobVNENh7CJH*aJh7CJaJh7CJOJQJaJhvOh7CJKHaJ h7CJhUh7CJKHaJhBDh4CJKHaJh4h456CJKHaJ h4h4CJKHOJQJaJhvOCJKHaJh4CJKHaJhMhvOCJ$OJQJaJ$hvOCJOJQJ hvOCJhvOCJOJQJaJhvOhvOCJH*OJQJaJVXj&8@N^<>FHfht0>@Pȼxlxh7CJ$OJQJaJ$hMh7CJ$OJQJaJ$hrCJOJQJaJhrCJOJQJ hrCJhrCJH*OJQJaJhrCJOJQJaJhR#CJOJQJaJhR#CJOJQJaJhR#CJOJQJ hR#CJh7CJOJQJ h7CJh7CJOJQJaJ&&8^ށ.\tȂ@PԄ2:Zgdsqgdl 1$5$7$8$H$gdl 1$5$7$8$H$gd7gd7gdrgdR#PT.1KuvЄф҄ӄ12:<DIYZb´£܇t܇n_S_S_nhsqCJ$OJQJaJ$hMhsqCJ$OJQJaJ$ hsqCJhl56CJKHaJ hlCJhBDhlCJKHaJh ~sh ~s0JCJKHaJ!j$h ~sCJKHUaJjh ~sCJKHUaJh ~sCJKHaJhlhl56CJKHaJhlCJKHaJh7CJKHaJhlh756CJKHaJZb$-4S[~NclsLJЇgdfH`gddf\ 1$5$7$8$H$gddf\gddf\`gdygdy 1$5$7$8$H$gdy 1$5$7$8$H$gdsqgdsqb#$-8ABFGLMQRS[]ej}~¶㬶~~tgtZgt jhdf\CJKHaJ j$hdf\CJKHaJhdf\CJKHaJhdf\CJ$OJQJaJ$hMhdf\CJ$OJQJaJ$ hdf\CJhyCJH*OJQJaJhyCJOJQJhyCJOJQJaJhyCJaJhyCJOJQJaJhvOhyCJKHaJ hyCJhUhyCJKHaJhsqCJKHaJ ?@bclwƇLJЇՇ܇݇އ߇̷~nh\~PhR#CJOJQJaJhdf\CJOJQJaJ hfHCJhR#hdf\CJH*OJQJaJhdf\CJH*OJQJaJ jhdf\CJH*OJQJaJ" jhclhdf\CJOJQJaJhdf\CJOJQJhdf\CJOJQJaJhdf\CJH*aJhdf\CJaJhdf\CJOJQJaJhvOhdf\CJKHaJ hdf\CJhUhdf\CJKHaJ    "#$%&'7FGHIJSTVW]^bcdefghilmnoqrsvⷪ➌|ofo|o|o|o|ohR#hfHCJhfHCJH*OJQJaJ jhfHCJH*OJQJaJ" jhclhfHCJOJQJaJhfHCJOJQJaJhR#CJH*OJQJaJ jhR#CJH*OJQJaJhR#CJOJQJaJ hR#CJhR#hR#CJhR#CJOJQJaJ" jhclhR#CJOJQJaJ( 7W~6@HЊJ^gd&>1gdygd!l 1$5$7$8$H$gdy 1$5$7$8$H$gdugdu 1$5$7$8$H$gdfHgdfHgdR#vwxy}~567?@JHXⶩƜvgvg]QEhuCJOJQJaJhuCJOJQJaJhuCJKHaJhMhuCJ$OJQJaJ$huCJ$OJQJaJ$ huCJhfHCJaJhfHCJOJQJaJhvOhfHCJKHaJhUhfHCJKHaJhR#hfHCJH*OJQJaJ hfHCJhR#hfHCJhfHCJH*OJQJaJhfHCJOJQJaJ" jhclhfHCJOJQJaJXnz|JL\^j $,6nrƹ{ukauUI:htNh&>1CJOJQJaJh&>1CJOJQJaJh&>1CJOJQJaJh&>1CJOJQJhyCJOJQJ h&>1CJhyCJOJQJaJh!lCJaJh!lh!lCJaJ j$hyCJaJhyCJaJhyCJOJQJaJhvOhyCJKHaJ hyCJhUhyCJKHaJ j"huCJOJQJaJhuCJOJQJaJhuCJOJQJaJ Yn-ō͍3;U]gd>gdu 1$5$7$8$H$gds 1$5$7$8$H$gd0gd0gdtNgd&>1`gdyrȌɌčō͍,÷ӫvve[U huCJhsCJKHaJ huhsCJ KHOJQJaJ huCJKHaJh0CJKHaJhMh0CJ$OJQJaJ$h0CJ$OJQJaJ$ h0CJh&>1CJOJQJaJh&>1CJOJQJaJ h&>1CJh&>1CJOJQJhtNCJOJQJaJ" jhtNhtNCJOJQJaJhtNhtNCJOJQJaJ23;TU],-.BCɑʑˑߺwh^P^h>0JCJKHaJ'j%h0h0CJKHUaJjh>CJKHUaJh>CJKHaJhMh>CJ$OJQJaJ$h>CJ$OJQJaJ$ h>CJhuhuCJ OJQJaJ huCJ OJQJaJ ]MU^f$,@DFJ 1$5$7$8$H$gdG" 1$5$7$8$H$gdsgds 1$5$7$8$H$gdKagdKa 1$5$7$8$H$gd>ˑܑݑ%&'9:MU]^f#$,"$ŶѬ{ŶѬŶѬmm`ѬmhshsCJKHaJhsCJ KHOJQJaJ hKahs0JCJKHaJ'j''h0h0CJKHUaJjhsCJKHUaJhsCJKHaJhMhsCJ$OJQJaJ$hsCJ$OJQJaJ$ hsCJhKaCJKHaJUjhKaCJKHUaJhKahKa0JCJKHaJ!. In general, before we attempt a proof we should look at enough examples to convince us that what we are attempting to prove is indeed true. Sometime this may surprise us (see immediately below). Look for counterexamples: Sometimes, in the process of looking at examples, we will be surprised to find an example for which the proposed proposition does not hold. This will, of course, be a counterexample and will enable us to disprove by counterexample.  HYPERLINK "http://faculty.kutztown.edu/rieksts/125/hw/answers/1-6.html" Exercise 38 of 1.6 illustrates this. Tilings: Tiling problems can be fiendishly difficult, but sometimes a single observation can lead to a simple and easy solution. Examples 18-22, pp. 98-100 illustrate. Role of Open Problems There are some fascinating stories in the history of mathematics involving attempts to solve open problems. Among these are: Fermat's Last Theorem and the Collatz Conjecture. One of keen interest to computer scientists is this question: is P = NP, where P is the set of problems that can be solved in polynomial time and NP is the set of problems which can be solved in non-deterministic polynomial time. Most computer scientists and mathematicians think that $%+-35vxy NR>@BFHLNRTXZ\^᯼ἣxh0mHnHuh;gjh;gUhhn hhnKHh@jh@UhsCJKHaJUhshG"CJKHaJhG"CJKHaJhshsCJKHaJhsCJ KHOJQJaJ hG"CJ KHOJQJaJ hG"hG"CJ KHOJQJaJ #P `" NP, and that problems in the class NP require exponential (or worse) time. We will look at some exponential and factorial algorithms later in this course.      PAGE \* MERGEFORMAT 25 JLPRVXZ\ 1$5$7$8$H$gdG"$a$ ! 200P/ =!"#$%` DyK F chap01.doc$$If!vh55#v:V l t065ytq$$If!vh55#v:V l t065ytq$$If!vh55#v:V l t065ytq$$If!vh5555555#v#v:V l@ t0655ytq$$If!vh5555555#v#v:V l@ t0655ytq$$If!vh5555555#v#v:V l@ t0655ytq$$If!vh5555555#v#v:V l@ t0655ytq$$If!vh5555555#v#v:V l@ t0655ytq$$If!vh5P5P5555555 5 5 5 5 5 5555#vP#v #v :V l@ t065ytq\kd $$Ifl@֐4tT 4t t06HHHH44 laytq$$If!vh5P5P5555555 5 5 5 5 5 5555#vP#v #v :V l@ t065ytq\kd $$Ifl@֐4tT 4t t06HHHH44 laytq$$If!vh5P5P5555555 5 5 5 5 5 5555#vP#v #v :V l@ t065ytq\kd$$Ifl@֐4tT 4t t06HHHH44 laytq$$If!vh5P5P5555555 5 5 5 5 5 5555#vP#v #v :V l@ t065ytq\kdq$$Ifl@֐4tT 4t t06HHHH44 laytq$$If!vh5P5P5555555 5 5 5 5 5 5555#vP#v #v :V l@ t065ytq\kd$$Ifl@֐4tT 4t t06HHHH44 laytq$$If!vh55555#v#v:V l@ t055yt5[D$$If!vh55555#v#v:V l@ t055yt5[D$$If!vh55555#v#v:V l@ t055yt5[D$$If!vh55555#v#v:V l@ t055yt5[D$$If!vh55555#v#v:V l@ t055yt5[D$$If!vh55555*55#v#v#v#v*#v#v:V l@ t065555*55yt}$$If!vh55555*55#v#v#v#v*#v#v:V l@ t065555*55yt}$$If!vh55555*55#v#v#v#v*#v#v:V l@ t065555*55yt}$$If!vh55555*55#v#v#v#v*#v#v:V l@ t065555*55yt}$$If!vh55555*55#v#v#v#v*#v#v:V l@ t065555*55yt}DyK yK http://www.math.niu.edu/~rusin/known-math/96/smallnumsyX;H,]ą'cDyK yK F../hw/answers/1-6.htmlyX;H,]ą'cDyK yK F../hw/answers/1-6.htmlyX;H,]ą'cDyK yK F../hw/answers/1-6.htmlyX;H,]ą'c0L@L Normal1$5$7$8$H$KH_HmH sH tH DA@D Default Paragraph FontVi@V  Table Normal :V 44 la (k@(No List *W@* Strong5\^^@^ Normal (Web)dd1$5$7$8$H$[$\$ CJKHaJ4@4 Header  !4 @"4 0Footer  !4U@14 Pp Hyperlink >*ph,OA, 1 yshortcuts.OQ. TE1 sense_break2Oa2 TE1 sense_contentzsz J Table Grid7:V01$5$7$8$H$0O0 ;g0 Char CharKHh| z z z z z z z z z z z z z z z z z z z z z z z z z z U;$!%)/96m<ADeG4JMFSX^@cglqyh|4  K ! -  0A \#U4o0;GSl<c$TK`oIj#(-23:=BGLQVW[^chmrwx| )FS]g !#%')+-/02468:<>@BDFHJLNPRTUWY[]_acegikmoqsuwyz ' 3 - . 6 9 < C I J Q T Y ` e f m p u |      ' ( / 2 7 > F K S T X [ ` d l q y z ~ ] i y 4VHvwCMtSir3Kp5K8Pq /UZ`T\r{3Pu}<D !;CQjz ! ) 9 Q f ~ !$!=!W!f!t!!!$"d"}"""""#4#H#|######$$=$H$k${$$$$$ %%&%B%%%%%&"&4&{&&&&& 'W'_'k'''''?(G(~((((((( ))#)P)b)j)))))))))*4*Q*n*****+++,?,`,r,s,,,-$-=------,.M._.`..../-/N/_//////F0g000001#1f111112/2R2k222 313R333334/4\4}4444405Q5d5e5555 696Z6m6n6666 79777788Z8{8888+9v99999 :6:Z:s::::: ;7;Z;r;;; <<<L<m<<<<<= =:=[====>>'>/>V>]>h>m>u>>>>"?^???#@+@V@e@z@@@@@@@@AA!A4ACAVAfAxAAAAAAAAAAB B0BJBYBsB{BBBBBC&C0CJCbCjCCCCCCCCD(DID]DwDDDDDDDDE,EFE`EvEEEEEF3FLFTFFFFFFFFFFFGG/G:GEGRGeG|GGGGGGGGGGHH#H0H7H>HKH^HjHuHHHHHHHHI/I>IQIlIyIIIIIIJJ4JdJpJJJJJJJ&K6KPKWKbKkK{KKKKKKKKK L'L2L;LNLtLLLLLLMM9MOMMMMMMNN4NONWNcNkNNNOpOO PNPPPPPPPPP'Q/Q?QQQQQQQR#ReRRRRRRSFSSSSTITYTaT~TTTTTTTTUUUUUU VV@VDVtVWWWWXXXXXYY Y+YZYbYpYxYYYZZ[[[\\\\ ]]]$]I]T]r]z]]]^^^^^^^_4_u______``9`D`X`u```````aDaSaaaaab b)bAbMb^bibbbbbb5c@cRccccccc dd%d9dKd}dddee&e.e@BDFHJLNPRTUWY[]_acegikmoqsuwyz ' 3 - . 6 9 < C I J Q T Y ` e f m p u |      ' ( / 2 7 > F K S T X [ ` d l q y z ~ ] i y 4VHvwCMtSir3Kp5K8Pq /UZ`T\r{3Pu}<D !;CQjz ! ) 9 Q f ~ !$!=!W!f!t!!!$"d"}"""""#4#H#|######$$=$H$k${$$$$$ %%&%B%%%%%&"&4&{&&&&& 'W'_'k'''''?(G(~((((((( ))#)P)b)j)))))))))*4*Q*n*****+++,?,`,r,s,,,-$-=------,.M._.`..../-/N/_//////F0g000001#1f111112/2R2k222 313R333334/4\4}4444405Q5d5e5555 696Z6m6n6666 79777788Z8{8888+9v99999 :6:Z:s::::: ;7;Z;r;;; <<<L<m<<<<<= =:=[====>>'>/>V>]>h>m>u>>>>"?^???#@+@V@e@z@@@@@@@@AA!A4ACAVAfAxAAAAAAAAAAB B0BJBYBsB{BBBBBC&C0CJCbCjCCCCCCCCD(DID]DwDDDDDDDDE,EFE`EvEEEEEF3FLFTFFFFFFFFFFFGG/G:GEGRGeG|GGGGGGGGGGHH#H0H7H>HKH^HjHuHHHHHHHHI/I>IQIlIyIIIIIIJJ4JdJpJJJJJJJ&K6KPKWKbKkK{KKKKKKKKK L'L2L;LNLtLLLLLLMM9MOMMMMMMNN4NONWNcNkNNNOpOO PNPPPPPPPPP'Q/Q?QQQQQQQR#ReRRRRRRSFSSSSTITYTaT~TTTTTTTTUUUUUU VV@VDVtVWWWWXXXXXYY Y+YZYbYpYxYYYZZ[[[\\\\ ]]]$]I]T]r]z]]]^^^^^^^_4_u______``9`D`X`u```````aDaSaaaaab b)bAbMb^bibbbbbb5c@cRccccccc dd%d9dKd}dddee&e.e|?|A|B|D|E|F|G|d|e|f|i|00000000000000000000000000000000000000000000000000000000000 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 000000000000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000@0000000000000000000000000000000@000@000@000000Ȧ0@000Ǧ0 0 ---0   "H%)-1"57,9;`=.@/AFCEBH.JKvM\PSTfVXX|Z$\^r`bTd~fjkopstvu`wdyz}hjl_oqtvvy{|~VPbvXrˑ$CFGIMX]boprtuvxz|~ 2:V[w|<qIe'/SXy~j `&-/"4:%@GO8W_ gjnp tVvRz~Oi,mzr"vl{}&Z]JDHJKLNOPQRSTUVWYZ[\^_`acdefghijklmnqswy{}E/jujjttt9vvvrxxxh|XXXXX&)0!8@0(  B S  ?x=8l;fi|@fi|9*urn:schemas-microsoft-com:office:smarttagsplace \:<{~#GJ]kln79_ahjSUsu^`s{$$$$/%2%=%@%%%F&I&^&a&v&y&&&"'%':'='R'U't'w' ( ("(%(:(=([(^(j(m(y(|())))))))* ***%*(*.*1*B*E*K*N*_*b*h*k*|******++++e,k,l,o,,, - - --- -----U.X.Y.\....../ //Y/\///0000000000001111 2*272:2;2>2K2N2$3*3+3.333M4W4d4g4h4k4x4{44444Z5]5^5a55566 6 666g6j6667 7 7 77777 88888888888899':1:>:A:B:E:S:V:::(;2;?;B;C;F;L;R;S;V;<<<<<<<<<<<<<<==y==========+A/ABB=BCBfBlBBB#E'EEEDFKFFFJJUP\PPPPPQQiQlQuQxQ\\$_'_bb(l7lLlNlllllnnknmnpprrxx_zfz9|i|x~8:npdf&NOop$ &  )DLNSu|"T]lot'GJLWq{ NPJNSVsv46^aBEwztu!!!!(")"g"h"""""""0#3#7#8#x#{#$$$$ %%(%)%%%%%%%&&6&9&&&&&&& ''u'w'''''''\(^())))))))))**6*7*S*T*p*q***++m,o,------Z.\...Z/\///000011<2>2,3.333i4k444_5a5 6 6h6j6o66 7 7 888899C:E:::D;F;<<<<====W>X>^>_>k>l>>>>>>>#?+?_?d?????RATAtAvAAAFBHBoBqBCC-D/DNDPDbDdDEEEEKEMEeEgE|E~EEEFFFFFFFFFFGG4G5GLGMGGGGGGGGGGGHHHH5H6Hm#n&n#p%ppppprrvv9|i|::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::3 qqrr9|i|9|i| :$@ ) )s-< X=2UEO)!Y"om@ )Aoi7}SR{"4'-;=qr)Df d t cx  ! ( :9 Rd aJyV5}81;d' -Lx''.x)/t7k{s Ed*s>GtNTx&m?QK9 u G^ E3!/T!t!8 "G"O}"R#$$;$<$&3Y&vj&'R(R~():2)W*hf*+T+"+P+l+c,1TE1S1t1&34C4aJ4hk4q4e.6M6bc78C80e8?;`o; ==B>X>/g>g>(1@6L@_@Ky@7A.A9BcBCJ!C4PCD_PD5[DhRE.gEo F\FLF?XFgpF>_GYrGyG5G(ITIcJ7 J}AKvK LLL*YL &M-M*NOlOvO+9PMPPR7;S3eSvpSUVVVrVBWIW\>YBZdCZKW[i[\B\df\]_@_j`KaJb9[bb Icd !d:e;ef(f4gP6g;gPg$h.iii/kl l[lafln$mE>8D!lugyaCX@)fs>p]Jl7u%payoOb\plh(uax/ffH[_I]#I3mZrXp?MO :?u*_U8WHo(q,:X .(V+*7?BDV sobIwS>%&*X[(Zc!& R2[6w -/H14UWX`f7n@)i9$fJc+"W"6e#)3Bl\~QoaY~A^Q vou1?6i-3y "4~4(vc*Lok#(-23:=BGLQVW[^chmrwx| !#%')+-/02468:<>@BDFHJLNPRTUWY[]_acegikmoqsuwyz - . 6 9 < C I J Q T Y ` e f m p u |      ' ( / 2 7 > F K S T X [ ` d l q y z ~ ] rxy{zi|33 UColorPosColorSetStylePosćStyleSetЇ-1-1-1-1@rGsurr"#$%&'()+,-./0123456789:;<=>BCFGIJK?M?NiQiRaTa^a_BaBbBcBdghiopv{h|`@``0@``8@`` `"`$`L@`2`4`6`8`:`<`>`@`B`D`F`H`J`L`N`P`R`T`V`X`Z`\`^```b`d`f`@`l`@`r`@`v`x`@`|`@``@`@`r`@`v`x`z`@```@``@`@`Unknown Gz Times New Roman5Symbol3& z ArialEF Script MT BoldU.{ @CalibriCentury Gothic7&  Verdana;Bodoni MTA& Arial Narrow7F Mistral?Wingdings 3;Wingdings"Ah)⦩ &Ŗi?i?!xx2d{{ 3QHX(?-L2TitleOSK Oh+'0h   $ 0 <HPX`TitleOSK Normal.dot 3Microsoft Office Word@Ik@W8y@>F@n,i՜.+,D՜.+,D hp  Kutztown University?{' Title Titleh 8@ _PID_HLINKSA p6 ../hw/answers/1-6.htmlp6 ../hw/answers/1-6.htmlp6../hw/answers/1-6.html6m7http://www.math.niu.edu/~rusin/known-math/96/smallnumss. chap01.doc  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry FPy>@Data '1Table1WordDocument4SummaryInformation(DocumentSummaryInformation8CompObjq   FMicrosoft Office Word Document MSWordDocWord.Document.89q՜.+,D՜.+,D hp  Kutztown University?{' Title Titleh 8@ _PID_HLINKSA p6 ../hw/answers/1-6.htmlp6 ../hw/answers/1-6.htmlp6../hw/answers/1-6.html6m7http://www.math.niu.edu/~rusin/known-math/96/smallnumss. chap01.doc