Selected Topics in Discrete Mathematics

Beata Fałda, Lech Gruszecki
ISBN: 978-83-7702-616-8
Stron: 204
Format: B5 (oprawa twarda)
Rok wydania: 2012


TABLE OF CONTENTS

Introduction

1 Logical and set theoretical preliminaries
1.1 Introduction to the classical two-valued statement calculus
1.2 Formal introduction to the classical statement calculus
1.3 Elements of many-valued statement calculus
1.4 Classical predicate calculus
1.5 Sets and their properties

2 Relations and functions
2.1 Relations and their properties
2.2 Relations between the elements of finite sets
2.3 Equivalence relations
2.4 Order relations
2.5 Functions and their properties

3 Set of natural numbers and induction
3.1 Set of natural numbers. Defining by induction
3.2 Recursive functions
3.3 Application of recursion: finite-state automata and their languages

4 Lattices, Boolean algebras and Boolean functions
4.1 Lattices and their properties
4.2 Boolean algebras
4.3 Boolean expressions and functions

5 Finite sets and methods of counting their elements
5.1 Introduction to combinatorial methods
5.2 Basics of combinatorics - formal approach
5.3 Binomial and polynomial coefficients
5.4 Inclusion-Exclusion Principle
5.5 Pigeonhole Principle (Dirichlet Drawer Principle)

6 Partitions and permutations. Stirling and Bell Numbers
6.1 Counting partitions
6.2 Factorizations of numbers
6.3 Permutations
6.4 Special numbers

7 Main concepts of graph theory
7.1 An informal introduction to graph theory
7.2 Basic definitions of graph theory
7.3 Connectivity of graphs

8 Graph traversal
8.1 Euler Graphs
8.2 Hamiltonian Graphs
8.3 Weighted graphs

9 Trees and digraphs
9.1 Basic concepts of tree theory
9.2 Spanning trees
9.3 Digraphs
10 Counting graphs. A few selected problems

Bibliography