Discrete Mathematics

verfasst von: Jean Gallier

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This books gives an introduction to discrete mathematics for beginning undergraduates. One of original features of this book is that it begins with a presentation of the rules of logic as used in mathematics. Many examples of formal and informal proofs are given. With this logical framework firmly in place, the book describes the major axioms of set theory and introduces the natural numbers. The rest of the book is more standard. It deals with functions and relations, directed and undirected graphs, and an introduction to combinatorics. There is a section on public key cryptography and RSA, with complete proofs of Fermat's little theorem and the correctness of the RSA scheme, as well as explicit algorithms to perform modular arithmetic. The last chapter provides more graph theory. Eulerian and Hamiltonian cycles are discussed. Then, we study flows and tensions and state and prove the max flow min-cut theorem. We also discuss matchings, covering, bipartite graphs.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Mathematical Reasoning, Proof Principles, and Logic

Jean Gallier

Chapter 2. Relations, Functions, Partial Functions

Abstract

We use functions all the time in mathematics and in computer science. But, what exactly is a function?

Jean Gallier

Chapter 3. Graphs, Part I: Basic Notions

Abstract

Graphs are mathematical structures that have many applications in computer science, electrical engineering, and more widely in engineering as a whole, but also in sciences such as biology, linguistics, and sociology, among others. For example, relations among objects can usually be encoded by graphs. Whenever a system has a notion of state and a state transition function, graph methods may be applicable. Certain problems are naturally modeled by undirected graphs whereas others require directed graphs. Let us give a concrete example.

Jean Gallier

Chapter 4. Some Counting Problems; Multinomial Coefficients, The Principle of Inclusion–Exclusion, Sylvester’s Formula, The Sieve Formula

Abstract

In this section, we consider some simple counting problems. Let us begin with permutations. Recall that a permutation of a set A is any bijection between A and itself.

Jean Gallier

Chapter 5. Partial Orders, Lattices, Well-Founded Orderings, Unique Prime Factorization in ℤ and GCDs, Equivalence Relations, Fibonacci and Lucas Numbers, Public Key Cryptography and RSA, Distributive Lattices, Boolean Algebras, Heyting Algebras

Abstract

There are two main kinds of relations that play a very important role in mathematics and computer science:

Partial orders

Equivalence relations

Jean Gallier

Chapter 6. Graphs, Part II: More Advanced Notions

Abstract

In this section, we take a closer look at the structure of cycles in a finite graph G. It turns out that there is a dual notion to that of a cycle, the notion of a cocycle.

Jean Gallier

Backmatter

Titel: Discrete Mathematics
verfasst von: Jean Gallier
Verlag: Springer New York
Electronic ISBN: 978-1-4419-8047-2
Print ISBN: 978-1-4419-8046-5
DOI: https://doi.org/10.1007/978-1-4419-8047-2