In this post, we will see the book Selected Problems In Discrete Mathematics by G. P. Gavrilov; A. A. Sapozhenko.
About the book
This collection of problems is intended as an accompaniment to a course on discrete mathematics at the universities. Senior students and graduates specializing in mathematical cybernetics may also find the book useful. Lecturers can use the material for exercises during seminars.The material in this book is based on a course of lectures on discrete mathematics delivered by the authors overa number of years at the Faculty of Mechanics and Mathematics, and later at the Faculty of Computational Mathematics and Cybernetics at Moscow State University.The reader can use Introduction to Discrete Mathematics by S. Yablonsky as the main text. when solving the problems in this collection.The exercises in the book have various origins. Most of the material is traditional and specialists on discrete mathematics are all too familiar with such problems. However, it is practically impossible to trace the origin of the problems of this kind. Most of the problems were conceived by the authors during seminars and practical classes, during examinations, and also while preparing this hook. Some of the problems resulted from studying publications in journals, and a few have been borrowed from other sources. Several problems were passed on to us by staff at the Faculty and by other colleagues. The authors express their sincere gratitude to them all.
The book was translated from Russian by was published in by Publishers.
Credits to original uploader.
You can get the book here.
Note: Scan quality is inconsistent, but mostly readable. OCR is not great.
Follow us on The Internet Archive: https://archive.org/details/@mirtitles
Follow Us On Twitter: https://twitter.com/MirTitles
Write to us: firstname.lastname@example.org
Fork us at GitLab: https://gitlab.com/mirtitles/
Add new entries to the detailed book catalog here.
Chapter 1. Boolean Functions: Methods of Defining and Basic Properties 10
1.1 Boolean Vectors and a Unit n-Dimensional Cube 10
1.2 Methods of Defining Boolean Functions, Elementary Functions. Formulas. Superposition Operation 22
1.3 Special Forms of Formulas. Disjunctive and Conjunctive Normal Forms. Polynomials 33
1.4 Minimization of Boolean Functions 42
1.5 Essential and Apparent Variables 49
Chapter 2. Closed Classes and Completeness 55
2.1 Closure Operation. Closed Classes 55
2.2 Duality and the Class of Self-Dual Functions 59
2.3 Linearity and the Class of Linear Functions 63
2.4 Classes of Functions Preserving the Constants 67
2.5 Monotonicity and the Class of Monotonic Functions 70
2.6 Completeness and Closed Classes 76
Chapter 3. k-Valued Logics 82
3.1 Representation of Functions of k-Valued Logics Through Formulas 82
3.2 Closed Classes and Completeness in k-Valued Logics 88
Chapter 4. Graphs and Networks 101
4.1 Basic Concepts in the Graph Theory 101
4.2 Planarity, Connectivity, and Numerical Characteristics af Graphs 110
4.3 Directed Graphs 117
4.4 Trees and Bipolar Networks 123
4.5 Estimates in the Theory of Graphs and Networks 137
4.6 Representations of Boolean Functions by Contact Schemes and Formulas 143
Chapter 5. Fundamentals of Coding Theory 155
5.1 Codes with Corrections 155
5.2 Linear Codes 160
5.3 Alphabetic Coding 163
Chapter 6. Finite Automatons 174
6.1 Determinate and Boundedly Determinate Functions 174
6.2 Representation of Determinate Functions by Moore Diagrams Canonical Equations Tables and Schemes Operations Involving Determinate Functions 187
6.3 Closed Classes and Completeness in the Seta of Determinate and Boundedly Determinate Functions 206
Chapter 7. Fundamentals of the Algorithm Theory 212
7.1 Turing’s Machines and Operations with Them Functions Computable on Turing’s Machines 212
7.2 Classes of Computable and Recursive Functions 233
7.3 Computability and Complexity of Computations 241
Chapter 8. Elements of Combinatorial Analysis 248
8.1 Permutations and Combinations Properties of Binomial Coefficients 248
8.2 Inclusion and Exclusion Formulas 259
8.3 Recurrent Sequences Generating Functions and Recurrence Relations 265
8.4 Polya’s Theory 275
8.5 Asymptotic Expressions and Inequalities 280
Solutions, Answers, ad Hints 289
Subject Index 409