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 over

a 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: mirtitles@gmail.com

Fork us at GitLab: https://gitlab.com/mirtitles/

Add new entries to the detailed book catalog here.

Contents

Preface 7

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

Bibliography 403

Notations 405

Subject Index 409