Elements of discrete mathematics (Q2778904)

The work under review is a textbook and has a broad coverage of topics in discrete mathematics, thought of as that part of mathematics in which one does not need continuity. The book comprises 3 independent parts: ``Fundamental notions'', ``Graphs'', and ``Algebras''. NEWLINENEWLINENEWLINEA very short introductory chapter serves to fix the notions and techniques needed from propositional and predicate logic. The inference rules are explained informally, by means of examples. In the chapter ``Sets'' there are stated many properties of union, intersection, difference, symmetric difference, and Cartesian product of sets. The next 3 chapters are devoted respectively to ``Binary relations'' (here one finds various representations of binary relations, inverse relation, computation of relations), ``Functions'' (including partial, multivalued, and generalized functions), and ``Internal binary relations'' (such as equivalence relations, (pre)orderings). In the fifth chapter, ``Functions, computability, recursivity'', one introduces Turing machine, Church's theses, recursive sets, Peano's axioms for the set of natural numbers. The final chapter of the first part has the title ``Complexity''. Here one compares the algorithms according to the asymptotic execution time. The relevant concepts are introduced by means of two examples: computation of Fibonacci sequence and representation of sparse matrices. NEWLINENEWLINENEWLINEThe part ``Graphs'' consists of 5 chapters. In the first one there are given the essentials of oriented, unoriented, and valued graphs. Chapter 8, titled ``Paths and circuits'', includes several algorithms for detecting shortest or longest path, as well as statements of Hamiltonian and Eulerian problems. In particular one finds here the Dijkstra-Moore algorithm and a proof for the existence of Hamiltonian paths in complete graphs. Chapter 9, ``Transitive closures'', consists of short sections that verbally discuss problems involving reachability in dynamic systems and Markov processes. The notions of cycle, (strongly) connected component, multigraph, tree, cyclomatic number, as well as Kruskal's algorithm, are encountered in the chapter entitled ``Trees and connectivity''. In chapter 11, ``Multipartite graphs'', one introduces Grundy function, \(p\)-chromatic graphs, hypergraphs.NEWLINENEWLINENEWLINEThe third part opens with the chapter ``Operators and algebras'', in which there are reviewed classical properties of operators, distinguished elements associated to operators, morphisms, and normal forms for formulae. In chapter 13, ``Monoids and groups'', one also defines formal languages and grammars, while the chapter ``Dioids'' is intended as a brief introduction to a theory, proposed by \textit{J. Kuntzmann} [Théorie des réseaux, Dunod, Paris (1972; Zbl 0239.05101)] and developed by \textit{M. Gondran} and \textit{M. Minoux} [Graphs and Algorithms, Wiley Chichester (1984; Zbl 0611.90096)] unifying several matrix algorithms encountered in operations research, equational approach to formal languages, and relations theory. The last chapters present ``Boolean algebras'' and ``Kleene algebras and finite state automata'', respectively. NEWLINENEWLINENEWLINEEach chapter has many well-thought-out exercises, original problems and challenging projects, paying close attention to real-world aspects of the topics under study. The reader finds just a few proofs in the book, so she or he is required to concentrate and exercise thinking. The references are mostly to other textbooks from French literature. Occasionally, historical notes aim to put things in the right perspective. The book ends with an appendix, containing hints for some of the proposed problems, and a comprehensive index. NEWLINENEWLINENEWLINEAs stated before, the work is a textbook, valuable by contents and presentation, aiming to serve graduate students and practitioners in computer science.