Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Department of Mathematical Sciences Introduction to Discrete Mathematics Only s

Department of Mathematical Sciences Introduction to Discrete Mathematics Only study guide for MAT2612 Prof C M Mynhardt Revised by Dr J E Singleton University of South Africa Open Rubric ii iii MAT2612/1 Contents Page Introduction 1 1 Fundamentals 5 2 Logic 6 2.1 Propositions and logical operations 6 2.2 Conditional statements 6 2.3 Methods of proof 6 2.4 Mathematical induction 6 Summary 15 3 Counting 16 3.0 Counting the elements of a list 16 3.1 Permutations 19 Possiblity trees and the product rule 19 The product rule 20 Permutations 24 Counting elements of disjoint sets: the addition rule 26 The diﬀerence rule 28 3.2 Combinations 29 Some advice about counting 35 3.3 Pigeonhole principle 36 Application to decimal expansions of fractions 38 Extended pigeonhole principle 39 3.4 Elements of probability 41 Summary 44 Deﬁnitions 44 Theorems 45 iv 4 Relations and Digraphs 47 4.1 Product sets and partitions 47 Product sets 47 Partitions 48 4.2 Relations and digraphs 48 Relations 48 Sets arising from relations 49 The matrix of a relation 50 Digraphs 50 4.3 Paths in Relations and digraphs 51 4.4 Properties of relations 51 Reﬂexive, symmetric and transitive relations 51 Irreﬂexive, asymmetric and antisymmetric relations 53 Questions 54 4.5 Equivalence relations 55 Congruence modulo n 55 Fractions 58 Equivalence relations and partitions 59 4.6 Data structures for (Computer representation of) relations and digraphs 61 4.7 Operations on relations 61 Closures 62 Composition 62 4.8 Transitive closure and Warshall’s algorithm 63 Transitive closure 63 Warshall’s algorithm 64 Summary 64 Deﬁnitions 65 Theorems 68 5 Functions 70 5.1 Functions 70 Special types of functions 70 Invertible functions 76 The pigeonhole principle 77 5.2 Functions for computer science 78 5.3 Growth of functions 79 5.4 Permutation functions 79 Even and odd permutations 82 Summary 83 Deﬁnitions 83 Theorems 85 v MAT2612/1 6 Order Relations and Structures 87 6.1 Partially ordered sets 87 Hasse diagrams 88 Isomorphism 89 6.2 Extremal elements of partially ordered sets 90 6.3 Lattices 91 Isomorphic lattices 93 Special types of lattices 93 6.4 Finite Boolean algebras 94 6.5 Functions on Boolean algebras 95 6.6 Circuit Design 96 Summary 96 Deﬁnitions 96 Theorems 99 1 MAT2612/1 Introduction Discrete Mathematics may loosely be described as dealing with objects most easily deﬁned in terms of the set of natural numbers. Properties such as nearness, smoothness and continuity −the key ideas of calculus −are not at issue. Traditional school mathematics aims to teach mainly arithmetic skills which form the basis of algebra, which itself is the cornerstone of trigonometry, analytic geometry and calculus. South Africa was built with these tools, applied by generations of engineers and scientists to the physical environment in which we live. But today’s growth industries are dominated by information, which is abstract and immaterial. Whereas the material world is modelled by calculus (the language of continuous change), the immaterial world of information requires discontinuous, discrete mathematics. Both genetic codes and computer codes are intrinsically discrete. Discrete mathematics basically deals with ways of arranging and counting. It can be used to enumerate ge- netic patterns and to count the branches in computer algorithms; it can be used to analyse the treelike branching of arteries and nerves, as well as the cascading options in a succession of either-or decisions. It can tell us how many things there are as well as help us ﬁnd what we want among a bewildering morass of possibilities. Combinatorial reasoning underlies all analysis of computer systems. Two of the most basic mathematical aspects of computer science concern the speed and logical structure of a computer programme. Speed involves enumeration of the number of times each step in a programme is performed. Logical structure involves ﬂow charts, a type of diagram. Analysis of the speed and logical structure of operations research algorithms to optimise eﬃcient manufacturing entails similar combinatorial mathematics. Determining the probability that one of a certain subset of equally likely outcomes occurs, requires counting the size of the subset. This type of combinatorial probability is the basis of many nonparametric statistical tests. Combinatorics is often called the art of counting without counting, because we try, as far as possible, to count the objects in some set without actually listing all the objects being counted. This explains why at its heart, combinatorial reasoning involves the idea of one to one correspondence. Prescribed Book The prescribed book for MAT2612 is B. Kolman, R.C. Busby and S. Ross, Discrete Mathematical Structures Pearson Prentice-Hall 5th ed (2004) or 6th ed (2009). This study guide is based on the 5th and 6th editions of the prescribed book and the aim of it is to supplement the book. It should therefore be read in conjunction with the book, which we shall usually refer to as “KBR”. Although KBR contains all the study material for this module, the study guide contains additional information, such as additional examples and further explanations. We begin by giving an outline of the chapters and sections of KBR which form the study material for the module MAT2612. Then we give a more detailed description of the type of study required for each section, e.g., whether the section is for reading purposes only or whether more intensive study is required. 2 Outline of Study Material in KBR Chapter 1: Fundamentals 1.1 Sets and Subsets 1.2 Operations on Sets 1.3 Sequences 1.4 Properties of integers/Division in the Integers 1.5 Matrices 1.6 Mathematical Structures Chapter 2: Logic 2.1 Propositions and Logical Operations 2.2 Conditional Statements 2.3 Methods of Proof 2.4 Mathematical Induction Chapter 3: Counting 3.1 Permutations 3.2 Combinations 3.3 Pigeonhole Principle 3.4 Elements of Probability Chapter 4: Relations and Digraphs 4.1 Product sets and Partitions 4.2 Relations and Digraphs 4.3 Paths in Relations and Digraphs 4.4 Properties of Relations 4.5 Equivalence Relations 4.7 Operations on Relations 4.8 Transitive Closure and Warshall’s Algorithm Chapter 5: Functions 5.1 Functions 5.2 Functions for Computer Science 5.3 Growth of Functions 5.4 Permutation Functions Chapter 6: Order Relations and Structures 6.1 Partially Ordered Sets 6.2 Extremal Elements of Partially Ordered Sets 6.3 Lattices 6.4 Finite Boolean Algebras 6.5 Functions on Boolean Algebras 6.6 Circuit Design 3 MAT2612/1 Type of Study Required Here we tell you whether each section is for reading purposes, for study purposes but not exam purposes or for study and exam purposes. If a section is designated reading material, it means that we think that you should know the work already, and so only need to read through the material to refresh your memory. However, if you don’t know the work, you will have to learn it as it will be used throughout the rest of the chapters. If a section is designated study material not for exam purposes, it means that you are required to know the material but that no questions directly related to this section will be asked in the exam. It may well be, however, that you will need results from this section to answer questions on other parts of the work. Sections such as these are often covered more extensively in other modules which are not necessarily prerequisites for MAT2612. If a section is designated study material for exam purposes, then obviously you can expect a question on this section in the exam. Most of the study material falls in this category. The proofs of theorems in these sections which are excluded for exam purposes, are nevertheless study material; you may need the techniques which are discussed in such proofs to do the problems in the problem sections. Chapter 1 All sections are for reading purposes, except Section 1.5 on matrices, which is study material not for exam purposes. Chapter 2 Sections 2.1–2.3 are for study but not for exam purposes, while Section 2.4 on mathematical induction is for exam purposes. Sections 2.5 and 2.6 in the 6th edition are for reading purposes only. Chapter 3 Section 3.1: Exam purposes, except for the proofs of Theorems 1 and 2. Pay special attention to the formula for nPr. Section 3.2: Exam purposes. Pay special attention to the formula for nCr, which is also denoted by (n r ) (read “n choose r”) or by C(n,r). Section 3.3: Exam purposes, apart from the proofs of Theorems 1 and 2. Section 3.4: Exam purposes. Section 3.5: Not part of the study material. (See MAT3707.) Chapter 4 Section 4.1: Exam purposes, including the proof of Theorem 1. Section 4.2: Exam purposes, excluding the proofs of Theorems 1 and 2. Section 4.3: Exam purposes, excluding the proofs of Theorems 1 and 2. 4 Section 4.4: Exam purposes. Given a relation, you must be able to determine whether or not it is reﬂexive, symmetric, asymmetric, antisymmetric or transitive, and to sketch its digraph. Section 4.5: Exam purposes, including the proofs of Lemma 1 and Theorems 1 and 2. Section 4.6: Not part of the study material. Section 4.7: Exam purposes, excluding the proofs of Theorems 6 and 7, but including the proofs of Theorems 1–5 and 8. Section 4.8: Exam purposes, excluding the proofs of the theorems. The most important uploads/Finance/ mat2612-study-guide.pdf