### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DISCRETEMATHEMATICS MATH245

SDSU

GPA 3.61

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Mathematics (M)

This 128 page Class Notes was uploaded by Camryn Rogahn on Tuesday October 20, 2015. The Class Notes belongs to MATH245 at San Diego State University taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/225273/math245-san-diego-state-university in Mathematics (M) at San Diego State University.

## Reviews for DISCRETEMATHEMATICS

### 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: 10/20/15

Math 245 Discrete Mathematics The Logic of Compound Statements Conditional Statements Valid and Invalid Arguments Lecture Notes 3 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminus SDSU EDU http terminus SDSU EDU 51d lecturetexv 116 20060907 182434 blomgren Exp S The Logic of Compound Stetemente Condxhonal Stetemente Vehd end Invele Axgumente e p 160 Previously2 Logical Form and Equivalence 1 of 2 Statements Sentences that are either TRUE or FALSE but not both Logical symbols not A and V or Statement form An expression made up of statement variables and symbols that becomes a statement when actual statements are substituted for the state ment variables The Logic of Compound Stetemente Condttmnel Stetemente Vehd end lnvehd Axgumente e p 260 Previously2 Logical Form and Equivalence 2 of 2 Truth table A table showing all possible truth39value combinations of the statement variables p q r as well as the corresponding truth values for a simple or compound statement of interest In the case of a compound statement we also tend to include columns for intermediate statements Logical equivalence Two logical expressions with the same truth values columns in a truth table are said to be logically equivalent l6 two different ways of expressing the same thingquot Tautology A logical expression that is always true for all input logical variables Eg p V N p Contradiction A logical expression that is always false for all input logical variables Eg p N p The Logic of Compound Stetemente Condxhonal Stetemente Vehd end Invele Axgumente e p 360 Conditional Statements if then gt A logical inference or deduction is made from a hypothesis to a conclusion Let p and q be statements A sentence of the form if p then qquot is denoted by P H q p is the hypothesis and q the conclusion a is a logical connective and like A and V it can be used to join statements to create new statements To define p H q as a statement we must specify the truth values for p H q just as we did for p A q and friends The Logic of Compound Stetemente Condttmnel Stetemente Vehd end lnvehd Axgumente e p 460 lfThen T Truth Table Example Truth Table for p v N q gt N p The formal definition of truth values for T is based on its everyday Recall intuitive meaning The promise If you show up for class on Tuesday then you will Defm39t39oquot cond39t39onal I I get an A in this classquot is false only if you do show up for class on If and arel St tenTem ranabl s the cond39t39onal of q byp 5 f Tuesday and do not get an A in this class In all other cases it is p the q or p mpl es q and 5 denomd p T qquot It 5 false When true the promise is not broken p is true and q is false otherwise it is true Hence the truth table looks like P q NP q PVq PVNQTP P q P H q T T F F T F T T T T F F T T F T F F F T T F F T F T T F F T T T T F F T The Logic of Compound scecemence Conditional scecemence Vehd end lnvahd Axgumence e p 560 The Logic of Compound scecemence Condxhonal scecemence Vehd end lnvalxd Axgumence e p 660 Vacuously True True By Default Logical Equivalences lnvolving a Example Showing that p V q T r E p T r q T r A conditional statement p T q that is true by virtue of the fact that the hypothesis p is false is often called vacuously true or P q T P V I P T T q T T P V I T T P T T A q T T true by default T T T T T T T T T T F T F F F F The statement Ifyou show up for work on Tuesday morning then you T F T T T T T T wilget tnejobquot is vacuously true if you do not show up for work on T p p T F T F F Tuesday morning In this case there is no promise hence it cannot T T T T T T T be broken F T F T T F F F F F T F T T T T F F F F T T T T Since the last two columns match we have shown that pV qgtTEpgtT A gar The Logic of Compound scecemence Condmonel scecemence Vehd end Invale Axgumence e p 760 The Logic of Compound scecemence Condmonel scecemence Vehd end lnvahd Axgumence e p aeo Negation of a Conditional Statement The negation of ifp then qquot is logically equivalent to p and not qquot Proof 19 q pmq q pmq MNq T T T F F F T F F T T T F T T F F F F F T T F F Example Note that we use N N q E q N If my car is in the shop then I cannot get to classquot E My car is in the repair shop and I can get to classquot The Ldgtc d Compound Stetennente Conditional Stetemente Vehd end Invalid Axgumente e p 960 The Contrapositive of a Conditional Statement Definition Contrapositive The contrapositive of a conditional statement of the form if p then qquot is If N q then N pquot Symbolically the contrapositive of p H q is q H N 13 You will be asked see homework to show that A conditional state ment is logically equivalent to its contrapositive ie PHQE glo Pl The Logic of Compound Stetennente cdndttmnel Stetemente Vehd end Invalid Axgumente e p 1060 Examples Writing the Contrapositive 1 The contrapositive of quotIf Howard can swim across the lake then Howard can swim to the islandquot is If Howard cannot swim to the island then Howard cannot swim across the lake quot 2 The contrapositive of quotIf today is Easter then tomorrow is Monday quot is If tomorrow is not Monday then today is not Easterquot The Logic d Compound Stetennente Conditional Stetemente Vehd end Invalid Axgumente e p 1160 The Contrapositive is an important Tool We will see the contrapositive form later on in this class The logical equivalence of a conditional statement and its contrapos39 itive is the basis for one of the laws of deduction modus tollens and for the contrapositive method of proof The Logic of Compound Stetennente cdndttmnel Stetemente Vehd end Invalid Axgumente e p 1260 The lnverse and Converse of a Conditional Statement Definition Converse and Inverse Suppose a conditional statement of the form if p then q is given 1 The converse is if q then p 2 The inverse is if N p then N q Symbolically The converse of p gt 6 l5 6 gt P The inverse of p gt q iS N 10 gt N 61 Note The inverse and converse are not logically equivalent to the statement they are however logically equivalent to each other since the inverse is the contrapositive of the converse A Midterm alertl The Logic of Compound Statements Conditional Statements Valid and Invalid Arguments p 1360 Only if To say p only if q means that p can take place only if q takes place also That is if q does not take place then p cannot take place By the logical equivalence of the contrapositive we can also say that ifp occurs then q must also occur Definition Only If pr and q are statements p only if q means if not q then not p or equivalently if p then qquot The Logic of Compound Statements Conditional Statements Valid and Invalid Arguments p 1460 If and only ifquot The Bi conditional Definition If and Only If Given the statement variables p and q the bi conditional of p and q is p if and only if q and is denoted p H q It is true if both p and q have the same truth values and is false if p and q have opposite truth values The words if and only if are sometimes abbreviated iff p q peg T T T T F F F T F F F T The Logic of Compound Statements Conditional Statements Valid and Invalid Arguments p 1560 Order of Operations In order of operations H is co equal with gt and we have the following precedence for our five logical connectives highest 1 N l 2 V lowest 3 gtH Order of operations The Logic of Compound Statements Conditional Statements Valid and Invalid Arguments p 1660 if only ifquot and if and only ifquot According to the definitions of if and only if saying p if and only if qquot should mean the same as saying p if qquot and p only if qquot That is indeed the case again we look at the truth table 1 only q p q p q 12 only if q and 12 if q p q peg gap qu PT9AQTP T T T T T T T F F T F F F T T F F F F F T T T T Since the last two columns are equal the statement forms are equiv alent is p lt gt q E p gt q q gt p The Logic d Compound Stetemente Conditional Stetemente Vehd end lnvelxd Axgumente e p 1760 Necessary and Sufficient Conditions The phrases necessary condition and sufficient condition as used in formal English correspond exactly to their definitions in logic Definition Sufficient and Necessary Conditions If r and s are statements r is a sufficient condition for 3 means if r then s r is a necessary condition for 3 means if not r then not 3 Note that due to the equivalence between a statement and its contra positive r is a necessary condition for s also means if s then rquot The Logic of Compound Stetemente Condttmnel Stetemente Vehd end lnvehd Axgumente e p 1860 Solved Problems Epp 1 2 28 1 of 2 Eppl 2 28 Do you mean that you think you can find out the answer to it said the March Hare Exactly soquot said Alice Then you should say what you mean the March Hare went I doquot Alice hastily replied at least at least I mean what I say that39s the same thing you knowquot Not the same thing a bitquot said the Hatter Why you might just as well say that see what I eatquot is the same thing as eat what I see from A Mad Tea Partyquot in Alice in Wonderland by Lewis Carroll That Hatter is right I say what I mean is not the same thing as I mean what I sayquot Rewrite in if then form and explain the difference The Logic d Compound Stetemente Conditional Stetemente Vehd end lnvelxd Axgumente e p 1960 Solved Problems Epp1228 2 of 2 The if then form of I say what I meanquot is quotIf I mean something then I say itquot mean gt say The if then form of I mean what I sayquot is quotIf I say something then I mean itquot say gt mean The two statements are the converse of each other and are not logically equivalent Corresponds to Eppev2011224 The Logic of Compound Stetemente Condttmnel Stetemente Vehd end lnvahd Axgumente e p 2060 Homework 1 Due 9152006 1200pm cmcssw Arguments introduction We are now going to use our new tools language logic statements Epp 1 2 13 24 25 2 6 27 connectives conditionals to generate arguments ln mathematics lo ic an ar ument is not a dis ute rather Epp11 3 14 16 21 25 29 31 37 41 g g p Extra BraineTwister for fun Epp1154 Dafinit bquot Argument An argument is a sequence of statements All statements but the final one are called premises or assumptions or hypotheses The final statement is called the conclusion The symbol read therefore is normally placed just before the conclusion We will be concerned with determining whether an argument is valid that is to determine whether the conclusion follows necessarily from the preceding statements The Logic of Compound Statements Conditional Statements Vahd and lnvahd Axguments e p 2160 The Logic of Compound Statements Conditional Statements Vahd and lnvahd Axguments e p 2260 Abstracting the Content from the Arguments Valid Arguments We have already seen Lecture Notes 2 that we can separate the When we consider the abstract form of an argument eg content from the argument recall If p or q then r Statement A q lf Jane is a math major or Jane is a CS major r then Jane will take Math 245 Jane is a CS major Therefore Jane will take Math 245 we think of p q and r as variables for which statements may be substituted Definition Valid Argument Form Abstract logical form With our new symbol To say that an argument form is valid means that no matter If p or q then r If p or q then r what particular statements are substituted for the statement vari39 q q ables in its premises ifthe resulting premises are all true then the conclusion is also true Therefore r r To say that an argument is valid means that its form is valid The Logic of Compound Statements Conditional Statements Vahd and lnvahd Axguments e p 2360 The Logic of Compound Statements Conditional Statements Vahd and lnvalxd Axguments e p 2460 Valid Arguments The truth of the conclusion of a valid argument follows necessarily or inescapably or by logic alone from the truth of its premises It is impossible to have a valid argument with true premises and a false conclusion When an argument is valid and its premises are true the truth of the conclusion is said to be inferred or deduced from the truth of the premises The Logic 6 Compound Stetemente Condxhonal Stetehnente Vehd end Invalid Axgumente e p 2560 Testing for Validity To test an argument form for validity 1 2 3 4 Identify the premises and conclusion of the argument Construct a truth table showing the truth values of all the premises and the conclusion Find the critical rows in which all the premises are true In each critical row determine whether the conclusion of the argument is also true a the argument form is valid b sion is false the argument form is invalid If in each critical row the conclusion is also true then If there is at least one critical row in which the conclue The Logic of Compound Stetemente Conditmnel Stetehnente Vehd end Invalid Axgnmente e p 2660 Example Time A Valid Argument Form Show that the following argument form is valid 19 V q V 7quot 7 P V q variables premises conclusion p q 7 qu pVqV7 N qu T T T T T F T T F T T T T T F T T T F T F F F T T T F T T T T F F T F T T T T F F T T T F F F F F F T The Logic 6 Compound Stetemente Condxhonal Stetehnente Vehd end Invalid Axgumente e p 2760 Example Time An invalid Argument Form Show that the following argument form is invalid quV N 7 q Hp 7 pa variables premises conclusion p q 7 NT qVNT pAT quVNT quAT par T T T F T T T T T T T F T T F T F T F T F F T F T T F F T T F T T F F T T F T F T F F T F T T F T F F F T F F F T T T F F F T T F T T T The Logic of Compound Stetemente Conditmnel Stetehnente Vehd end Invalid Axgnmente e p 2860 Modus Ponens The Method of Affirming If we have an argument of the form If p then q p q The fact that this argument forms is valid is called modus ponens from Latin premises conclusion P q P H q P q T T T T T T F F T F T T F F F T F The Logic of Compound Statements Conditionei scenemehte Vehd and Invalid Axgumehte e p 2960 Modus Tollens The Method of Denying If we have an argument of the form If p then q If q then Np N q contrapositive N q N p N p The fact that this argument forms is valid is called modus tollens from Latin premises conclusion P q P H q N 4 N P T T T F T F F T F T T F F F T T T The Logic of Compound Statements Comhmhei scenemehte Vehd and Invalid Axgumehte e p 3060 Disjunctive Addition Generalization Disjunctive addition is used for making generalizations P q Vw 5V premises conclusion premises conclusion 19 q p 19 V q p q q 19 V q T T T T T T T T T F T T T F F F T F F T T T F F F F F F Example Students p and LOGICAL 0R Seniors q get a discount at store X You are a student p therefore p V q you get a discount The Logic of Compound Statements Conditionei scenemehte Valid and Invalid Axgumehte e p 3160 Conjunctive Simpli cation Specialization Conjunctive simplification is used for particularizing pAq pAq P q premises conclusion premises conclusion P 1 P A 1 P P 1 P A q q T T T T T T T T T F F T F F F T F F T F F F F F F F Example You are tired of logic and Peter Therefore in particular you are tired of logic The Logic of Compound Statements Comhmhei scenemehte Vehd and Invalid Axgumehte e p 3260 Disjunctive Syllogism Elimination Disjunctive Syllogisms are used to rule out possibilities P V q P V q N 9 N P P q premises conclusion premises conclusion P 1 P V 1 N 1 P P 1 P V 1 N P 1 T T T F T T T F T F T T T T F T F F T T F F T T T T F F F T F F F T Example You are tired of logic or surfing You are not tired of surfing Therefore you are tired of logic The Logic 6 Compound Stetemente Conditionei Stetemente Valid end Invalid Axgumente e p 3360 Hypothetical Syllogism Transitivity Hypothetical Syllogisms are used to build chains of implication P H q q H T p H T premises conclusion p q 7 p gt q q gt 7 p gt 7 T T T T T T T T F T F T F T F T F F F F T T T T T F T F T F F F T T T T F F F T T T The Logic of Compound Stetemente Conditmnei Stetemente Valid end Invalid Axgumente e p 3460 Hypothetical Syllogism Example If it is sunny the sky is blue Ifthe sky is blue we ll go surfing Therefore If it is sunny we ll go surfing sunny gt sky blue sky blue gt surfing sunny gt surfing The Logic 6 Compound Stetemente Conditionei Stetemente Valid end Invalid Axgumente e p 3560 Where are the glasses A Complex Deduction 1 of 2 The following statements are true a If my glasses are on the kitchen table x 17 then I saw my glasses at breakfast 10 gt q 1 q b l was reading the newspaper in the living room T or l was reading the newspaper in the kitchen r V 5 c If r then my glasses are on the coffee table r gt t x t d I did not see my glasses at breakfast N q e If I was reading my book in bed then my glasses are on the bed table u gt v x f If s then 10 s Hp The Logic of Compound Stetemente Conditmnei Stetemente Valid end Invalid Axgumente e p 3660 Where are the glasses A Complex Deduction 2 of 2 We have the following a paq b TVS c rat dq eugtv fsgtp We make the following deductions 1 By a and d we deduce N p by modus tollens 2 By E and 1 we deduce N s by modus tollens 3 By b and 2 we deduce r by disjunctive syllogism 4 By c and 3 we deduce t by modus ponens Hence the glasses are on the coffee table The Logic of Compound Stetemente Conditionel Stetemente Vehd end Invalid Axgumente e p sreo Fallacies Broken Logic A fallacy is an error in reasoning resulting in an invalid statement Three common mistakes 1 Using vague or ambiguous premises 2 Assuming what is to be proved 3 Jumping to conclusions without adequate grounds In the next few slides we39ll explore two other fallacies 4 Converse Error 5 Inverse Error Which give rise to arguments which resemble modus ponens and modus tollens but are invalid The Logic of Compound Stetemente Conditmnel Stetemente Vehd end Invalid Axgumente e p saeo Checking for Fallacies There are two ways 1 Construct the truth table and demonstrate that there is at least one critical row in which the premises are true but the conclusion false 2 Find an argument of the same form logical equivalence with true premises and a false conclusion Countereexample The Logic of Compound Stetemente Conditionel Stetemente Vehd end Invalid Axgumente e p 3960 Converse Error lf Peter is a cheater then Peter will sit in the back row Peter sits in the back row Therefore Peter is a cheater It is quite possible that Peter is not a cheater but is sitting in the back row You will be asked homework to construct the truth table showing that this type of argument is invalid The Logic of Compound Stetemente Conditmnel Stetemente Vehd end Invalid Axgumente e p 4060 inverse Error lf Peter is a cheater then Peter will sit in the back row Peter is not a cheater Therefore Peter does not sit in the back row It is quite possible that Peter is not a cheater even though he is sitting in the back row You will be asked homework to construct the truth table showing that this type of argument is invalid The Logic of Compound Stetennente Condxhonal Stetemente Vehd end Invehd Axgumente e p 4160 Homework 1 Due 9152006 1200pm cmcssw Ema13 13 21 39 Ema13 Read examples 1315 1316 Ema12 13 24 25 26 27 Ema11 3 14 16 21 25 29 31 37 41 Extra BraineTwister for fun Epp1154 The Logic of Compound Stetennente Condttmnel Stetemente Vehd end Invale Axgumente e p 4260 Application of Logic Digital Circuits introduction A lot of the theory of symbolic logic we have seen so far was developed by Augustus De Morgan 1806 1871 and George Boole 1815 1864 in the 19th century One of the cleanest application of logic in the wildquot is to construc39 tion of digital logic circuits In essence a processor chip is nothing but a huge collection of AND OR and NOT39switches Claude Shannon 1916 2001 made the connection between switched systems and logic and used formal logic to solve circuit design prob lems His master39s thesis A Symbolic Analysis of Relay and Switching Circuits was published in 1938 The Logic of Compound Stetennente Condxhonal Stetemente Vehd end Invehd Axgumente e p 4360 Application of Logic Digital Circuits introduction Claude Shannon39s doctoral thesis was on theoretical genetics His paper A Mathematical Theory of Communication 1948 founded the subject of information theory The idea that one could transmit pictures words sounds etc by sending a stream of 139s and 039s down a wire was fundamentally new In 1956 William Bradford Shockley 1910 1989 John Bardeen 1908 1991 and Walter Houser Brattain 1902 1987 received the Nobel Prize in Physics quotfor their researches on semiconductors and their discovery of the transistor effect quot The transistor is the small semiconductor device which makes modern computers possible The Logic of Compound Stetennente Condttmnel Stetemente Vehd end Invale Axgumente e p 4460 The Transistor We39ll take a quick look at how to build logic circuits using the transistor as a building block First let39s look at the transistor A bipolar junction transistor consists of three regions of doped semiconductors A small current in the center or base Eniiector Base Base region can be used to control a larger current flowing between the end regions emitter and PNP Enliectur NPN Collector collector The device can Base Base be characterized as a current amplifier having many appli Emitter Emitter cations for ampli cation and switching quot Note Figures and text borrowed from http hyperphysics phy astr gsu edu The Logic of Compound Stetemente Conditionei Stetemente Vehd end Invalid Axgumente e p 4560 The Transistor AND Gate A B The use of transistors for the con struction of logic gates depends upon their utility as fast switches When the baseemitter diode is turned on enough to be driven into saturation the collector voltage with respect to ground may be less than a volt and can be used as a logic 0 in the TTL logic familyquot Here if we connect a true value 1quot or 6V to both A and B then both transistors open and the out value is Otherwise there is no connection to 6V from the out hence the value is false 0quot or 0V The Logic of Compound Stetemente Conditional Stetemente Vehd end Invalid Axgumente e p 4660 The Transistor OR Gate A v B 6V The use of transistors for the con struction of logic gates depends upon their utility as fast switches When the baseemitter diode is turned on enough to be driven into saturation ZNZZZZ up the collector voltage with respect to ground may be less than a volt and can be used as a logic 0 in the TTL logic family quot Here if we connect a true value 1quot or 6V to at least one of A and B then there is a path from out to 6V and the output value if true Otherwise there is no connection to 6V from the out hence the value is false 0quot or 0V The Logic of Compound Stetemente Conditionei Stetemente Vehd end Invalid Axgumente e p 4760 The Transistor NAND Gate A B The use of transistors for the con struction of logic gates depends upon their utility as fast switches When the baseemitter diode is turned on enough to be driven into saturation the collector voltage with respect to ground may be less than a volt and can be used as a logic 0 in the TTL logic family quot Here if we connect a true value 1quot or 6V to both A and B then both transistors open and the out value is Otherwise there is no connection to 0V from the out hence the value is true 1quot or 6V The Logic of Compound Stetemente Conditional Stetemente Vehd end Invalid Axgumente e p taeo The Tiaiismi more Gem N A v 8 mm 0va m m m i im im Jammy m w Mi a 215 um i in ii we mm a true m m u Wm H m iw we M pm min b mm m m uucva m i x mm mm m m min in our NW m mm m Wm x G Am t in we w m w 1mm mm w Q m mi Wm mi i emvm quot M m we mi mm m imiig m KOR am 8 XIIC l ii tum mm ahea my 0 mm mm mm Dim Q wok Building 3 NOT circuk m Wimiig in mm mi in MM mm m m wing we a M iiwm quotimam Building an xon circuit wommm no mei Finding the Logic Boolean Expression for a Circuit in order the find the expression for a CWCU L foreach gate simpiy appiy the appropriate operation to the inputs n W a amen stunmu cumum sum v N xmum We e p szsn The InputOutput Table for a Circuit The inputOutput tabie for a circuit is a tabie much iike the truth tabie which shows the output vaiue of the circuit for aii possibie Combinations of inputs Two circuits are equivalent ifi and oniy ifi their inputoutput tsbies are identicai Exampie EIHWEI Equivaient circuits naugz cmymasumts cenmtwnusumtsiVumumhwumnsumury smn Showing that Two Circuits are Equivalent Exampie er Wu Equivaient circuits We can either construct the inputoutput tsbies for the circuits and check that the tsbies are identicaii or we can use our knowiedge of symboiic iogic For the circuit above PA M Q v P A Q A Q E distributive iavv P A N Q v Q A Q E negatiun iavv PAtQ EPAQ identityiavv n W a amen sum cumum stunmist v N mm We e p sscn Adding Bits with Circuits The haifeadder When adding binary bits we have the teiiewmg in base2 1 1 0 0 naugz cmpmmasumts cenmtwnusumtsiVumumhwumnsumury sccn Adding More Bits with Circuits The Fulerdder Homework 1 7 Due 9152006 1 want GMCS 5I31 Read seulons 1 as and 1 5 1 background and ememmmem value EW1420 EpprlAJS Suggested but net due EW13 13 21 39 EW13 Read examples 1315 1310 EW12 13 24 25 2o 27 awn 3 14 1o 21 25 29 31 37 41 Ema Bralanwmer Bur my mum mecmpmwm Mme wwwmumumwe We Dictionar PM www mm mam ewmelm n a Lumplex sentence m Icglc me e and cniy s em as us Lumpunems e we gunmen n a wmpcund sentence m Icglc same by ulnlng we slmple statements by or a deduulve scheme as a maul argument cummmg as a me and a mum premee an a cancluslcn lee m quotevery vlrtue s laudable knurlee s a wave mereme loudness s laudablequot sy39IoKsm n M mm seem MM Susannava w ham MW e sale Homework 3rd Edition H 2nd Edition Please use the 3m Editoil numberlng when handlng m ycursalm lens mecmpmwm Mme wwwmumumwe We C C Elementary Number Theory and Methods of Proof Floor and Ceiling Proofs by Contradiction and Contraposition Lecture Notes 6 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminusSDSUEDU httpterminusSDSUEDU Id lectureitexv 1 4 20060927 204710 blomgren Exp Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 133 x 00rx ceilx Imagine a real number x E R sitting on the number line The floor of x is the integer Q E Z which is to the left of a ie the largest integer which is smaller than or equal to The ceiling of x is the integer n E Z which is to the right of x ie the smallest integer which is larger than or equal to We have I E x 3 where equality holds if and only if x is an integer x ltgt x E Z Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 233 n n1 X 00rx Definition The floor of X Given any real number x the floor of x denoted is defined as follows ix the unique integer n such that n g a lt n 1 Symbolically if x is a real number and n is an integer then ixjn ltgt n xltn1 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 333 ceilx Definition The ceiling of X Given any real number x the ceiling of x denoted ix is defined as follows xi the unique integer n such that n 1 lt a g n Symbolically if x is a real number and n is an integer then ixin ltgt n 1ltx n Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 433 1 Loading students into Buses 1370 students are going to the zoo Due to budget constraints the principal will only allow full buses to leave Each bus holds at most 40 students How many buses can leave Solution l137040l l3425l 34 Comment This example may seem a little silly since we are dealing with integer quantities we could have used 1370 div 40 34 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 533 2 Tax Refund Due to a sudden miracle the state controller has found a surplus of 416832521832 in the budget This money is to be distributed among 24123451 taxpayers However each check must be in whole dollars only no pennies How large will the tax refund be Solution l41683252183224123451l l172791414392576j 172 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 633 3 Hot Dogs on the Grill You are expecting 12 friends to come over for a BBQ An average person eats 32 hotdogs Hotdogs are packaged 12pack and buns 10pack How many packs of hotdogs and buns do you have to buy Solution Hotdogs l133212l346671 4 Buns l133210l416001 5 Why 13 You39re eating too right Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 733 4 Disproving an alleged property of the floor function Statement For all real numbers a and y x yj Disproof by Counterexample Consider the case a y Then But Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 833 Theorem VxERandeZ lx l ml m Proof Let a be real number and m be an integer Let n By the definition of floor n is an integer and n g a lt n 1 Add m to all three entries in the inequality to get nm S 33m lt nm 1 Since n m is an integer by the definition of floor ix ml n m Now we recall that n and by substitution we have lx l ml D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 933 712 Theorem For any integer n n if n IS even if n is odd Proof Let n be an integer By the quotientremainder theorem n is odd or n is even case 1 When n is odd then n 2k 1 for some integer k By substitution l312l2k11l2lllklk because k is an integer and k g k 12 lt k 1 Now since n 2k 1 it follows that k and we have shown that l lquotT1whennisodd 2 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1033 712 case 2 When n is even then 71 2k for some integer k By substi izizisjaw because k is an integer and k g k lt k 1 Now since tution n 2k it follows that k and we have shown that when n is even Together case 1 n odd and case 2 n even shows that the statement is true D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1133 Theorem If n is a nonnegative integer and d is a positive integer and if C I and r n d then ndqr and 0 rltd Proof Let n be a nonnegative integer d a positive integer q and r n d By substitution dqrd ltn d 71 So it remains to show that 0 g r lt d But q Thus by the definition of floor q ltq1 RI Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1233 Then dq nltdqd andso Ogn dqltd But rn d n dq Hence we have shown 0 g 7 lt d Both parts of the theorem have been proved D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1333 Epp3519 Is the following statement true or false For all real numbers 3 fx ll 1 Solution Let a be a real number Then n lx ll is an integer By the definition of ceiling n 1 lt x l 1 g n Subtracting 1 from all parts of the inequality gives n 2ltx n 1 and by the definition of ceiling 71 1 Solving this expression for n gives n 1 Putting the two expressions for n together shows lx ll 1 Hence the statement is true Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1433 Homework 5 Due 10132006 12noon GMCS587 Version g Know this by the midterm turn in problems on 10132006 Epp 2nd3rd edition Understand the following theorems with proofs Theorem351 Theorem352 Theorem353 Problems 3513 3517 Next New methods of proof Proof by Contradiction Proof by Contraposition Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1533 C C C In Direct proof we start with the hypothesis of a statement and make a series of deductions using known theorems definition and some algebraic manipulations until we reach the conclusion Indirect proofs are a little more complicated ln arguments by contradiction we use the fact that a well formed argument is either true or false but not both If you can show that a given assumption is not true leads to a con tradiction impossibility or absurdity then that assumption must be false hence the given statement must be true If N Px gt Qx and Qx clearly is wrong then Px Qx could be something like all integers are negative or all real numbers equal to 4 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1633 C C In arguments by contraposition we rely on the fact that a statement is logically equivalent to its contrapositive To prove something by contraposition we write down the contrapos itive of the statement prove that this form is true by direct proof Then we can conclude that the original statement is true by the logical equivalence of the two statements Recall Definition The contrapositive of a conditional statement of the form if p then q is 391 N 61 the N p Symbolically the contrapositive of p gt g is q gt N Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1733 Method of Proof by Contradiction 1 Suppose the statement to be proved is false 2 Show that this supposition leads logically to a contradiction 3 Conclude that the statement to be proved is true Keep in mind that supposing that a statement is false is the same thing as supposing that the negation of the statement it true Hence step 1 means we must write down the negation of the statement Here we are using quite a few of our tools from chapters 1 2 Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1833 C Unfortunately there are no clear rules for when a proof by contra diction is better or easier to execute than a direct proof Proofs by contradiction tends to come in handy when you want to show that there is no object with a certain property or if you want to show that a certain object does not have a certain property As you see more proofs throughout you mathematical career you will get a better gutfeeling for when proofs by contradiction are the preferred method The next few examples is a starting point Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 1933 Theorem There is no greatest integer Proof Suppose the statement is false That is suppose there is a greatest integer N Since N is the greatest integer N Z n Vn E Z Now let M N 1 M being a sum of integers must be an integer Further M gt N since M N 1 Thus M is an integer greater than the greatest integer which is a contradiction The contradiction shows that the supposition is false and therefore the theorem is true D Note After a contradiction has been reached the argument is always the same This is a contradiction Hence the supposition is false and the theorem is true Most mathematical texts end proofs by contradiction once the contradiction has been reached Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2033 Theorem The sum of any rational number and any irrational number is irrational The theorem talks about the sum of a rational and irrational number not having the property of being rational Suggesting a proof by contradiction Proof Suppose the theorem is false That is suppose there is a rational number r and an irrational number s so that the sum r s is rational By the definition of rational we must have a c r 6 r s a for some integers a b c d continued Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2133 C Proof Suppose the theorem is false That is suppose there is a rational number r and an irrational number s so that the sum r s is rational By the definition of rational we must have c r 6 r s a for some integers a b c d By substitution at c a t 8 Z a Hence a little bit of algebra shows C a bC ad 8 d b bd Now be ad and bd are both integers and bd 7E 0 since both I 7E 0 and d 7E 0 Hence 3 is a quotient of two integers By the definition of a rational number s is rational This contradicts the supposition that s is irrational D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2233 Method of Proof by Contraposition Express the statement to be proved in the form Vx E D if Px then Rewrite this statement in the contrapositive form Vx E D if N Qx then N Px Prove the contrapositive by a direct proof a Suppose a is a particular but arbitrarily chosen element of D such that Qx is false b Show that Px is false Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2333 Theorem Given any integer n if n2 is even then n is even Proof Suppose n is odd and show n2 is odd Since n is odd n 2k 1 by the quotientremainder theorem with d 2 or by the definition of odd Now nn 2k12k1 4k24k1 22k22k1 EH integer Hence n2 2 integer 1 which by the definition of odd shows that n2 is odd D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2433 Proof by contraposition only works for statements that are universal and conditional ie of the form 5 Vx E D if Px then Qx It turns out that any statement that can be proved by contraposition can also be proved by contradiction but not the other way around The contrapositive of the statement 5 above is C Vx e D if N om then N Pm Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2533 In a proof by contraposition we 1 Suppose a is an arbitrary element of D such that N 2 Execute a sequence of steps to show N We can use the same sequence of steps to show the result by contradiction In a proof by contradiction we 1 Suppose a is an arbitrary element of D such that Px and N 6250 2 Execute a sequence of steps to show a contradiction N Px Px Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2633 Theorem Given any integer n if n2 is even then n is even Proof Suppose there exists an integer n such that n2 is even and n is odd Since n is odd n 2k1 by the quotientremainder theorem with d 2 or the definition of odd Now nn 2k12k1 4k24k1 22k22k1 EH integer Hence n2 2 integer 1 which by the definition of odd shows that n2 is odd Now n2 is odd and n2 is even a contradiction D Note The steps of the proof are exactly the same as in the proof by contraposition Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2733 C In a sense we don39t need proofs by contraposition since they can always be converted to proofs by contradiction The advantage of the proof by contraposition is that you know exactly what conclusion you need to show ie the negation of the hypothesis In a proof by contradiction it may be difficult to see where the contradiction will appear Further in a proof by contradiction you have to negate the full statement of the theorem which may be complicated We like contraposition since it seems easier to argue forward toward a known goal However these proofs only work for universal conditional statements Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2833 Theorem is irrational Proof Suppose not proof by contradiction Then there are two integers m and n with no common factors so that T n Squaring both sides gives m 2 H2 or equivalently m2 2712 This shows that m2 is even by the definition of even We have previously slide 24 shown that this implies that m is even continued Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 2933 Now since m is even we can write m 2k for some integer k Substituting this into m2 2712 gives m2 2k2 4k2 2712 Dividing both sides 01c 4k2 2712 by 2 gives 712 2k2 which shows that n2 is even therefore n is even Now both m and n are even hence they have a common factor of 2 This contradicts the supposition that m and n does not have any common factors D Something to think about is 3 irrational How would you prove it Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 3033 There are infinitely many prime numbers ie there is no largest prime In order the show this we first need to prove the following result Theorem For any integer a and prime number p ifp a then p a 1 Proof Suppose the statement is false then there is an integer a and a prime number p such that pin and pla 1 By definition we can find integers r and s such that a pr and a 1 p5 It follows that 1 a l 1 a p8 pr ps r 1 but i1 are the only divisors of 1 Since p is a prime we must have p gt 1 Since 5 r is an integer it follows that p a contradiction D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 3133 Theorem The set of prime numbers is infinite Proof Suppose not suppose the set of prime numbers if finite Then all prime numbers can be listed in ascending order 2912 2923 1935 7 Now consider the integer Then N gt 1 so by theorem332 see Epp N is divisible by some prime number p plN Also since p is prime it must equal one of the primes pi 1 lt z lt Thus plp1p2p3pn By the previous theorem slide 31 p M191 p2 p3 pn l 1 This contradicts plN D Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 3233 Homework 5 Due 10132006 12noon GMCS587 Final Version Know this by the midterm turn in problems on 10132006 Epp 2nd3rd edition Understand the following theorems with proofs Theorem351 Theorem352 Theorem353 Problems Epp3513 Epp 3517 Epp 3rd edition Epp365 Epp3683 Epp368b Epp3630 Epp 2nd edition Epp362 Epp366 If you do not have the 3rd edition it is your responsibility to seek out the quotmissingquot questions PhoneaFriend or come to office hours Floor and Ceiling 8 Proofs by Contradiction and Contraposition 7 p 3333 Math 245 Discrete Mathematics Relations on Sets Refiexivity Symmetry and Transitivity Equivalence Relations Lecture 14 Peter Biomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminus SDSU EDU http terminus SDSU EDU 51d lecturetexv 15 20061205 005229 blomgren Exp 5 Reietmns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietisns e p 143 Relations introduction Mathematical Relations Examples Two logical expressions can be said to be related ifthey have the same truth tables ai A set A can be said to be related to a set B if A g B ai A real number 2 can be said to related to y if 2 lt y ai An integer n can be said to related to m if nlm ai An integer n can be said to related to m ifn and m are both odd Etc etc etc We are going to study mathematical relations on sets their properties and representations Reietmns on Sets Retiexmty Symmetxy and mensitmty Equweience Reietmns e p 243 Relations introductory Example 1 of 2 Let A 012 and B 123 The relation Let an element 2 E A be related to an element 3 E B if and only if 2 lt y Notation 2 Ry E 2 is related to y 2 R y E 2 is not related to y We have the following relations 0R1 since 0lt1 1R1 since 1 1 0R2 since 0 lt 2 2 R 1 since 2 5i 1 0 R3 since 0 lt 3 2 R 2 since 2 5i 2 1 R2 since 1 lt 2 1 R3 since 1 lt 3 2 R3 since 2 lt 3 Reietmns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietisns e p 343 Relations introductory Example 2 of 2 Relations and Cartesian Products The Cartesian product A X B of two sets A and B is the set of all ordered pairs whose rst element is in A and second elements in B AgtltBzyizeAandyeB In our example A X B 0 1 02 03 1 1 12 13 2 1 22 23 The elements of some ordered pairs 071707270737172717372730 are considered to be related others are not Knowing which ordered pairs are in this set is equivalent to knowing which elements are related Reietmns on Sets Retiexmty Symmetxy and mensitmty Equweience Reietmns e p 443 Relations Formal Definition Definition Binary Relation Let A and B be sets A binary relation R from A to B is a subset of A X B Given an ordered pair 2y E A X B 2 is related to y by R written 22123 if and only if 2231 6 R Symbolic Notation ny ltgt xy R MM lt3 23721er The term binary is used in the definition to indicate that the relation is a subset of the Cartesian product of two sets Relations on Sets Re exmiy Symmehy and Txansxhvny Equivalence Relations 7 p 543 illustration Relations Figure Given 2 sets A and B we Figure The Relation R is a subset of form the Cartesian product A gtlt B A gtlt B If and only if zy E Rwe z y E AgtltB 31 6 A and y E saythat z is related toy by R symbol B ically zRy The subset R Q A X B can be specified 1 Directly Explicitly by indicating what pairs 2231 6 B This is only feasible when A and B are finite and small sets 2 By specifying a rule for what elements are in B eg by saying that 22y E R if and only if 2 32 Relations on Sets Reflexxvity Symmehy and nansnmiy Equivalence Relations 7 p 643 Example Congruence Modulo 2 Relation 1 of 2 We generalize the previous example to the set of all integers Z tie forall 72111 6 Z X Z mRn ltgt m7n iseven Questions a is4R0 2R6 3R73 5R2 b List 5 integers that are related by R to 1 c Prove that if n is odd then nR 1 Answers a4 Yes 4R0 since 4 7 0 4 is even aii Yes 2R6 since 2 7 6 74 is even aiii Yes 3R73 since 3 7 73 6 is even aiv No 5 R 2 since 5 7 2 3 is odd Relations on Sets Re exmiy Symmehy and Txansxhvny Equivalence Relations 7 p 743 Example Congruence Modulo 2 Relation 2 of 2 b There are in nitely many examples eg 1 since 1 7 1 0 is even 11 since 11 7 1 10 is even 111 since 111 7 1 110 is even 1111 since 1111 7 1 1110 is even 11111 since 11111 7 1 11110 is even c Proof Suppose n is any odd integer Then n 2k 1 for some integer k By substitution n712k1712kiseven Hence nR17 Vn odd D Relations on Sets Reflexxvity Symmehy and nansnmiy Equivalence Relations 7 p 543 Representation Arrow Diagrams for Relations Let A 123 and B 135 Figure Arrow diagram representation of Figure Arrow diagram representation of the relation the relation forallzyEAXB R2125 zy e R gt z lt y Notes I It is possible to have an element that does not have an arrow coming out of it 0 It is possible to have several arrows coming out of the same element of A pointing in different directions iii It is possible to have an element in B that does not have an arrow pointing to it Reietmns on Sets Retiexmty Symmetty and Txansihvity Equweience Reietmns e p 943 Relation from A to A Directed Graph of a Relation Definition A binary relation on a set A is a binary relation from A to A In this case we can modify the arrow diagram to be a directed graph instead of representing A twice we only represent it once and draw arrows from each point of A to each related point eg 1 2 there is an arrowfrom xtoy ltgt ny ltgt x y E R Reietmns on Sets Retiexmty Symmetty and Txansxhvxty Equweience Reietmns e p 1043 3 Example Directed Graph ofa Relation Let A 345 678 and de ne a binary relation R on A Rzy AgtltA 2lz7y Figure We notice that the graph must be symmetric since if Zln then 2l7n Since 2 0 there is a loop at every node in the graph Reietmns on Sets Retiexmty Symmetty and Txansihvity Equweience Reietmns e p 1143 Properties of a Binary Relation on One Set A Recall Definition A binary relation on a set A is a binary relation from A to A In the context of a binary relation on a set we can name 3 properties Definition Let R be a binary relation on a set A 1 R is Reflexive if and only if Va 6 A 22 Rm 2 R is Symmetric if and only if V00 3 E A if 2 By then 3 Rm 3 R is Transitive if and only if Vac yz E A if 2 By and y Ptz then sz Reietmns on Sets Retiexmty Symmetty and Txansxhvity Equweience Reietmns e p 1243 Reflexivity Symmetry Formal R is Reflexive if and only if V22 6 A 22Rz22 Formal R is Symmetric if and only if V22y E A if 22 By then y R22 Functional R is Reflexive ltgt for all 22 E A 2222 6 R h I I If Functional R is Symmetric ltgt for all 2231 6 A if 2273 E R then Informal Eac e ement is re ated to itse nygt 6 RI graph Eac point I the graph has an arrow limping around Informal If one element is related to a second element then the bac to use 39 second element is related to the first Graph In all cases where there is an arrow going from one point to a second there is an arrow going from the second point back to the first C C O lt Relauons on Secs Re exmcy Symmech and Txansmvny Equivalence Relamns 7 p 1343 Relauons on Secs Re exmcy Symmech and Txansmmy Equivalence Relauons 7 p 1443 Transitivity NonReflexivity NonSymmetry and NonTransitivity Formal R is Transitive if and only if V22yz E A if 22 By If R is a binary relation defined on a set A then and sz then 22Rz Functional R is Transitive lt for all 227y7z e A if 9573 e R 1 R is not reflexive ltgt there is an element 22 E A such that and yz e R then 2z e R 2 R 23 tie 2222 if R Informal If one element is related to a second element and that second element is related to a third element then the 2 R 395 quot0t symmetr39c 6 there are Elements xvy E A SUCl that first element is related to the third element 9 7 Ry bl y R a quot639 9573 E R bUt 3795 R Graph In all cases where there is an arrow going from one I I I 3 B Is not transitive lt2 there are elements 227 y z E A such that point to a second and from the second point to a third there is an arrow going from the first point to the third A Relamns on Set Reflexxvxby Symmeuy and Tmnsmmy Equivalence Relamns 7 p 1543 22 By and sz but 22 Rz Le any 3712 6 R but 2212 B To show that a binary relation does not have one of the properties it is sufficient to find a counterexample Relamns on Set Re eany Symmeuy and Txansxhvxby Equivalence Relamns 7 p 1643 Example 1 of 5 Let A 0123 and de ne relations R S and T R 90071073170171727273707373 S 07 07 07 27 07 37 27 T 07 D7 27 Fill in the table Reflexive Symmetric Transitive Relations on Sets Reflexivity Symmeuy and Txansmmy Equivalence Reiamns e p 1743 Example The Relation R 2 of 5 We have A 0123 and R 0707071707371707171727273707373 O 9 0001 3 2 R is reflexive since there is a loop at each point in the directed graph R is symmetric since in for every arrow going from one point to another there is an other arrow going back R is not transitive since eg 1R0 and 0 R3 but 1 R 3 ie there is no shortcutquot arrow connecting 1 and 3 Reialmns on Sets Re eany Symmehy and Txansihvny Equivalence Reialmns e p 1343 Example The Relation S 3 of 5 We have A 0123 and S 07 072 073 273 3olt 02 S is not reflexive since there are missing loops at 1 2 and 3 S is not symmetric the arrows from 2to0 3to0 and 3to2 are missing S is transitive since there is always a shortcutquot arrow so that if zy E S and yz E Sthen 12 6 S Relations on Sets Reflexivity Symmeuy and Txansmmy Equivalence Reiamns e p 1943 Example The Relation T 4 of 5 We have A 0123 and T 07 D7 27 lo gt01 3 2 Tis not reflexive since there are missing loops at 0 1 2 and 3 Tis not symmetric the arrows from 1to0 and 3to2 are missing T is transitive since it is not not transitive Reialmns on Sets Re eany Symmehy and Txansihvny Equivalence Reialmns e p 2043 Example Let A 0123 and de ne relations R S and T R 00 01 0 S 00 02 03 2 T 07 D7 The Relations R S and T 73170171727273707373 73 50f5 Fill in the table Reflexive Symmetric Transitive R Yes Yes No S No No Yes T No No Yes Reiacmns on Secs Re exmcy Symmeuy and Txansxhvny Equivalence Reiamns e p 2143 irreflexivity AntiSymmetry and intransitivity De nition Let R be a binary relation on a set A 1 R is lrreflexive if and only if Va 6 A 2 R 22 2 R is Antisymmetric if and only if Vxy E A if ny then 3 R is lntransitive if and only if Vxyz E A if ny and 3 R3 then 2 R z o R can be re exive nonre exive or irre exive o R can be symmetric nonsymmetric or antisymmetric o R can be transitive nontransitive or intransitive Think about these definitions Reiacmns on Secs Re eany Symmehy and Txansmmy Equivalence Reiacmns e p 2243 irreflexivity Forma l Functional R is lrreflexive ltgt for all 2 E A xx g R Informal Graph back to itself Reiacmns on Secs Re exmcy Symmeuy and Txansxhvny Equivalence Reiamns e p 2343 R is lrreflexive if and only if Va 6 A x R x No element is related to itself No point of the graph has an arrow looping around AntiSymmetry R is AntiSymmetric if and only if V05 3 E A if 2 By then y R x Formal Functional R is AntiSymmetric ltgt for all 2231 6 A if 2231 6 R then y x g R Informal If one element is related to a second element then the second element is NOT related to the rst Graph In all cases where there is an arrow going from one point to a second there is no arrow going from the second point back to the rst o o Reiacmns on Secs Re eany Symmehy and Txansxhvny Equivalence Reiacmns e p 2443 intransitivity Formal R is lntransitive if and only if V27yz E A if 2Ry and sz then x R 2 Functional R is lntransitive ltgt for all 2yz E A if 2y E R and 313 6 R then x72 g R Informal If one element is related to a second element and that second element is related to a third element then the first element is not related to the third element Graph In all cases where there is an arrow going from one point to a second and from the second point to a third there is never an arrow going from the first point to the third no shortcut exist anywhere lt Reretmns on Sets Retrexmty Symmetxy and Txansxhvxty Equwerence Reretmns e p 2543 Example Equality on R Let A IR the set of real numbers and define the relation R 2 By ltgt 2 y Properties R is reflexive R is reflexive if and only if V2 E R 2 Pt2 Here this means 2 2 lie V2 E R 2 2 This statement is certainly true every real number equals itself R is symmetric This is true since if 2 y then y 2 hence 27 y E R and y2 E R R is transitive This is true since if 2 y and y z then 2 z Reretmns on Sets Retrexmty Symmetxy and Txansxhvxty Equwerence Reretmns e p 2643 Example Less Than lt on R Let A IR the set of real numbers and define the relation R 2 By ltgt 2 lt 3 Properties R is irreflexive f2 Pt2 then 2 lt 2 but that is nevertrue hence 2 R 2 V2 E R R is antisymmetric If 2 B y then 2 lt 3 which means y 5i 2 lie y R 2 R is transitive This is true since if 2 lt y and y lt z then 2 lt z Reretmns on Sets Retrexmty Symmetxy and Txansxhvxty Equwerence Reretmns e p 2743 Example Congruence Modulo 3 on Z We define a relation R on Z as follows Vmn E Z mRn ltgt 3lm7n R is reflexive Suppose m is an integer Now m 7 m 0 and 3l0 since 0 3 0 so by definition of Rwe have mRm D R is symmetric Suppose 71212 6 Z such that mRn By definition of R we have3lm7nltgtm7n 3kforsomek E Z Multiplying both sides by 71 gives 12 7 m 3 which shows 3ln 7 hence n Rm D R is transitive Suppose m7 n p E Z such thatm R n and n Ftp We have 3lm7n and 3ln7p and we can write m7n 37 and n 7 p 33 for some 7 s E Z Adding the two gives m 7 n n 7 p m 7p 37 s which shows that 3lm 7 13 Hence m Ftp and it follows that R is transitive D Reretmns on Sets Retrexmty Symmetxy and Txansxhvxty Equwerence Reretmns e p 2343 Equivalence Relations Different but the Same Idea We are going to group elements that look different but really are the same Example Think about the rational numbers there are several ways of writing the same fraction eg 1 71 2 4711 2 f2 4 9422 We can define a relation on Q X Q where Q is the set of all rational numbers Ry QXQx2 now at e R 4 6 R at e R Reietmns on Sets Reflexivity Symmetxy and Txensitmty Equweience Reietmns e p 2943 A Relation induced by a Partition Recall Definition A collection of noneempty sets A1A2 An is a partition of a set A if and only if 1 AA1UA2UUAn 2 A1A2 A are mutually disjoint Definition Given a partition of a set A the binary relation induced by the partition R is defined on A as follows Vac y E A 2 By ltgt there is a set A ofthe partition such that both 2 E A and y 6 Al We need an example to make sense out of this definition Reietmns on Sets Reflexivity Symmetxy and Txensitmty Equweience Reietmns e p 3o43 Example Relation induced by a Partition Let A 01234 and consider the following partition of A A1 0737497 A2 1 A3 2 Now two elements 2231 6 A are related if and only if they belong to the same subset of the partition 0 3 lt1 2 H O O Hence 0707073707471717 4 27 2 37 0 37 3 37 4 4 0 4 3 4 4 Reietmns on Sets Reflexivity Symmetxy and Txensitmty Equweience Reietmns e p 3143 Equivalence Relations Theorem Let A be a set with a partition and let R be the relation induced by the partition Then R is reflexive symmetric and transitive Definition Equivalence Relation Let A be a non empty set and R a binary relation on A R is an equivalence relation if and only if R is reflexive symmetric and transitive Example By the theorem the relation induced by a partition is an equivalence relation Reietmns on Sets Reflexivity Symmetxy and Txensitmty Equweience Reietmns e p 3243 Notation Congruence Modulo n Notation Let m7n7d E Z with d gt 0 The notation m E n mod d is read quotm is congruent to n modulo clquot and means that dlm 7 n Symbolically m E n mod d ltgt dlm7n Recall the QuotientRemainder Theorem Theorem Given any integer n and a positive integer d there exist unique integers q the quotient and 7 the remainder such that ndqr and 0 Tltd Reietisns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietisns e p 3343 Equivalence Relation Congruence Modulo 3 Let R be the relation R mn E Z X Z m nmod 3 We show that this is an equivalence relation Reflexivityl Let m E Z then 3lm 7 m since 0 30 and it follows that mRm Symmetry Let mm 6 Z so that mRn We have 3lm 7 n ltigt m7n3kforsomek Zltgtn7m37k ltgt3ln7mltgtnPtm Transitivityl Let m7n7p E Z so that mRn and an We have 3lm7n ltgt m7n3TTEZ 3ln7p ltgt n7p3ssEZ add m7p3Ts Hence 3lm 7 p and we have mes D Reietmns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietmns e p 3443 Equivalence Classes Suppose we have a set A and an equivalence relation R on A Given a particular element 2 E A it is natural to ask the question quotwhat elements are related to 2 quot All the elements that are related to 2 form a subset of A and this subset is called the equivalence class of 22 Definition Suppose A is a set and R is an equivalence relation on A For each element 2 E A the equivalence class of 22 denoted x and called the class of 2 for short is the set of all elements 3 E A such that y Rx Symbolically 23 y 6 Al yR v Reietisns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietisns e p 3543 Example Equivalence Classes 1 of 2 Let A 0172374 and de ne a binary relation R on A R 07070747171717372727371737374707474 G gtOc Figure The array diagram directed graph corresponding to the relation By quick inspection we see that R is reflexive symmetric and transie tive hence an equivalence relation Reietmns on Sets Retiexmty Symmetxy and Txensitmty Equweience Reietmns e p 3643 Example Equivalence Classes 2 of 2 ill 10 The equivalence classes are 0 xEAlxRO 04 1 xeAlle 13 2 xEAlxRQ 2 3 xEAlxRB 13 4 Tammi 04 Note that 0 4 and 1 3 hence the distinct equivalence classes are 04 13 2 Equivalence Classes A Theorem The following theorem tells us that an equivalence relation induces a partition Theorem If A is a nonempty set and R is an equivalence re lation on A then the distinct equivalence classes of R form a partition of A tie the union of the equivalence classes is all of A and the intersection of any two distinct classes is empty Relauons on 3945 Re exmiy Symmehy and Txansxhvxby Equivalence Relamns e p 3743 Relauons on 3945 Re exmcy Symmech and Txansxhvxby Equivalence Relauons e p 3343 Example Equivalence Classes of Congruence Module 3 1 of 3 Example Equivalence Classes of Congruence Module 3 2 of 3 Let R be the relation of congruence modulo 3 on the set Z tie We have Vm7n Z 0z Zlz3kk Z 03736m6979 mRnltgt 3lm7n ltgtmEnmod3 l1l le339k1ik Z 1747 2777 57107 87n 2 62 Sk 2keZ 25718741177 We describe the equivalence classes For each integer a the class of x 00 39 B l 1 as a xez xRa y emma 23 e Z 3 07 7 a 0 3 3 6 6 9 9 xElema3kk Z 1 4l72l 7l75l 10ll78l xEle3kak Z 2 5ll1l l8ll4 11ll77l In particular 0z Zlz3k keZ 03736m6979 1x le3k1keZ 14727751078 2x le3k2keZ 25718741177 Relahons on Set Re exmiy Symmeuy and Txansxhvny Equivalence Relamns e p 3943 Hence the distinct equivalence classes are xEle3k kEZ xEle3k1k Z xEle3k2 kEZ Relahons on Set Reflexxvny Symmehy and Txansxhvny Equivalence Relahons e p 4043 Example Equivalence Classes of Congmence Module 3 3 of 3 The distinct equivalence classes are xEle3k kEZ xEle3k1k Z xEle3k2 kEZ The class of 0 can also be called the class of 3 or the class of 96 but the class is the set 22 E lez 3 k k E Z Definition Suppose R is an equivalence relation on a set A and S is an equivalence class of R A representative of the class S is any element a E A such that a S Remus on Set Reflexxvxby Symmeuy and Txansmmy Equivalence Relamns 7 p 4143 Notes It is possible to de ne multiplication and addition of the equiva39 lence classes corresponding to the rational numbers previous ex ample The rational numbers can be de ned as equivalence classes of ordered integers It can be shown that all integers negative zero and positive can be de ned as equivalence classes of ordered pairs of positive integers Frege and Peano showed late 19th century that the positive in tegers can be de ned entirely in terms of sets Dedekind 1848 1916 showed that all real numbers can be de ned as sets of rational numbers All together these results show that the real numbers can be de ned using logic and set theory alone Relahons on Set Re eany Symmeuy and Txansmvuy Equivalence Relahons 7 p 4243 Homework 12 Not Due Final Version Epp39v30 10111015101710115101231012510231024 10212 10214 10237 1033 10317 10319 10340 Epp39v20 10111015101710115101231012510231024 10212 10214 10237 1032 10314 10316 10335 Remus on Set Reflexxvxby Symmeuy and Txansmmy Equivalence Relamns 7 p 4343 C C The Logic of Quantified Statements Predicates and Quantified Statement Statements Containing Multiple Quantifiers Arguments with Quantified Statements Lecture Notes 4 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminusSDSUEDU httpterminusSDSUEDU Id lecture texv 1 9 20060914 232419 blomgren Exp The Logic of Quantified Statements 7 p 156 C C So far we have discussed statement calculus or propositional calculus ie symbolic analysis of compound statements We have introduced logical connectives such as A V N gt and lt gt We have created quite a useful toolbox it is quite sufficient if you want to build microchips for a living You can indeed live quite large if you build microchipsl We cannot however determine if the following is a valid statement All humans need logic Peter is human Peter needs logic The Logic of Quantified Statements 7 p 256 C C In order to study intuitively valid arguments All humans need logic Peter is human Peter needs logic We must understand in the logic sense the meaning of words like all some etc Further we must separate our statements into parts in much the same way we separate declarative statements into subject and predicates The symbolic analysis of predicates and quantified statements is called predicate calculus The Logic of Quantified Statements 7 p 356 C In grammar the predicate refers to the part of the sentence which gives information about the subject eg Peter is a professor at SDSU V x V SUbjeCt predicate The predicate is the part of the sentence from which the subject has been removed In logic predicates are obtained by removing any some nouns from a statement P is a professor at SDSUquot is a professor at R isaat Example P Q and R are predicate symbols The Logic of Quantified Statements 7 p 456 C We use the predicate variables a and y to define predicates Px and Qxy Px x is a professor at SDSU Qxy x is a professor at y RJJJJ Z x is a 3 at yquot Example Px Qxy and Rxyz are predicate symbols x y and z are predicate variables Definition Predicate A predicate is sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables The domain of a predicate variable is the set of all values that may be substituted in place of the variable The Logic of Quantified Statements 7 p 556 C We must specify the domains of our predicate variables If A is a set we say that a is a member of the set A denoted x E A If x is not a member ofthe set A we write x if A A could be the set of all students at SDSU The following sets are so common they have their own reserved sym bols Symbol Set of C Set of all Complex Numbers N Set of all Nonnegative Integers Q Set of all Rational Numbers R Set of all Real Numbers Z Set of all Integers The Logic of Quantified Statements 7 p 656 When an element in the domain of a variable of a onevariable predicate is substituted for the variable the resulting statement is either true or false Definition Truth Set If Px is a predicate and a has domain D the truth set of Px is the set of all elements of D that make Px true when substituted for x The truth set of Px is denoted xEDlPW which is read the set of all a in D such that The Logic of Quantified Statements 7 p 756 Example 1 Let Px x is a senior and suppose the domain D of a is the set of all SDSU students Then the truth set of Px is the set of all SDSU students in senior standing Example 2 Let Px 3 is a factor of x and D N Then x E D l 3 6 9 12 15 Example 3 Let Px x is a factor of 8 and D N Then the truth set of Px is 1 2 4 8 The Logic of Quantified Statements 7 p 856 Let Px and Qx predicates and suppose they have a common domain a E D The notation Px gt Qx means that every element in the truth set of Px is in the truth set of The notation Px ltgt Qx means that Px and Qx have identical truth sets The Logic of Quantified Statements 7 p 956 Example Let Px x is a factor 01 8quot Qx x is a factor of 4 Rx x lt 5 and x 7E 3quot D Z the set of positive integers The truth sets are x E D l 1248 93 E D l Qx 17274 x E D l 124 We have the following Qx gt Rx gt Px 6293 lte Rb The Logic of Quantified Statements 7 p 1056 V The symbol V denotes for all and is called the universal quantifier If we let S be the set of all humans beings we can write Vx E S a is mortal The following phrases translate to V for all for every for arbitrary for any H H H I H for each given any The Logic of Quantified Statements 7 p 1156 The Existential Quantifier There existsquot Symbol El The symbol 3 denotes there exists and is called the existential quantifier If we let S be the set of all humans beings we can write 3x 6 S such that a is student in Math 245 The following phrases translate to 3 there exists there is a we can find a there is at least a for some for at least one The Logic of Quantified Statements 7 p 1256 Formal Definitions Universal and Existential Statements Definition Universal Statement Let Qx be a predicate and D the domain of x A universal It is defined to be true if and only if Qx is true for every x in D statement is a statement in the form Vx E D A value for which Qx is false is called a counterexample to the universal statement Definition Existential Statement Let Qx be a predicate and D the domain of 3 An existential statement is a statement of the form 3 a E D such that It is defined to be true if and only if Qx is true for at least one x in D If is false if and only if Qx is false for all x in D The Logic of Quantified Statements 7 p 1356 C Example Rewrite the following statements formally 1 All triangles have three sides 2 No dogs have wings 3 Some programs are structured Solutions la Let T be the set of triangles Vt E T t has three sides lb V triangles t t has three sides 2a Let D be the set of all dogs Vd E D d does not have wings 2b V dogs d d does not have wings 3a Let P be the set of all programs 3p 6 P such that p is structured 3b 3 a program p such that p is structured The Logic of Quantified Statements 7 p 1456 One of the most important forms of statements in mathematics in proofs and theorems is the universal conditional statement Vx if Px then Qx Example 1 Let the domain of a be the positive integers Z Px x is prime Qx x cannot be factored We make the statement Vx E Z if Px then Example 2 The definition of a valid argument form is a universal conditional statement V combinations of truth values for the component statements if the premises are all true then the conclusion is also true The Logic of Quantified Statements 7 p 1556 Consider the two statements V real numbers 3 if a is an integer then a is a rationalquot V integers r r is a rationalquot They mean the same thing In general given a statement of the form Vx E U if Px then Qx and the truth set D for Px D x6 UiPx the statement can be rewritten as Vx E D Qx The Logic of Quantified Statements 7 p 1656 Consider the two statements 3 a number n such that n is prime and n is even 3 a prime 7 such that n is evenquot They mean the same thing In general given a statement of the form 3x 6 U such that Px and Qx and the truth set D for Px D x6 UiPx the statement can be rewritten as 3x 6 D such that Qx The Logic of Quantified Statements 7 p 1756 C C There Be Dragons Here The statement if a number is an integer then it is a rational numberquot is equivalent to a universal statement see slide 16 However it does not contain any of the telltale V phrases see slide 11 The only indication of universal quantification is the indefinite article H H a This is an example of implicit quantification The quantification of a statement crucially determines both how the statement can be applied and what method must be used to establish its truth Thus is is important to be alert to the presence of hidden implicit quantifiers when reading mathematics so that statements are interpreted in a logically correct way The Logic of Quantified Statements 7 p 1856 C C The informal statement 24 can be written as a sum of two integers Formally means 3 integers n m such that 24 m Consider a x12x22x1 b Solve x 22 25 a is implicitly universally quantified and b implicitly existentially quantified a VxER x12x22x1 b Show that 3x 6 R such that x 22 25 The Logic of Quantified Statements 7 p 1956 version 3rd Edition 2nd Edition Problems 21 12 14 22 217916 Please use the 3rd Edition numbering when handing in your solutions The Logic of Quantified Statements 7 p 2056 The negation of All mathematicians are strange is not No mathe maticians are strange it is N All mathematicians are strange Some mathematicians are not strange Theorem Negation of a Universal Statement The negation of a statement of the form Vx E D Qx is logically equivalent to a statement of the form 3x 6 D such that N Symbolically N Vx E D E 3x 6 D such that N The Logic of Quantified Statements 7 p 2156 The negation of Some mathematicians are strange is not Some mathematicians are not strange it is N Some mathematicians are strange No mathematicians are strange Theorem Negation of an Existential Statement The negation of a statement of the form 3x 6 D such that Qx is logically equivalent to a statement of the form Vx E D N Symbolically N 3x 6 D such that E Vx E D N The Logic of Quantified Statements 7 p 2256 The negation of a universal statement all are is logically equivalent to an existential statement 3 N some are not The negation of an existential statement some are is logically equivalent to a universal statement N all are not The Logic of Quantified Statements 7 p 2356 The negation of a Universal Conditional Statement N W PW e 6206 is very important in mathematical arguments We already know how to negate a forallstatement 3x such that Px gt Qx And we know how to negate an implication thus N W PW e Qx E 3x such that Px Qx or N Vx if Px then E 3x such that Px and N The Logic of Quantified Statements 7 p 2456 We have seen that the negation of a for all statement is a there is statement and the other way around This is analogous to De Morgan39s Laws where the negation of an and statement is and or statement and vice versa A universal statement is a generalization of the and statement If Qx is a predicate and the domain D of the predicate variable a is the set 31 32 xn then the statements VX E DQX and QX1 2le 39 39 39 9an are logically equivalent The Logic of Quantified Statements 7 p 2556 An existential statement is a generalization of the or statement If Qx is a predicate and the domain D of the predicate variable a is the set 31 32 xn then the statements 3X 6 D such that Qx and QX1VQX2 Vquot VQxn are logically equivalent The Logic of Quantified Statements 7 p 2656 Now N Vx E DQx E N Qx1 Qx2 is logically equivalent to 3x EDN Qx E N Qx1 N Qx2 NQxn And N 3x 6 DQx E N Qx1 Qx2 is logically equivalent to Vx EDN Qx E N Qx1 N Qx2 NQxn The Logic of Quantified Statements 7 p 2756 We know that a conditional statement has a contrapositive a con verse and an inverse We can generalize these definition to universal conditional statements Definition Contrapositive Converse Inverse Consider a statement of the form Vx E D it Px then Qx 1 lts contrapositive is the statement Vx E D if N then N 2 lts converse is the statement Vx E D if Qx then 3 lts inverse is the statement Vx E D if N then N The Logic of Quantified Statements 7 p 2856 Write the contrapositive converse and inverse of the following statement If a real number is greater than 2 then its square is greater than 4 Formal V7 6 R if r gt 2 then r2 gt 4 Contrapositive Vr E R if r2 g 4 then r g 2 Converse V7 6 R if r2 gt 4 then r gt 2 Inverse V7 6 R if r g 2 then r2 lt 4 The Logic of Quantified Statements 7 p 2956 Write the contrapositive converse and inverse of the following statement If a real number is greater than 2 then its square is greater than 4 Formal V7 6 R if r gt 2 then r2 gt 4 Contrapositive Vr E R if r2 g 4 then r g 2 Converse V7 6 R if r2 gt 4 then r gt 2 Inverse V7 6 R if r g 2 then r2 lt 4 Formal Contrapositive s Converse E Inverse The Logic of Quantified Statements 7 p 2956 Further we can extend the definitions of necessary sufficient and only if to apply to universal conditional statements Definition Sufficient Necessary Only If 1 Vx rx is a sufficient condition for rx then means Vx if 2 Vx rx is a necessary condition for means Vx if N then N or equivalently Vx if 5x then 3 quotVx rx only if means quotVx if N then N or equivalently Vx if rx then The Logic of Quantified Statements 7 p 3056 C C Rewrite the following statements as quantified conditional statements without using the words necessary or suf cient 1 Squareness is a sufficient condition for rectangularity 2 Being at least 35 years old is a necessary condition for being President of the United States The Logic of Quantified Statements 7 p 3156 C C Rewrite the following statements as quantified conditional statements without using the words necessary or suf cient 1 Squareness is a sufficient condition for rectangularity 2 Being at least 35 years old is a necessary condition for being President of the United States 1 Let S be the set of shapes Vx E S if a is a square then a is a I rectangle If a shape is a square then it is a rectangle 2 Let H be the set of human beings Vx E H if x is younger than 35 years old then 3 cannot be the President of the United States Using the contrapositive V33 6 H if x is the President of the United States then a is at least 35 years old The Logic of Quantified Statements 7 p 3156 Rewrite the following as a universal conditional statement A product of two numbers is 0 only if one of the numbers is 0 Solution If neither of the two numbers is 0 then the product of the numbers is not 0 Let T1 E R and T2 E R lf T1 7g 0 and T2 7g 0 then T1 T2 7 0H If a product of two numbers is 0 then at least one of the numbers is 0 Let T1 E R and T2 E R lf T1 T2 0 then T1 0 0quot T2 0H Here we have used the equivalent contrapositive form The Logic of Quantified Statements 7 p 3256 version 3rd Edition 2nd Edition Problems 22 15 17 29 40 21 28 23 22 33 21 12 14 22 21 7 9 16 Please use the 3rd Edition numbering when handing in your solutions The Logic of Quantified Statements 7 p 3356 In the previous section we expanded our logic vocabulary to include quantifiers eg V for all and 3 there exists Next we are going to construct more complicated statements using these quantifiers in particular we look at statement which contain more than one quantifier The Logic of Quantified Statements 7 p 3456 First off lets translate the following informal statements to formal symbolic statements H Everybody loves somebody 2 Somebody loves everybody 1 Let H be the set of human beings Vx E H 3y 6 H such that a loves y 2 Let H be the set of human beings 3x 6 H such that Vy E H x loves y The Logic of Quantified Statements 7 p 3556 In calculus we define the limit of a sequence The limit of the sequence can as it goes to infinity equals to L rm can L TL gtOO if and only if the values of can become arbitrarily close to L as it grows More precisely this means that for any positive num ber e we can find and integer N such that whenever n is larger than N then the number an is in the interval between L e and L i equot Symbolically Ve gt 0 EN 6 N such that Vn ifngtN then L ltanltL i e Once you know the symbols this is a very effective way of communi cating The Logic of Quantified Statements 7 p 3656 How do we negate a statement like Everybody loves somebody Let H be the set of human beings Vx E H 3y 6 H such that a loves y The negation of the statement must be false when the statement is true Since the statement talks about a property assumed to be true for all people all we need is the existence of a counterexample Let H be the set of human beings 3x 6 H such that 3y E H such that a loves ltgt 3x 6 H such that Vy E H a does not love The Logic of Quantified Statements 7 p 3756 That 39s I N Everybody loves somebody is logically equivalent to There is somebody who does not love anybody The argument we made can be generalized The negation of Vx 3y such that Pxy is logically equivalent to 3x such that Vy N 133379 In our example Pxy x loves The Logic of Quantified Statements 7 p 3856 We have The negation of is logically equivalent to Vx 3y such that Pxy 3x such that Vy N 133379 Similarly The negation of is logically equivalent to 3x such that Vy Pxy Vx 3y such that N Pxy The Logic of Quantified Statements 7 p 3956 Negate each of the following statements 1 Vn E Z 3k 6 Z such that n 2k All integers are even 2 3 a person a such that V people y a loves y Somebody loves everybody The Logic of Quantified Statements 7 p 4056 Negate each of the following statements 1 Vn E Z 3k 6 Z such that n 2k All integers are even 2 3 a person a such that V people y a loves y Somebody loves everybody 11 3n 6 Z such that 3k E Z such than n 2k 12 3n 6 Z such that We 6 Z 71 7E 2k There is some integer which is not equal to twice any other integer The Logic of Quantified Statements 7 p 4056 Negate each of the following statements 1 Vn E Z 3k 6 Z such that n 2k All integers are even 2 3 a person a such that V people y a loves y Somebody loves everybody 11 3n 6 Z such that 3k E Z such than n 2k 12 3n 6 Z such that Vk E Z 71 7E 2k There is some integer which is not equal to twice any other integer 21 V people 3 V people y a loves 22 V people 3 3 person y such that a does not love y Nobody loves everybody The Logic of Quantified Statements 7 p 4056 C C We have introduced predicates Px sentences with a finite number of variables which become statements when specific values are substituted for the variables We talked about the truth set of a predicate all the values of the variables which make the predicate true We added the concepts of universal statements V for all existential statements 3 there exists and conditional state ments if then to our vocabulary To enable us to express more complex statements we studied multi ply quantified statements Things we do to all our statements finding truth values writing the contrapositive the converse the inverse and negating the statement The Logic of Quantified Statements 7 p 4156 The Rule of Universal lnstantiation If some property is true of everything in the domain then it is true of any particular thing in the domain Example All students want to graduate Jane is a student Jane wants to graduate Universal instantiation is the fundamental tool of deductive reasoning it is used mathematical formulas definitions and theorems as well as in all kinds of everyday legal etc arguments The Logic of Quantified Statements 7 p 4256 Recall Modus Ponens The method of affirming If p then q p q If we combine the rule of universal instantiation with modus ponens we get universal modus ponens Universal Modus Ponens Formal version Informal version Vx If then Qx Ifx makes Px true then x makes Qx true Pa for a particular a a makes Px true Qa a makes Qx true The Logic of Quantified Statements 7 p 4356 Universal Modus Ponens Formal version Informal version Vx If then Qx Ifx makes Px true then x makes Qx true Pa for a particular a a makes Px true Qa a makes Qx true Universal Modus Ponens consists of two premises Vx if then Qx premise1 Pa for a particular a premise2 one of which 1 is quantified An argument of this form is called a syllogism rule of inference The first and second premise are called the major and minor premises respectively The Logic of Quantified Statements 7 p 4456 C Part of the reason we are building our logic toolbox is that we are gearing up to discussing methods of proving quantified statements one of the most important activities in mathematical research For illustration let us break the proof that the sum of two even integers is evenquot into its smallest parts and show how universal modus ponens guides us Suppose m and n are particular but arbitrarily chosen even in tegers Then m 2r for some integer r amp1 and n 25 for some integer s amp2 Hence m n 27 25 by substitution 2r s by factoring out the 2 amp3 Now r l s is an integer amp4 and so is 2rs amp5 Thus m n is even The Logic of Quantified Statements 7 p 4556 C amp1 amp2 amp3 amp 4 amp5 If an integer is even then it equals twice some integer m is a particular even integer m equals twice some integer r If an integer is even then it equals twice some integer n is a particular even integer n equals twice some integer 5 If a quantity is an integer then it is a real number r and s are integers r and s are real numbers and 2r 25 2r s For all m and n if m and n are integers then m n is an integer m r and n s are two particular integers r s is an integer If a number equals twice some integer then that number is even 2r 3 equals twice the integer r s 2r s is even The Logic of Quantified Statements 7 p 4656 Recall Modus Tollens The method of denying If p then q Np If we combine the rule of universal instantiation with modus tollens we get universal modus tollens Universal Modus Tollens Formal version Informal version Vx If then Qx If x makes Px true then x makes Qx true N Qa for a particular a a does not make Qx true N Pa a does not make Px true The Logic of Quantified Statements 7 p 4756 Universal Modus Tollens Formal version Informal version Vx If then Qx If x makes Px true then x makes Qx true N Qa for a particular a a does not make Qx true N Pa a does not make Px true Universal modus tollens is the key to mathematical proofs of contra diction one of the most important mathematical arguments Example All human beings are mortal Zeus is not mortal Zeus is not human The Logic of Quantified Statements 7 p 4856 Proving Validity of Arguments with Quantified Statements Definition To say that and argument form is valid means the following No matter what particular predicates are substituted for the predicate symbols in its premises if the resulting premise statements are all true then the conclusion is also true An argument is called valid if and only if its form is valid Note Note Note If you think this looks familiar it is a straightforward generalization of the validity for statements with compound statements We have to use the laws of logic to prove that the laws of logic are valid Proving that a general quantified statement form is valid is beyond the scope of this class The Logic of Quantified Statements 7 p 4956 Finally Something Less Abstract Proof by Diagramquot Consider the following statement Informal All integers are rational number Formal V integers n n is a rational number Rational Numbers Picture the sets of rational numbers and integers as disks The truth of the state ment means that the integer disk must be contained inside the disk of rational numbers The Logic of Quantified Statements 7 p 5056 Finally Something Less Abstract Proof by Diagramquot Rational Numbers Consider the following state ments 51 n is an integer 52 r is a rational 53 z is not a rational From the diagram we see that 1 gt n is a rational 52 75gt r is an integer There are rationals that are not integers 3 gt z is not an integer The Logic of Quantified Statements 7 p 5156 Rational Numbers Rational Numbers Rational Numbers Major premise Minor premise Conclusion All integers are rational numbers Major premise z is not a rational number Minor premise z is not an integer Conclusion Example of a valid argument The Logic of Quantified Statements 7 p 5256 Rational Numbers Rational Numbers Rational Numbers Major premise Minor premise Conclusion All integers are rational numbers Major premise r is a rational number Minor premise r is an integer Conclusion Example of an invalid argument Converse Error The Logic of Quantified Statements 7 p 5356 Rational Numbers Rational Numbers Major premise Minor premise Conclusion All integers are rational numbers Major premise r is not an integer Minor premise r is not a rational number Conclusion Example of an invalid argument Inverse Error The Logic of Quantified Statements 7 p 5456 The reason inverse and converse errors are common is that the con clusions would be true if the major premise was a biconditional quotif and only if ltgt Call it fuzzy logic artificial intelligence or abduction if you have a major premise for all x if Px then theni Qa is true for a particular a then is it a good idea to check if Pa is true This kind of reasoning is used by criminal investigators doctors auto mechanics etc etc Qa true is not evidence of Pa true but possibly a due The Logic of Quantified Statements 7 p 5556 Final Version 3rd Edition 2nd Edition Problems 24 19 20 25 31 23 19 20 24 27 23 37 22 15 22 15 17 29 40 21 28 23 22 33 21 12 14 22 21 7 9 16 Please use the 3rd Edition numbering when handing in your solutions The Logic of Quantified Statements 7 p 5656 C C Elementary Number Theory and Methods of Proof Floor and Ceiling Proofs by Contradiction and Contraposition Lecture Notes 6 Peter Biomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921824720 blomgrenterminusSDSUEDU httpterminusSDSUEDU 51d lecturetexv 14 20060927 204710 blomgren Exp 5 Elm and Ceiling 2 Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 133 floorx ceilx Imagine a real number 2 E R sitting on the number line The floor of 2 is the integer Q E Z which is to the left of 2 Le the largest integer which is smaller than or equal to 2 The ceiling of 2 is the integer 6 Z which is to the right of 2 Le the smallest integer which is larger than or equal to 2 We have g 2 g E B where equality holds if and only if 2 is an integer Q 2 ltgt 2 E Z Elm and Calm 2 Pxoofs by cbnuadmmn and cbnuapbsmbn 7 p 233 n n1 x floorx Definition The floor of x Given any real number 2 the floor of 2 denoted 2 is defined as follows 2 the unique integer n such that n g 2 lt n 1 Symbolically if 2 is a real number and n is an integer then lxjn ltgt n 2ltn1 Elm and Ceiling 2 Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 333 n l n ceilx Definition The ceiling of x Given any real number 2 the ceiling of 2 denoted la l is defined as follows lxl the unique integer n such that n 7 1 lt 2 g n Symbolically if 2 is a real number and n is an integer then lxln ltgt n71lt2 n Elm and Calm 2 Pxoofs by cbnuadmmn and cbnuapbsmbn 7 p 433 1 Loading students into Buses 1370 students are going to the zoo Due to budget constraints the principal will only allow full buses to leave Each bus holds at most 40 students How many buses can leave Solution 137040 3425 34 Comment This example may seem a little silly since we are dealing with integer quantities we could have used 1370 div 40 34 Elm and ceiling amp Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 533 2 Tax Refund Due to a sudden miracle the state controller has found a surplus of 416832521832 in the budget This money is to be distributed among 24123451 taxpayers However each check must be in whole dollars only no pennies How large will the tax refund be Solution 41683252183224123451 172791414392576 172 Fibbx and Calm amp Pxoofs by Conhadlchon and cbnuapbsmbn 7 p ess 3 Hot Dogs on the Grill You are expecting 12 friends to come over for a BBQ An average person eats 32 hot39dogs Hot39dogs are packaged 12pack and buns 10pack How many packs of hot39dogs and buns do you have to buy Solution Hot39dogs 133212 346671 4 Buns 133210 416001 5 Why 13 You39re eating too right Fibbx and ceiling amp Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 733 4 Disproving an alleged property of the floor function Statement For all real numbers 2 and y z y z ly Disproof by Counterexample Consider the case 2 y Then Fibbx and Calm amp Pxoofs by Conhadlchon and cbnuapbsmbn 7 p ass Theorem VxelRandeZ lxmjlzjm Proof Let 2 be real number and m be an integer Let n 22 By the definition of floor n is an integer and n g 2 lt n 1 Add m to all three entries in the inequality to get nm zmltnm1 Since n m is an integer by the definition of floor lxmj nm Now we recall that n 22 and by substitution we have la mj m D Flow and Calm x bebfs by cbncxadmubn and cbncxapbsmbn 7 p 933 712 tution case 2 When n is even then n 2k for some integer k By substi39 lglllwk 712 Theorem For any integer n if n is even if n is odd Proof Let n be an integer By the quotient39remainder theorem n is odd or n is even case 1 When n is odd then n 2k 1 for some integer k By substitution lEllllllklk because k is an integer and k g k 12 lt k 1 Now since n 2k 1 it follows that k quot 71 la 71 and we have shown that j quot7 1 when n is odd nd c9111 amp Pxoofs by Conhadlchon and cbncxapbsmbn 7 p 1033 lglquot Theorem because k is an integer and k g k lt k 1 Now since n 2k it follows that k and we have shown that 2 when n is even Together case 1 n odd and case 2 n even shows that the statement is true D Elm and c9111 amp Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 1133 If n is a nonnegative integer and d is a positive integer and if q and r nid lndl then nclqr7 and 0 rltd Proof Let n be a non39negative integer cl a positive integer q lndl and r n 7 d lndl By substitution n n dqrd nid 11 So it remains to show that 0 g r lt cl But q lndj Thus by the definition of floor q gltq1 Elm and c9111 amp Pxoofs by Conhadlchon and cbncxapbsmbn 7 p 1233 dq nltdqd andso 0 n7dqltd rn7d n7dq Hence we have shown 0 g r lt cl Both parts of the theorem have been proved D F100 and c9111 amp Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 1333 Epp3519 Is the following statement true or false For all real numbers 22 2 11 1 Solution Let 22 be a real number Then 12 22 11 is an integer By the definition of ceiling n 7 1 lt 22 1 g n Subtracting 1 from all parts of the inequality gives 12 7 2 lt 22 g n 7 1 and by the definition of ceiling n7 1 Solving this expression for n givesn 1 Putting the two expressions for 12 together shows 22 11 221 1 Hence the statement is true F100 and c9111 amp Pxoofs by Conhadlchon and cbnuapbsmbn 7 p 1433 Homework 5 Due 10132006 12n00n GMCS587 Version Know this by the midterm turn in problems on 10132006 Epp 2nd3rd edition Understand the following theorems with proofs Theorem7351 Theorem7352 Theorem39353 Problems 3513 3517 Next New methods of proof Proof by Contradiction Proof by Contraposition F100 and c9111 amp Pxoofs by cbnuadmubn and cbnuapbsmbn 7 p 1533 C C C ln Direct proof we start with the hypothesis of a statement and make a series of deductions using known theorems definition and some algebraic manipulations until we reach the conclusion Indirect proofs are a little more complicated ln arguments by contradiction we use the fact that a well formed argument is either true or false but not both If you can show that a given assumption is not true leads to a con tradiction impossibility or absurdity then that assumption must be false hence the given statement must be true If N P22 Q227 and Q22 clearly is wrong then P22 Q22 could be something like all integers are negative or all real numbers equal to 4quot F100 and c9111 amp Pxoofs by Conhadlchon and cbnuapbsmbn 7 p 1633 C C ln arguments by contraposition we rely on the fact that a statement is logically equivalent to its contrapositive To prove something by contraposition we write down the contrapos39 itive of the statement prove that this form is true by direct proof Then we can conclude that the original statement is true by the logical equivalence of the two statements Recall Definition u The contrapositive of a conditional statement of the form if p then qquot is If Q then P Symbolically the contrapositive of p H q is q H N 13 Flow and Calm amp Pxoofs by Conbxadxchon and ccnuaposmcn 7 p 1733 Method of Proof by Contradiction 1 Suppose the statement to be proved is false 2 Show that this supposition leads logically to a contradiction 3 Conclude that the statement to be proved is true Keep in mind that supposing that a statement is false is the same thing as supposing that the negation ofthe statement it true Hence step 1 means we must write down the negation of the statement Here we are using quite a few of our tools from chapters 1 2 F100 and Calm amp Pxoofs by Conbxadxchon and Conbxaposxhon 7 p 1333 C Unfortunately there are no clear rules for when a proof by contra diction is better or easier to execute than a direct proof Proofs by contradiction tends to come in handy when you want to show that there is no object with a certain property or if you want to show that a certain object does not have a certain property As you see more proofs throughout you mathematical career you will get a better gut39feeling for when proofs by contradiction are the preferred method The next few examples is a starting point Flow and Calm amp Pxoofs by Conbxadxchon and ccnuaposmcn 7 p 1933 Theorem There is no greatest integer Proof Suppose the statement is false That is suppose there is a greatest integer N Since N is the greatest integer N 2 n Vn E Z Now let M N 1 M being a sum of integers must be an integer Further M gt N since M N 1 Thus M is an integer greater than the greatest integer which is a contradiction The contradiction shows that the supposition is false and therefore the theorem is true D Note After a contradiction has been reached the argument is always the same This is a contradiction Hence the supposition is false and the theorem is true Most mathematical texts end proofs by contradiction once the contradiction has been reached F100 and Calm amp Pxoofs by Conbxadxchon and Conbxaposxhon 7 p 2033 Theorem The sum of any rational number and any irrational number is irrational The theorem talks about the sum of a rational and irrational number not having the property of being rational Suggesting a proof by contradiction Proof Suppose the theorem is false That is suppose there is a rational number r and an irrational number s so that the sum r s is rational By the definition of rational we must have rsic 7d a 74 b7 for some integers a b7 07 cl continued Elm and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 2133 C Proof Suppose the theorem is false That is suppose there is a rational number r and an irrational number s so that the sum r s is rational By the definition of rational we must have 7 a 7 C 7 7 b 7 s 7 d for some integers a b7 07 cl By substitution a 7 C b 3 d Hence a little bit of algebra shows 0 a be 7 ad d b bd Now bciad and bd are both integers and bd 73 0 since both I 73 0 and cl 75 0 Hence 3 is a quotient of two integers By the definition of a rational number s is rational This contradicts the supposition that s is irrational D Flbbx and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 2233 Method of Proof by Contraposition 1 Express the statement to be proved in the form Va 6 D7 if 13057 then 2 Rewrite this statement in the contrapositive form Va 6 D if Qz then N Pz 3 Prove the contrapositive by a direct proof 3 Suppose 2 is a particular but arbitrarily chosen element of D such that Qz is false b Show that Pz is false Elm and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 2333 Theorem Given any integer n if n2 is even then n is even Proof Suppose n is odd and show n2 is odd Since n is odd n 2k 1 by the quotientremainder theorem with d 2 or by the definition of odd Now nn 2k12k1 4k24k1 22k22k1 EH integer Hence n2 2 integer 1 which by the definition of odd shows that n2 is odd D Flbbx and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 2433 Proof by contraposition only works for statements that are universal and conditional Le of the form 5 Va 6 D7 if Pz7 then Qz It turns out that any statement that can be proved by contraposition can also be proved by contradiction but not the other way around The contrapositive of the statement 5 above is C W e D if N om then N Pm Flow and Calm amp Pxoofs by Conbxadxchon and csnuaposmsn 7 p 2533 In a proof by contraposition we 1 Suppose 2 is an arbitrary element of D such that N Qz 2 Execute a sequence of steps to show N Pz We can use the same sequence of steps to show the result by contradiction In a proof by contradiction we 1 Suppose 2 is an arbitrary element of D such that Pz and QM 2 Execute a sequence of steps to show a contradiction N Pz AP2 Floox and Calm amp Pxoofs by Conbxadxchon and Conbxaposxhon 7 p 2633 Theorem Given any integer n if n2 is even then n is even Proof Suppose there exists an integer n such that n2 is even and n is odd Since n is odd n 2k 1 by the quotient39remainder theorem with d 2 or the definition of odd Now nn2k12k14k24k122k22k1 39t Ineger Hence n2 2 integer 1 which by the definition of odd 2 2 shows that n2 is odd Now n is odd and n is even a contradiction D Note The steps of the proof are exactly the same as in the proof by contraposition Flow and Calm amp Pxoofs by Conbxadxchon and csnuaposmsn 7 p 2733 C In a sense we don39t need proofs by contraposition since they can always be converted to proofs by contradiction The advantage of the proof by contraposition is that you know exactly what conclusion you need to show 6 the negation ofthe hypothesis In a proof by contradiction it may be difficult to see where the contradiction will appear Further in a proof by contradiction you have to negate the full statement of the theorem which may be complicated We like contraposition since it seems easier to argue forward toward a known goal However these proofs only work for universal conditional statements Floox and Calm amp Pxoofs by Conbxadxchon and Conbxaposxhon 7 p 2333 Theorem xi is irrational Proof Suppose not proof by contradiction Then there are two integers m and n with no common factors so that vi 7 E n Squaring both sides gives 2 m 2 W 2 is even by or equivalently m2 2112 This shows that m the definition of even We have previously slide 24 shown that this implies that m is even continued Flow and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 2933 Now since m is even we can write m 2k for some integer k Substituting this into m2 2132 gives m2 2k2 4k2 2n Dividing both sides of 462 2112 by 2 gives n2 262 which shows that n2 is even therefore n is even Now both m and n are even hence they have a common factor of 2 This contradicts the supposition that m and n does not have any common factors D Something to think about is g irrational How would you prove it Fibbx and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 3o33 There are infinitely many prime numbers tie there is no largest prime In order the show this we first need to prove the following result Theorem For any integer a and prime number p if pla then 13 a 1 Proof Suppose the statement is false then there is an integer a and a prime number p such that pla and pla 1 By definition we can find integers r and s such that a pr and a 1 133 It follows that 1 a 1 7 a ps 7 pr ps 7 r Since 377quot is an integer it follows that pll but i1 are the only divisors of 1 Since p is a prime we must have p gt 1 a contradiction D Flow and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 3133 Theorem The set of prime numbers is infinite Proof Suppose not suppose the set of prime numbers if finite Then all prime numbers can be listed in ascending order 1912 19237 19357 Pn Now consider the integer NP139P239P3Pn1 Then N gt 1 so by theorem39332 see Epp N is divisible by some prime number p plN Also since p is prime it must equal one of the primes p 1 lt 2 lt n Thus plp1p2pg pn By the previous theorem slide 31 p M101 p2 39pg pn 1 This contradicts plN D Fibbx and Calm amp Pxoofs by cbnuadicubn and cbnuapbsmbn 7 p 3233 Homework 5 Due 10132006 l2noon GMCS587 Final Version Know this by the midterm turn in problems on 10132006 Epp 2nd3rd edition Understand the following theorems with proofs Theorem351 Theorem39352 Theorem39353 Problems Epp3513 Epp 351 7 Epp 3rd edition Epp365 Epp36Ba Epp368b Epp3630 Epp 2nd edition Epp362 Epp366 If you do not have the 3rd edition it is your responsibility to seek out the quotmissingquot questions PhoneaFriend or come to office hours Flow and Calm amp Pxoofs by Conbxadxchon and ccnuaposmcn 7 p 3333

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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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