第 1 页
MATH 221, Formal Logic and Discrete Mathematics Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. --Brian W. Kernighan Table Of Contents Chapter 1: Logic and Proofs 1 Chapter 2: Sets, functions, sequences and sums 13 Chapter 3: Algorithms, the integers and matrices 20 Chapter 4: Induction and recursion 35 Chapter 5: Counting 44 Chapter 9: Graphs 50 Chapter 10: Trees 61 Chapter 1: Logic and Proofs Section 1: Propositional logic proposition - a declarative statement that is either true or false, but not both {p, q, r, s} - typically represent a proposition Logical Operators negation: not p read, not p true when p is false connectives: conjunction pq read, p and q true when both p and q are true disjunction pq read, p or q true when either p or q are true exclusive or pq read, p x-or q true when p q F but p qT conditional: implication p→q read, p implies q true when p F or p qT biconditional: bi-implication p q read, p if and only if q true when p → q T and q → p T Important Conditional Constructs statement p → q contrapositive q → p statement p → q converse q → p statement p → q inverse p → q Order of operations
第 2 页
1. ( ) 2. 3. 4. 5. → 6. Truth Tables Truth tables start with a systematic and exhaustive list of the possible truth values for each proposition, typically followed by the resulting truth value of the compound propositions leading ultimately to the final truth value. Example (pq)→ r There are three variables (simple propositions). There is a compound or, the negation of r and the complete statement. p q r p q r (pq)→ r T T T T F F T T F T T T T F T T F F T F F T T T F T T T F F F T F T T T F F T F F T F F F F T T Bit strings consist of a sequence of 0's and 1's, each of which is a bit. The length of the string is the number of bits. By convention 1 denotes true and 0 denotes false. Bitwise operations require stings of the same length, the propositions are evaluated on bits in corresponding positions in the strings. Example 0 1 1 1 String 1 1 0 1 1 String 2 0 0 1 1 And 1 1 1 1 Or 1 1 0 0 Xor HW 18. first determine p and q a. Promotion - p, Wash Car - q. If you want to get promoted, then you must wash the boss's car. b. Winds - p, thaw - q. If the winds are from the south, then there is a spring thaw. c. Bought - p, warranty - q. If you bought the computer less than a year ago, then the warranty is good. d. Cheats - p, caught - q. If Willy cheats, then he gets caught. e. Access - p, pay - q. If you access the website, then you must pay a subscription fee. f. Know - p, elected - q. If you know the right people, then you will be elected. g. Boat - p, sick - q. If Carol is on a boat, then she gets seasick.
第 3 页
46. Let p denote truth teller, and r denote truthful response to question. a. p r actual r T F p → rF F T p → r F b. If a truth teller is asked, do you tell the truth, the response is, yes. If a liar is asked the same question the answer will also be yes. So ask either one, what would you say, if I asked you if you tell the truth? The truth teller still says yes, but the liar must now say no. 62. Truth table approach. Let each be denoted by their first initial. The first compound proposition that is false removes that combination. A H K R V K or H R xor V if A then R (V and K) or (not V and not K) if H then (A and K) Truth T T T T T TRUE FALSE TRUE TRUE TRUE FALSE T T T T F TRUE TRUE TRUE FALSE TRUE FALSE T T T F T TRUE TRUE FALSE TRUE TRUE FALSE T T T F F TRUE FALSE FALSE FALSE TRUE FALSE T T F T T TRUE FALSE TRUE FALSE FALSE FALSE T T F T F TRUE TRUE TRUE TRUE FALSE FALSE T T F F T TRUE TRUE FALSE FALSE FALSE FALSE T T F F F TRUE FALSE FALSE TRUE FALSE FALSE T F T T T TRUE FALSE TRUE TRUE TRUE FALSE T F T T F TRUE TRUE TRUE FALSE TRUE FALSE T F T F T TRUE TRUE FALSE TRUE TRUE FALSE T F T F F TRUE FALSE FALSE FALSE TRUE FALSE T F F T T FALSE FALSE TRUE FALSE TRUE FALSE T F F T F FALSE TRUE TRUE TRUE TRUE FALSE T F F F T FALSE TRUE FALSE FALSE TRUE FALSE T F F F F FALSE FALSE FALSE TRUE TRUE FALSE F T T T T TRUE FALSE TRUE TRUE FALSE FALSE F T T T F TRUE TRUE TRUE FALSE FALSE FALSE F T T F T TRUE TRUE TRUE TRUE FALSE FALSE F T T F F TRUE FALSE TRUE FALSE FALSE FALSE F T F T T TRUE FALSE TRUE FALSE FALSE FALSE F T F T F TRUE TRUE TRUE TRUE FALSE FALSE F T F F T TRUE TRUE TRUE FALSE FALSE FALSE F T F F F TRUE FALSE TRUE TRUE FALSE FALSE F F T T T TRUE FALSE TRUE TRUE TRUE FALSE F F T T F TRUE TRUE TRUE FALSE TRUE FALSE F F T F T TRUE TRUE TRUE TRUE TRUE TRUE F F T F F TRUE FALSE TRUE FALSE TRUE FALSE F F F T T FALSE FALSE TRUE FALSE TRUE FALSE F F F T F FALSE TRUE TRUE TRUE TRUE FALSE F F F F T FALSE TRUE TRUE FALSE TRUE FALSE F F F F F FALSE FALSE TRUE TRUE TRUE FALSE TOC
第 4 页
Section 2: Propositional equivalences Compound Proposition is an expression formed from propositional variables and logical operators. tautology - CP always true contradiction - CP always false contingency - CP neither a tautology nor a contradiction Logical equivalence occurs when two propositions have the same truth values in all conditions. The notation is, p q , and a consequence of equivalence is the fact that p q is a tautology. An equivalent structure for p → q is p q which is illustrated in the truth table below. p q p → q p p q T T T F T T F F F F F T T T T F F T T T To show that the bi-conditional of these is a tautology we use the equivalence we just showed. Since either both are false, in which case the negation of one is sufficient to make an or statement true, or both are true, in which case the negation of one is not sufficient to make an or statement false. Some important logical equivalences: Equivalence Name Equivalence Name p T p (pq)r p(qr) p F p Identity ( ) ( ) Associative pq r p qr pT T p(qr)(pq)(pr) p F F Domination ( ) ( ) ( ) Distributive p qr pq pr p p p (pq) p q p p p Idempotent ( ) De Morgan's pq p q ( p) p Double Negation p(pq) p p q q p ( ) Absorption p pq p p q q p Commutative p p T p p F Negation
第 5 页
Logical equivalences involving conditionals p → q p q p → q q → p p q p → q pq (p → q) (p →q) p q (p →q)(p →r) p →(qr) (p →q)(p →r) p →(qr) (p →r)(q →r)(pq)→r (p →r)(q →r)(pq)→r Logical equivalences involving biconditionals p q (p →q)(q → p) p q p q p q (pq) ( p q) (p q) p q Example Show that (p →q)→r p →(q →r). Method 1, truth table. p q r (p →q)→r p →(q →r) T T T T T T T F F F T F T T T T F F T T F T T T T F T F F T F F T T T F F F F T Method 2, use known equivalences. (p → q)→ r (p → q) r p → (q → r) p(q → r) (p → q) r (p q) r p(q → r) p ( q r) (p q) r (r p)(r q) p ( q r) p(r q) (r p) p (p → q)→ r p → (q → r) HW 57. Assign variables - directory database open → p, monitor in closed state → q, system in initial state → r. Write the conditional statement - →r (p →q). Write the equivalent with disjunctions and negations - r ( pq). Translate to English - either the system should be in its initial state, or the directory database should not be opened or the monitor should be in a closed state. But your book really wants a single conditional, note where the "not" is. If the data base is open, then either the system should be in its initial state or the monitor should be put in a closed state. TOC
第 6 页
Section 3: Predicates and quantifiers A predicate is an assertion made about a variable which is neither true nor false until a value is assigned to the variable, at which time the assertion becomes a logical proposition. A propositional function takes the form of a function with a variable for the argument, a predicate for the mapping criterion. When the variable has been assigned a value, the function takes on the value of either True or False. Propositional functions may take on more than one variable. Quantifiers modify predicates by expressing the extent to which the predicate is to be applied to the domain. Two primary quantifiers are the universal, denoted , and the existential,. The universal quantifier states that the predicate will yield the same output regardless of the input (provided the input is valid), while the existential quantifier merely claims that there is some valid input which will produce the claimed output. The area of logic that treats predicates and quantifiers is called predicate calculus. Given a universal quantifier, one only needs to find a single counterexample to show that the statement is false. Given an existential quantifier, a single example suffices to show that the statement is true. Quantifiers may be employed to give the exact number of x's which satisfy a propositional function. One such is uniqueness; it is represented by placing an exclamation mark after the existence symbol. When quantifiers are applied to a variable, it is said to be bound. When not bound, a variable is free. Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value no matter what predicates are employed and regardless of domain. Negation of quantifiers. Negation Equivalent xP x( ) x P x( ) xP x( ) x P x( ) HW 12. Q x( ): x+1 2x xZ a. Q(0) →T b. Q(-1) → T c. Q(1) → F d. xQ x( )→T e. xQ x( ) →F f. x Q x( ) →T g. x Q x( ) →F 18. a. xP x( ) P(−2) P(−1) P(0) P( )1 P(2) b. xP x( ) P(−2) P(−1) P(0) P( )1 P(2) c. x P x( ) P(−2) P(−1) P(0) P( )1 P(2) d. x P x( ) P(−2) P(−1) P(0) P( )1 P(2) e. xP x( ) P(−2) P(−1) P(0) P( )1 P(2) f . xP x( ) P(−2) P(−1) P(0) P( )1 P(2) TOC
第 7 页
Section 4: Nested quantifiers A quantifier is nested if it is in the scope of another quantifier, e.g. x y x( + y = 0). Order is not commutative. Statement Meaning x yP x y( , ) ( ) P(x,y) is true for all x, y. y xP x y, x yP x y( , ) For every x, there is at least one y which makes P(x,y) true. x yP x y( , ) There is at least one x which makes P(x,y) true for every y. x yP x y( , ) There is at least one x, y pair that makes P(x,y) true. HW 28. Domain of all variables is . a. x y x( 2 = y) T b. x y x( = y2 ) F c. x y xy( =0) T d. x y x( + y y+ x) F e. x x( 0→ y xy( =1)) T f. x y y( 0→(xy =1)) F g. x y x( + y =1) T h. x y((x+2y = 2)(2x+4y =5)) F i. x y((x+ y = 2)(2x− y =1)) F j. x y z z( =(x+ y)/ 2) T 33. Rewrite so negation appears only within predicates. a. x yP x y( , ) x y P x y( , ) b. y xP x y( , ) y x P x y( , ) c. y x P x y( ( , )Q x y( , )) x y(P x y( , ) Q x y( , )) d. ( x y P x y( , ) x yQ x y( , )) x yP x y( , ) x y Q x y( , ) e. x( y zP x y z( , , ) z yP x y z( , , )) x( y z P x y z( , , ) z y P x y z( , , )) TOC Section 5: Rules of inference An argument is a sequence of statements (premises) which lead to a conclusion. An argument is valid when the truth of the premises assures the truth of the conclusion. The notion of an argument form is that the premises are propositions as is the conclusion. When the truth of the premises imply the truth of the conclusion, it is the form not the assignment of variables that make the argument valid.
第 8 页
General Inference: Rule Tautology Name p p → q p (p → q) → q modus ponens q q p → q q (p → q) → p modus tollens p p → q q → r (p → q)(q → r) →(p → r) hypothetical syllogism p → r p q p (p q) p → q disjunctive syllogism q p ( ) p q p → pq addition p q p pq → p simplification p q (p)(q) → (p q) conjunction p q p q p r (p q) ( p r) → (q r) resolution q r Remember that p → q p q. This means the implication is true when p is false no matter what value q takes on. Assuming that p must be true because q is, is a fallacy known as affirming the conclusion. By the same token, assuming that q must be false because p is false is equally invalid, a fallacy known as denying the hypothesis. Inference and Quantifiers: Rule Name xP x( ) ( ) universal instantiation P c P c( ) for an arbitrary c universal generalization
第 9 页
xP x( ) xP x( ) ( ) existential instantiation P c for some c P c( ) for some c ( ) existential generalization xP x HW 6. Assign variables - r → it rains, f → it is foggy, s → sailing race is held, l → life saving demo is on and t → trophy is awarded. Form logical propositions: (r f )→ (s l) s → t t Construct a valid argument: ( r f )→(sl) premise t premise ( r f )→s simplification ( r f )→t premise s →t premise ( r f )(r f ) modus tollens ( r f )→t hypothetical syllogism 16. a. Let P(x) mean x is enrolled in the university. Let Q(x) mean x has lived in a dormitory. xP x( )→ Q x( ) Q Mia( ) Universal modus tollens, valid. P Mia( ) b. Let P(x) mean x is a convertible and Q(x) mean x is fun to drive. xP x( )→ Q x( ) P Isaac( ) Denying the hypothesis, not valid. Q Isaac( ) c. Let P(x) mean x is an action movie and Q(x) mean that Quincy likes x. xP x( )→ Q x( ) Q(Eight Men Out) Affirming the conclusion, not valid. P(Eight Men Out)
第 10 页
TOC Section 6: Introduction to proofs A theorem is a statement which can be proven to be true, propositions are theorems considered to be less important. A proof for a theorem is a valid argument the conclusion of which establishes the truth of the theorem. Often included in proofs are axioms or postulates statements assumed to be true without proof. Often these are definitions. Complicated proofs are sometimes broken up into smaller proofs (modules) called lemmas. Theorems which can be established as the direct consequence of the truth of another theorem are corollaries and statements which are thought to be true, but which are not yet proven are called conjectures. The words obviously and clearly should be avoided in a proof. They bring no real information to the reader except perhaps some insight into the ego of the author. Generally it is neither clear nor obvious, but surely we must be in awe of anyone for whom it is. Brown's Maxim - If you have completed more than three steps in a proof without mentioning a definition, you are probably doing it wrong. Some forms of proof for theorems of the form x P x( ( )→Q x( )): Direct Begin by assuming that P(x) is true, and then show that Q(x) must be. Show that the sum of two odd integers is even. Statement Justification Let p and q be odd integers By premise we have two odd integers p = 2k -1 Definition of odd integer q = 2j -1 Definition of odd integer p + q = 2k +2j - 2 Definition of addition p + q = 2(k + j -1) Distributive property of multiplication over addition Definition of even integer (also closure of integers P + q is even since 2(k + j -1) is even under addition and multiplication) Contraposition A direct proof of the contrapositive, that is, since p → q q → p, assume that "not q" is true, then show that "not p" must also be true. Show that if n is an integer and n3 +5 is odd, then n is even. (n3 +5 odd) →(n even) (n odd)→ (n3 +5 even) Statement Justification Let n be an odd integer Premise by way of contraposition n = 2k - 1, k an integer Definition of odd integer n3 +5 = (8k3 −12k2 +6k −1)+5 By definition of exponents
第 11 页
(8k3 −12k2 +6k −1)+5 = 2 8( k3 −12k2 +6k +2) Distributive property of multiplication over addition 2 8( k3 −12k2 +6k +2) an even integer Definition of even integer (n3 +5 odd) →(n even) Contraposition Contradiction Assume that what you are trying to prove is false, then show that this leads to a contradiction. (r3 + r +1= 0)→ r Lemma 1 If k is an integer, then 2k + 1 is odd. 2k + 1 = 2k + 2 - 1 = 2(k + 1) -1. Lemma 1 is used in the following Lemmas. Lemma 2 If p is an odd integer, then pn is an odd integer when n is a positive integer. ( )n ( )n ( )n−1 ( ) n( )n−2 ( )2 n ( ) (2 )n−2 ( )( )n−1 ( )n 2k −1 = 2k +n 2k −1 + 2k −1 +...+ 2k −1 +n 2k −1 + −1 2 n−2 n−1 ( )i n ( )n by the Binomial Theorem. But this is equal to 2 2n− −i 1kn−1 −1 + −1 , which is odd. i i=0 Lemma 3 If p and q are both odd, then pq is odd. (2k - 1)(2j - 1) = 2j(2·k - 1) - 2k + 1 = 2(j(2·k - 1) - k) +1 which is odd. Lemma 4 If p, q, and r are all three odd integers, then the sum of the three is odd. (2k -1) + (2j - 1) + (2m -1) = 2(k + j + m - 1) - 1. Lemma 5 If p is even and q is odd, then p + q is odd. (2k) + (2j - 1) = 2(k + j) - 1 Statement Justification r BWOC r = p/q, p and q integers with no common divisors Definition of rational p3 + pq2 +q3 = 0 Multiply both sides by q3 Case 1, p even and q even is not possible p and q integers with no common divisors Case 2, p odd and q odd Premise LHS is sum of three odd not 0 Lemmas 2 - 5 Case 3, p even and q odd Premise LHS is sum of three odd not 0 Lemmas 2 - 5 Case 4, p odd and q even Premise LHS is sum of three odd not 0 Definition of odd integer
第 12 页
p and q are integers, but neither odd nor even r HW 8. If n is a perfect square, then n + 2 is not. BWOC n = b2 and n + 2 = a2, where a and b are both integers greater than zero (by definition of perfect square). This means a2 - b2 = 2, equivalently (a - b)(a + b) = 2. Since n + 2 > n it follows that a > b, so a - b is a positive integer as is a + b. Since 1 and 2 are the only positive integers whose product is 2, a - b = 1 and a + b = 2. But this implies 2a = 3 or a = 3/2 which is not an integer. TOC Section 7: Proof methods and strategy Additional methods of proofs. Exhaustive proof or proof by cases enumerates every possible configuration that p can take, then shows that all of them imply q. One of the most important of these is trichotomy, the fact that all real numbers belong to one of three categories: r < 0; r = 0; r > 0. WLOG, without loss of generality is a shortcut that claims when assignment of values is arbitrary; we may assume whichever assignment we want. For example to prove that a + b is odd if a and b are not both odd. WLOG we can assume that the two cases, a odd, b even and a even, b odd are equivalent and so let a be odd and b even. Existence proofs require that some x exist so that P(x) is true. If such an x can be found, our proof is constructive. It is sometimes the case that it can be proved that such an x exists, but not possible (or convenient) to find a specific case. Uniqueness proofs require that an x exists that meets our requirements, and that everything that meets our requirements can be shown to be that same x. When constructing a proof it must be shown, ultimately, that the premises lead to the conclusion. Quite often it is more convenient to start at the conclusion and work backwards. Provided that we can simply reverse the path of this train of thought, the proof is valid. Recall the delta-epsilon proofs in calculus used to show that a limit existed, we needed to show that when x was no farther from "a" than delta, that this forced f(x) to be no farther from the limit as x approached "a" than epsilon. Choosing delta is very problematic unless we start at the conclusion. Just remember to put the line of your proof in the correct order before you present the proof. Be on the lookout for counterexamples whenever you are asked if a statement is true. For example, is it true that cos(x2) ≥ cos2(x) for 0 ≤ x ≤ 2π. We know that cos(π) = -1, so if x = then LHS < RHS since the minimum value for RHS is zero. A single counterexample is sufficient, we need not show that the claim is always false, merely that it is not always true.
第 13 页
HW 5. Proving the triangle inequality can be approached by taking 9 cases (trichotomy requires three choices for x and three for y). This list can be reduced WLOG to 6 cases. Of these, one is vacuous and two re trivial. a a +1 c 33. we pick two arbitrary rational numbers with common denominator, WLOG, . b b b 2 2 a a + c Since 1, it follows 2 . By definition, a and b are integers, so proving that 2 b b b 2 a+ x = 2 is irrational should not be hard. We can assume that we already know 2 is irrational. b TOC Chapter 2: Sets, functions, sequences and sums Section 1: Sets A set is an unordered collection of objects called elements. We will use uppercase letters to denote sets, and lower case letters to denote the elements. Some notation used with sets: Symbol Meaning Symbol Meaning {…} a set with elements in the xS x is an element of S braces S = {x| requirements} set builder notation, the Used to denote the empty set pipe means such that Some important sets: Symbol Name Description natural numbers {0, 1, 2, 3, …} integers {…, -2, -1, 0, 1, 2, …} p rational numbers | p ,q + q real numbers all numbers not imaginary A superscript of "+" or "-" indicates the positives or negatives only. By defining q as an element of the positive integers we have avoided division by zero, and have not excluded any rational numbers. Sets are considered equal iff they have the same elements.
第 14 页
The set U denotes the universal set, that is, the set containing all elements of interest in a particular inquiry. Subsets and proper subsets refer to sets which are contained in other sets. If all of the elements in A are also elements of B, then A is a subset of B, written A B . If B has at least one element not contained in A, and A is a subset of B, then A is a proper subset of B, written A B . The empty set is considered a subset of every set, and every set is considered a subset of itself. The cardinality of a set refers to the number of distinct elements in the set, it is written |S|. The power set of any given set is the set of all subsets of that set. This includes the empty set and the set itself. Since sets are not ordered, we use n-tuples when order matters. These look much like n- dimensional points. Equality of n-tuples occurs when all of the corresponding elements are equal. Cartesian Product of two sets is a binary operation on two sets which results in the set of ordered pairs in which every element in the first set is paired with every element in the second set. Example A = {1, a, cat} and B = {2, dog}. A × B = {(1, 2), (1, dog), (a, 2), (a, dog), (cat, 2), (cat, dog)} This can be extended to multiple sets by taking the first element of the first set followed by every possible combination of the remaining sets, each of which follows the same protocol as in the binary case. The truth set for P, where P is a predicate is the subset, T, of the domain of P so that xT → P x( )is true. HW 15. Use contradiction, suppose x is an element of A, but not an element of C. By definition it cannot be an element of B, since B is a subset of C. But it must be, since A is a subset of B. 28. In Excel this is easy; by hand use a table to make it easier. Set A Set B Set C A × B × C a x 0 (a, x, 0) a x 1 (a, x, 1) a y 0 (a, y, 0) a y 1 (a, y, 1) b x 0 (b, x, 0) b x 1 (b, x, 1) b y 0 (b, y, 0) b y 1 (b, y, 1)
第 15 页
c x 0 (c, x, 0) c x 1 (c, x, 1) c y 0 (c, y, 0) c y 1 (c, y, 1) TOC Section 2: Set operations Symbolic Representation Definition Name A B x x| A xB Union A B x x| AxB Intersection A− B x x| AxB Difference A x x| A Complement A B = A + B − A B Identity Name Identity Name A = A A (B C)= (A B) C Identity ( ) ( ) Associative A U = A A B C = A B C A U =U A (B C)= (A B) (A C) Domination ( ) ( ) ( ) Distributive A = A B C = A B A C A A = A A B = A B Idempotent De Morgan A A = A A B = A B A B = B A A (A B)= A Commutative ( ) Absorption A B = B A A A B = A A A =U A = A Complementation Complement A A = Unions and intersections may be indexed to indicate the use of more than two sets. Bitstring representation assumes some arbitrary ordering of Un. Strings of length n, are then formed so that a 1 in the jth position indicates that the jth element of U is included. A zero indicates that it is not. Example Let U = {1, 2, 3, 4, 5, 6, 7, 8} Let A = {1, 2, 3, 5, 8} → 1110 1001 Let B = {1, 4} → 1001 0000 HW
第 16 页
14. Use a Venn Diagram. 48. Problems such as this are often made easier by writing the first few sets. a A. =1, 2,3,... A =2,3, 4,... A =3, 4,5,... 1 2 3 A = + A = i i i=1 i=1 b A. =0,1 A =0, 2 A =0,3 1 2 3 A = − − A = 0 i i i=1 i=1 c. A = + A = (0,1) i i i=1 i=1 d. A = (1,) A = i i i=1 i=1 TOC Section 3: Functions The term, function, assigns elements from one set, the domain, to a single element of another set, the range. This is stated symbolically as f(a) = b, where aA, the domain, and bB, the range. Other ways of describing this is a is the preimage, f(a) is the image, f is a mapping or a transformation of A to B. The set B is the codomain, where the set B* b|xf ( )x =bis the range. If we take f : → where f (x)= x2 the reals are the codomain, but there are elements in the reals which are not in the range. Two functions f and g are considered equal iff they have the same domain, codomain and x Domain(f ( )x = g x( )). A function is one-to-one or an injection iff f (a)= f (b) a = b. A function is referred to as onto or a surjection if every element in the codomain is the image of some element in the domain. A bijection is both one-to-one and onto. When a function, f, is a bijection there exists another function, f -1, called the inverse so that f (a)=b → f −1 ( )b = a. The floor function (round down) assigns the largest integer less than or equal to x, the ceiling function assigns the smallest integer greater than or equal to x.
第 17 页
Floor: x example 3.9 =3 (note that floor and greatest integer are the same). Ceiling: x example 3.1 = 4. n Factorial: (n 0)→ n!= i , 0! = 1. i=1 HW 14. Remember that the domain and codomain are the integers. a. We can show that 2m - n will give all the odd integers if n is one and all of the even inters if n is zero, and zero if m and n are both zero. b. All perfect squares end in either 0, 1, 4, 5, 6, or 9. As a result, no integer ending in a 7 will be a function value. c. See a. d. If either m or n is zero, we have all of the integers. e. This is a subset of part b. 29. Start with the definitions, then establish that the requisite memberships must exist. 34. Start by explicitly writing f(g(x)) and g(f(x)). TOC Section 4: Sequences and summations A sequence is an ordered set of objects, as such it can be thought of as a function from the integers to the set. When the elements of an infinite set can be so listed, it is said to be countable. Geometric sequence a ar ar, , 2,...,arn,... Arithmetic sequence a a, +d a, +2 ,...,d a+nd,... A finite sequence is called a string. Problems that involve discovering a generating function for a sequence, that is some function where f (n)= a are equivocal. No matter how many initial values are given, infinitely many n functions may produce those first n values. Example Let S = {1, 2, 3, …}. Possible functions: −2n3 +12n2 −19n+12 n n f (n)= − n−4 +4 f (n)= f (n)= 4* − 1 2 3 3 4 4 f ( )5 =3 f ( )5 = −11 f ( )5 =1 1 2 3
第 18 页
Summation notation is used to indicate the sum of a sequence. It requires an index, lower limit, upper limit and a function that generates the elements of the sequence. Example 4 ( ) i2 −3i The index variable, i, acts as a counter. It takes on the integers starting with the lower i=1 limit, and proceeds to the upper limit. As the index variable takes on these values, they are substituted into the sequence generating function; these values are treated as terms to be added. 4 (i2 −3i)= (( )1 2 −3 1( )) + ((2)2 −3 2( )) + (( )3 2 −3 3( )) + ((4)2 −3 4( )) = 0 i=1 Changing the index of a summation is illustrated by: n n+k a i( )= a i( −k) i=r i= +r k Double sums are a way of allowing two variables to take on predetermined values. Consider the situation where the rows and columns of a checkerboard are assigned numeric values 1 through 8. A rule is assigned where the loser of a bet is required to place on each square the sum of 3r + 2c dollars. How much is the payoff of this bet worth? 8 8 ( ) 8 8 8 8 8 3r +2c = 3r +2 c = 24r +72 = 24 r +576 =864+576 = $1440 r=1 c=1 r=1 c=1 1 r=1 r=1 Sum Closed Form Sum Closed Form Sum Closed Form n ark r 0 arn+1 −a n c nc n k3 n2 (n+1)2 r 1 k=0 r −1 k=1 k=1 4 1 n n n( +1) xk x 1 k k=0 1− x k=1 2 1 n n n( +1)(2n+1) kxk−1 x 1 k2 (1− x)2 6 k=0 k=1 Countability is a term which implies a one-to-one correspondence with the positive integers. An infinite set with this property is said to be countably infinite. Such a set has cardinality of , 0 pronounced aleph null. To show that the positive rationals are countable, consider arranging them in rows where the first row has all rationals with a denominator of one, the second two etc. A zigzag pattern from the upper left passes through all rationals in a clearly defined sequence. By the same token, the negative rationals are countable. By straightening the two zigzags, and placing the negatives on top, we can create another zigzag that combines the two. If we start with zero before commencing this last zigzag, we have all of the rationals, and motivation for the fact that the union of two countable sets is also countable.
第 19 页
To show that the reals are not countable, start by assuming that they are, then considering only the interval (0, 1) list them: r = 0.d 0.d 0.d ... 1 11 12 13 r = 0.d 0.d 0.d ... 2 21 22 23 r = 0.d 0.d 0.d ... 3 31 32 33 r = 0.d 0.d 0.d ... 4 41 42 43 Now if we make the following rule: r = 0.d 0.d 0.d ... 1 2 3 4 d 4 d = ii i 5 d = 4 ii This systematically creates a number different in at least one decimal place from all of the other numbers. HW 8. To determine a polynomial of degree n, it is sufficient to provide n + 1 points, think of the sequence as the points (1,3), (2,5) and (3,7) where the x-value is the term number. 14. The notation f ( j)implies that every element of S is used exactly once to create a term in jS the sum. 32. Creating a function, f (n) n , which produces the set in question is sufficient to show countability. 40. Let B =b b, ,b ,...,b ,... and A=a a, ,a ,...,a ,...by definition of countable. 1 2 3 n 1 2 3 n C =c c, ,c ,...,c ,... 1 2 3 n c =b and c = a 2i−1 i 2i i The subscripts for c are all of the odd integers, b, and all of the even integers, a. TOC Chapter 3: Algorithms, the integers and matrices Section 1: Algorithms An algorithm is a finite set of instructions for performing a computation or solving a problem. While your text uses pseudocode for its examples, I will use TI-83+ programming language where possible. It is very similar, in that the language is very intuitive, but for those with this kind of calculator, it will actually run. The indentation is to make it easier to read. Function Y9 is reserved as int(X), the floor function, and Y0 is reserved as (X>int(X))+int(X), the ceiling function.
第 20 页
The TI programming language requires an, "End" statement for the for-next loops, if-then-else and the while constructs. The TI-86's, 89's and 92's have some differences in their syntax and the way functions are treated. You should consult your manual if these programs do not work on your machine. The ability to program your calculator is not a course requirement. Many of the algorithms discussed can be duplicated with built in functions; the object is to get a better feel for how algorithms work, their structure and their size. The algorithm below is a very simple algorithm designed to find the largest item in a list. Input is performed by entering the desired numbers into a list, the output is performed in the display step. Max If a list of numbers is stored in L1 this algorithm will find the largest value in the list. L1(1) sto M For(I,2,dim(L1)) If L1(I)>M Then L1(I) sto M End End Disp M Stop values 1st element added to assigned to m list 1 loop to last element if yes, new m loop over this element bigger than if no, same m m display m A flow chart like the one above is very useful in organizing your thoughts and assuring that your algorithm performs as expected. The parallelograms are data, I use them to indicate data in and data out, the rectangles are processes and the diamonds are decisions. Some things that all good algorithms have in common are: Input/Output, clarity, correctness, finite number of steps, finite amount of time and generality. Using the nomenclature of your book: It - Input a specified set of initial values/conditions. Only - Output a subset of values from a solution set. Does - Definiteness, each step is precisely defined. Computations - Correctness, the output values are valid for the given input. For - Finiteness, the number of steps from input to output are finite.
评论 (0)
暂无评论。快来抢沙发吧！