Discrete Mathematics: An Open Introduction
Subject: Mathematics and Discrete Structures
Author or source: Oscar Levin
Updated:
Oscar Levin’s complete third-edition textbook on counting, sequences, logic, proofs and graph theory, with exercises, hints and selected solutions.
Overview of the complete resource
Source page 1–414
This is the complete third edition of Oscar Levin’s textbook, including its front matter, exercises and back matter, across 414 PDF pages. Topics progress from mathematical statements, sets and functions to counting, sequences, logic, proofs and graph theory, with further work on number theory and generating functions. Investigate activities encourage students to explain why a result holds before applying a formula. The hints and selected solutions support independent checking, but should follow an honest attempt at an exercise. The third edition is retained under its own CC BY-SA licence; it is not represented as the newer fourth edition. The accompanying course videos are linked by the author. The MIT examination is a real related-subject paper from another institution, not an exam for this book or a Mumbai University paper.
Original textbook: introduction preview
Source page 17
Chapter 0 Introduction and Preliminaries Welcome to Discrete Mathematics. If this is your first time encountering the subject, you will probably find discrete mathematics quite different from other math subjects. You might not even know what discrete math is! Hopefully this short introduction will shed some light on what the subject is about and what you can expect as you move forward in your studies. 0.1 What is Discrete Mathematics? dis·crete / dis’krët. Adjective: Individually separate and distinct. Synonyms: separate - detached - distinct - abstract. Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part, but you also study functions and lines and triangles and parallelepipeds and vectors and . . . . Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Okay, those that involve numbers, functions, lines, triangles, . . . . Whatever your conception of what mathematics is, try applying the concept of “discrete” to it, as defined above. Some math fundamentally deals with stuffthat is individually separate and distinct. In an algebra or calculus class, you might have found a particular set of numbers (maybe the set of numbers in the range of a function). You would represent this set as an interval: [0, ∞) is the range of f (x) x2 since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them which are also in the set. Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function which gives the number of children of each person reading this. What is the range? I’m guessing it is something like {0, 1, 2, 3}. Maybe 4 is in there too. But certainly there is nobody reading this that has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person. One way to get a feel for the subject is to consider the types of problems you solve in discrete math. Here are a few simple examples: 1