### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# INTR THY PROBAB&S I MATH 341

ISU

GPA 3.98

### View Full Document

## 5

## 0

## Popular in Course

## Popular in Mathematics (M)

This 131 page Class Notes was uploaded by Ms. Helen Sipes on Sunday September 27, 2015. The Class Notes belongs to MATH 341 at Iowa State University taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/214499/math-341-iowa-state-university in Mathematics (M) at Iowa State University.

## Popular in Mathematics (M)

## Reviews for INTR THY PROBAB&S I

### 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/27/15

The Real Heart of Mathematics George Voutsadakis School of Mathematics and Computer Science Lake Superior State University Sault Sainte Marie7 MI 49783 USA gvoutsad lssu edu November 297 2002 Contents O CO Linear Equations and Systems 11 First Degree Equations Ordered Pairs Cartesian Systems of Coordinates Linear Equations in 2 Variables Graphs and Intercepts Slope and Equations of Lines HHHH UIHgtOJM Systems of 2 Linear Equations in 2 Variables 16 Applications of Linear Systems Matrices and Systems 21 Matrices Additive Structure 22 Multiplicative Structure 23 Augmented Matrices and Systems of Equations 24 The Determinant Method Propositional Logic 31 Statements Compound Statements Truth and Falsity 32 Logical Equivalence Tautologies and Contradictions Conditional Statements Converse lnverse and Biconditionals 35 Valid Arguments 36 Fallacies 41 Basic De nitions and Examples 42 Operations on Sets Proving Subset Relations Proving Set Identities 45 Finding Counterexamples and Detecting Mistakes 46 Empty Set Partitions and Power Sets 3 5 Basic Combinatorics 97 51 Simple Counting 97 52 The Multiplication Principle 100 53 Permutations 104 54 The Addition Rule 108 55 Combinations 113 6 Basic Probability 119 7 Graphs 121 8 Finite State Automata 123 9 Basic Number Theory 125 10 The Principle of Mathematical Induction 127 11 Number Systems Complex Numbers 129 12 Geometry 131 Chapter 1 Linear Equations and Systems 11 FirstDegree Equations An equation is a statement that two mathematical expressions are equal for example 3m5y27 2m4y7 3x773y8m73 are examples of equations The letters in each equation are called variables A rstdegree equation is one that can be written in the form axbc where a7 1 and c are constants real numbers and a 7 O For instance 4x 5 7 is a rst degree equation but 3 13 or 2 7 5x 2 9 are not rst degree equations since one of the variables appears cubed and squared7 respectively A solution of an equation is a number that7 when substituted for the variable in the equation produces a true statement For instance7 consider the rst degree equation 3z5 11 The number 2 is a solution to this equation because7 if 2 is substituted for z in the equation7 we get 3 2 5 117 which is a true statement On the other hand 1 is not a solution of this equation since 31 5 8 7 117 ie7 substituting 1 for z in the equation does not produce a true statement To solve a rst degree equation means to nd its solutions There is a speci c method one can follow in order to solve a rst degree equation This method is based on the following two properties of equality 1 The same number may be added to or subtracted from both sides of an equation lfab7 thenL l bc7 andaicbic 2 Both sides of an equation may be multiplied or divided by the same nonzero number lfabandc 0 thenacbcandg C C Here are some examples of how these properties may be used to solve rst degree equa tions Example 1 Solue the equation 6x 5 77 Solution We start from the given equation 6z 5 77 By subtracting 5 from both sides7 we get 69557577757 ie7 695712 Now divide both sides of the equation by 6 to get 6m 7 712 i 7 2 6 7 6 1e7 as 7 We nally substitute 72 for z in the original equation to verify that it produces a true statement 6725712577 I Now solve the following exercises to get used to the process of solving rst degree equa tions Exercise 1 Solue the equation 4x 7 2 18 Exercise 2 Solue the equation 2x 7 3x 7 4 Exercise 3 Solue the equation 5x 7 8 2x 1 Why are rst degree equations so important They help us to solve problems from all areas of life and science Some examples follow Example 2 Physics Town A and town B are 450 miles apart and connected via a straight railroad A train moues along the straight track from A to B at a speed of 50 mph and is already 100 miles away from town A In how many hours will it reach town B Solution First7 we pick a variable to represent the unknown quantity Let us pick t for the time that will be needed to arrive at town B Since the train is already 100 miles away from A and is moving at a speed of 50 mph7 it will be 100 50t miles away from town A in t hours Therefore to nd t we have to solve the rst degree equation 100 50t 450 Subtract 100 from both sides to obtain 100 50t 7 100 450 7 1007 ie7 50t 350 THE REAL HEART OF MATHEMATICS 7 Now divide both sides by 50 to get 50t7 350 ie 7577 50 7 50 39 quot 7 39 Check that 7 is the correct solution by substituting 7 for t in the original equation and verifying that it produces a true statement I Example 3 Business A small business producing a certain item needs 1000 for sup plies It then takes the company 40 to produce and sell each item If each item sells for 60 nd how many items the company has to produce and sell so that its revenue becomes equal to its expenditures Solution Let x represent the number of items that the company has to produce and sell Since each item sells for 60 the revenue of the company will be 60m On the other hand to produce z items the company has to spend 1 000 1 40m Thus the revenue becomes equal to the expenditures when 6095 1000 40x Subtract 40m from both sides to get 6095 7 40m 1 000 40x 7 40m ie 20x 1 000 Now divide both sides by 20 to get 2095 1 000 7 77 50 20 20 e7 3 Thus the company needs to produce and sell 50 items to have revenue equaling its expen ditures Verify that 50 is the right solution by substituting 50 for z in the original equation and seeing that it produces a true statement I Example 4 Geometry If the length of a side of a square is increased by 5 inches the new perimeter is 40 inches more than twice the length of the side of the original square Find the length of the side of the original square Solution Draw a gure to convince yourself that if z is the length of the side of the original square then we must have 495 3 2m 40 This gives 4z12 2z40 Subtract 2x from both sides to get 4m1272z2m4072z ie 2z12 40 Now subtract 12 from both sides to get 2x 12 712 40 712 ie 2x 28 Finally divide both sides by 2 to get 23 278 ie z 14 Now check that this is the correct answer by substituting 14 for z in the original equation Now try to solve the following exercises to see whether you can set up and solve applied problems involving rst degree equations on your own Exercise 4 Joe bought two plots of land for a total of 120000 On the rstplot he made a pro t of 15 On the second he lost 10 His total pro t was 5500 How much did he pay for each piece of land Exercise 5 Suppose that 20 000 is inuested at 5 How much additional money has to be inuested at 3 so that the yield on the entire amount ends up being 4 Exercise 6 A plane flies nonstop from New York to London which are about 3500 miles apart After one hour and six minutes in the air the plane passes through Halifax Noua Scotia which is 600 miles from New York Estimate the flying time from New York to London Exercise 7 On uacation Mary aueraged 50 mph traueling from Denuer to Minneapolis Returning by a di erent route that couered the same number of miles she aueraged 55 mph What is the distance between the two cities if her total traueling time was 32 hoursf2 Exercise 8 The length of a rectangular label is 5 centimeters less than twice the width The perimeter is 54 centimeters Find the width Exercise 9 A puzzle piece in the shape of a triangle has a perimeter of 30 centimeters Two sides of the triangle are each twice as long as the shortest side Find the length of the shortest side THE REAL HEART OF MATHEMATICS 9 12 Ordered Pairs Cartesian Systems of Coordinates A pair of real numbers a 1 taken in a speci c order rst a and then b is called an ordered pair and denoted by ab or sometimes by 0119 For instance 3 61 and x2 as well as 6 2 are ordered pairs of real numbers The rst number in the pair is called the rst coordinate and the second the second coordinate A direct consequence of the de nition is that if a 7 b then the pairs ab and b a are not considered to be the same In fact equality between ordered pairs is de ned by ab c d if and only if a c and b 1 Example 5 Find z and y if z 3 4 2y Solution By the de nition of equality between ordered pairs we have x 3 4 2y implies z 4 and 3 2y Therefore 3 z 4 and y 5 Example 6 Find x if 1 x6 32z 2 z 17 42m 3 Solution 1 We have x 6 3 2x implies z 3 and 6 2x Thus we obtain z 3 and z 3 which together give us the condition z 3 to Wehave m1742z3 implies m14and72m3 These give z3 and 2z4 ie z3andm2 The condition z 3 and z 2 is clearly inconsistent m cannot be both 3 and 2 simultaneously Hence no x that makes the required equality valid exists Or in other words the equality has no solutions Now take up the following exercises to make sure that you understand ordered pairs and equality of ordered pairs Exercise 10 Find z and y if z8 y 1y 7 2 Exercise 11 Find x if 1 2m 14 1195 71 2 3m 27 13 3 A number line is a straight line on which there is a distinguished point 0 called the origin a distinguished direction called the positive direction and a distinguished length called the unit length The opposite of the positive direction is termed the negative direction Given a number line every point on the line may be associated with a unique real number it is the positive distance to the point from the origin if the origin point segment points to the positive direction and it is the negative of the distance to the point from the origin in case the origin point segment points to the negative direction Conversely given any real number there is a point on the number line associated with it It is the point Whose distance from the origin equals the absolute value of the number and that lies in the positive direction with respect to the origin if the real number is positive and to the negative direction if the real number is negative The above statements mean that real numbers are in oneto one correspondence with points on the number line The following exercise asks you to perform these back and forth steps for speci c numbers Example 7 Construct a number line on the plane 1 Pick a point on the line and nd the real number that is associated to that point 2 Find the points associated to the real numbers 45 and 28 Solution 1 The number line is shown in Figure 11 Note that except for the line a positive direction and a unit length have been picked These are necessary components Also on the line an arbitrary point has been picked The point lies in the negative direction with respect to the origin and its distance from the origin is measured to be 25 times the given unit length Therefore the real number associated to that point is the number 25 to The points associated to 45 and 28 are constructed by taking segments that are 45 times the length of the unit length in the negative and 28 times the length of the unit in the positive direction respectively See Figure 12 These are depicted in Figure THE REAL HEART OF MATHEMATICS Figure 11 The number line with a chosen point Figure 12 The number line with the points associated with 45 and 28 Figure 13 The Cartesian Plane Exercise 12 Construct a number line on the plane Do not miss any of the three require ments Take a point on the line Find which real number is associated to that point Explain the process Exercise 13 Find the points on the number line that you constructed corresponding to the numbers 2 35 and 46 Explain the process Following a similar process to the construction of the number line one may construct the real plane Now instead of the oneto one correspondence between real numbers and points on the number line a one to one correspondence between ordered pairs and points on the plane is to be established Here is the way A Cartesian coordinate system on the plane consists of two number lines which intersect in a right angle at their origins The point of intersection is called the origin The unit lengths of the two lines are usually taken to be equal Also by convention one of the lines is placed horizontally and is called the z axis and the other vertically and is called the y axis Moreover east is taken to be the positive direction on the m axis and north the positive direction on the y axis Note that these are all conventions but that the only requirement imposed by the de nition is that the two number lines intersect at their origins forming a right angle Figure 13 is depicting the situation graphically Given a Cartesian coordinate system every point on the plane may be associated with a unique ordered pair of real numbers it is the pair having as its rst coordinate the real number associated with the projection of the point on the horizontal axis in the horizontal number line and as its second coordinate the real number associated with the projection of the point on the vertical axis on the vertical number line Conversely given any ordered pair of real numbers there is a point on the plane associ ated with it It is the point of intersection of the vertical line that passes through the point associated with its rst coordinate on the horizontal number line with the horizontal line that passes through the point associated with its second coordinate on the vertical number line THE REAL HEART OF MATHEMATICS 13 Figure 14 The plane with a point The above statements mean that pairs of real numbers are in one to one correspondence with points on the plane The following exercise asks you to perform these back and forth steps for speci c pairs of real numbers Example 8 Construct a Cartesian coordinate system on the plane 1 Pick a point on the plane and nd the ordered pair that is associated to that point 2 Find the point associated to the ordered pairs 72 5 71 72 and 23 Solution 1 The coordinate system is shown in Figure 14 Note that except for the two lines a positive direction and a unit length have been picked on each line These are necessary components Also on the plane an arbitrary point A has been picked The projections A and A of the point A on the m axis and the y axis respectively have been drawn A is associated with 2 in the horizontal number line and A is associated with 15 in the vertical number line Therefore the point A is associated to the ordered pair 2 715 in the Cartesian system to The point associated to 72 5 is found by rst identifying the point associated with 2 in the horizontal number system and drawing the vertical line that passes through that point then identifying the point associated to 5 in the vertical number system and drawing the horizontal line passing through that point and nally taking the point of intersection of these two lines The points associated to 71 72 and 23 have been similarly constructed These are depicted in Figure 15 Exercise 14 Construct a Cartesian coordinate system on the plane Do not miss any of the requirements Take a point on the plane Find which ordered pair of real numbers is associated to that point Explain the process Figure 15 The plane with the points associated with 727 57 717 72 and 27 3 Exercise 15 Find the points on the Cartesian plane that you constructed corresponding to the ordered pairs 72 5 and 2 71 Explain the process THE REAL HEART OF MATHEMATICS 15 13 Linear Equations in 2 Variables Graphs and Intercepts A linear equation in two variables x and y is an equation of the form am 1 by c where a b c are constants real numbers For instance 3x 1 5y 8 is a linear equation in two variables 3x2 7 5y 6 is not a linear equation because one of the variables appears squared Similarly z 7 y3 5x 1 is not a linear equation since y appears cubed A solution of a linear equation in two variables x and y is an ordered pair of real numbers such that substitution of the rst coordinate for z and of the second for y in the equation produces a true statement For instance 5 2 is a solution for the linear equation 3x 7 2y 11 since substituting 5 for z and 2 for y in the equation gives 3 5 7 2 2 11 which is a true statement On the other hand 3 72 is not a solution of the equation since substituting 3 for z and 2 for y gives 3 3 7 2 72 11 which is not a true statement since 3 3 7 2 72 9 4 13 7 11 Note that 3 71 is also a solution of the given equation Verify this fact Exercise 16 Consider the linear equation in two variables 72m y 2 Give three so lutions of this equation Find the corresponding points on a Cartesian coordinate system What do you observef2 To solve a linear equation in two variables means to nd its solutions As the example above suggests a linear equation in two variables may have more than one solutions Example 9 Solve the linear equation in two variables 3m 7 y 1 Solution The given equation has in nitely many solutions This may be seen by observing that for every real number s that is substituted for z in the equation one may nd a number t that can be substituted for y that makes the equation true Given z 5 3s 7 y 1 gives y 3s 7 1 So if we set t 3s 7 1 the ordered pair 5 3s 7 1 satis es this equation no matter what 5 is Hence this equation has the in nitely many solutions 5 3s 7 1 s an arbitrary real number Most often 5 and t are not used and the letters z and y are still used to denote an arbitrary solution In that case one would have x y z3z 7 1 m an arbitrary real number Exercise 17 Solve the equation 2x 7 3y 5 Figure 16 The graph of y 7 2x 1 Exercise 18 Solve the equation 75m 1 2y 1 1 3x 7 2y 1 6 The graph of a linear equation in two variables x and y is the set of points in the plane whose coordinates ordered pairs are solutions of the equation As we saw before a linear equation may have in nitely many solutions And as you may have discovered by doing one of the exercises the corresponding points on the plane all lie on a straight line This makes it possible to obtain the graph of the equation by only determining two points on the graph ie two solutions of the equation and then joining them by a straight line Example 10 Plot the graph of the equation y 7 2m 1 Solution Now that we know that the graph is a straight line it suf ces to determine two solutions of the equation Working as before it is not very dif cult to see that the complete set of solutions is given by z y x 2m 1 m an arbitrary real number To obtain thus two solutions it suf ces to choose two real numbers say 0 and 1 and substitute them for z in the general form of the solution given above This will give us the two solutions 0 2 0 1 and 12 1 1 ie 01 and 13 Now nd the points on the Cartesian plane corresponding to these ordered pairs and join them via a straight line The resulting graph is depicted in Figure 16 Usually when the graph of the linear equation is to be drawn the two points that are chosen to guide the plotting are the points where the straight line intersects the z and the y axis The rst is called the m intercept and the second the y intercept To nd the intercepts the following steps are useful THE REAL HEART OF MATHEMATICS Figure 17 The graph of y 7 2x 1 m intercept The z intercept is by de nition the point of intersection with the z axis At that point then the y coordinate is equal to 0 Thus to determine the z intercept we set y 0 and solve the resulting linear equation in one variable for m y intercept The y intercept is by de nition the point of intersection with the y axis At that point then the z coordinate is equal to 0 Thus to determine the y intercept we set x 0 and solve the resulting linear equation in one variable for y Example 11 Plot the graph of the equation 3y 2m 5 Solution First determine the two intercepts by following the process outlined above Set y 0 Then we obtain 5 2 5 7 x 1e x 2 Thus the z intercept is the point g 0 Next set x 0 Then 5 3 5 7 y 7 157 y 3 Thus the y intercept is the point 0 Now nd the points on the Cartesian plane corresponding to these ordered pairs and join them via a straight line The resulting graph is depicted in Figure 17 I Now work the following exercises to make sure that you understand intercepts and the concept of a graph of a linear equation in two variables Exercise 19 Find the intercepts of 3x y 4 Exercise 20 Find the intercepts of 77m By 2 4y 3m 18 Exercise 21 Consider the equation x 2y 3 1 Solve this equation 2 Find its intercepts 3 Sketch its graph Exercise 22 Consider the equation 2x 7y 14 1 Solve this equation 2 Find its intercepts 3 Sketch its graph THE REAL HEART OF MATHEMATICS 19 14 Slope and Equations of Lines A straight line is determined by two of its points If 1341 and 2 yg are two points on a straight line then the slope in of the line is de ned to be 242 T 241 m 7 2 T 1 The slope in other words gives the change in g per unit change of z Example 12 Find the slope of the line going through the points 72 1 and 3 4 Solution Let phyl 721 and 2 yg 3 4 and apply the de nition to obtain 242 T 241 4 T 1 3 271 73772 Thus the slope of the given line is m I Example 13 Using the de nition nd the slope of the line with equation 3m 7 2y 3 Solution The de nition requires two points on the line So we rst have to determine two solutions of the equation 3x 7 2y 3 We choose to determine the intercepts Setting y O we get the z intercept 10 Setting z 0 we get the y intercept 0 Thus using plug1 1 0 and 2342 0 7 we obtain 3 70g 27M 071 39 szyi m T I Now try to solve the following exercises to make sure that you understand the de nition of the slope Exercise 23 Find the slope of the line that goes through the points 73 5 and 27 Exercise 24 Find the slope of the line that goes through 75 72 and 7411 Exercise 25 Find the slope of the line giuen by the equation 4m 7 3y 24 The slope of a horizontal line is 0 and the slope of a vertical line is unde ned Can you explaine based on the de nition why this is the case SlopeIntercept Form If a line has slope in and y intercept 01 then the line is the graph of the equation y mm b This form of the equation of a line is called the slopeintercept form Can you see based on the de nition why a line with slope in and y intercept at the point 01 is the graph of the equation y mm b 20 Example 14 Find the equation of the line with slope in 5 and y intercept b 7 Solution An application ofthe slopeintercept form gives directly the equation y mzb 5m7 I Example 15 Find the equation of the line with slope in 2 passing through the point 0771 Solution Since the line has slope m 2 the slopeintercept form gives an equation y 2x b where b is the y intercept of the line But since 071 is a point on the line lying on the y axis the y intercept of the line is b 71 Hence the equation is y 2x 7 1 Example 16 Find the equation of the line with slope in 73 going through the point 72 5 Solution By the slope intercept form since the line has slope m 73 it must have an equation y 73m b where b is its y intercept But since 725 is a point on the line its coordinates must be solutions of the equation of the line This means that if you substitute 72 for z and 5 for y in the equation of the line you would obtain a true statement Hence 5 7 72 1 Hence 5 6 b ie b 1 7 The equation of the line is therefore I Example 17 Find the equation of the line going through the points 72 73 and 571 Solution We rst set 1 yl 72 73 and 2342 5 71 and compute the slope m of that line using the de nition 7 92 91 7 1 3 2 7 m271 7 5772 7 Now the slopeintercept form of the line yields an equation y z I But the line passes through the point 72 73 whence 72 73 must be a solution of the equation of the line Therefore 73 72 b whence 73 7 b ie b 71777 The equation of the line is therefore 2 17 y 7 z 7 I Another type of problem asks you given an equation whose graph is a straight line to determine the slope of that line Example 18 Find the slope of the line which is the graph of the equation y 7m 7 3 THE REAL HEART OF MATHEMATICS 21 Solution Compare the given equation with the slope intercept form This comparison gives slope in 7 and y intercept b 73 Example 19 Find the slope of the line with equation 4m 7 7y 13 Solution The given equation is not in the slope intercept form So we cannot read the information regarding the slope and y intercept directly off the equation However we may easily solve for y to obtain the slope intercept form We have 4x 7 7y 13 implies 7y 4x 7 13 ie y z 7 Hence by comparison with the slopeintercept form we obtain slope in and y intercept b 7 Now try to solve the following problems to make sure that you have a good grasp of the slope intercept form of the equation of a line Exercise 26 Find the equation of the line with slope in 7 and y intercept b 73 Find the equation of the line with slope in 73 passing through the point 05 Exercise 27 Find the equation of the line with slope in 2 passing through the point 73 1 Exercise 28 Find the equation of the line going through the points 72 2 3 75 Exercise 29 Find the slope and y intercept of the line which is the graph of the equation y 7m Exercise 30 Find the slope and the y intercept of the line with equation 3m 7 7y 2 Exercise 31 Find the slope and the y intercept of the line with equation 73m 1 2y 12 Parallel and Perpendicular Lines Two non vertical lines are parallel if they have the same slope Symbolically for two lines l1 and l2 with slopes m1 and mg respectively we have l1l2 m1 m2 Two non vertical lines are perpendicular if the product of their slopes is 1 Symbolically l11l2 if m1m2 71 Example 20 Determine which of the following pairs of lines are parallel and which are perpendicular 1 4x73y6 and3z4y8 2 3x2y8and6y579m 3 4x2y3and2y2m3 Solution H Solve both equations for y so as to transform them to the slopeintercept form and determine their slopes 4x731 6 implies 3y 4m76 ie y gm72 Thus the slope of the rst line is m1 335 4y 8 implies 4y 7335 8 ie y 73s 2 Thus the slope of the second line is m2 7 Now note that m1 m2 g 71 71 Hence the two given lines are perpendicular D g Following the same process we get 3z2y 8 implies 2y 73z8 ie y 7gz whence m1 7 Also 6y 5 7 9x implies y 7z 2 whence m2 7 Now observe again that m1 7 m2 whence the two given lines are parallel 7 03 4x 2g 3 implies 2y 4x 7 3 whence y 2x 7 Hence m1 2 On the other hand 2y 2x 3 implies y z Hence m2 1 So we have neither m1 m2 nor mlmg 71 Therefore the two given lines are neither parallel nor perpendicular I Example 21 Find the equation of the line that is parallel to y 2m2002 and goes through the point 0 6 Solution Since the unknown line is parallel to the line y 2x 2002 its slope must be m 2 Thus its equation must have the form y 2x b where b is its y intercept But 0 6 is a point of the line lying on the y axis ie 6 is its y intercept Thus we obtain y 2x 6 as the equation of the line Example 22 Find the equation of the line that is perpendicular to the line with equation y 75m 2003 and goes through the point 17g Solution Since the unknown line is perpendicular to the line y 75m 2003 it must have slope in Thus its equation has the form y z b where b is its y intercept The point 1 7 is by assumption a point on this line whence we must have 7 b whence b 71 Therefore the equation of our line is y z 7 1 I Now work out the following exercises to make sure that you have a solid understanding of parallel and perpendicular lines Exercise 32 Say whether the following pairs of lines are parallel or perpendicular 1 2x75y7 and 15y756m 2 73y4 andyl73m 3 2m7y6andm72y4 THE REAL HEART OF MATHEMATICS 23 Exercise 33 Find the equation of the line that is parallel to y 7m 6 and goes through the point 723 Exercise 34 Find the equation of the line that is perpendicular to the line y 2m 1 and goes through the point 1 PointSlope Form If a line has slope m and passes through the point a b then it is the graph of the equation y 7 b mm 7 a This is called the pointslope form of the equation of the line Can we see why a line with slope m passing through a 1 must have equation y 7 b mm 7 a Example 23 Find the equation of the line that has slope m 2 and goes through the point 15 Solution By the point slope form we obtain y 7 5 2m 7 1 ie y 7 5 2x 7 2 and therefore y 2m 3 I Example 24 Find the equation of the line that is parallel to the line 2m 7 3y 5 and goes through the point 1 Solution First solve the given equation for y to determine its slope We have 2x 7 3y 5 implies 3y 2x 7 5 ie y gm 7 Hence its slope is m The unknown line is parallel to this and so it has the same slope Since it also goes through the point 1 7 its equation is given by the point slope form Hencey z71 I Example 25 Find the equation of the line that is perpendicular to the line y 77m 2001 and goes through the point 1 Solution Since the unknown line is perpendicular to the given line its slope must be m Since in addition it goes through the point 1 g its equation is given by the point slope form 8 1 l 8 1 1 y7z71 ie y7z7 This gives y z 1 l 24 Example 26 Find the equation of the line that goes through the points 72 3 and 4 71 Solution First determine the slope by the de nition 7173 74 2 m 4772 773 Then use the point slope form 2 2 4 y737 z772 ie y737 x73 Hencey7z I Now work through the following exercises Exercise 35 Find the equation of the line that has slope m 9 and goes through the point 14 Exercise 36 Find the equation of the line that is parallel to the line 2m 7 y 7 and goes through the point 63 Exercise 37 Find the equation of the line that is perpendicular to the line 5y 7 m 2003 and goes through the point 214 Exercise 38 Find the equation of the line going through the points 24 and 5 76 Finally the equation of the vertical line with z intercept a 0 is given by z a and the equation of the horizontal line with y intercept 01 is given by y 1 Example 27 Find the equation of the horizontal line passing through 25 Solution This line is horizontal and has y intercept 5 Hence its equation is y 5 I Example 28 Find the equation of the uertical line through 1 74 Solution This line is vertical and has z intercept 1 Hence its equation is z 1 I Example 29 Find the equation of the line that is parallel to m 3 and goes through 72 6 Solution The given line is vertical Hence the unknown line is vertical and has z intercept 2 Thus its equation is z 72 THE REAL HEART OF MATHEMATICS 25 Example 30 Find the equation of the line perpendicular to m 71 that goes through 777 72002 Solution The given line is vertical Thus7 the unknown line is horizontal and has y intercept 2002 Thus7 its equation is y 72002 Exercise 39 Find the equations of the horizontal and of the uertical lines that go through the point 20027 72003 Exercise 40 Find the equation of the line that is parallel to y 73 and goes through the point 513 Exercise 41 Find the equation of the line that is perpendicular to the line m 5 and goes through 72 5 26 15 Systems of 2 Linear Equations in 2 Variables A system of 2 linear equations in 2 variables or a 2 x 2 system for short is a system of the form 11195 any b1 12195 012234 52 7 where a11a12a21 a22b1 and 2 are constants An example of a 2 x 2 system is the following 2m 3y 10 90 y 5 39 In this example we have an 2 an 3 a21 71a22 1 and b1 10 b2 5 Geometrically a 2 x 2 system corresponds to a system of 2 straight lines in the plane A solution of a 2 x 2 system is an ordered pair a 1 such that a b is a solution of both linear equations in 2 variables constituting the system Geometrically this means that a solution of the 2 x 2 system is a point lying in both straight lines which are graphs of the linear equations of the system Consider the 2 x 2 system given above The ordered pair 2 2 is not a solution of the system Despite the fact that 2232 10 2 2 is not a solution because 722 0 344 5 le 2 2 is a solution of the rst linear equation of the system only The point 71 4 is a solution because 2 71 3 4 10 and 771 4 5 Example 31 Consider the 2 x 2 system m 3y 7 7x y 1 39 Is the ordered pair 41 a solution of this system How about the pair 12 Solution 41 is a solution of the rst equation but not of the second Therefore it is not a solution of the system 12 is a solution of both equations Therefore it is a solution of the given system I Example 32 Consider the 2 x 2 system m 3y 7 72m 7 6y 714 39 Is the ordered pair 41 a solution of this system How about the pair 12 Solution 4 1 is a solution of both equations It is therefore a solution of the system 1 2 also satis es both equations It is therefore a solution of the given system as well I THE REAL HEART OF MATHEMATICS 27 Example 33 Consider the 2 x 2 system 2m 7 y 7 76m 1 3y 9 39 Is the ordered pair 2 73 a solution of this system How about the pair 1 5 Solution 2 73 satis es only the rst of the two equations It is therefore not a solution of the system 1 5 on the other hand satis es only the second equation It is therefore not a solution of the given system either Exercise 42 Consider the 2 x 2 system 72m 1 5y 14 77m y 16 39 Is the ordered pair 34 a solution of this system How about the pair 72 2 Exercise 43 Consider the 2 x 2 system 751 7 2x710 14 39 Is the ordered pair 2 71 a solution of this system How about the pair 70 Exercise 44 Consider the 2 x 2 system 73m 7 y 7 6x 2y 3 39 Is the ordered pair 0 77 a solution of this system How about the pair 73 To solve a 2 x 2 system means to nd all its solutions To solve a 2 x 2 system one usually follows the following steps H Solve one of the 2 equations for one of the variables pick the one that has the easiest solution to Substitute the expression you obtained in 1 for the same variable in the other equation and solve for the other variable 03 Now back substitute into the expression obtained in 1 Example 34 Solue the 2 x 2 system 2m75y 71 75x8y 72 39 Solution 2m75y 71 ziiy 7 75m8y 7275m8y 72 gt 1 5 1 9 y 9 y i 75 y8y 7 2 7y 8y 7 2 l 5 1 5 1 z 7 7 x 7 9 2 my 2 29 2 34 Example 35 Solve the 2 x 2 system 7z2y 8 2m74y 716 39 7z2y 8 m 23478 25741 716295741 716 j m 23478 gt m 23478 22y7874y 716 434716741 716 z2y78 00 Therefore7 the solution set of this system is Solution 2y 7 87 y y any real number Example 36 Solve the 2 x 2 system 3m7y 5 6x721 9 39 3m7y 5 y 3m75 635723 96z72y 9 y 3m75 y 3m75 6m723x75 9 6zi6m10 9 y3z75 071 39 So the given system is inconsistent Solution THE REAL HEART OF MATHEMATICS 29 Exercise 45 Solve the 2 x 2 systems 7my 71 75x2y 3 2m75y 71 72135731 3 z4y 17 and 62571514 3 There is another method of 2 x 2 systems which is more useful than the simple method presented above because it applies equally well when one wants to solve systems of more than 2 linear equations in more than 2 variables This method is called Gauss elimination The operations that we are allowed to performed at each step of applying this method are the following 1 Change the order in which the equations appear in the system 2 Multiply both sides of an equation in the system by a nonzero constant 3 Add to an equation a multiple of another equation sideby side Here follows an example of how these 3 operations may be applied to solve a 2 x 2 system Example 37 Solve the 2 x 2 system 5my 61 7z2y 12 RH Solution The given system is 5m y 61 7x 1 2y 12 39 First7 apply operation 1 to change the order of the equations 7x 1 2y 12 5m y 61 39 Then multiply the rst equation by 71 m 7 2y 712 5m y 61 39 Next add to the second equation the rst multiplied by 75 We do this to eliminate the variable x from the second equation That is why the method is called Gauss elimination x721 712 11y 121 39 Now multiply both sides of the second equation by x721 712 y 11 39 30 Finally add to the rst equation the second multiplied by 2 We do this to eliminate the variable y from the rst equation m 10 y 11 39 Thus 1011 is a solution of the given 2 x 2 system I We summarize the method as follows Gauss Elimination 1 Multiply both sides of one of the equations by a nonzero constant so as to make the coef cient of z equal to 1 2 Change the order of the equations so as to make this equation your rst equation 3 Now apply operation 3 to eliminate z from the second equation of the system 4 Next multiply the second equation by the inverse of the coef cient of y so as to solve it for y 5 Finally use operation 3 once more to eliminate y from the rst equation Important Remarks 1 If at any point during the above process the equation 0 0 appears throw it away and solve the remaining linear equation in two variables 2 If at any point during the above process an equation of the form a 1 appears with ab constants and a 7 b then this means that your system is inconsistent ie a system with no solutions You have to keep the above two remarks in mind during the Gauss elimination process Example 38 Apply Gauss elimination to solve the 2 X 2 system x731 711 7z2y 7 39 731 711 gt 731 711 7z2y 7 7y 74 73 711 gt z 1 y 4 y 4 39 Thus 1 4 is a solution of the above equation I Solution THE REAL HEART OF MATHEMATICS 31 Example 39 Apply Gauss elimination to solue the 2 X 2 systems 7z2y 3 3m2y 712 2x74y is and 9mm 736 39 7x 2y 3 2m 7 4y 78 39 Multiply the rst equation by 71 m 7 2y 73 2m 7 4y 78 39 Add to the second equation the rst multiplied by 72 m72y 73 0 72 39 Solution The equation 0 72 appeared in the system Thus the system is inconsistent 3m 2y 712 9m 6y 736 39 Multiply the rst equation by m y 74 9m 6y 736 39 Add to the second equation the rst multiplied by 79 m y 74 0 0 39 The equation 0 0 appeared in the system Thus the system is equivalent to the single linear equation x y 74 This gives z 7 7 4 Thus the solutions are 2 73y 7 47y7 y any real number I Now solve the following exercises to make sure you have a good understanding of Gauss elimination Exercise 46 Solve the following 2 X 2 systems using Gauss elimination 72x5y 1 3m7y 710 d 3m7y 5x3y 13 7 75x3y 18 a 76z2y Exercise 47 Solve the following 2 X 2 systems using Gauss elimination 72x6y 3 72x78y 4 d 7m7y 5m715y 75 7 75x3y 713 an 7z2y 5 710 32 16 Applications of Linear Systems Why studying systems of linear equations in many variables They are very useful in solving problems encountered in different areas of science and real life Example 40 Fifty six biscuits are to be fed to ten pets Each pet is either a cat or a dog Each dog is to get six biscuits and each cat to get ue How many dogs are theref2 Solution Suppose that there are x dogs and y cats Then7 since the number of pets is 10 and7 since there are 56 biscuits available7 the following two linear equations in the variables x my 10 6x5y 56 We solve the system by the substitution method and y must hold my 10 m 107y 6m5y 56 6m 5y 56 gt m 107y m 107y 6107y5y 56 6076y5y 56 Z idem i Example 41 A friend of yours has inuested 250 in two companies A and B The stocks ofA currently sell for 3 a share and the stock of B sells for 5 a share If the stock ofA triples and the stock of B doubles then her stocks will be worth 650 Can you determine how many shares she own from each stockf2 Solution Suppose that she owns z shares from stock A and y shares from stock B Then the following two equations hold 3m 5y 250 9m 10y 650 39 We solve this 2 x 2 system 3m5y 250 9xl5y 750 5y 100 9m10y 650 9x10y 650 9x10y 650 y 20 gt y 20 gt y 20 9z10y 650 9z200 650 gm 450 THE REAL HEART OF MATHEMATICS y 20 m 50 39 Example 42 A flight leaues New York at 8pm and arriues in Paris at 9am Paris time This 13 hour di erence includes the flight time plus the change in time zones The return ight leaues Paris at 1pm and arriues in New York at 3pm New York time This 2 hour di erence includes the ight time minus the time zones plus an extra hour due to the fact that flying westward is against the wind Find the actual flight time eastward and the di erence in time zones Solution We set x the actual ight time eastward and y the difference in time zones Then my 13 mfg1 2 39 Then we have my 13 my 13 my 13 mfg1 2 n1 15 2m 14 my 13 y 5 z 7 gt m 7 39 Thus7 the actual time ight is 7 hours and the timezone difference is 5 hours I Example 43 If 20 lbs of rice and 10 lbs of potatoes cost 9 and 30 lbs of rice and 12 lbs of potatoes cost 12 then how much do 10 lbs of rice and 50 lbs of potatoes costf2 Solution Set z the price per lb of rice and y the price per lb of potatoes Then we have 20x10y 9 xy 2 30z12y 12 30z12y 12 9 1 9 1 9 m T 59 9 m T 59 307y12y 12 gt277715y12y 12 l 9 1 9 1 3 T379 gt9 i o y 39 T y 5 7 ll 22 H816 7 9 11 renew y 5 y if than 0chan RH 34 So to nd the cost of 10 lbs of rice and 50 lbs of potatoes we calculate 1 1 107 50727 5 2 I Example 44 A liquor store sells two brands of wine A and B A sells for 10 a bottle and B for 8 a bottle The entire stock is worth 820 Sales are slow and only half of the bottles ofA and g of the bottles of B are sold for a total of 490 How many bottles of each wine are left in the storef2 Solution Suppose that the store has initially z bottles of A and y bottles of B Then the following two equations must hold 10z8y 820 10z8y 820 108 490 5z6y 490 m y 82 m y 82 5z6y 490 2y 80 zgy 82 xg40 82 w 50 y 40 j y 40 j y 40 39 Therefore7 the bottles of A remaining are 25 and the bottles of B remaining are 10 I Example 45 A rectangle has perimeter 14 feet and its length is 1 unit less than 5 times its width Find the length of each of its sides Solution Let l denote the length and w the width of the rectangle Then we have 2l2w 14 23w712w 14 z 3w71gtl 3w71 6w722w 14 8w 16 l 3w71 l 3w71 Example 46 Two runners start moving towards each other on a straight line from two points that are 1000 feet apart When they meet the rst runner has covered 200 feet less that twice the distance that the second runner has covered How much distance has each of the two covered until they meetf2 THE REAL HEART OF MATHEMATICS 35 Solution Let x denote the distance that the rst runner has covered and y the distance that the second runner has covered until they meet Then my 1000 2y7200y 1000 m 2347200 m 2347200 3y 1200 j y 400 j m 2347200 m 2347200 y 400 y 400 z 24007200gt 600 39 I Now do the following exercises to get used to setting up applied problems and to solVing the resulting 2 x 2 systems of linear equations Exercise 48 An animal shelter houses 5 dogs and 7 cats The animal shelter needs 29 units of food per day to feed the 10 animals at the cost of 44 a day If the dog food costs 2 per unit and the cat food 1 per unit how many units of food does each dog and each cat consume Exercise 49 If 10 lbs of apples and 5 lbs of oranges cost 8 and 24 lbs of apples and 15 lbs of oranges cost 21 then how much do 5 lbs of apples and 50 lbs of oranges cost Exercise 50 A liquor store sells two brands of beer A and B A sells for 4 a six pack and B for 8 a six pack The entire stock is worth 320 Sales are slow and only half of the packs ofA and of the packs ofB are sold for a total of 124 How many six packs of each beer are left in the store Exercise 51 An isosceles triangle has perimeter 31 feet and its sides have length two units less than twice the length of its base What is the length of the base and the length of its sides Exercise 52 Two runners start moving towards each other on a straight line from two points that are 400 feet apart When they meet the rst runner has covered 50 feet less that twice the distance that the second runner has couered How much distance has each of the two couered until they meet Chapter 2 Matrices and Systems 21 Matrices Additive Structure Matrices are very important in management natural science engineering and social science as a way to organize data An n xm matrix is a rectangular array of numbers consisting of n rows and in columns Each number in the array is called an element or an entry of the matrix The element that occupies the i th row and the j th column of the matrix A is usually denoted by aij A itself is sometimes denoted by A aij to give a notation for its elements For an example consider the 2 x 3 matrix 2 rows and 3 columns 2 576 Al714 9 We have an 5 and agg 9 n x m is sometimes referred to as the dimension of the n x in matrix Example 47 A liquor distributor ships six packs of Budweiser Miller and Coors to the grocery stores in a small town Each brand comes in two uersions of regular and light If the distributor ships 10 Buds and 20 Bud Lights 15 Millers and 20 Miller Lights and 12 Coors and 30 Coors Lights construct a 2 X 3 matrix organizing the shipment of beer Solution The data may be depicted by the following table l Budweiser Miller Coors 10 15 12 20 20 30 Regular Light This data may be written in the form of a 2 x 3 matrix 101512 B l20 20 30l 37 38 with the understanding that the rst row corresponds to regular and the second to light and that the three columns correspond to Budweiser Miller and Coors respectively I Exercise 53 A Ford dealership ships cars to 4 small towns in the area euery month To town A they ship 5 Escorts 2 Contours and 1 Taurus To town B they ship 5 Escorts 12 Contours and 5 Tauruses to town C 2 Escorts 2 Contours and 1 Taurus and to town D 10 Escorts 20 Contours and 7 Tauruses Create a 4 X 3 matrix to organize the data Explain what each row and each column represents A row matrix is a matrix haVing only one row A column matrix is a matrix haVing only one column For instance A 2 4 7 45 is a row matrix The matrix B 75 2 is a column matrix A square matrix is a matrix with the same number of rows and columns An n x n square matrix is sometimes said to have dimension n For instance 1 7 74 C 6 75 4 is a square matrix of dimension 3 2 5 719 The sum of two n x m matrices A and B is the n x in matrix AB in which each element is the sum of the corresponding elements of A and B le more formally if C A B cijaijbij Example 48 Compute the sum A B of the following matrices 1 72 7 71 1A 76 7 andB 6 75 12 5 7215 1 73 1 73 74 2A675andB675 4 Solution 1 Wehave 1 72 7 71 17 7271 8 73 AB 76 7 6 75 766 775 0 2 12 5 72 15 1272 515 10 20 2 The rst matrix is a 2 x 2 matrix whereas the second matrix is a 2 x 3 matrix Since the dimensions of the matrices do not match the two matrices cannot be added ie their sum is not de ned Exercise 54 Compute the sum A B of the following matrices THE REAL HEART OF MATHEMATICS 39 1A27713andB 7 79 8 13 4 13 3 13 4 2Al6 512lmdBl6 5 4l 13 5 1 0 3A6 5 andBl17 5 10 Note that the n x m matrix 0 all of Whose entries are equal to 0 has the property AOOAA7 for everynxm matrixA This is the reason Why it is said to be the zero matrix For instance consider the 2 x 4 matrix A 13 g J We have 1 3 7 10 0 0 0 0 AOl6 5 9 2ll0 0 0 ol 10 30 70 100713 7 10 60 50 90 20 6 5 9 2lA39 The additive inverse or negative of a matrix A is the matrix 7A in which each element is the additive inverse of the corresponding element of A le7 more formally7 if B 7A then bij7aij forall Example 49 Compute the additive inverse 7A of the matrix A 13 14 J Solution We have 71477 1 3 4 7 1 773 774 7 1 3 4 7 6 5 4 7 6 775 4 7 6 5 4 39 4 10andB 6 7 6 75 91 Exercise 55 Compute the additive inverses 7A and 7B of the following matrices A 4 The negative inverse 7A of the matrix A has the important property that when added to A the sum is the zero matrix That is A 7A 7A A 0 for every matrix A Consider for instance the matrix A 756 3 7 109 J We have that 6 73 0 7Al75 7 719i 76 3 0 6 73 0 7 5 7719 75 7 7 766 373 00 0 0 0 70 0 0 0 quot 575 77719719 The subtraction of matrices of the same dimension is de ned in a manner comparable to the subtraction of real numbers Therefore A 7A 7 The difference A7 B of two 71 x m matrices A and B is the n x m matrix in which each element is the difference of the corresponding elements of A and B le more formally AiBAiB Example 50 Compute the di erence A 7 B where 6 313 10 7517 1A75 7 iSandB 7 712 6 10 75 2H3 gym 1 7812 79 713 Solution 1 Wehave AiBA7B765E7170 152167l 6 313 7105717 75778 7712 76 6710 35 13717 74 8 i4 712 19 714 39 7577 712 7876 THE REAL HEART OF MATHEMATICS 41 2 The two given matrices are of different dimensions Thus7 their difference is not de ned I Exercise 56 Compute the di erence A 7 B where 71 2 74 90 746 12 J39Al75 26 77lmd3l71710l7 71 2 2A 75 26 andBH 9 8 71 2 9 76 3A 75 26 andB 1 71 9 8 74 3 The product of a number 0 and a matrix A is the matrix CA each of whose elements is 0 times the corresponding element of A le7 more formally7 if B CA7 bijcaij forall Example 51 Compute the matrix 3A and the matrix 224175B7 whereA and 3 77 31 5 Solution Wehave 9 76 39 3 76 27 718 3A3l171ll313lt71gtll3 73l Also 9 76 3 77 225B2171571 5 7 18 712 15 735 7 3 23 7 2 72 7 75 25 7 7 727 39 I 9 72 5 ExerCISe 57 ComputethematrszA andthematrZI72A3B7whereA 71 71 2 73 71 7 andB5 g 712 42 22 Multiplicative Structure Multiplying matrices is a more involved operation than multiplying a number with a matrix To explain this operation7 the product of a row matrix with a column matrix is explained rst The product of a row matrix A with in columns with a column matrix B with in rows is de ned to be the square matrix of dimension 1 Whose entry is obtained by multiplying the corresponding entries of A and B and adding the results le7 more formally7 if C A B7 C11 aiibii 0112521 aimbmi Example 52 Find the product of the matrices 1A73 717landB 774 12 6 2 A3 74 2 i6landB 5 Solution 1 Wehave 74 AB73 717 7 7374717712 12 12778489 2 Wehave 6 AB3 74 2 76 j 3674722717675l 75 188723054 Exercise 58 Find the product A B if 5 1 A 76 2 711 andB 77 3 THE REAL HEART OF MATHEMATICS 43 4 7 2A73 illandB 12 5 5 3A73 612 illandB 3 8 Now7 with the multiplication of a row matrix by a column matrix de ned7 the de nition of the product of two matrices will be introduced Let A be an n x m matrix and B an m x k matrix The product matrix A B is the n x k matrix Whose entry in the i th row and j th column is the entry of the product of the i th row of A with the j th column of B le7 more formally7 if C A B7 then Cij ailblj ai2b2j aimbmj7 for all 1g 2 g n 1 g j g k Example 53 Compute the product A B if 5 2 1A 213 6 glandB 71 2 3 77 5 2 2A 13landB 712 2 76 77 75 3 RA 72 76 andB 727 3 8 Solution 1Wehave 5 2 AB 213 6 3 12 3 77 715371723 712327277 257671733 227627377 757376 72614 71418 il10679 471221ll 7 13l 2 A is a 2 x 2 matrix and B is a 3 x 2 matrix So the number of columns ofA is different from the number of rows of B Therefore the product A B is not de ned 3 We have 75 3 AB 72 76 5 2 3 8 75533 752377 lt72 5 lt76 3 lt72 2 lt76 lt77 3583 32877 7259 710721 716 731 710718 7442 728 38 1524 6756 39 750 Now do the following exercise to make sure that you understand the notion of product of an n x m with an m x k matrix Exercise 59 Compute the product A B if 71 3 LA 2 76 andBi 5131l 4 7 71 3 5 2A 2 i6andB73 75 3 5 2 3A 72 76 andB 3 77 3 8 71 0 Matrix multiplication has some of the nice properties of the multiplication of numbers For instance it is associatiue and distributive This means that if A is an n x m B is an m x k and C is a k x 1 matrix then ABCABC ifAis anuxm matrix and Band Care twomx kmatrices then ABCABAC and if BCarenxm matrices andAis anm x k matrix then BCABACA However matrix multiplication is not commutatiue In other words there exist square matrices of dimension n A and B such that 14373314 THE REAL HEART OF MATHEMATICS 45 Exercise 60 Find two 2 x 2 matn39ces A and B such that A B 7 B A The identity matrix of dimension n is the square matrix of dimension 71 whose diagonal entries are equal to 1 and all other entries equal to O For instance the identity matrix of 0 dimension 2 is 12 1 1 J and the identity matrix of dimension 3 is 13 0 1 0 0 0 1 The identity matrix plays in matrix multiplication the same role that the identity ele ment 1 plays in the multiplication of numbers It has the property that if A is an n x m matrix and Im the identity matrix of dimension m then A Im A and if In is the identity matrix of dimension n and A is any n x m matrix then 1 A A Exercise 61 Let A 2 6 Compute the products 11 8 113A 46 23 Augmented Matrices and Systems of Equations We revisit in this lecture the Gauss elimination method of solving 2 x 2 systems Our goal is to rst recast the systems as matrices by keeping only the coef cients of the variables and the constants involved in each of the linear equations and then reformulate the allowable operations in terms of row operations of the corresponding matrices This recasting will lead to the so called Gauss Jordan method for solving n x m systems ie systems consisting of 71 linear equations in m variables We rst present an example of a solution of a 2 x 2 system with the Gauss elimination as a reminder of the method Example 54 Solve the following 2 X 2 system using Gauss elimination 2m 7 5y 717 73m 1 3y 12 39 Solution First multiply the rst equation by We get 95 3y 73m 1 3y 12 39 Now add to the second equation the rst multiplied by 3 r Mx R l 1 010le Q6 QC 1 l l wl ml RH Next multiply the second equation by 7 migy y 339 Finally add to the rst equation the second equation multiplied by g m 71 y 3 39 Hence our system has the solution 71 3 I Note that the variables x and y are carried over from stage to stage in the solution of the system without really affectng the process The crucial elements in each stage are the coef cients of the variables and the constants and the way they are manipulated To organize these data without showing the variables we use the following table coef cient of z coef cient of y constant term rst equation 2 75 second equation 73 3 12 THE REAL HEART OF MATHEMATICS 47 Thus recasting this table as a matrix we obtain 2 75 717 73 3 12 Note the vertical line that separates the coefficients from the constant terms The square matrix of dimension 2 on the left of the vertical line 2 75 l 73 3 l is called the coef cient matrix of the system The 2 x 3 matrix above is called the augmented matrix of the system The three allowable operations in the Gauss elimination method translate to the fol lowing three allowable operations for manipulating the augmented matrix with the goal of solving the 2 x 2 system Matrix Row Operations for Solving Linear Systems 1 lnterchange two rows of the matrix 2 Multiply all the entries in a single row of the matrix by a nonzero constant 3 Add to one row a multiple of another row We see how these operations may be applied to solve the given 2 x 2 system Example 55 Consider the augmented matrix of the system given in Example 54 Apply matrix row operations to solve the system Solution 2 75 717 mg 1 7 7 news 1 75 73 73 3 12lal73 3 a 07 7 Tzig 1 7 71277 rier1gr2 1 0 71 A A 0 1 3 0 1 3 The system corresponding to this augmented matrix is the system z 71 and y 3 I The process followed to solve the 2 x 2 system above is called the augmented matrix method or the GaussJordan method The usefulness of this method lies in the facts that rst it is applicable for systems with more equations in more variables and second in that it is easily programmable to be executed by a computer We outline the steps of this method GaussJordan Method H to DJ q 01 a Obtain from the system its augmented matrix A Use row operation 2 to make all 1 Use repeatedly row operation 3 to eliminate the remaining entries in the rst column Next make 122 1 using again row operation 2 Use repeatedly row operation 3 to eliminate all other entries in the second column Repeat the above steps for all other columns The Gauss Jordan method is applied below to some more complicated systems Example 56 Use the Gauss Jordan method to solve the 3 X 3 system S m 7 2y 1 z 0 3m y 52 8 72m 7 5y 1 z 73 olution The augmented matrix of the given system is 1 72 1 0 3 1 75 8 72 75 1 73 We proceed to apply a series of row operations to solve this system 17210 17210 17210 3 175 8 quot173 0 7 78 8 it 0 7 78 8 L 72 75 1 73 72 75 1 73 0 79 3 73 1 72 1 0 1 0 9 E 1 0 79 E 0 1 g 7195272 0 1 g 7 7393ng 0 1 7 7 7 37571 079373 079373 0075757 10 E 176 THHQT 10 0 1 THHL 10 0 1 01717301932L73010 0 0 0 1 71 0 0 1 71 0 0 1 71 Thus the system obtained is m17 3107 and 271 THE REAL HEART OF MATHEMATICS Example 57 Use the Gauss Jordan method to solve the system m y 3 72m y 0 3m 1 3y 9 Solution The augmented matrix of the system is 113 113 113 7210 it 0 3 6 FEB 0 3 6 339 339 000 OOH OHO OMH 113 012 if 000 The nal system gives z 1 and y 2 Example 58 Use the Gauss Jordan method to solve the system m y 7 z 3 2m 7 y 32 13 Solution Take the augmented matrix 1 1 71 3 729727271 1 1 71 3 we 2 71 3 13 a 0 73 5 7 a 1 1 71 37137210 0177 0 g E Thus7 the equations of the equivalent system are 2 m m1 w a m 37 3 9 32 T y 3 32 Hence the solutions are given by 2 16 5 quot2 mm 7 3 37 32 7 372 2 any real number 50 Example 59 Use the Gauss Jordan method to solve the system m 2y 7 32 1 72m 7 4y 62 72 7x y 52 5 Solution Take the augmented matrix 12731 12731 12731 72 74 6 72 Wit 0 0 0 0 73 71 1 5 5 12 71 1 5 5 711 5 5 0 0 0 0 12731l 2731 10 73 0326401 2TWEZT201 2 0 0 0 0 0 0 0 0 0 0 0 0 Thus the equations are x7 2 73 i m 73 2 2 1e 2 y g2 2 y 2 7 32 Hence the solutions are given by 13 2 2 7 3 732 22 2 any real number Example 60 Use the Gauss Jordan method to solve the system 3m y 52 4 2m 5y 7 32 9 74m 10y 62 77 Solution Take the augmented matrix 3 71 5 4 l 1 7 g g 2 5 73 9 h 2 5 73 9 WK 74 710 6 77 74 710 6 77 1 1 5 A 1 1 5 1 3 0 0 3 3 3 3 3 35 34 38 74 710 6 77 0 77 7 7g l E A Q g 0 5 3 5 0 5 3 5 3 3 3 3 3 3 THE REAL HEART OF MATHEMATICS 51 17H 00 0L The last equation gives 0 7 which shows that we have an inconsistent system with no solutions I Now try to use the Gauss Jordan method to solve the following exercises to make sure that you have a good understanding of the method Exercise 62 Use the Gauss Jordan method to solve the following systems 1 m 7 2y 42 6 m 7 y 52 76 m y 132 6 and 3m 3y 7 2 10 72m 6y 7 2 710 m 3y 22 75 2 z 2y 7 2 0 m 2y Z 5 3 7 7 6 and 2m y 7 32 72 y 2 7 3m y 42 75 5 3m 5y 7 2 0 3m 7 2y 2 6 4m 7 y 22 1 and 3m y 7 2 74 76m 710y 22 0 7x 2y 7 22 78 4 imiy yiiii d y 2 7 an 2m 7 y 22 0 6m2y74278 52 24 The Determinant Method In Lecture 8 the operation of multiplication of an n x m matrix by an m x k matrix was de ned It was pointed out that the square matrix In of dimension n all of whose diagonal entries are equal to 1 and all of whose other entries are 0 has the property that for every square matrix A of dimension n AInInAA le 1 plays in the matrix algebra a similar role to the role of the unit element 1 in the algebra of numbers It is therefore natural to ask whether matrices have inverses That is given an n x m matrix A does there exist a matrix B such that ABBAIn Example 61 Show that if a matrix A has an inverse B as shown above then A must necessarily be a square matrix of dimension n and the same is then true for B Solution Suppose that A is an n x m matrix Then since the product A B is de ned B has to be an m x k matrix for some k But the product B A is also de ned which shows that k n Hence A is n x m and B is m x n But note that in this case A B would be n x n whereas B A would be m x m Since both are equal to In by assumption we must have m n Thus nally both A and B have to be square matrices of dimension n Being a square matrix of dimension n is not enough to have an inverse Some square matrices have inverses and others do not Those that do have inverses are said to be invertible and those that do not are said to be singular Example 62 Show that if the n X n matrix A is invertible then its inverse B is unique Solution Suppose that A has two inverses B and C Then ABBAIn and ACCAIn But in this case B B In B A C B A C In 0 Hence B C and the inverse of A is unique I The unique inverse of A if it exists is denoted by analogy with the inverse of a number by A l THE REAL HEART OF MATHEMATICS Ulchan 1 OH For instance the matrix A J i 31 J has as inverse the matrix B J check this note that 11 1 Z 11 10 115 3113 H EH 112 2 3 5 3 5 53 01 and similarly 3 1 3 2 3 3 7 7 1 71 77 quot7 1 0 15 511 115 5 H 112 7 2 3 7 01 1 71 1 l Thus we may write 52 2 3 5 Exercise 63 Show that the inverse of A 1 is A ie A 1 1 A Example 63 Show that if a 2 X 2 matrix A J Z J is invertible then adi be 7 0 and d 7b 71 7 1 A 7 adibc J C a J Solution Suppose that A is invertible with inverse matrix B J i J Then A B 12 which is This gives am 2 ay bu 7 1 0 cm dz cy div 7 0 1 39 Thus we must have ambz 1 and aybw 0 cxdz 0 7 cydw 1 39 From the rst equation of the system in the right we conclude that not both of a and b can be 0 Suppose that a 7 0 Then solving that equation for y we get y 7 Now substituting this value for y in the second equation of the same system yields 7177 dw 1 ie ibcw adw a whence w7bc ad a Since a 7 O we have ad 7 be 7 0 and furthermore w adibc Similarly one can show that z m y 7m and z ifflw Therefore the inverse B of A is d b B 9 y adibc Tm d 71 t Z w Twila 1750 C a One may handle similarly the case where b 7 0 Now try to prove the easier converse statement 54 Exercise 64 Show thatifA a b J andadec 344 0 then the matrixB i J d 7b J c d d be He a is the inverse matrix of A a b c d is invertible or not it suffices to compute the quantity D ad H be and check whether it is zero or not This quantity is called the determinant of the matrix A It is denoted A By the previous Example and Exercise to check whether a 2 x 2 matrix A J or sometimes So if the determinant is zero the matrix is singular whereas if the determinant is not zero then A is invertible and 1 1 HI A l 7 ad H be J C a J 1 H1 J iniertiblef2 If yes compute its inverse Do the Example 64 Is the matrix A J 2 1 sameforBJ 2 33J 1 7 Solution We compute the determinant of A Dadec11HH121237 0 Hence A is invertible and D7 H m H r l O amp Q J w 1 l 03 H r J H to H H 1 H r cub t mm ADM 0le 1 For B we have Dadec2HH3H1H330 Hence B is singular I Exercise 65 Find the inuerses A 1 and B 1 if they exist where 2 5 4 2 AHJng and BHJ63J Exercise 66 Find the inuerses A 1 and B 1 if they exist where 3H5 H21 AJ5 BJ and BJ6 74J THE REAL HEART OF MATHEMATICS 55 The reason why determinants are so important in linear algebra is that they are very helpful in solving systems of linear equations The two methods that are presented below both use determinants First we present two examples one for each method Example 65 Solve the system of equations 2my 1 7xy 72 39 Solution Notice that the given system may be written in the form 2 1 as 1 liullyHal lt2 Check whether the matrix of the coef cients A 71 i J is invertible D ad 7 be 2 17 1 71 2 1 3 7 0 Now determine its inverse 1 1 1411 d 7b 1171 7 39 D 7c a 3 1 2 g g Now take equation 21 and multiply both sides on the left by A l We have 2 1 as i 1 1 11171417217 A 1 1 1 24 which gives since A 1 A 12 1 1 m 7 77 1 I 3 7 2M l 1 1721 and since multiplying any matrix by the unit matrix gives the matrix itself m l 71 1 lHi 23117217 9 3 3 ie z 1lt7gtlt72gt 1 y l 1 g 72 71 7 whencez1andy71 I The method given in the preceding example is called the Inverse Matrix Method Exercise 67 Check whether the matrix of coe icients of the system 5m 7 y 5 73m 1 2y 4 is invertible and if yes then use the inverse matrix method to solve the system 56 Exercise 68 Check whether the matrix of coe icients of the system 7x 1 4y 72 3m 7 10y 10 is invertible and if yes then use the inverse matrix method to solve the system The second method7 called the Determinant Method or Cramer7s Method works as follows Example 66 Solve the system 73m 7 y 71 2m 7 y 9 Check whether the determinant of the matrix of the coef cients is zero or not 33 j l73717712325 0 Solution Now compute 71 71 73 71 9 1 2 9 m 7 and y7 7 73 1 73 71 2 71 2 71 iez2andy T2575 Exercise 69 Use Crdmer s method to solve the system 7x 1 2y 72 3m 7 7y 2 Exercise 70 Use Crdmer s method to solve the system 75x2y 2 8m72y 4 Chapter 3 Propositional Logic 31 Statements Compound Statements Truth and Falsity A statement or proposition is a sentence that is either true or false but not both For instance 22 equals 4 is a statement since it is a sentence that is true but He is a college studen is not a statement because depending of who is meant by the He it may be a true or a false statement but we cannot tell Similarly z y gt 0 is not a statement why One uses small letters p q r or capital letters P Q R to denote statements Three symbols that are used to build more complicated expressions from simpler ones will now be introduced 0 The symbol is used to denote not 0 the symbol A is used to denote and and o the symbol V is used to denote or Thus given a statement P the sentence P is read n0t P or it is not the case that P and it is called the negation of P Given a second statement Q the sentence PAQ is read P and Q and is called the conjunction of P and Q Finally the sentence P V Q is read P or Q and is called the disjunction of P and Q Important Remark In an expression like PAQ the negation symbol assumes priority and then come the conjunction and disjunction symbols with equal priority Thus P A Q is the same as P A Q but an expression like P A Q V R is ambiguous because since A and V have the same priority it is not clear whether it means P A Q V R or P A Q V R Example 67 Let P quotIt is hot and Q quotIt is sunny Translate the following sentences in symbolic logical expressions 1 It is not hot but it is sunny 2 It is neither hot nor sunny Solution H lt is not hot but it is sunny means really it is not hot and it is sunny Therefore since lt is not hot is P and lt is sunny is Q the given sentence can be written symbolically as P A Q to lt is neither hot nor sunny means lt is not hot and it is not sunny Therefore since lt is not hot is P and lt is not sunny is Q the given sentence may be written symbolically as P A Q Exercise 71 Let S quotstocks are increasingquot and I quotinterest rates are steadyquot Write the following statement in symbolic form 1 Stocks are increasing but interest rates are steady 2 Neither are stocks increasing nor are interest rates steady Exercise 72 Let M quotKate is a math major and C quotKate is a Computer Science majorquot Write in symbolic form the statement quotKate is a math major but not a computer science majorquot If our compound sentences are to be statements then they must always be either true or false The truth value of the compound sentences may be determined by the truth values of the statements out of which they are composed by the following rules o If P is a statement variable the negation of P not P is denoted by P and has the opposite truth value from P P is true if P is false and P is false if P is true Summarizing as a truth table P P F T T F o If P Q are statement variables the conjunction ofP and Q P and Q is denoted by P A Q and it is true only when both P and Q are true Summarizing as a truth table THE REAL HEART OF MATHEMATICS 59 o If P7 Q are statement variables7 the disjunction of P and Q7 77P or Q 7 is denoted by P V Q and it is true if at least one of P and Q is true and false if both P and Q are false Summarizing as a truth table Up to this point7 only the expressions P P A Q and P V Q have been assigned truth values Out of the connectives not7 and and or one can compose increasingly complex expressions such as P V Q7 P V Q A P A Q7 P A Q V R and so on Such expressions are called statement forms or propositional forms More precisely7 a statement form or propositional form is an expression made up of statement variables P7 QR7 and logical connectives such as o A7 V that becomes a statement when actual statements are substituted for the component statement variables The truth table for a given statement form displays the truth values that correspond to the different combinations of truth values for the variables Example 68 Construct the truth table for the connective EB de ned by PQPVQA PAQ Solution P QlPVQ PM TPAQlPVQATPAQ T T T T F F T F T F T T F T T F T T F F F F T F 63 is called the 77XOR77 or exclusive or connective and its meaning in English is 77P or Q but not both Exercise 73 Construct the truth table for P A Q V R Exercise 74 Construct the truth table for P A Q V P V Q 60 32 Logical Equivalence Tautologies and Contradictions Consider the two compound statements P A Q and Q A P They have the following truth tables We see that they are both true or both false at exactly the same combination of truth values for their variables Such statement forms are said to be logically equivalent More precisely two statement forms are said to be logically equivalent if and only if they have identical truth values for each possible substitution of statements for their statement variables Logical equivalence of P and Q is denoted by P E Q Two statements are logically equivalent if and only if when the same statement variables are used to represent identical component statements their forms are logically equivalent Testing for the logical equivalence of two statement forms P and Q 1 Construct the truth table for P 2 Construct the truth table for Q using the same statement variables for identical com ponent statements 3 Check each combination of truth values of the statement variables to see whether the truth value of P is the same as the truth value of Q a If in each row the truth value of P is the same as the truth value of Q then P and Q are logically equivalent b If in some row P and Q assume different truth values then P and Q are not logically equivalent Example 69 Show that P E P Solution We have Thus P and P agree on all rows of their truth tables and therefore they are logically equivalent I Example 70 Show that P A and P A Q are not logically equivalent THE REAL HEART OF MATHEMATICS 61 Solution Method 1 Construct the truth tables and show that there exists at least one line where the two statement forms assume different truth values P Ql P so PAQl PAQ PA Q T F TTF F F TFF T F T F FTT F F T F FFT T F T T Since at the second and third lines the truth tables differe P A Q 3E P A Q Method 2 Find an example to show that the two statement forms are not equivalent To nd an example you must nd two statements such that when you substitute one for P and the other for Q in the two forms you will obtain a new statement that is true in the rst case and false in the second or Vice versa To illustrate this let P 0 lt177 and Q 771 lt 0 Then P A Q is the statement 77It is not both the case that 0 lt 1 and 1 lt 077 which is a true statement On the other hand P A Q is the statement 770 K 1 and 1 K 0 which is false I Example 71 Prove the First De Morgan7s Law P A Q E P v Q Solution We use the truth table method Q T F T F P Q WM Pv Q F T T T The entries in all rows of the columns corresponding to P A Q and P V Q are the same Hence P A Q E P V Q sssss Hadwq u ssss ssssgt sass Exercise 75 Determine whether P V Q V P A R E P V Q A R Exercise 76 Determine whether P V Q A P V R A P V Q E P V R Example 72 Use De Morgan s Laws to write the negations of the statements 1 John is six feet tall and he weighs at least 200 pounds 2 The bus was late or Tom s watch was slow Solution 1 John is not six feet tall or he weighs less than 200 pounds 2 The bus was not late and Tom s watch was not slow I Exercise 77 Use De Morgan s laws to write the negation of 71 lt m g 4 Exercise 78 Use De Morgan s Laws to write the negation of quotHat is a math major and Hal s sister is a computer science majorquot A tautology is a statement form that is always true regardless of the truth values of the individual t uh ri m red for its t variables A statement whose form is a tautology is called a tautological statement A contradiction is a statement form that is always false regardless of the truth values of the individual t uh ri m red for its t variables A statement whose form is a contradiction is called a contradictory statement Example 73 Determine whether the statement form PAQV PVPA Q is a tautology or a contradiction Solution We construct the truth table P Q PAQ so PA Q AP PVPA Q PAQV PVPA Q FF F T F T T T FT F F F T T T TF F T T F T T TT T F F F F T Thus7 since for all truth values of the statement varialoles7 FAQ V PV PA Q assumes the truth value T7 it is a tautology I Exercise 79 Determine whether the statement form P A Q A P V is a tautology or a contradiction Exercise 80 Determine whether the statement form PAQAQARA Q is a tautology or a contradiction THE REAL HEART OF MATHEMATICS 63 33 Conditional Statements Let P and Q be statements A sentence of the form If P then Q is symbolically denoted as P a Q P is the hypothesis and Q is the conclusion The sentence If 48 is divisible by 6 then 48 is divisible by 3 is an example of such a sentence Such sentences are called conditionals because the truth of Q is conditioned on the truth of P gt is a connective like A and V and it can be used to combine statements to create new ones More formally if P and Q are statement variables the conditional of Q by P is read If P then Q or P implies Q and is denoted by P a Q It is false only if P is true and Q is false It is true for all other combinations of truth values for the variables P and Q lts truth table is therefore A conditional statement Whose hypothesis is false is said to be vacuously true For instance the statement If the Lakers win the game they will be champions is vacuously true if the Lakers do not win the game gt has the lowest priority among the connectives Thus the statement form P V Q a P should be read as P V Q a P Example 74 Construct the truth table for the statement form P V Q gt P Solution PV Q PV QH P wwaaw unadjwo Hahwq u swarms Hausa Hairs Exercise 81 Construct the truth table for P V Q a Q Exercise 82 Do the same for P A Q a R Exercise 83 Do the same for P V P A Q a Q Example 75 Show thatPVQ HR E P HR A Q a R Solution We construct the truth tables P Q R PVQ PAR QHR PVQHR PHRAQgtR T T T T T T T T T T F T F F F F T F T T T T T T T F F T F T F F F T T T T T T T F T F T T F F F F F T F T T T T F F F F T T T T Now the last two columns agree on all rows Thus P V Q a R and P a R A Q a R are logically equivalent I Exercise 84 Use the Example to rewrite the statement quot Ifm gt 2 arm lt 72 then m2 gt 4quot Example 76 Show that P a Q E P V Q Solution Construct the truth tables Thus7 since all entries in the last two columns are the same P a Q and P V Q are logically equivalent Example 77 Rewrite the following statement in the if then form quotEither the Red Wings win this game or they end the season lastquot Solution Let P 77The Red Wings win this game77 and Q 77They end the season last Then the given statement is the statement P V Q Now P 77The Red Wings do not win this game So the equivalent if then version P a Q is 77If the Red Wings do not win this game7 then they end the season last I THE REAL HEART OF MATHEMATICS 65 Exercise 85 1 Show that P a Q E P A Q 2 Use part 1 to write the negation of quotIf Sue is Dan s mother then Ron is his cousinquot 3 Do the same with quotIf I study hard then I will get an Aquot Exercise 86 1 Show that the following statement forms are all equivalent PAQVR PA QHR PA RHQ 2 Use part 1 to write quotIfn is prime then n is odd or n is 2quot in two di erent ways The contrapositive of a conditional 77If P then Q77 is the statement 77If Q then P ln symbols the contrapositive of P a Q is Q a P It is a fundamental law of logic that a conditional statement is logically equivalent to its contrapositive Example 78 Show that P a Q E ag a P Solution Construct the truth tables P Ql P QlPHQ oss F F T T T T F T T F T T T F F T F F T T F F T T Thus P a Q and Q a P are logically equivalent I Exercise 87 Write the contrapositiue of quotIf today is Easter then tomorrow is Mondayquot Exercise 88 Use the contrapositiue to rewrite the statement quotIf Terry is in good form then he will play in the gamequot 66 34 Converse Inverse and Biconditionals Suppose we are given the conditional statement If P then Q The converse of if P then Q is the statement if Q then P The inverse of if P then Q is the statement if P then Q ln symbols we have converse of P a Q is Q a P and inverse of P a Q is P a Q Example 79 Write the inverse and converse statements of a If the keeper saves this shot then the team will win 17 If Kate drops this class she will not be full time Solution a Let P the keeper saves this shot and Q the team will Win Then the given statement is the statement P a Q lts converse is the statement Q gt P7 ie7 if the team Wins7 then the keeper will save this shot lts inverse is the statement P a Q But7 P the keeper does not save this shot and Q the team will not Win Hence7 the inverse statement is if the keeper does not save this shot7 then the team will not Win Let P Kate drops this class and Q she will not be full time Then the given statement is the statement P a Q lts converse is the statement Q gt P7 ie7 if Kate is not full time then she will drop this class lts inverse is the statement P a Q But7 P Kate does not drop this class THE REAL HEART OF MATHEMATICS 67 and Q she will be full time Hence the inverse statement is if Kate does not drop this class then she will be full time Exercise 89 Write the converse and the inverse of the statements 1 IfS is a square then S is a rectangle 2 Ifn is prime then n is odd or n is 2 3 Ifn is divisible by 6 then n is divisible by 2 and n is divisible by 5 We can show that oPecioeP P a Q a P a ea c Q a P E P a Q In fact these may be derived by the following truth table P Ql P QlPHQ QHP PH Q FFT T T T T FTT F T F F TFF T F T T TTF F T T T Note that the columns under Q a P and P a Q are identical but that they both differ from the column corresponding to P a Q So neither the converse nor the inverse of a statement is logically equivalent with the statement itself but they are equivalent with each other If P Q are statements then P only if Q means if not Q then not P or equivalently If P then Q Example 80 Use the contrapositive to write in two ways Terry will play only if he is in top form Solution Let P Terry will play and Q he is in top form Then the given statement is P only if Q This is by de nition equivalent to P a Q and by the logical equivalence of a statement with its contrapositive also with Q a P Hence it may be written equivalently in the following two forms 1 If Terry plays then he is in top form and 2 If Terry is not in top form then he will not play I Exercise 90 Use the contrapositiie to write in two ways Don will be allowed in the boat only if he is an expert sailor Given statement variables P and Q the biconditional ofP and Q is P if and only if Q and is denoted by P lt gt Q It is true if both P and Q have the same truth values and false if they have opposite truth values Sometimes instead of if and only if the abbreviation iff is used In summary the truth table for lt gt is PHQ HWHWQ NEWS The connective lt gt has the same priority with a Thus in complicated statement forms containing several connectives the following table gives the order of strength in decreasing order order connectives It is not a coincidence that the biconditional is called if and only if The following truth table shows that Plt gtQ3PgtQAQgtP The rst of these is P only if Q and the second is P if Q Hence P if and only if Q turns out to be logically equivalent to P only if Q and P if Q PCNPHQQHPUMQ mamwwam F39F T T T T F39T T F F F T17 F T F F J T T T T T Exercise 91 Prove that P lt gt Q lt gt R 3E P lt gt Q A Q lt gt R Exercise 92 Write the following statements as conjunctions of two if then statements 111wxw THE REAL HEART OF MATHEMATICS 69 2 lxl m i m Z 0 If P and Q are statements7 then 0 P is a suf cient condition for Q means If P then Q o P is a necessary condition for Q means If not P then not Q Since P a Q E Q a P7 P is a necessary condition for Q also means if Q then P Therefore P is a necessary and suf cient condition for Q means P if7 and only if7 Q Example 81 Write the following statements in the if then form 1 Mike s studying is a necessary condition for his passing this class 2 Ryan s being a student is a su icient condition for using the computer labs on cam pus Solution 1 Since P is a necessary condition for Q means if Q then P 7 the given statement is equivalent to if Mike studies7 then he will pass this class 2 Since P is a sufficient condition for Q means if P then Q 7 the given statement is equivalent to if Ryan is a student7 then he may use the computer labs on campus I Exercise 93 Rewrite the following statements in if thenform 1 Starting from home at 800am is a su icient condition for my being at work on time 2 Hauing two equal angles is a su icient condition for a triangle to be isosceles 3 Being diuisible by 5 is a necessary condition for a number to be diuisible by 9 4 The temperature being at or under 32 is a necessary condition for water to turn into ice 70 35 Valid Arguments An argument is a sequence of statements All statements except the nal one are called premises or assumptions or hypotheses The nal statement is called the conclu sion One uses the symbol 1 read therefore or7 sometimes a horizontal line7 also read therefore to separate the premises from the conclusion For instance If Socrates is a human being7 then Socrates is mortal Socrates is a human being Socrates is mortal is an argument It has the abstract form If P then Q If P then Q P or also P Q An argument form is a sequence of sentence forms that yield an argument when all statement variables in the sentence forms are substituted for by actual statements An argument form is valid if no matter what particular statements are substituted for the statement variables in its premises7 if the resulting premises are all true7 then its conclusion is also true An argument is valid if its argument form is valid When an argument is valid and its premises are true7 the truth of the conclusion is said to be inferred or deduced from the truth of the premises Test an argument form for validity 1 Identify the premises and the conclusion 2 Construct a truth table for all the premises and the conclusion 3 Find the rows7 called the critical rows in which all the premises are true 4 In each critical row determine whether the conclusion of the argument is true a If it is7 then the argument form is valid b If not7 the argument is invalid Example 82 Show that the argument form PVQVR R PVQ is valid THE REAL HEART OF MATHEMATICS 71 Solution We construct the truth table for the premises P V Q V R and R and the conclusion PVQ P Q RleRleQvR R PVQ T T T T T F T T T F T T T T critical T F T T T F T T F F F T T T critical F T T T T F T F T F T T T T critical F F T T T F F F F F F F T F The second7 fourth and sixth rows in the truth table are critical because both assumptions are true Since in these three rows the conclusion is also true the given argument form is valid Example 83 Show that the argument form is invalid Solution PHQV R7QgtPAR PAR Construct the truth table for the premises and the conclusion Q R R QV R PAR PHQV R QHPAR PHR WWWWHHHH U WWHHEEHH TF T T T T T FT T F T F TF F T F T FT T F T T F TF T F T F FT T F T F TF F F T T T FT T F T T T Only the truth values of the conclusion at the critical rows have been computed Since in one of these fourth row the conclusion is false7 the argument is invalid Exercise 94 Determine whether the following argument forms are valid 1 PHQ7QHPLPVQ 2 P7PaQ7 QVR R 3 PVQ7Pgt Q7PgtRR 4 PHQ7PgtRXPgtQAR In what follows7 several special valid argument forms that are used very often for de ductions are presented The argument form If P then Q P Q is called modus ponens7 which is the Latin for method of affirming The following truth table shows that it is a valid argument form Only the rst row is critical and in that row the conclusion is true Hence modus ponens is a valid argument form The argument form If P then Q ac P is called modus tollens7 which is the Latin for method of denying The following truth table shows that it is a valid argument form Only the last row is critical and in that row the conclusion is true Hence modus tollens is a valid argument form Example 84 Use modus ponens or modus tollens to ll in the blank rows so that the following arguments become valid deductions 1 If there are more balls than boxes then two balls are in the same box There are more balls than boxes THE REAL HEART OF MATHEMATICS 73 If this number is divisible by 6 then it is divisible by 2 This number is not divisible by 2 Solution 1 Two balls are in the same box 2 This number is not divisible by 6 I Exercise 95 Disjunctive Addition 1 Show that the following argument forms are valid P Q P v Q and P v Q 2 Suppose you are compiling a list of all freshmen and sophomores in your class Explain how the argument forms above allow you to add someone who is a freshman to your list Exercise 96 Conjunctive Simpli cation 1 Show that the following argumentforms are valid P V Q P V Q TQ and P P Q 2 Construct an example to show how these argument forms may be used for deductions Exercise 97 Hypothetical Syllogism 1 Show that the following argument form is valid P gt Q Q gt R P gt R 2 Construct an example to show how this argument form may be used for deductions Exercise 98 Dilemma Proof by Division into Cases 1 Show that the following argument form is valid P v Q P gt R Q gt R R 2 Show how this argument form may be used to deduce from the premise that every real number is either negative or nonnegative the conclusion x2 74 36 Fallacies A fallacy is an error in reasoning that results in an invalid argument Example 85 Converse Error Show that the following argument is invalid If George is a cheater then George sits in the back row George sits in the back row George is a cheater Solution The general form of the above argument is P gt Q Q7 P The truth table exploring the validity of that form is From the table we see that row 2 is a critical row both premises are true in which the conclusion is false Therefore7 the given argument form is invalid Example 86 Inverse Error Show that the following argument is invalid If interest rates are going up then stock market prices will go down Interest rates are not going up Stock market prices will not go down Solution The general form of the above argument is P gt Q P nQ The truth table exploring the validity of that form is P gt Q P J Q WHEN THE REAL HEART OF MATHEMATICS 75 From the table we see that row 2 is a critical row both premises are true in which the conclusion is false Therefore the given argument form is invalid I Exercise 99 Use symbols to write the logical form of each argument and then use the truth table to test the argument for ualidity 1 If Tom is not on team A then Euan is on team B If Euan is not on team B then Tom is on team A Tom is not on team A or Euan is not on team B 2 Daue is a math major or Daue is an economics major If Daue is a math major then Daue is required to take Math 341 Daue is an economics major or Daue is not required to take Math 34 Exercise 100 Some of the following arguments are ualid and some exhibit the conuerse or the inuerse error Use symbols to write the logical form of each argument If the argument is ualid identify which ualid argument form guarantees its ualidity Otherwise state whether the conuerse or the inuerse error has been made 1 If Jim solued this problem correctly then Jim got the answer 2 Jim obtained the answer 2 Jim solued the problem correctly 2 This real number is rational or it is irrational This real number is not rational This real number is irrational 5 If I go to the mouies I will not nish my homework If I don t nish my homework I won t do well on the exam tomorrow If I go to the mouies I won t do well on the exam tomorrow Sometimes people mix up the ideas of validity and truth If an argument seems valid they accept the conclusion as true And if an argument seems shy really a slang expression for invalid they think the conclusion must be false This is not correct For instance consider the argument If John Lennon was a rock star then John Lennon had red hair John Lennon was a rock star John Lennon had red hair 76 This argument is a valid argument by modus ponens But one of its premises is false and so is its conclusion Also consider the argument If Detroit is a big city7 then Detroit has big buildings Detroit has tall buildings Detroit is a big city This argument is invalid by the converse error but it has a true conclusion Exercise 101 1 Giue an example of a ualid argument with a false conclusion 2 Giue an example of an inualid argument with a true conclusion Example 87 Contradiction Rule Show that the following argument form is valid P gt C where C is a contradiction P Solution The following truth table shows the validity of the argument Only the rst row is a critical row and in that row the conclusion is also true I Study the following examples and exercises to get an idea on how you would tackle more complex situations based on the argument forms that have been presented so far Example 88 How to use logic to nd your glasses You are about to leave for school one morning and discouer that you don t have your glasses You know that the following statements are true a If my glasses are on the kitchen table then I saw them at breakfast b I was reading the newspaper in the liuing room or I was reading the newspaper in the kitchen c If I was reading the newspaper in the liuing room then my glasses are on the co ee table d I did not see my glasses at breakfast e If I was reading my book in bed then my glasses are on the bed table I I was readin the news a er in the kitchen then m lasses are on the kitchen table 9 p P y y g THE REAL HEART OF MATHEMATICS 77 Where are the glasses Solution Here is the reasoning that leads via valid arguments to the conclusion that the glasses are on the coffee table 1 The glasses are not on the kitchen table by ad and modus tollens 2 I did not read the newspaper in the kitchen by f1 and modus tollens 3 I read the newspaper in the living room by b2 and disjunctive syllogism 4 My glasses are on the coffee table by c3 and modus ponens I Example 89 Knights and Knaves or Hints for travelling abroad You nd your self on an island containing two types ofpeople knights who always tell the truth and hnaues who always lie You visit the island and are approached by two natives who speak to you as follows A says B is a knight B says A and I are of opposite type What are A and B Solution Here is the reasoning that leads via valid arguments to the conclusion that both A and B are knaves 1 Suppose A is a night 2 What A says is true by the de nition of a knight 3 B is a night too by 2 4 What B says is also true by the de nition of a knight 5 A and B are of opposite types by 4 6 1 and 3 and 5 are contradictory So the assumption 1 is false by the contradiction rule 7 A is not a knight by 6 8 A is a knave by 7 and disjunctive syllogism 9 What A says is false by the de nition of a knave 10 B is not a night by 9 78 11 B is a knave also by disjunctive syllogism I Exercise 102 How to nd a hidden treasure You nd a note written by a pirate containing ue true statements about a hidden treasure a If this house is next to a lake then the treasure is not in the kitchen b If the tree in the front yard is an elm then the treasure is in the kitchen c This house is next to a lake d The tree in the front yard is an elm or the treasure is buried under the flagpole e If the tree in the backyard is an oak then the treasure is in the garage Where is the hidden treasuref2 Exercise 103 More hints for travelling abroad You nd yourself on an island con taining two types of people knights who always tell the truth and knaues who always lie You uisit the island and are approached by natiues who speak to you as follows 1 A says Both of us are knights B says is a knaue What are A and B 2 C says Both of us are knaues D remains silent What are C and D 5 E says F is a knaue F says E is a knaue What are E and F 4 U says None of us is a knight V says At least three of us are knights W says At most three of us are knights X says Exactly ue of us are knights Y says Exactly two of us are knights Z says Exactly one of us is a knight Which are knights and which are knauesf2 THE REAL HEART OF MATHEMATICS 79 Exercise 104 How to solve crime mysteries A detectiue who is trying to solue a murder mystery determined that a Lord Hazelton the murdered man was killed by a blow on the head with a brass candlestick F Either Lady Hazelton or a maid Sara was in the dining room at the time of the murder c If the cook was in the kitchen at the time of the murder then the butler killed Lord Hazelton with a fatal dose of strychnine d if Lady Hazelton was in the dining room at the time of the murder then the chau eur killed Lord Hazelton e If the cook was not in the kitchen at the time of the murder then Sara was not in the dining room when the murder was committed If Sara was in the dining room at the time when the murder was committed then the wine steward killed Lord Hazelton Assuming only one cause of death is it possible for the detectiue to deduce the identity of the murderer from the aboue factsf2 If so who did kill Lord Hazeltonf2 Chapter 4 Sets 41 Basic De nitions and Examples A set is a collection of objects called its elements or members For instance 123 is the set containing the elements 12 and 3 1 23 denotes the set containing all positive integers The axiom of extension says that a set is completely determined by its ele ments This means that when writing a set repeating elements or changing the order of elements is irrelevant The only property that matters is membership of an element in the set For instance 1 233 1 13 2 and 213 all denote the same set the set that contains the three elements 12 and 3 Sets are usually denoted by capital letters such as A B C S X Y etc If x is an element of the set A then we write x E A read z is in77 A or z is an element of77 A or z belongs to77 A To indicate that z is not an element of a set A we write z A Sets may be themselves elements of other sets For instance the set 1 has two elements It contains the number 1 and it also contains the set that contains the number 1 Do not confuse 1 with They are two different mathematical entities Example 90 Which of the following sets are equalf2 a7 5767 d7 176417 0 d7 57 0 a7 ML 6767 6 Solution The rst and third sets are the same because they both contain the elements a b c and d The difference is just in the order in which they are listed and it is irrelevant by the axiom of extension Similarly the second and fourth sets are the same since they both contain exactly the same elements a c d e The order in which these elements are listed is different in the two sets and there are repetitions in the fourth set but these are irrelevant Only membership matters by the axiom of extension Given a set S and a property P that elements of S may or may not satisfy one may construct a new set by aggregating together the elements of S that have the property P This new set is denoted by m E S and it is read the set of all z E S such that Pm is true Before seeing some more examples let us agree to denote by R the set of all real numbers by Z the set of all integers and by N the set of all nonnegative integers or natural numbers Then m E R 0 lt m g 2 denotes the set of all real numbers that are positive and less than or equal to 2 Exercise 105 Which of the following sets are equalf2 a A 012 17 Bz R71 mlt3 c Cz R71ltmlt3 d Dm Z71ltzlt3 e Ez N71ltmlt3 Example 91 Describe the set S n E Z n 71 for some integer Solution As k ranges over the set of all integers 71 only takes the values 71 and 1 Hence S 711 Exercise 106 Describe the set T m E Z m 1 71quot for some integeri If A B are sets A is called a subset of B written A Q B if and only if every element of A is also an element of B The phrases A is contained in77 B and B contains77 A are alternative ways of saying that A is a subset of B In this case B is also said to be a superset of A and one also writes B Q A For instance 1 23 Q 1234 5 because every element in the rst set is also an element in the second and 1 23 Q N since 1 2 and 3 are all contained in N If A is not a subset of B then one writes A Q B This is the case if there is at least one element in A that is not an element of B For instance 73 12 5 Q N since 73 E 73 1 25 but 73 N Example 92 Show that for every set A A Q A THE REAL HEART OF MATHEMATICS 83 Solution Every element in A is also an element in A Therefore by the de nition A Q A I Let A and B be sets A is said to be a proper subset of B denoted A C B if and only if every element of A is an element of B but there is at least one element of B that is not in A For instance 123 Q 123 but 123 gZ 123 because every element in 123 is also an element in 123 but there exists no element in 123 that is not an element in 123 On the other hand N C Z Can you explain this Example 93 Let A 3 d fg B and C dg Answer each of the following questions explaining your answers a Is B Q A b Is C Q A c Is C Q C d Is C C A Solution a B Q A becausejC B but j A b C Q A because every element in C is also an element of A c C Q C because every element of C is also an element of C d C C A because every element of C is an element of A and there is an element of A namely 0 that is not an element of C I Example 94 Which of the following are true state rnentsf2 a2 123 b 2 123 c2Q123 d 2 S 17273 6 2 Q 172 f 2 E 172 Solution a 2 6 123 is a true statement since 2 is an element of the set 123 b 2 6 123 is not a true statement since 123 does not contain the set contain ing 2 c 2 Q 123 is not true because 2 is not even a set AA d 2 Q 123 is true because every element of 2 is also an element of 123 e 2 Q 1 is not a true statement because 2 C 2 but 2 1 AA VVVV f 2 C 1 is a true statement because 2 is an element of 1 I 84 Exercise 107 Answer each of the following questions explaining your answers a Is3 1232 b Is1Q12 o Is 2 122 d Is 3 1232 615161 f1f2 17273 a Is 1 g 12 h1516172 i151 172 i151 172 Given sets A and B A equals B written A B if and only if every element of A is in B and every element of B is in A In symbols A B if and only if A Q B and B Q A Example 95 Let A n E Z n 2p for some integerp B m E Z m 2q72 for some integer q andC k E Z k3r1 forsome integerr IsAB2 IsAC392 Solution We claim that A B To prove this we must show that A Q B and B Q A So suppose rst that n E A Thus n 2p for some integer p Thus n 2p 2 7 2 whence n 2p 1 7 2 Since p is an integer p 1 is also an integer Thus n 2q 7 2 for the integer q p 1 which shows that n E B Thus A Q B Suppose conversely that m E B Then m 2q 7 2 for some integer q Therefore m 2q 7 1 But q being an integer p q 71 is also an integer which shows that m 2p for the integer p q 7 1 Therefore m E A and B Q A having shown that A Q B and B Q A we may now conclude that A B We claim that A 7 C 2 E A since 2 2 1 and 1 is an integer But 2 C If it was an element of C then there would be an integer r such that 2 3r 1 Then 1 3r whence r which is not an integer I Exercise 1 08 Let A m E Z m 2i71 for some integeriB n E Z n 3j2 for some integerj Cp Z p2r1for some integerrDq Zq3s71for some integers IsABQIsAC39IsAD2 IsBD2 Exercise 109 Let R m E Z m is divisible by 2S y E Z y is divisible by 3 and T z E Z z is divisible by 6 Is R Q T Is T Q B Is T Q S Explain your answers THE REAL HEART OF MATHEMATICS 85 42 Operations on Sets When we are discussing about sets all the sets under consideration will be assumed to contain elements that are taken from a large set understood in advance called the universe of discourse or universal set and denoted by U So fo instance if all our sets consist of real numbers we could use R the set of all real numbers as our universal set If all our sets consisted of human beings we could take the set of all human beings as being our universal set In the sequel we introduce operations on sets that produce new sets from old ones much like the matrix operations produce new matrices from old ones and the logical connectives that produce new statement forms from old simpler ones Let A B be sets in U The union A U B of A and B is the set of all elements z in U such that z is in A or z is in B Note that or here is used in the same way as in logic le it has its inclusive meaning AUB contains all elements that are in A or in B or maybe in both A and B In symbols AUBz Um A or zEB The intersection A O B of A and B is the set of all elements z in U such that z E A and z E B In symbols A Bz Uz A and zEB The difference B minus A or relative complement of A in B denoted B 7 A is the set of all elements z in the universe U such that z is in B but z is not in A In symbols B7Az Um B and The complement Ac of A is the set of all elements z in U such that z is not in A In symbols Acz Uz A Example 96 Let U abcdefgA acegB 1 5 g Find AU BA BB7A and Ac Solution The union A U B contains all elements z E U such that z E A or z E B Thus AUB acdefg The intersection A O B consists of all z E U such that z E A and z E B Thus A O B 59 The difference B 7 A consists of all z E U such that z E B and z A Therefore B 7 A d f Finally the complement ofA consists of all z E U such that z A Hence Ac 1 d f I Example97 LetURAz R71ltz O andBm R0 mlt1Fmd AUBA BandAC Solution AU B consists of all real numbers x such that z E A or z E B These are all real numbers m suchthat 71ltm 00r0 mlt1 Thus AUBz R71ltxlt1 A O B contains all real numbers m such that z E A and z 6 B7 ie7 71 lt x g 0 and O mlt 1 HenceA B Finally7 the complement of A consists of all real numbers m such that z A These are all real numbers that do not satisfy 71 lt x g 0 Therefore Acz Rz 710rmgt0 Exercise 110 Let U a7 130 deA a7 130 B 1 07d and C 19075 a Find A U B O C7 A U B O C and A U B O A U C Which of these sets are equal 17 Find Am B U C7 A O B U C and Am B U A O C Which of these sets are equal c Find A7 B 7 C and A7 B 7 C Are these two sets equal Exerciselll LetURAm RO zlt2 andBz R1ltzlt5 Find AUB7A BandAc Exercise 112 Pick a universe U and nd in it three sets A7 B and C that satisfy A Q B7 C Q B and A and C have no elements in common Let n be a positive integer and 1727 an be not necessarily distinct elements of the universe U The ordered n tuple 1727 7z consists of these elements together with the ordering rst m1 then m2 then 3 and so on7 up to zn An ordered 2 tuple is called an ordered pair and an ordered 3 tuple is called an ordered triple Two ordered n tuples 1727 zn and yhyg Wyn are equal if7 and only if7 1 y172 yg Wm y In symbols 17277n917927Hvyn ltgt901 yi z y27mwn yn Example 98 Is 12 21 How about 3 42 NM 3 Solution 1221ltgt127 21 Since the right hand side is false7 the left is also false On the other hand 3722 4 ltgt3 424 6 THE REAL HEART OF MATHEMATICS 87 Thus since the right hand side is true the two ordered triples are equal I Given two sets A and B the Cartesian product of A and B denoted A X B is the set of all ordered pairs a b with a in A and b in B In symbols AXBaba Aandb B Similarly given n sets A1A2 An the Cartesian product of A1A2 An denoted A1 X A2 X X A is the set of all ordered n tuples a1a2 an such that al is in A1 a2 is in A2 an is in An In symbols A1XA2XXA a1a2ana16A1a2 A2an A Example 99 Let A zyB 123 and C ab FindA X B A X B X C and A X B X 0 Solution We have AXB 90717727737y717y727y73 Similarly AXBWC 90797 M90737 7737a7y717a7 9727a7y737a7WWW727b7 737b7y717b7y727b77375 Finally A X B X C m1az2a m3ay1a y2a y3a x1bz2b 737b7y717b7y72yb7y737b Exercise 113 Let A z yzw and B a b List the elements in each ofA X B B X AAXAandBXB Exercise 114 LetA 1 23B uu and C mn FindAX BXC AXBXC andA X B X C Exercise 115 This will be presented in class Use Venn diagrams to depict the follow ing sets Am B B U C A0 A7 B U C A U B0 and A0 O BC Venn diagrams are extremely useful in prouiding intuition about relations between sets 88 43 Proving Subset Relations In this section we learn how to prove a relation involving unions intersections complements and difference of sets that holds for arbitrary sets Example 100 Show that for all sets A and B A O B Q A and A O B Q B Solution Recall that by the de nition of the subset relation A B Q A means that every element in A O B is also an element in A That is what we want to show So let s take an arbitrary element x in Am B By the de nition of intersection z 6 Am B means that z E A and z E B Thus z E A which was what we wanted to show Now work similarly for A O B Q B Example 101 Show that for all sets A B A Q A U B and B Q A U B Solution For A Q A U B we need to show that every element of A is also an element of A U B For B Q A U B we need to show that every element of B is also an element of A U B We do the rst and challenge you to do the second Let x be an element in A This means that z E A or z E B is also a true statement But this means that z E A U B Hence any element of A is also an element of A U B Now prove B Q A U B on your own following the same line of thought I The above proofs illustrate the basic technique that is used to prove that one set is a subset of another We summarize this method below Method for proving that one set is a subset of another set Let XY be two given sets To show that X Q Y 1 suppose that z is a particular but arbitrarily chosen element of X 2 show that z is also an element of Y Exercise 116 Show that for all sets A B C lfA Q B and B Q C then A Q C The basic properties that are used in applying the method above to show that a given set is a subset of another set are 1 zEXUYlt gtm Xorz Y 2 m6X Ylt gtm Xandm Y 3 m X7Ylt gtm Xandm Y 4 mEXclt gtx X 5 zy XxYlt gtz Xandy Y THE REAL HEART OF MATHEMATICS 89 Example 102 Show that for all sets A and B A 7 B Q A Solution We need to show that every element in A7 B is also an element of A We start by letting x be a particular but arbitrarily chosen element of A 7 B By the de nition of A 7 B we conclude that z E A and z B In particular z E A which was what we wanted to show Thus A 7 B Q A Example 103 Show that for all sets A and B if A Q B then A U B Q B Solution we are assuming that A Q B and want to show that A U B Q B le we want to show that every element of A U B is also an element of B So let us take a particular but arbitrarily chosen element x of A U B By the de nition of union this means that z E A or z E B But by out hypothesis A Q B this implies that z E A or z E A whence z E A which is what we wanted to show I Exercise 117 Show that for all sets A and B lfA Q B then A Q A O B Example 104 Show that for all sets A B and C lfA Q B then A O C Q B O C Solution We assume that A Q B and want to show that A O C Q B O C ie that every element of Am C is also an element of B O C So let x be a particular but arbitrarily chosen element of A O C By the de nition of intersection z E A and z E C But by assumption A Q B whence z E B and z E C Hence again by the de nition of intersection z E B O C We have thus shown that z E A O C implies z E B O C Therefore A O C Q B O C as was to be shown I Now follow the steps in the proof above to solve the next exercise Exercise 118 Show that for all sets AB and C lfA Q B then AU C Q B U C Example 105 Show that for all sets A B lfA Q B then B0 Q Ac Solution Suppose that A Q B We need to show that B Q Ac ie that every element in BC is also an element in A0 So let x be a particular but arbitrarily chosen element in BC By the de nition of BC we get that z B Then z A because if z E A A Q B would yield z E B and we know that z B But z A is by the de nition of A0 the same as saying that z 6 Ac Hence we showed that z E B0 implies that z 6 A0 I Exercise 119 Show that for all sets A B if A Q B and A Q C then A Q B O C Exercise 120 Show that for all sets A B lfA Q C and B Q C then A U B Q C 90 44 Proving Set Identities In this section we use the technique developed in the previous section to prove several identities between sets ie equality relations between sets that hold for all sets Method for proving that two sets are equal Let XY be given sets To prove that X Y 1 prove that X Q Y 2 prove that Y Q X Example 106 Show that for all sets A B and C A U B O C A U B O A U C Solution We need to show that AUB C Q AUB AUC and AUB AUC Q AUB C We rst undertake AU BOO Q AU B O AU C Let x be a particular but arbitrarily chosen element of A U B O C Then by the de nition of union z E A or z E B O C 1 If x E A then both m E A or z E B and m E A or z E C are true statements Hence by the de nition of union both z E A U B and z E A U C are true Therefore by the de nition of intersection we get z E A U B O A U C Thus in this case x is also in AU B AU C to If x E B O C then by the de nition of intersection z E B and z E C Therefore both m E A or z E B and m E A or m E C are true statements By the de nition of the union both z E A U B and z E A U C hold Therefore by the de nition of intersection z E A U B O A U C Thus in this second case we also showed that z must be in A U B O A U C Thus in either case m E A or z E B O C we have also that z E A U B A U C Hence AU B O C Q A U B O A U C as was to be shown Next we need to show that A U B O A U C Q A U B O C So let x be a particular but arbitrarily chosen element of A U B O A U C Then by the de nition of intersection we have x E A U B and z E A U C We reason now by cases We must have either z E A or m A 1 If x E A then x E A or z 6 BO C is a true statement and therefore by the de nition of union we get z E A U B O C which is what we wanted to show to In the other case if z A and since z E A U B we must have x E B Similarly if z A and since z E A U C we must have x E C Hence x has to be in B O C But then x E A or z E B O C is a true statement Therefore by the de nition of the union z 6 AU B O C We showed that in either case m E A or z A x has to be in A U B O C But then x E A U B O A U C implies that z E A U B O C which is what we wanted to show I THE REAL HEART OF MATHEMATICS 91 Exercise 121 Show that for all sets A B and C A O B U C A O B U A O C Example 107 Show that for all sets A B A U B A O B Solution We need to show that A U B Q A O B and that A O B Q A U B We undertake rst A U B Q A O B Let x be a particular but arbitrarily chosen element of A U B Then by the de nition of complement z A U B If x E A or z E B then x E A U B whence since we know that z A U B we must have z A and z B Hence by the de nition of complement again we have x E A and z E B But then by the de nition of intersection we get that z E A B So we showed that every x E AUB is also an element of A O B which gives A U B Q A O B We next undertake the reverse inclusion A O B Q A U B So suppose that z is a particular but arbitrarily chosen element of A O B By the de nition of intersection we then have x E A and z E B Then by the de nition of complement we have that z Aandz Blfm Aandz Bthenz AUBbecauseinthatcasem EAor z E B Therefore again by the de nition of complement we get z E A U B Thus we showed that every element in A O B is also an element in A U B which shows that A O B Q A U B as required Having shown both A U B Q A O B and A O B Q A U B we may now conclude that A U B A O B I Exercise 122 Show that for all sets A B A O B A U B Example 108 Show that for all sets A B lfA Q B then A O B A Solution Suppose that A Q B This is a global assumption and we are free to use it at any point in the proof that we need it Then we have to show that A O B Q A and A Q A O B We rst undertake A O B Q A Let x be a particular but arbitrarily chosen element of A O B We have then by the de nition of intersection z E A and z E B In particular z E A must be true Thus we showed that every element in A O B is also an element in A Therefore A O B Q A Now we undertake to show that A Q A O B If x E A then since A Q B we must also have x E B Therefore z E A and z E B are both true Thus by the de nition of intersection z E A O B Thus we have shown that every element of A is also an element of Am B This shows that A Q A O B Having shown that A O B Q A and A Q A O B we may now conclude that if A Q B then A O B A I Exercise 123 Show that for all sets A B if A Q B then A U B B Example 109 Show that for all sets A B B 7 A B O A Solution We need to show that B7A Q BOA and that A B Q B7A We rst undertake B 7 A Q B O A So let x be a particular but arbitrarily chosen element of B 7 A Then by the de nition of the relative complement we have x E B and z A Thus by the de nition of complement z E B and z E A Thus by the de nition of intersection we get z E B A We have shown that every element of B 7 A is also an element of B O A ie that B 7 A Q B O A We undertake next to show that B O A Q B 7 A So let x be a particular but arbitrarily chosen element of B O A Then by the de nition of intersection z E B and z E A Therefore by the de nition of complement z E B and z A But then by the de nition of the relative complement we get z E B 7 A Thus we showed that every element of B O A is also an element of B 7 A ie that B O A Q B 7 A Having shown both B 7 A Q B A and A B Q B 7 A we may now conclude that B 7 A B O A I Exercise 124 Show that for all sets A B C 1 A7BUA B A 2 A7B7B7CA7B 3 A7BUB7AAUB7AOB 4 A7B7CA7BUC Example 110 Show that for all sets A B A0 U B 7 A A Solution We need to show that A U B 7 A Q A and A Q A U B 7 A We rst undertake A U B 7 A Q A So let x be a particular but arbitrarily chosen element of A U B 7 A By the de nition of complement z A U B 7 A This implies z A U B or z E A 1 If z A U B then z A and z B Therefore by the de nition of complement z E A and z E B Thus z E A is true which is what we wanted to show 2 If x E A we are done In either case x E A which shows that every element of A U B 7 A is also an element of A ie A U B 7 A Q A Next we undertake to show that A Q A U B 7 A So let x be a particular but arbitrarily chosen element of A Then z A U B 7 A since otherwise z would not be in A Therefore by the de nition of complement z E A U B 7 A as was to be shown Having shown that ACUB7A Q A and A Q ACUB7A we may now conclude that A U B 7 A A I Exercise 125 Show that for all sets A B B U B 7 A B THE REAL HEART OF MATHEMATICS 93 45 Finding Counterexamples and Detecting Mistakes In this section a technique is introduced for showing that a given conjectured property between sets is not true for all sets Some problems are also presented on how to detect fallacies in arguments showing that a set is a subset of another set or that two sets are equal Example 111 Is the following property true For all sets ABC A7BU B7 C A7C Solution Draw a Venn diagram of the situation to realize where this property may fail Then construct an example to show that the property is not true Such an example is called a counterexample for the given property We must 1 Construct a universe U 2 Pick three sets A B C in the universe U for which the given property fails 3 Verify the conjecture that the property fails for these three sets that we picked So let U be the set U 1 b cl Then pick A 1 b B b and C 1l Then we have AT B U B T C avb T 5709 U 570 T a7d a U 57 C 1 bC On the other hand A7C 1b71 d Hence we see that A7BUB7C 31 A70 for some sets A B C I Example 112 Is the following property true For all sets ABC A7 B70 A7 B 70 Solution Let U 1 b clA 1bB 1 c and C 1l Then AT B T C 175 T ayc T avd 175 T C 11 On the other hand AT B T C ayb T a76 T ad 5 T ad 5 Therefore A 7 B 7 C 31 A 7 B 7 C for some sets A B and C I 94 Exercise 126 Is the following property true For all sets ABC A7B 07B A7 BUG Exercise 127 Is the following property true For all sets ABC ifA C B C thenA B Exercise 128 Is the following property true For all sets ABC ifAUC BUC thenA B Exercise 129 Is the following property true For allsetsABC ifA C QB C andAUCQ BUC thenAB Exercise 130 Is the following property true For all sets ABC AUB CAU BOO Exercise 131 Is the following property true For all sets ABC ifA Q B and B Q C then A Q 0 Example 113 Find the mistake in the following proof that for all sets A B and C if AQBandBQC thenAQC Proof Suppose A B and C are sets such that A Q B and B Q C Since A Q B there is an element m so thatz E A and m E B Since B Q C there is an element m so that m E B and m E C Hence there is an element m so that m E A and m E C and so A Q Cquot Solution There are many errors First A Q B does not mean that there is an element x so that z E A and z E B Second the x that is in A and in B may be a different element from the one erroneously denoted by x as well that is in B and C I Exercise 132 Find the mistake in the following proof of the statement that for all sets AB A0 U B0 Q A U B Proof Suppose A and B are sets and suppose m E A0 U BC Then m E A0 or m E B0 by de nition of union It follows that m A or m B by de nition of complement Therefore m A U B by de nition of union Thus m E A U B0 by de nition of complement Hence A0 U B0 Q A U Bquot Exercise 133 Find the mistake in the following proo quot of the statement that for all sets AB A7BUA B gA Proof Suppose A and B are sets and suppose that m E A 7 B U A O B Ifz E A then m E A 7 B Then by de nition of di erence m E A and m B Hence m E A and so A 7 B U A O B Q A by the de nition of subsetquot THE REAL HEART OF MATHEMATICS 46 Empty Set Partitions and Power Sets Chapter 5 Basic Combinatorics 51 Simple Counting Example 114 How many integers there are from 5 through 12 Solution We just count these integers integers 5 6 7 8 9 10 11 12 I I I I I I I I count 1 2 3 4 5 6 7 8 So there are 8 integers from 5 through 12 I Example 115 Let m7 n be two integers with m g n How many integers are there from in through n Solution Note that m m0 is element 17 m1 is element number 27 etc Setting up a counting list as above we get integers m0 m1m2 nmn7m I count 1 2 3 nim1 Hence there are n 7 m 1 elements in the given list I Example 116 How many three digit integers integers from 100 to 999 inclusive are di visible by 59 Solution The integers that are divisible by 5 between 100 to 999 are the integers 100 105 110 115 995 These are the same as 5205215225235199 There are as many on this list as in the following list 20 21 22 23 199 According to the counting principle above this list contains 199 7 20 1 180 elements Thus there are 180 threedigit integers that are divisible by 5 I Exercise 134 How many positive two digit integers are multiples of 3 Exercise 135 How many positive three digit integers are multiples of 6 Example 117 Consider the list of numbers 424344 100 What is the 27th element on this list Solution Suppose that n denotes the 27th element We then have n 7 42 1 27 Therefore n27427168 I Exercise 136 Consider the list of numbers 293031 100 What is the 27th element on this list Example 118 If the largest of 56 consecutive integers is 279 what is the smallest Solution Suppose that the smallest element in the list is n Then we have the list nn1n2279 This list contains 56 integers Thus 279 7 n 1 56 Therefore n 279 7 56 1 224 I Exercise 137 If the largest of 87 consecutive integers is 326 what is the smallest Example 119 How many even integers are there between 1 and 1001 THE REAL HEART OF MATHEMATICS 99 Solution The list of even integers between 1 and 1001 is 24 68 1000 These are the same as 212223242500 The number of these is the same as the number of the elements in the following list 1 234500 here are 500 7 1 1 500 elements in this list Hence there are 500 even integers between 1 and 1001 Exercise 138 How many integers are there between 1 and 1001 that are multiples of 39 Example 120 How many integers are there between 1 and 600 that are divisible by 79 Solution The list of integers between 1 and 600 that are divisible by 7 is 7 14 21 28 595 These are the same as 71727374785 There as many in this list as in the list 123485 Hence there are 85 7 1 1 85 integers between 1 and 600 that are divisible by 7 I Exercise 139 How many integers between 100 and 800 are divisible by 49 100 52 The Multiplication Principle A tree structure is very useful for keeping track of all possibilities in situations in which events happen in order Example 121 Teams A and B are to play each other repeatedly until one wins two games in a row or a total of three games One way this tournament can be played is for A to win the rst game B to win the second and A to win the third and fourth games Denote this by writingAi BiAiA 1 How many ways can the tournament be played 2 In how many of these ways 5 games are needed to determine the tournament winner Solution Build a tree for the possible outcomes of the tournament 1 The following are all the possibilities for complete tournaments AiAA7B7BA7B7A7AA7BiAiBiAA7B7A7B7B B7BB7A7AB7A7BiBB7A7B7A7AB7A7B7A7B So there are 10 possible ways to play this game 2 Only 4 of these ways require 5 games to determine the winner I Exercise 140 In baseball World Series the rst team to win four games wins the series Suppose that team A wins the rst 5 games How many ways can the series be completed Exercise 141 In a competition between players X and Y the rst player to win three games in a row or a total of four games wins How many ways can the competition be played if X wins the rst two games Exercise 142 Urn U1 contains two black balls B1 and B2 and one white ball Urn U2 contains one black ball and two white balls W1 and W2 Suppose that an urn is chosen and then a ball is drawn from the chosen urn Subsequently a second ball is also drawn without rst replacing the rst ball How many possible outcomes are there in this experiment Example 122 Suppose that you want to trauel from Ames IA through Chicago IL to Sault Sainte Marie MI You look at the map and nd out that there are three possible routes a bc you could follow from Ames to Chicago and ue possible routes A B CDE you can follow from Chicago to the Soo How many di erent routes could you possibly follow from Ames to the Soo THE REAL HEART OF MATHEMATICS 101 Solution All the possibilities are given by an appropriate tree It shows that the possible different routes are aAaBaC aDaEbAbBbC bDbE cAcBcCcD cE Thus there are 3 x 5 15 possible ways I The Multiplication Principle If a task consists of k subtasks the rst ofwhich can be performed in n1 ways the second in n2 ways and so on and the k th in nk ways then the entire task may be completed in n1 n2 nk different ways Exercise 143 Suppose that you want to travel from Pittsburgh PA through Cleveland OH through Detroit M1 to Sault Sainte Marie MI You look at the map and nd out that there are two possible routes a b you could follow from Pittsburgh to Cleveland three possible routes A B C from Cleveland to Detroit and two possible routes xy you can follow from Detroit to the 300 How many di erent routes could you possibly follow from Pittsburgh to the Soo Exercise 144 You want to dress up for a formal Thanksgiving dinner You discover that in you have available 5 di erent shirts 4 di erent trousers and 5 pairs of socks and 2 pairs of shoes that are all matching in colors How many di erent out ts could you make out of the available shirts trousers socks and shoes Exercise 145 A person buying a personal computer system is o ered a choice of three models of the basic unit two models of a keyboard and two models of a printer How many distinct systems can be purchased Example 123 A typical PIN is a sequence offour symbols chosen from the 26 letters of the alphabet and the ten digits with repetition allowed How many di erent PINs are possible Solution Divide the task of setting up a PIN to the following four subtasks Subtask 1 Choose the rst symbol Subtask 2 Choose the second symbol Subtask 3 Choose the third symbol Subtask 4 Choose the fourth symbol Subtask 1 may be performed in 36 ways Subtask 2 in 36 ways Subtask 3 in 36 ways and Subtask four in 36 ways Thus by the multiplication principle the complete task may be performed in 364 ways Thus many are the possible Ple I Example 124 Suppose that A B and C are three sets with 6 5 and 9 elements respectively Show that the Cartesian product A X B X C has 270 elements 102 Solution Recall the the Cartesian product A x B x C is the set of all triples a b c where a E A b E B and c E C In how many ways is it possible to build such a triple SubdiVide the task into the following subtasks Subtask 1 Choose the rst element of the triple Subtask 2 Choose the second element of the triple Subtask 3 Choose the third element of the triple Subtask 1 may be completed in 6 possible ways Subtask 2 in 5 possible ways and Subtask 3 in 9 possible ways Thus by the multiplication principle there are 6 5 9 270 different ways to build a triple in A x B x C ie there are 270 different triples available I Example 125 A four symbol PIN is to be formed as before where each symbol is either a letter of the alphabet or a digit 1 How many possible PINs are there with no repeated symbols 2 How many PINs contain at least one repeated symbol Solution 1 SubdiVide the task of forming a PIN to the following four subtasks Subtask 1 Choose the rst symbol Subtask 2 Choose the second symbol Subtask 3 Choose the third symbol Subtask 4 Choose the fourth symbol Now the rst subtasks may be carried out in 36 ways the second in 35 ways the third in 34 ways and the fourth in 33 ways Thus by the multiplication principle there are 36 35 34 33 ways to perform the entire task Hence there are 36 35 3433 different Ple with no repeated symbols to The number of Ple with at least one repeated symbol may be computed by taking the total number of possible Ple and subtracting from it the number of these Ple with no repeated symbols Thus there are 364 7 36 35 34 33 Ple with at least one repeated symbol I Exercise 146 In a certain state automobile license plates each have three letters followed by three digits 1 How many license plates are possible THE REAL HEART OF MATHEMATICS 103 2 How many of these begin with A and end with a 0 3 How many begin with PDQ 4 How many are possible with all letters and digits distinct Example 126 Suppose that you want to construct the truth table for a sentence form that contains 5 di erent sentence uariables How many rows will that truth table haue Solution The task is to construct all sequences of length 3 out of the letters T and F SubdiVide this task to the subtasks Subtask 1 Choose the rst truth value Subtask 2 Choose the second truth value Subtask 3 Choose the third truth value Each of the subtasks may be performed in 2 ways Therefore by the multiplication principle there are 23 8 possible ways to carry out the complete task Thus there should be 8 rows in the truth table for the given sentence form Exercise 147 A bit string is a sequence of 0 2 and 1 s How many bit strings haue length 8 How many of these strings begin with a 1 How many begin and end with a 1 Exercise 148 A coin is tossed four times Each time the result H for heads or T for tails is recorded An outcome of HHTT means that heads were obtained in the rst two tosses and tails were obtained in the last two tosses How many distinct out comes are possible How many of these contain exactly two heads 104 53 Permutations A permutation of a set of objects is an ordering of the objects in a row For example the set of elements a b c has six permutations abc acb bac bca cab cba In general if we are given a set ofn elements how many permutations does the set have To calculate this number we use the multiplication principle The task of forming a permutation may be subdivided into n subtasks Subtask 1 Choose the rst element Subtask 2 Choose the second element Subtask n Choose the n th element Subtask 1 may be performed in n ways Subtask 2 may be performed in n 7 1 ways and so on up to Subtask n which may be performed in just 1 way Now by the multiplication principle there are n n7 1 n 7 2 2 1 ways to perform the complete task In other words there are nl nn71n7221 different permutations of a set with n elements Example 127 1 In how many ways can the letters of the word COMPUTER be arranged in a rowf2 2 In how many ways can the letters of the word COMPUTER be arranged in a row if the letters 00 must remain next to each other in order as a unit Solution H All letters in COMPUTER are distinct So there are 8 876 21 permutations of this set to lf CO must appear in the permutation together as a unit then the number of possible arrangements is the same as the number of permutations of the seven different objects CO M P U T E R Hence there are 7 7 6 2 1 possible arrangements I Exercise 149 1 In how many ways can the letters of the word ALGORITHM be arranged in a rowf2 THE REAL HEART OF MATHEMATICS 105 m In how many ways can this be done if the letters A and L must remain together in order as a unit 93 In how many ways can it be done if the letters COR must remain together in order as a unit In how many ways can it be done if AL and COR have to remain together in order as units i Exercise 150 Six people go to the mouies together N In how many ways can they be seated in a row N If one of them is a doctor who musty seat on the aisle in case she is paged in how many ways can they be seated in six seats if exactly one of the seats is on the aisle as If the six people consist of three couples and each couple wants to sit together with the boyfriend on the left in how many ways can the six friends be seated in a row Example 128 At a meeting of diplomats the six participants are to be seated around a circular table Since the table has no ends to confer particular status it does not matter who sits in which chair But it does matter how the diplomats are seated relatiue to each other In other words two seatings are considered the same if one is a rotation of the other In how many di erent ways can the diplomats be seated Solution Fix one diplomat at a speci c position His position is irrelevant Only the positions of the remaining 5 diplomats relative to him are important Thus7 there are 5 5 43 2 1 120 different possible ways to seat the diplomats at the round table I Permutations like the one above are sometimes termed cyclic permutations Thus7 following the same argument as aloove7 we may show that n different objects have n 7 1 different cyclic permutations le7 they may be arranged in a cycle in n 7 1 different ways Exercise 151 Fiue people are to be seated around a circular table Two seating are con sidered the same if one is a rotation of the other In how many di erent ways can they be seated around the table Given the set a7b7 c7 there are six ways to select two letters from the set and write them in order ab ac ba bc ca cb Each such ordering of two elements of a7 b7 c is called a 2 perrnutati0n of a7 b7 c Exercise 152 1 Write all the possible 2 permutations of X7 Y7 Z 106 2 Write all possible 3 permutatlons of a b cd In general an r permutation of a set of n elements is an ordered selection of r elements taken from the set of n elements The number of r permutations of a set of n elements is denoted by Pn r Can we calculate how many r permutations of a set of n elements there are le can we compute the number Pn r We use the multiplication principle SubdiVide the task of forming an r permutation into the following r subtasks Subtask 1 Choose the rst element Subtask 2 Choose the second element Subtask r Choose the r th element Subtask 1 may be performed in n ways Subtask 2 may be performed in n71 ways Subtask 3 may be performed in n72 ways and so on until Subtask r which may be performed in n7r1 ways Thus by the multiplication principle there are nn71n7 2 n7r 2n7 H 1 possible ways to perform the complete task le there are nn 7 1 n 7 r 1 possible r permutations of n elements Thus we obtain nn 7 1 1 nl Pnr 7nn7 1n7r 1 7 7 71776 Example 129 1 Evaluate P52 2 How many 4 permutat239ons are there of a set of 7 objects 3 How many 5 permutatlons are there of a set of 5 objects Solution 1 P5 2 E32 g 5 4 20 7 7 2 P74W 7654840 3 P5 5 752 g 5T 120 l Exercise 153 Evaluate P6 4P6 6 P6 2 and P61 Exercise 154 1 How many dl erent 3 permutatlons are there of a set of 5 objects 2 How many dz39 erent 2 permutatlons are there of a set of 7 objects THE REAL HEART OF MATHEMATICS Example 130 be chosen and written in a rowf2 107 1 In how many di erent ways can three of the letters of the word BYTES 2 In how many ways can this arrangement be performed if the rst letters must be B Solution 5 573 1 P53 2 The number is the same as the number of 2 permutations of the remaining 4 letters Thus it is the number P4 2 Exercise 155 GORITH 442 4312 l 1 In how many di erent ways can three of the letters of the word AL be selected and written in a rowf2 2 In how many di erent ways can ve of the letters of the word ALGORITHM be selected and written in a rowf2 3 In how many di erent ways can ve of the letters of the word ALGORITHM be selected and written in a row if the rst letter must be A In how many di erent ways can ve of the letters of the word ALGORITHM be selected and written in a row if the rst two letters must be TH Example 131 Prove that for all integers n 2 2 Pn2 Pn 1 n2 Solution Pn 2 Pn Exercise 156 2 Prove that for all integers n 2 2 P 3 Prove that for all integers n 2 3 P 4 Prove that for all integers n 2 2 P 1 n n 717 nn71n n27nn n 1 Prove that for alln Z 2 Pn 13 n3 7 n 1 2 7 Pm 2 2Pn1 137 Pm 3 3Pn2 1 Pnn 71 108 54 The Addition Rule Suppose that a nite set A equals the union of k mutually disjoint subsets A17 A27 7Ak Then7 the Addition Rule states that MA nA1 nA2 nAk Example 132 A computer access code word consists of from one to three letters chosen from the 26 in the alphabet with repetitions allowed How many di erent code words are possiblef2 Solution The set of all code words A is the disjoint union of the set A1 of code words of length 17 the set A2 of code words of length 2 and the set A3 of code words of length 3 The number of code words in each of these three sets may be determined by using the multiplication principle We have nA1 26nA2 262nA3 263 Therefore7 by the Addition rule7 nA nA1 nA2 nA3 26 262 263 I Example 133 How many three digit integers integers from 100 to 999 inclusive are di visible by 59 Solution The set A of all threedigit integers that are divisible by 5 is the disjoint union of the set A1 of all three digit integers that end in 0 and of the set A2 of all threedigit integers that end in 5 One may now use the multiplication principle to determine the number of elements in each of these sets nA1910190nA2 910190 Hence7 by the Addition rule7 nA nA1 nA2 90 90 180 If A is a nite set and B is a subset of A7 then the Difference Rule states that nA 7 B nA 7 Example 134 Determine the number of 4 symbol PINs formed out of the 26 letters of the alphabet and the 10 digits that contain at least one repeated symbol THE REAL HEART OF MATHEMATICS 109 Solution Let A denote the set of all 4 symbol PINS and B be the set of all 4 symbol PINS that contain no repeated digits We have by the multiplication principle nA 364 713 36 35 34 33 Thus by the Difference rule we get nA 7 B nA 7 713 364 7 36 35 34 33 But A7 B is exactly the set of all 4 symbol Ple that contain at least one repeated symbol I Example 135 An experiment consists of rolling 5 dice 1 How many possible outcomes are there in this experiment 2 How many outcomes are there in which at least one 5 appears Solution H By the multiplication principle the set A of all outcomes contains nA 63 elements to By the multiplication principle the set B of all outcomes in which no 5 appears has nB 53 elements Therefore the set A 7 B of all outcomes in which at least one 5 appears has by the Difference rule nA7 B nA 7 nB 63 7 53 elements I Exercise 157 1 How many integers from 1 through 100000 contain the digit 6 exactly once 2 How many integers from 1 through 100000 contain the digit 6 at least once 3 How many integers from 1 through 100000 contain the digit 6 at least twice Exercise 158 Six new employees two of whom are married to each other are two be assigned six desks that are lined up in a row In how many ways may the desks be assigned so that the married couple will have two non adjacent desks Exercise 159 Consider strings of length 10 over the alphabet a b cd How many of these contain at least one pair of consecutive characters that are the same 110 The InclusionExclusion Principle for Two or Three Sets If A B and C are any nite sets then nA U B nA nB 7 nA O B and nAUBUC nA nBnC inA BinA C7nB CnA B C Example 136 1 How many integers from 1 through 1000 are multiples of 5 or multi ples of 59 2 How many integers from 1 through 1000 are neither multiples of 5 not multiples of 5 Solution 1 Denote by A the set of all integers from 1 to 1000 that are multiples of 3 and by B the set of all those integers from 1 to 1000 that are multiples of 5 Then A U B is the set of all the integers from1 to 1000 that are multiples of 3 or multiples of 5 and Am B is the set of all integers from 1 to 1000 that are multiples of 3 and multiples of 5 ie that are multiples of 15 We may use the techniques we saw in the rst section of the chapter to calculate nA nB and nA O B We have for nA 369 777quot397 999 which is the same as 3132333333 whence nA 333 For nB 510151000 which is the same as 5152535200 whence nB 200 Finally for nA O B 15 30 45 990 which is the same as 1511521531566 ie nA B 66 Now apply the Inclusion Exclusion Principle for two Sets to obtain nA o B nA nB 7 nA o B 333 200 7 66 467 THE REAL HEART OF MATHEMATICS 111 to The set of all numbers from 1 to 1000 that are neither multiples of 3 nor multiples of 5 is the set A0 O B0 which is the same as the set A U B Then by the difference formula nA U B0 1000 7 nA U B 1000 7 467 533 I Exercise 160 1 how many integers from 1 through a 1000 are multiples of4 or mul tiples of 79 2 How many integers from 1 through a 1000 are neither multiples of4 nor multiples of 7 Exercise 161 1 how many integers from 1 through a 1000 are multiples of 2 or mul tiples of 99 2 How many integers from 1 through a 1000 are neither multiples of 2 nor multiples of 9 Example 137 The food seruice at your school has conducted a suruey for the tastes of the students using the seruice Of the 100 students that responded to the suruey 60 like rice 36 like spaghetti 52 like pizza 18 like both rice and spaghetti 32 like rice and pizza 16 like spaghetti and pizza and 94 like at least one of the three foods 1 How many students do not like either of the three foods 2 How many students like all three of the foods 3 How many like rice and spaghetti but not pizza How many rice but neither spaghetti nor pizza Solution 1 By the difference rule the number of students that like neither of the three foods equals the number of respondents minus the number of all those that liked at least one of the foods 100 7 94 6 to Let RSP denote respectively the sets of students that liked rice spaghetti and pizza Then by the Inclusion Exclusion Principle for Three sets we get nRUSUP nRnSnP7nR S7nR P7nS PnR S P Thus 94603652718732716nR S P whence nR S P 12 Thus 12 students liked all three foods 112 3 To answer these two questions construct the Venn diagram for the three sets R S and P Then ll in the regions with the appropriate numbers The regions should contain the numbers given in the following table region number R S P 12 R S PC 6 ROSCOPC 22 R Sc P 20 Rc S P 4 RCOSOPC 14 RCOSCOPC 6 Rc Sc P 16 Then nR S P06and nR Sc P022 I Exercise 162 a market research project studied student readership of certain news maga zines by asking students to place checks underneath the names of all news magazines they read occasionally Out of 100 students it was found that 28 checked Time 26 checked Newsweek 14 checked US News and World report 8 checked both Time and Newsweek 4 checked both time and US News 5 checked both Newsweek and US News and 2 checked all three 1 How many students checked at least one of the magazines 2 How many checked none of the magazines 5 How many read Time and Newsweek but not US News Exercise 163 A study was conducted to determine the e icacy of three drugs A B and C in relieuing headache pain Ouer the period of the study 40 subjects were giuen the chance to use all three drugs The following results were obtained 25 reported relief from A 18 reported relief from B 31 reported relief from C 11 reported relief from both A and B 19 relief from both A and C and 14 reported relief from both B and C Finally 37 reported relief from at least one of the drugs 1 How many people got relief from none of the drugs 2 How many people got relief from all three of the drugs 3 How many got relief from drug A only Exercise 164 How many positiue integers less than 1000 have no common factors with 1000 Exercise 165 How many integers from 1 through 999999 contain each of the digits 12 and 5 at least once THE REAL HEART OF MATHEMATICS 113 55 Combinations Given a set S with n elements how many subsets of size r can be chosen from S This number is the same as the number of distinct subsets of size r that S has Each of these subsets is called an r cornbination of S More precisely let 717 be two distinct nonegative integers with r g n An r cornbination of a set of n elements is a subset containing r of the n elements The symbol read it choose r denotes the number of subsets of size r r combinations that can be chosen from a set of n elements Example 138 Let S Al Bob Chris Dan Each committe consisting of three of the four people in S is a 3 combination of S 1 List all 3 combinations of S 2 What is 2 Solution 1 Each 3 combination of S is a subset of S of size 3 Each of these subsets may be obtained by omitting one of the elements of S Thus the four 3 combinations are Bob Chris Dan A1 Chris Dan A1 Bob Dan A1 Bob Chris 2 The number is by de nition the number of 3 combinations of a set of 4 elements Therefore 4 I Example 139 How many 2 element subsets does the set 0123 hauef2 Solution We list the subsets 07 117 07 217 07 317 17 217 17 317 273 Hence there are 6 2 element subsets of 0 1 2 3 This also shows that 6 I Exercise 166 List all E combinations of the set zlm2m3m4x5 Deduce the value of 5 3 How can we compute the number of r combinations of a set with n elements for arbitrary n and r the secret is to relate the r combinations to the r permutations for the number of which we already have the formula Pn r WEN Here is a description on how this may be accomplished Suppose we want to compute the number Pnr of all r permutations of a set S with n elements We consider this as the main task and subdivide it into two subtasks 114 Subtask 1 Choose r elements out of the set of n elements Subtask 2 Order the chosen r elements to form an r permutation of the set S Subtask 1 may be accomplished in by the de nition of Subtask 2 may be accom plished in Pr r ways by the de nition of Pr r The complete task may be accomplished in Pn r ways by the de nition of Pn r Therefore the multiplication principle gives Pm r 313ml But we know that Pn r g and that Pr r 73 Therefore we have whence since r 7 r Ol 1 we get n i 7 nl r rln7rl39 Exercise 167 Write an equation relating P7 2 with Exercise 168 Write an equation relating P8 5 with Example 140 Compute Solution Wehave 8 8 871 876 78756 lt5 51675 541321 6 Exercise 169 Compute 3 and Example 141 Choose ue members from a group of twelue to work as a team on a special project How many distinct ue person teams can be chosenf2 Solution The number of 5 member teams is the number of 5 combinations of a set of 12 elements Thus the number of different 5 member teams is 152 I Exercise 170 A student council consists of 15 students In how many ways can a com mittee of six be selected from the membership of the council THE REAL HEART OF MATHEMATICS 115 Example 142 Suppose that a team of ue is to be formed out of a group of twelve people Two members of the group insist on working as a pair ie the team is going to contain either both or neither How many ue person teams can be formed Solution The set A of all teams of ve members that can be formed is the disjoint union of the set A1 of all ve member teams that contain both persons and the set A2 of all teams of ve members that contain neither of the two persons Thus by the Addition Rule nA nA1 nA2 Now the number of all vemember teams that contain both persons are as many as the 3 combinations of the set of the remaining people that has 10 elements Just choose the remaining 3 members of the team from the remaining 10 people Thus nA1 30 On the other hand the number of all ve member teams that contain neither person are as many as the 5 combinations of the set of the remaining people that has 10 elements Just choose all 5 members of the team from the set of the remaining 10 people Hence we have nA2 150 Therefore we have 10 10 lol 101 nAnA1nA2 lt3 lt5 I Exercise 171 1 A student council consists of 15 students Two of the council members have the same major and they are not allowed to serve together on a committee In how many ways can a committee of six be selected from the membership of the council N Two council members always insist on serving on committees together If they do not serve together then they will not serve at all In how many ways can a committee of six be formed from the membership of the council Example 143 Suppose that a group of twelve people contains ue men and seuen women 1 How many ue person teams can be chosen that consist of three men and two women 2 How many ue person teams contain at least one man 3 How many ue person teams contain at most one man Solution 1 Divide the task of choosing a team of ve persons three of which are men and two women in the following two subtasks Subtask 1 Choose the men 116 Subtask 2 Choose the women The rst subtask may be accomplished in ways and the second subtask in ways Thus by the multiplication principle the whole task may be accomplished in 5 7 3 2 ways39 to By the Difference rule the number of teams that contain at leat one man are the total number of vemember teams minus the number of ve member teams that contains no man The total number of ve member teams is 152 The number of ve member teams that are entirely formed out of women is equal to Hence the number of teams that contain at least one man is 152 7 OJ These are the teams that contain either no man at all ar exactly one man The number of the teams that contain no man is and the number of the teams that contain exactly one man are Hence the number of teams that contain at most one A 7 5 7 man Is 5 1 All I Exercise 172 A student council consists of 15 students eight men and seuen women 1 How many committees of six contain three men and three women 2 How many committees of six contain at least one woman 93 If the council consists of three freshmen four sophomores three juniors and ue se niors How many committees of eight contain two representatiues from each class Example 144 How many eight bit strings have exactly three 1 s Solution Think of the eight positions as eight spots three out of which are to be chosen and lled with 1 s This the number of strings that contain exactly three 1 s is the number of 3 combinations of a set of 8 elements This is Exercise 173 An instructor giues an exam with fourteen questions students are allowed to choose any ten to answer 1 How many di erent choices of ten questions are there 2 Suppose six questions require proof and eight do not a How many groups of ten questions contain four that require proof and six that do not b How many groups of ten questions contain at least one that requires proof c How many groups of ten questions contain at most three that require proof THE REAL HEART OF MATHEMATICS 117 3 Suppose the exam instructions specify that at most one of questions 1 and 2 maybe included among the ten How many choices of ten questions are there 4 Suppose the exam instructions specify that either both questions 1 and 2 are to be included among the ten or neither is to be included How many di erent choices of ten questions are there Exercise 174 An all male club is considering opening its membership to women In a preliminary suruey on the issue 19 of the 30 members fauored admitting women and 11 did not A committee of six is to be chosen to giue further study to the issue 1 How many committees of six can be formed from the club membership 2 ow many of the committees will contain at least three men who in the preliminary suruey fauored opening the membership to women Exercise 175 A coin is tossed ten times In each case the outcome H or T is recorded 1 How many possible outcomes are there m In how many of these outcomes there are exactly ue heads obtained as In how many of the outcomes there are at least nine heads i In how many outcomes there is at least one head F In how many outcomes there is at most one head 118 Chapter 6 Basic Probability 119 120 Chapter 7 Graphs 121 122 Chapter 8 Finite State Automata 123 124 Chapter 9 Basic Number Theory 125 126 Chapter 10 The Principle of Mathematical Induction 127 128 Chapter 1 1 Number Systems Complex Numbers 129 130 Chapter 12 Geometry 131

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

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

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.