Skip to main content
main-content

Ü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

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

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

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

There are two main kinds of relations that play a very important role in mathematics and computer science:
1.
Partial orders
 
2.
Equivalence relations
 
Jean Gallier

Chapter 6. Graphs, Part II: More Advanced Notions

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

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise