Lecture notes Discrete Mathematics

lecture notes discrete mathematics and its applications. what mathematics are used in engineering. what mathematics is needed for computer science pdf free download
Dr.HaroldNolon Profile Pic
Dr.HaroldNolon,United States,Professional
Published Date:15-07-2017
Your Website URL(Optional)
Comment
0N1 (MATH19861) Mathematics for Foundation Year Lecture Notes 23 Jan 2017 Short URL bit.ly/2d9dG6Z In Arial font: bit.ly/2ctSx6u Twitter math198610N1 Mathematics Course Arrangements 23 Jan 2017 2 Contents Arrangements for the Course 7 Aims and description . . . . . . . . . . . . . . 7 Tests . . . . . . . . . . . . . . . . . . . . . . . 9 Examination . . . . . . . . . . . . . . . . . . . 11 Questions for students, email policy . . . . . . 12 Acknowledgements 13 I Lecture Notes 14 1 Sets 14 1.1 Sets: Basic de nitions . . . . . . . . . . . . . 14 1.2 Questions from students . . . . . . . . . . . . 17 2 Subsets; Finite and In nite Sets 18 2.1 Subsets . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Finite and in nite sets . . . . . . . . . . . . . 21 2.3 Questions from students . . . . . . . . . . . . 22 3 Operations on Sets 23 3.1 Intersection . . . . . . . . . . . . . . . . . . . 23 3.2 Union . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Universal set and complement . . . . . . . . . 24 3.4 Relative complement . . . . . . . . . . . . . . 26 3.5 Symmetric di erence . . . . . . . . . . . . . . 26 3.6 Boolean Algebra . . . . . . . . . . . . . . . . 26 3.7 Sample Test Questions . . . . . . . . . . . . . 28 3.8 Questions from Students . . . . . . . . . . . . 28 4 Set theory 330N1 Mathematics Course Arrangements 23 Jan 2017 3 4.1 Proof of Laws of Boolean Algebra by Venn di- agrams . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Proving inclusions of sets . . . . . . . . . . . . 34 4.3 Proving equalities of sets . . . . . . . . . . . . 35 4.4 Proving equalities of sets by Boolean Algebra 36 4.5 Sample test questions . . . . . . . . . . . . . . 37 4.6 Additional Problems: Some problems solved with the help of Venn diagrams . . . . . . . . . . . . . . . . . . . . . 38 4.7 Questions from students . . . . . . . . . . . . 42 5 Propositional Logic 43 5.1 Statements . . . . . . . . . . . . . . . . . . . . 43 5.2 Conjunction . . . . . . . . . . . . . . . . . . . 43 5.3 Disjunction . . . . . . . . . . . . . . . . . . . 44 5.4 Negation . . . . . . . . . . . . . . . . . . . . . 45 5.5 Conditional . . . . . . . . . . . . . . . . . . . 45 5.6 Questions from students . . . . . . . . . . . . 47 6 Propositional Logic, Continued 50 6.1 Converse . . . . . . . . . . . . . . . . . . . . . 50 6.2 Biconditional . . . . . . . . . . . . . . . . . . 50 6.3 XOR . . . . . . . . . . . . . . . . . . . . . . . 51 6.4 Compound statements and truth tables . . . . 51 6.5 Tautologies . . . . . . . . . . . . . . . . . . . 53 6.6 Contradictions . . . . . . . . . . . . . . . . . . 54 6.7 Sample test questions . . . . . . . . . . . . . . 54 6.8 Questions from students . . . . . . . . . . . . 55 7 Logically equivalent statements 56 7.1 Exercises . . . . . . . . . . . . . . . . . . . . . 59 7.2 Sample test question . . . . . . . . . . . . . . 590N1 Mathematics Course Arrangements 23 Jan 2017 7 Arrangements for the Course Aims and description Aims of 0N1  A basic course in pure mathematical topics for members of the foundation year.  Key ingredient: language of Mathematics, including spe- ci c use of English in Mathematics. Brief description 13 lectures: Sets. De nition, subsets, simple examples, union, intersection and complement. De Morgan's Laws. Ele- mentary Logic; universal and existential quali ers. Proof by contradiction and by induction. 9 lectures: Methods of proof for inequalities. Solution of inequalities containing unknown variables. Linear in- equalities with one or two variables, systems of liner inequalities with two variables. Some simple problems of linear optimisation. Quadratic inequalities with one variable. 2 review lectures at the end of the course, Week 12. A brief very pragmatic description The course contains all mathematics necessary for writing standard commercial time-dependent spread- sheets using theExcel (or a similar software pack- age) macro language. Textbooks:  S Lipschutz, Set Theory and Related Topics. McGraw- Hill.0N1 Mathematics Course Arrangements 23 Jan 2017 8  J Franklin and A Daoud, Proof in Mathematics: An In- troduction. Kew Books (Jan 2011).  R Steege and K Bailey, Intermediate Algebra. (Schaum's Outlines.) McGraw-Hill.  R. Hammack, Book of Proof,http://www.people.vcu. edu/ rhammack/BookOfProof/index.html Detailed lecture notes will be provided as course progresses. Course Webpage: http://www.maths.manchester.ac.uk/ avb/math19861.html Short URL bit.ly/2cgtpRx Twitter math19861  Arrangements As of 201617 academic year Two lectures a week in weeks 112: Monday 12:00, Renold/C16 Friday 14:00, Renold/C16 Learn to take lecture notes One tutorial (in small groups) in weeks 212, Tuesday 13:00.  Exercise sheets are posted on the Web/Blackboard a week before tutorial.  Work on your own, in the tutorial discuss your solutions with an Instructor.  Solutions to exercises are distributed after the tu- torial. Hours of private study: 68.0N1 Mathematics Course Arrangements 23 Jan 2017 9 Tests 7-minute multiple choice tests: 10 minutes at the end of each of 10 tutorials are reserved for the test (but experi- ence shows that clearing the desks from books, etc, and then collection of scripts takes some time, so the actual test time is 7 minutes).  Two questions, each costing 2%, so that all together they make  Missed test = 0%  The sum of 10 best test marks makes up to 10 2 2% = 40% of the total mark for course:  One problem is on material from the previous week, another from all previous weeks at random.  Please notice that one of the tests will be on the last  week of classes, Tuesday 13 December. The date is for 201617 academic year  You have been warned: if you decide to go home early, you loose, with every missed test, 4% of your mark for the course. Test Resits: No Resits or Reworks  All medical notes, honourable excuses, etc.: submit to Foundation Year Oce. Their decision is nal.  The Lecturer will not look into any detail.  If Foundation Studies Oce decides that you have a valid reason to miss a test, the total for tests will be adjusted in proportion to your marks for those tests that you sat. Rules for Tutorial Tests 1. Students will be admitted to the test only after showing an ocial University ID card. No ID) No Test.0N1 Mathematics Course Arrangements 23 Jan 2017 10 2. During the test, the ID card has to be positioned at the corner of the student's desk and ready for inspection. 3. After the test has started, the examiner checks the IDs. 4. Students who have been late to class are not allowed to take test. 5. Students are not allowed to leave the room until the end of the test. Examiners will not collect their scripts until the test is over. 6. No books or any papers other than test paper are al- lowed to be kept on the table. 7. Examiners should remove any remaining formulae from the blackboard/whiteboard. 8. If a student breaches any of this rules, or behaves noisy, etc., Examiners are instructed: 8.1 con scate the o ender's test script; 8.2 write across the script: report to the Lecturer; 8.3 make note of the o ender's name and ask him/her to leave the room, quietly; 8.4 after the test, immediately report the incident to the Lecturer. The Lecturer will take care of further necessary actions.  Detailedminute-by-minuteinstructionsfortests: Times are for 2016/17 academic year 1. At 13:40 the tutor makes a loud announcements in class: \Time is 13:40. Clear your desks for test." 2. At 13:41 0r at 13:42, if clearing desks, etc, took too much time the tutor makes another announcement: \Time is 13:41 or 13:42. Start writing" 3. At 13:47 or 13:48 the tutor announces:0N1 Mathematics Course Arrangements 23 Jan 2017 11 \one minute to the end of test" 4. At 13:48 or 13:49 the tutor announces: \Stop writing and pass your test papers to me." 5. By 13:50 all test papers have to be collected. Examinatios 2 hour examination (January):  Weighting within course 60%.  Ten problems, you choose and solve six of them. Each problem costs 10%; notice 6 10% = 60%.  Unlike tests, examination problems are not multiple choice.  You will have to give not only an answer, but justify it by a detailed calculation and/or a complete proof.  Past exam papers are available at the course webpage: bit.ly/2cgtpRx or http://www.maths.manchester.ac.uk/ avb/math19861.html. E-mail policy:  Questions are welcome, e-mail them to borovikat manchester.ac.uk  When relevant, the Lecturer will send a response (with- out naming the author of the original question) to all the class.0N1 Mathematics Course Arrangements 23 Jan 2017 12  Ensure that the subject line of your message is meaning- ful. Always include the name of the course e.g. \0N1 Tutorial". Otherwise your message will be deleted as spam.  Use your university e-mail account. The lecturer will delete, without reading, e-mails from outside of the Uni- versity. Questions for students, email policy Questions from students These lecture notes include some questions asked by students in the course. These parts of notes contain no compulsory material but still may be useful. Notation and Terminology: Some textbooks use notation and terminology slightly di erent from that used in the lectures. These   notes make use of marginal comments like this marginal = written on the margin, the empty space at the side of a one to give other words which are frequently used pagelike this one. in English mathematical literature in the same sense as the marked word. Outside of mathemat- margin = edge, border ics, the usage of such words could be di erent. comment = remark, commentary, Also, the choice of words very much depends on note the sentence in which they are used.0N1 Mathematics Course Arrangements 23 Jan 2017 13 Acknowledgements Special thanks go to Dave Rudling for his comments on math- ematical notation and to Alexander Watson for help with A LT X. E0N1 Mathematics Lecture 1 Sets 23 Jan 2017 14 Lecture Notes Part I Lecture Notes 1 Sets 1.1 Sets: Basic de nitions A set is any collection of objects, for example, set of numbers. The objects of a set are called the elements of the set. A set may be speci ed by listing its elements. For exam- ple,f1; 3; 6g denotes the set with elements 1, 3 and 6. This  is called the list form for the set. Note the curly brackets. Typographical terms: f opening curly bracket  We usually use capital letters A, B, C, etc., to denote g closing curly bracket sets. capital letter =  The notation x2 A means \x is an element of A". But upper case letter x62A means \x is not an element of A". Alternatively we may say \x belongs to A" or \A contains x". Example. 12f1; 3; 6g; 32f1; 3; 6g; 62f1; 3; 6g but 262f1; 3; 6g:  A set can also be speci ed in predicate form , that is or descriptive form by giving a distinguished property of the elements of the set  (or an explicit description of the elements in the set). For explicit = speci c, de nite example, we can de ne set B by B =fx : x is a possitive integer less than 5g: The way to read this notation is15 \B is the set of all x such that x is a positive integer less than 5".  The curly brackets indicate a set and the colon Typographical terms: : colon 0 0 : is used to denote \such that", and, not surprisingly, is read 1 \such that".  Two sets are equal if they have exactly the same ele- We also say: two sets coincide. ments. Thus f1; 2; 3; 4g =fx : x is a possitive integer less than 5g: In list form the same set is denoted whatever order the el- ements are listed and however many times each element is listed. Thus f2; 3; 5g =f5; 2; 3g =f5; 2; 3; 2; 2; 3g: Note thatf5; 2; 3; 2; 2; 3g is a set with only 3 elements: 2, 3 and 5. Example. fx : x is a letter in the word GOODg =fD;G;Og: 1 I have received this delightful email from David Rudling: I have been working through your lecture notes at home now that I am retired and trying to catch up on not going to university when younger. I have noticed that when introducing : as the symbol for \such that" in set theory you have not added an asterisk commentary note mentioning the American usage of the vertical barj as an alternative which your students will undoubtedly encounter. Might I have the temerity to suggest that an asterisk com- ment on this would be helpful? Indeed, in some books you can nd this notation for sets: B =fxjx is a possitive integer less than 5g:16 The setf2g is regarded as being di erent from the number 2. A set of numbers is not a number.f2g is a set with only one element which happens to be the number 2. But a set is not the same as the object it contains: f2g =6 2. The statement 22f2g is correct. The statementf2g2f2g is wrong. The set 2 fx : x is an integer such that x =1g  has no elements. This is called an empty set . It was said Some books call it null set. earlier that two sets are equal if they have the same elements. Thus ifA andB are empty sets we haveA =B. Mathemati- cians have found that this is the correct viewpoint, and this  makes our rst theorem. The word theorem means a statement that has been proved and therefore be- came part of mathematics. We shall Theorem. If A and B are empty sets then A =B. also use words proposition and lemma:  they are like theorem, but a proposition Proof. The setsA andB are equal because they cannot be is usually a theorem of less importance, non-equal. Indeed, for A and B not to be equal we need an while lemma has no value on its own and element in one of them, say a2 A, that does not belong to is used as a step in a proof of a theorem. B. But A contains no elements Similarly, we cannot nd The word proof indicates that an ar- an element b2 B that does not belong to A because B gument establishing a theorem or other contains no elements at all.  statement will follow.   Corollary. There is only one empty set, THE empty set. Corollary is something that easily fol- lows from a theorem or a proposition. The empty set is usually denoted by;. Notice the use of de nite article THE. Thus 2 fx : x is an integer such that x =1g =;: Consider the sets A and B where A =f2; 4g and B = f1; 2; 3; 4; 5g. Every element of the setA is an element of the set B. We say that A is a subset of B and write A B, or  BA. We can also say that B contains A. Also: A is contained in B, A is included in B. The expression B Notice that the word \contains" is used in set theory in A is read \B is a superset of A", or B two meanings, it can be applied to elements and to subsets: contains A. the setfa;b;cg contains an element a and a subsetfag. Sym- bols used are di erent: a2fa;b;cg; fagfa;b;cg; and a =6 fag:17 1.2 Questions from students  This section contains no compulsory material but still may be useful. 1. My question is: Are all empty sets equal? No matter the condi- tions. For example is fx :x is positive integer less than zerog equal to fx :x is an integer between 9 and 10g Answer. Yes, all empty sets are equal. To see that in your example, let us denote A =fx :x is positive integer less than zerog and B =fx :x is an integer between 9 and 10g So, I claim that A =B. If you do not agree with me, you have to show that A is di erent from B. To do so, you have to show me an element in one set that does not belong to another set. Can you do that? Can you point to an o ending element if both sets have no elements whatsoever? Indeed, can you point to a \positive integer less than zero" which is not an \integer between 9 and 10"? Of course, you cannot, because there are no positive integers less than zero. Can you point to an \integer between 9 and 10" which is not a \positive integer less than zero"? Of course, you cannot, because there are no integers between 9 and 10. Hence you cannot prove that A is not equal to B. Therefore you have to agree with me that A =B.0N1 Mathematics Lecture 2 Subsets 23 Jan 2017 18 2 Subsets; Finite and In nite Sets 2.1 Subsets '  A B  & % Figure 1: A diagram ofAB (which is the same asBA). Figure 1 is a simple example of a Venn diagram for show- ing relationships between sets. Figure 2 is an example of a Venn diagram for three sets G, L, C of uppercase letters of the Greek, Latin and Cyrillic alphabets, respectively. Figure 2: Venn diagram showing which uppercase letters are shared by the Greek, Latin and Cyrillic alphabets (setsG,L, C, respectively). Some basic facts:0N1 Mathematics Lecture 2 Subsets 23 Jan 2017 19  AA for every set A. Every set is a subset of itself.  The empty set is a subset of every set: ; A for any set A.   If AB and BC then AC. We say that is a transitive relation between sets. Notice that the relation2  If AB and BA then A =B. \being an element of" is not transitive. relation = connection, bond Example. Let A =f 1; 2g. Denote by B the set of subsets of A. Then B =f;;f1g;f2g;f1; 2gg: Notice that 12f1g and 12A, but it is not true that 12B. On the other hand,f1g2B, but it is not true thatf1g2 A. Example. The subsets off1; 2; 3g are ;;f1g;f2g;f3g;f1; 2g;f1; 3g;f2; 3g;f1; 2; 3g: Note: don't forget the empty set; and the whole setf1; 2; 3g. Thusf1; 2; 3g has 8 subsets. n Theorem. If A is a set with n elements then A has 2 subsets. Here, n 2 = 2 2 2 with n factors. Proof. Let A =fa ;a ;:::;ag. How many are there ways 1 2 n to choose a subset in A? When choosing a subset, we have to decide, for each element, whether we include this elements into our subset or not. We have two choices for the rst element: `include' and `do not include', two choices for the th second element, etc., and nally two choices for the n ele- ment: 2 2 2 choices overall.  Another proof. When revising for the examination, prove this Theorem using the method of mathematical induction from the last lectures. 0N1 Mathematics Lecture 2 Subsets 23 Jan 2017 20 Example. In some books, the set of subsets of a set A is denotedP(A). Stating with the empty set;, let us take sets of subsets: P(;) = f;g P(P(;)) =P(f;g) = f;;f;gg P(P(P(;))) =P(f;;f;gg) = f;;f;g;ff;gg;f;;f;ggg . . . which have, correspondingly, 0 1 2 4 2 = 1; 2 = 2; 2 = 4; 2 = 16; :::; elements. In particular, the four sets ;;f;g;ff;gg;f;;f;gg (the subsets off;;f;gg) are all di erent If AB and A6=B we call A a proper subset of B and  write AB to denote this. If AB, we also write BA. Similarly, AB is the same as BA Example. Let A =f1; 3g, B =f3; 1g, C =f1; 3; 4g. Then A =B true AB false CA false AB true AC true CC false BA true AC true Compare with inequalities for numbers: 26 2 true, 16 2 true, 2 2 false, 1 2 true. n A set with n elements contains 2 1 proper subsets.0N1 Mathematics Lecture 2 Subsets 23 Jan 2017 21 2.2 Finite and in nite sets A nite set is a set containing only nite number of elements. For example,f1; 2; 3g is nite. IfA is a nite set, we denote by jAj the number of elements inA. For example,jf1; 2; 3gj = 3 andj;j = 0. A set with in nitely many elements is called an in nite set. The set of all positive integers (also called natural numbers) N =f1; 2; 3;:::;g is in nite; the dots indicate that the sequence 1; 2; 3 is to be  continued inde nitely. inde nitely = for ever, without end  The set of all non-negative integers is also in nite: There is no universal agreement about whether to include zero in the set of natural numbers: some de ne the nat- N =f0; 1; 2; 3;:::;g: 0 ural numbers to be the positive inte- gers f1; 2; 3;:::g, while for others the More examples of in nite sets: term designates the non-negative in- tegers f0; 1; 2; 3;:::g. In this lecture Z = f:::;2;1; 0; 1; 2;:::g (the set of integers) course, we shall stick to the rst one (and more traditional) convention: 0 is f:::;4;2; 0; 2; 4;:::g (the set of all even integers) not a natural number. f:::;3;1; 1; 3;:::g (the set of all odd integers) Q denotes the set of all rational numbers (that is, the num- bers of the form n=m where n and m are integers and m =6 0), p R the set of all real numbers (in particular, 2 2 R and 2R), C the set of all complex numbers (that is, numbers of the form x +yi, where x and y are real and i is a square  2 root of1, i =1). The letters ABCDEFGHIJKLMOPRSTUVWXYZ are called blackboard bold and were They are all in nite sets. We have the following inclusions: invented by mathematicians for writing on a blackboard instead of bold letters NN ZQRC: 0 ABC::: which are dicult to write with chalk.0N1 Mathematics Lecture 2 Subsets 23 Jan 2017 22 2.3 Questions from students This section contains no compulsory ma- terial but still may be useful. 1. When considering sets 1, 1, 1, 1, ... is it true that 1 is an element of 1, but not of 1? Answer. Yes, it is true. 2. (c) Let U = u, v,w, x, y, z. (i) Find the number of subsets of U. (ii) Find the number of proper non-empty subsets of U. i think the answer of question (ii) should be 63, not 62 which is given by exam sample solution. how do u think about it 6 Answer. The answer is 62: there are 2 = 64 subsets in U alto- gether. We exclude two: U itself (because is is not proper) and the empty set (because it is not non-empty. 3. My question relates to one of the mock exam questions, worded slightly differently. Question: List the 8 subsets of a,b,c,d containing d? Answer. A very good questionhow to list in a systematic way all subsets of a given set? I emphasise the word systematic, this means that if you do the same problem a week later, you get exactly the same order of subsets in the list. There are several possible approaches, one of them is to use the principle of ordering words in a dictionary; I will illustrate it on the problem list all subsets in the setfa;b;cg. In my answer to that problem, you will perhaps immediately recognise the alphabetic order:  fg ;fag,fa;bg,fa;cg,fa;b;cg;fbg,fb;cg;fcg. fg is the empty set; Returning to the original question, List the 8 subsets offa;b;c;dg containingfdg, we have to add the element d to each of the sets: fdg;fa;dg,fa;b;dg,fa;c;dg,fa;b;c;dg;fb;dg,fb;c;dg; fc;dg.0N1 Mathematics Lecture 3 Operations on Sets 23 Jan 2017 23 3 Operations on Sets A A\B AB B Figure 3: Sets A and B and their intersection A\B and union AB. 3.1 Intersection SupposeA andB are sets. ThenA\B denotes the set of all elements which belong to both A and B: A\B =fx : x2A and x2Bg:  A\B is called the intersection of A and B. The typographic symbol\ is some- times called \cap". Notice that the name of a typographical symbol for an Example. Let A =f1; 3; 5; 6; 7g and B =f3; 4; 5; 8g, then operation is not necessary the same as the name of operation. For example, A\B =f3; 5g. symbol plus is used to denote addition of numbers, like 2 + 3. 3.2 Union AB denotes the set of all elements which belong toA or to B: AB =fx : x2A or x2Bg:  AB is called the union of A and B. The typographic symbol is some- times called \cup". Notice that, in mathematics, or is usually understood in the inclusive sense: elements from AB belong to A or to

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.