Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 10 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 10 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
3THEOREM A theorem is a mathematical statement for which there is a proof Hence the theorem becomes valid true universally with no exceptions other than those explicitly indicated in the statement Theorems adopt different structures to be analyzed as this course progresses but the vast majority follows the quotif A then Bquot scheme quotIf A then Bquot means that if condition A holds then condition B is true In other words if we assume A to be true then B occurs Totally equivalent forms for quotIf A then Bquot are A is suf cient for B B is necessary for A A implies B B is implied byA J Viola Prioli Let us consider some examples with the only aim of rewriting each statement in the form quotIf A then Bquot regardless of whether the statement happens to be true or not for the time being 1 The sum of the angles of any triangle is 180 degrees If 0L 3 and y are the angles of a triangle then x 3 y 180 degrees In this case A stands for 0L 3 and y are the angles of a triangle whereas B means on 3 y 180 degrees Hence If a B and y are the angles of a triangle then a 3 y 180 degrees J Viola Prioli 2 No two consecutive integers can be both even Equivalently if a is even a1 is not even Equivalently if a is even then a1 is odd In this case A stands for a is even whereas B means a1 is odd Hence If a is even then a 1 is odd 3 The sum of any three consecutive integers is always divisible by 3 Equivalently if a is any integer then a a1 a2 is divisible by 3 Equivalently if a E Z then a a1 a2 is divisible by 3 Thus if a E Z then 3 a a1 a2 which can be written as If aEZthen 3 3a3 J Viola Prioli CAUTION do not misinterpret a statement ofthe form quotif A then B nothing is said about whether A is true or what to conclude about B when A is false It only claims that if you assume that A is true then B will be true In other words is crucial not to read more than what is being said Mathematicians use a special symbol to denote quotif A then B is the symbol of direct implication a special arrow A gtB Therefore A gtB can be read indistinctly as quotA implies Bquot or as quotif A then B The symbol is suggestive of a one way road and in fact our remarks above indicate that this is the direction our reasoning should move start at A and arrive at B As to terminology when A gtB is to be considered A is called the hypothesis and B is called the conclusion Notice that 2 10 is true but 102 is false Therefore A gtB should never be confused with B gtA J V I P r We will introduce next the so called quottruth tables which give the fundamental logical support to our arguments We have pointed out that ifA is true then B follows In other words ifA is true it can not be that B is false Hence T implies T is true but T implies F is impossible What may surprise you is that from false we can logically arrive to both true and false Therefore we have the following table 39l39I I I39l I gt I in ill W 39I39I39I39I l l J Viola Prioli When A gtB and B gt A both hold we write A ltgt B two way road now and we say quotA if and only if B This amounts to saying that A and B are equivalent statements that is if one of them is true the other must be true and similarly if one is false so is the other one We have thus the following truth table for our double implication T T T T F F F T F F F T J Viola Prioli Some statements are connected with the word quotandquot like in quotif a is composite and a 3 is primequot a situation that is governed by a truth table also As common sense indicates the only possible way for such quotA and Bquot to be true is that both be true We can present the corresponding table T T T T F F F T F F F F J Viola Prioli Our fourth table emerges when considering the statements that happen to be connected with quotorquot like in quotif n gt 2 then n is prime or n is composite In Mathematics the quotorquot is inclusive as opposed to street talking in which the quotorquot is not inclusive So for quotA or Bquot to occur is enough that one of them be true ts table is next T T T T F T F T T F F F J Viola Prioli As an illustration consider a simple statement like if a is even or divisible by 5 In this case 6 meets the rst requirement 15 meets the second one and 10 meets both Each ofthese three numbers satis es if a is even or divisible by 5 Finally in many instances we will need to negate a sentence In that case what is true turns into false and conversely The negation table is simply this J Viola Prioli In some occasions particularly when dealing with sets we may encounter a statement whose hypothesis never holds For instance how would we treat a non sensical statement like if a fruit talks then it is red It is of the form quotifA then Bquot but clearly A never holds In Mathematics statements like this one are given the T value they are considered to be true If you think for a second and believe that they are false then I will ask you to show me a fruit that talks but is not red The situation is called quotvacuous truth In some cases theorems are preceded by a Lemma which is a result needed in the proof of the theorem and followed by a Corollary which is a result that either needs no proof or requires a very short and simple argument in the presence ofthe theorem already proved Construct the truth table of A gt B or C Remark it will have eight rows not four See the link More Illustrations on Section 3 Syllabus J Viola Prioli
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'