• Document: Lecture Notes in Discrete Mathematics. Marcel B. Finan Arkansas Tech University c All Rights Reserved
  • Size: 1.03 MB
  • Uploaded: 2019-01-12 18:43:54
  • Status: Successfully converted


Some snippets from your converted document:

Lecture Notes in Discrete Mathematics Marcel B. Finan Arkansas Tech University All c Rights Reserved 2 Preface This book is designed for a one semester course in discrete mathematics for sophomore or junior level students. The text covers the mathematical concepts that students will encounter in many disciplines such as computer science, engineering, Business, and the sciences. Besides reading the book, students are strongly encouraged to do all the exer- cises. Mathematics is a discipline in which working the problems is essential to the understanding of the material contained in this book. Students are strongly encouraged to keep up with the exercises and the sequel of concepts as they are going along, for mathematics builds on itself. Instructors can request the solutions to the problems via email: mfinan@atu.edu Finally, I would like to take the opportunity to thank Professor Vadim Pono- marenko from San Diego State University for pointing out to me many errors in the book and for his valuable suggestions. Marcel B. Finan May 2001 3 4 PREFACE Contents Preface 3 Fundamentals of Mathematical Logic 7 1 Propositions and Related Concepts . . . . . . . . . . . . . . . . . 8 2 Conditional and Biconditional Propositions . . . . . . . . . . . . 18 3 Rules of Inferential Logic . . . . . . . . . . . . . . . . . . . . . . . 24 4 Propositions and Quantifiers . . . . . . . . . . . . . . . . . . . . . 33 5 Arguments with Quantified Premises . . . . . . . . . . . . . . . . 41 6 Project I: Digital Logic Design . . . . . . . . . . . . . . . . . . . 45 7 Project II: Number Systems . . . . . . . . . . . . . . . . . . . . . 50 Fundamentals of Mathematical Proofs 53 8 Methods of Direct Proof I . . . . . . . . . . . . . . . . . . . . . . 53 9 More Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . 59 10 Methods of Indirect Proofs: Contradiction and Contraposition . 64 11 Method of Proof by Induction . . . . . . . . . . . . . . . . . . . 67 12 Project III: Elementary Number Theory and Mathematical Proofs 75 13 Project IV: The Euclidean Algorithm . . . . . . . . . . . . . . . 77 14 Project V: Induction and the Algebra of Matrices . . . . . . . . 79 Fundamentals of Set Theory 83 15 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 16 Properties of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 92 17 Project VI: Boolean Algebra . . . . . . . . . . . . . . . . . . . . 100 Relations and Functions 101 18 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . 101 19 Partial Order Relations . . . . . . . . . . . . . . . . . . . . . . . 113 5 6 CONTENTS 20 Functions: Definitions and Examples . . . . . . . . . . . . . . . 119 21 Bijective and Inverse Functions . . . . . . . . . . . . . . . . . . . 127 22 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 23 Project VII: Applications to Relations . . . . . . . . . . . . . . . 149 24 Project VIII: Well-Ordered Sets and Lattices . . . . . . . . . . . 152 25 Project IX: The Pigeonhole Principle . . . . . . . . . . . . . . . 153 26 Project X: Countable Sets . . . . . . . . . . . . . . . . . . . . . 154 27 Project XI: Finite-State Automaton . . . . . . . . . . . . . . . . 156 Introduction to the Analysis of Algorithms 159 28 Time Complexity and O-Notation . . . . . . . . . . . . . . . . . 159 29 Logarithmic and Exponential Complexities . . . . . . . . . . . . 167 30 Θ- and Ω-Notations . . . . . . . . . . . . . . . . . . . . . . . . . 171 Fundamentals of Counting and Probability Theory 175 31 Elements of Counting . . . . . . . . . . . . . . . . . . . . . . . . 175 32 Basic Probability Terms and Rules . . . . . . . . . . . . . . . .

Recently converted files (publicly available):