3rd Edition

Discrete Mathematics Proofs, Structures and Applications, Third Edition

By Rowan Garnier, John Taylor Copyright 2009
    846 Pages 302 B/W Illustrations
    by CRC Press

    Taking an approach to the subject that is suitable for a broad readership, Discrete Mathematics: Proofs, Structures, and Applications, Third Edition provides a rigorous yet accessible exposition of discrete mathematics, including the core mathematical foundation of computer science. The approach is comprehensive yet maintains an easy-to-follow progression from the basic mathematical ideas to the more sophisticated concepts examined later in the book. This edition preserves the philosophy of its predecessors while updating and revising some of the content.

    New to the Third Edition
    In the expanded first chapter, the text includes a new section on the formal proof of the validity of arguments in propositional logic before moving on to predicate logic. This edition also contains a new chapter on elementary number theory and congruences. This chapter explores groups that arise in modular arithmetic and RSA encryption, a widely used public key encryption scheme that enables practical and secure means of encrypting data. This third edition also offers a detailed solutions manual for qualifying instructors.

    Exploring the relationship between mathematics and computer science, this text continues to provide a secure grounding in the theory of discrete mathematics and to augment the theoretical foundation with salient applications. It is designed to help readers develop the rigorous logical thinking required to adapt to the demands of the ever-evolving discipline of computer science.

    Logic

    Propositions and Truth Values

    Logical Connectives and Truth Tables

    Tautologies and Contradictions

    Logical Equivalence and Logical Implication

    The Algebra of Propositions

    Arguments

    Formal Proof of the Validity of Arguments

    Predicate Logic

    Arguments in Predicate Logic

    Mathematical Proof

    The Nature of Proof

    Axioms and Axiom Systems

    Methods of Proof

    Mathematical Induction

    Sets

    Sets and Membership

    Subsets

    Operations on Sets

    Counting Techniques

    The Algebra of Sets

    Families of Sets

    The Cartesian Product

    Types and Typed Set Theory

    Relations

    Relations and Their Representations

    Properties of Relations

    Intersections and Unions of Relations

    Equivalence Relations and Partitions

    Order Relations

    Hasse Diagrams

    Application: Relational Databases

    Functions

    Definitions and Examples

    Composite Functions

    Injections and Surjections

    Bijections and Inverse Functions

    More on Cardinality

    Databases: Functional Dependence and Normal Forms

    Matrix Algebra

    Introduction

    Some Special Matrices

    Operations on Matrices

    Elementary Matrices

    The Inverse of a Matrix

    Systems of Linear Equations

    Introduction

    Matrix Inverse Method

    Gauss–Jordan Elimination

    Gaussian Elimination

    Algebraic Structures

    Binary Operations and Their Properties

    Algebraic Structures

    More about Groups

    Some Families of Groups

    Substructures

    Morphisms

    Group Codes

    Introduction to Number Theory

    Divisibility

    Prime Numbers

    Linear Congruences

    Groups in Modular Arithmetic

    Public Key Cryptography

    Boolean Algebra

    Introduction

    Properties of Boolean Algebras

    Boolean Functions

    Switching Circuits

    Logic Networks

    Minimization of Boolean Expressions

    Graph Theory

    Definitions and Examples

    Paths and Cycles

    Isomorphism of Graphs

    Trees

    Planar Graphs

    Directed Graphs

    Applications of Graph Theory

    Introduction

    Rooted Trees

    Sorting

    Searching Strategies

    Weighted Graphs

    The Shortest Path and Traveling Salesman Problems

    Networks and Flows

    References and Further Reading

    Hints and Solutions to Selected Exercises

    Index

    Biography

    Rowan Garnier was a professor of mathematics at Richmond, the American International University in London, where she served ten years as Chair of the Division of Mathematics, Science and Computer Science.

    John Taylor is Head of the School of Computing, Mathematical and Information Sciences at the University of Brighton, UK. He has published widely on the applications of diagrammatic logic systems to computer science.

    The authors’ diligent attempt to present, analyse and thoroughly demonstrate the subject of DMths is noteworthy. In keeping with the textbook character of their book, they also cite many examples. The book is an integrated textbook of DMths, adequate for undergraduate computer scientists, featuring a synoptic and vital presentation of this important, useful and interesting field. Of course, it is also interesting and useful for students of mathematics, as well as for those who work with informatics in general. It is a classic textbook, well structured and sufficiently complete within the framework established by similar textbooks. The work does a good job keeping a balance between conciseness and in-depth examinations … .
    Contemporary Physics, Vol. 52, No. 2, March-April 2011

    This is a textbook on discrete mathematics for undergraduate students in computer science and mathematics. The choice of the topics covered in this text is largely suggested by the needs of computer science. It contains chapters on set theory, logic, algebra (matrix algebra and Boolean algebra), and graph theory with applications. … The style of exposition is very clear, step by step and the level is well adapted to undergraduates in computer science. The treatment is mathematically rigorous; therefore it is also suitable for mathematics students. Besides the theory there are many concrete examples and exercises (with solutions!) to develop the routine of the student. So I can recommend warmly this book as a textbook for a course. It looks very attractive and has a nice typography. … Although I haven’t used this book in class (up to now), I think it is an excellent textbook.
    —H.G.J. Pijls, University of Amsterdam, The Netherlands

    Praise for Previous Editions
    Garnier and Taylor offer a work on discrete mathematics sufficiently comprehensive to be used as a resource work in a variety of courses … Now in its second edition, it would also make an excellent general reference book on these areas … a fine undergraduate book.
    —R.L. Pour, Emory & Henry College, CHOICE

    Provides an accessible introduction to discrete mathematics, including the core mathematics requirements for undergraduate computer science students.
    SciTech Book News, Vol. 122

    This is the second edition of this accessible yet rigorous introduction to discrete mathematics. As in the first edition, the theory is illustrated by a large number of solved exercises. In this edition further exercises have been added, in particular, at the routine level. In addition, some new material on typed set theory is included.
    —S. Teschl

    The book is designed for students of computer science. It contains main mathematical topics needed in their undergraduate study. In the second edition, the authors added a lot of new exercises and examples, illustrating discussed concepts. The book contains a lot of well-ordered and nicely illustrated material.
    —Vladimir Soucek, European Mathematical Society Newsletter, June 2004