Wallis's book on discrete mathematics is a resource for an introductory course in a subject fundamental to both mathematics and computer science, a course that is expected not only to cover certain specific topics but also to introduce students to important modes of thought specific to each discipline . . . Lower-division undergraduates through graduate students. —Choice reviews (Review of the First Edition)
Very appropriately entitled as a 'beginner's guide', this textbook presents itself as the first exposure to discrete mathematics and rigorous proof for the mathematics or computer science student. —Zentralblatt Math (Review of the First Edition)
This second edition of A Beginner’s Guide to Discrete Mathematics presents a detailed guide to discrete mathematics and its relationship to other mathematical subjects including set theory, probability, cryptography, graph theory, and number theory. This textbook has a distinctly applied orientation and explores a variety of applications. Key Features of the second edition: * Includes a new chapter on the theory of voting as well as numerous new examples and exercises throughout the book * Introduces functions, vectors, matrices, number systems, scientific notations, and the representation of numbers in computers * Provides examples which then lead into easy practice problems throughout the text and full exercise at the end of each chapter * Full solutions for practice problems are provided at the end of the book
This text is intended for undergraduates in mathematics and computer science, however, featured special topics and applications may also interest graduate students.
W.D. Wallis
A Beginner’s Guide to Discrete Mathematics Second Edition
W.D. Wallis Department of Mathematics Southern Illinois University Carbondale, IL 62901 USA
[email protected]
ISBN 978-0-8176-8285-9 e-ISBN 978-0-8176-8286-6 DOI 10.1007/978-0-8176-8286-6 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011940047 Mathematics Subject Classification (2010): 05-01, 05Axx, 05Cxx, 60-01, 68Rxx, 97N70 1st edition: © Birkhäuser Boston 2003 2nd edition: © Springer Science+Business Media, LLC 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.birkhauser-science.com)
For Nathan
Preface
This text is a basic introduction to those areas of discrete mathematics of interest to students of mathematics. Introductory courses on this material are now standard at many colleges and universities. Usually these courses are of one semester’s duration, and usually they are offered at the sophomore level. Very often this will be the first course where the students see several real proofs. The preparation of the students is very mixed, and one cannot assume a strong background. In particular, the instructor should not assume that the students have seen a linear algebra course, or any introduction to number systems that goes beyond college