James L. Hein - Discrete Structures, Logic, And Computability

FOURTH EDITION

James L. Hein

Professor Emeritus

Portland State University

World Headquarters
Jones & Bartlett Learning
5 Wall Street
Burlington, MA 01803
978-443-5000
www.jblearning.com

Jones & Bartlett Learning books and products are available through most bookstores and online booksellers. To contact Jones & Bartlett Learning directly, call 800-832-0034, fax 978-443-8000, or visit our website, www.jblearning.com.

Substantial discounts on bulk quantities of Jones & Bartlett Learning publications are available to corporations, professional associations, and other qualified organizations. For details and specific discount information, contact the special sales department at Jones & Bartlett Learning via the above contact information or send an email to .

Copyright 2017 by Jones & Bartlett Learning, LLC, an Ascend Learning Company

All rights reserved. No part of the material protected by this copyright may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner.

The content, statements, views, and opinions herein are the sole expression of the respective authors and not that of Jones & Bartlett Learning, LLC. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not constitute or imply its endorsement or recommendation by Jones & Bartlett Learning, LLC, and such reference shall not be used for advertising or product endorsement purposes. All trademarks displayed are the trademarks of the parties noted herein. Discrete Structures, Logic, and Computability, Fourth Edition is an independent publication and has not been authorized, sponsored, or otherwise approved by the owners of the trademarks or service marks referenced in this product.

There may be images in this book that feature models; these models do not necessarily endorse, represent, or participate in the activities represented in the images. Any screenshots in this product are for educational and instructive purposes only. Any individuals and scenarios featured in the case studies throughout this product may be real or fictitious, but are used for instructional purposes only.

Production Credits

VP, Executive Publisher: David D. Cella
Publisher: Cathy L. Esperti
Acquisitions Editor: Laura Pagluica
Editorial Assistant: Taylor Ferracane
Production Editor: Sara Kelly
Senior Marketing Manager: Andrea DeFronzo
Manufacturing and Inventory Control: Therese Connell
Composition: Cenveo Publisher Services
Cover Design: Kristin E. Parker
Rights and Media Research Coordinator: Merideth Tumasz
Media Development Assistant: Shannon Sheehan
Cover Image: Marco Andras/Orange Stock RF/age fotostock
Printing and Binding: RR Donnelley
Cover printing: RR Donnelley

To order this product, use ISBN: 978-1-284-07040-8

Library of Congress Cataloging-in-Publication Data
Hein, James L.
Discrete structures, logic, and computability / James L. Hein
Fourth edition.
pages ; cm
Includes bibliographical references and index.
ISBN 978-1-284-09986-7 (casebound)
1. Computer scienceMathematics. 2. Logic, Symbolic and mathematical. 3. Computable functions. I. Title.
QA76.9.M35.H44 2016
005.115dc23
2015019684
6048

Printed in the United States of America

19 18 17 16 15 10 9 8 7 6 5 4 3 2 1

The last thing one discovers in writing a book
is what to put first.

Blaise Pascal (16231662)

This book is written for the prospective computer scientist, computer engineer, or applied mathematician who wants to learn the ideas that underlie computer science. The topics come from the fields of mathematics, logic, and computer science itself. I have attempted to give elementary introductions to those ideas and techniques that are necessary to understand and practice the art and science of computing. This fourth edition of the book contains all the topics for discrete structures listed in Computer Science Curricula 2013 by the ACM/IEEE Joint Task Force on Computing Curricula.

The structure of the fourth edition continues to support the spiral (i.e., iterative or nonlinear) method for learning. The spiral method is a just in time approach. In other words, start by introducing just enough basic information about a topic so that students can do something with it. Then revisit the topic whenever new skills or knowledge about the topic are needed for students to solve problems in other topics that have been introduced in the same way. The process continues as much as possible for each topic.

Topics that are revisited with the spiral approach include logic, sets, relations, graphs, counting, number theory, cryptology, algorithm analysis, complexity, algebra, languages, and machines. Therefore, many traditional topics are dispersed throughout the text to places where they fit naturally with the techniques under discussion.

The coverage of logic is much more extensive than in other current books at this level. Logic is of fundamental importance in computer sciencenot only for its use in problem solving, but also for its use in formal specification of programs, for its formal verification of programs, and for its growing use in areas such as databases, artificial intelligence, robotics, and automatic reasoning systems. Logic is covered in a spiral manner. For example, informal proof techniques are introduced in the first section of , where we also introduce higher forms of logic and automatic reasoning.

The coverage of algebraic structures differs from that in other texts. In we introduce the algebra of regular expressions for simplifying representations of regular languages.

The computing topics of languages, automata, and computation are introduced in . The last section of the book gives an elementary introduction to computational complexity.

Every section of the book now contains learning objectives and review questions. There are over 350 review questions in the book.

The first section of the book on informal proof (A Proof Primer) has been expanded to provide a wider range of proof techniques, along with simple examples of informal proofs that use the techniques.

A new chapter on graphs has been added (). It expands on the introductory material contained in the first chapter.

Two new topics, conditional independence and elementary statistics, have been added to Section 5.4 on discrete probability.

The coverage of logic programming has been reduced, but it is still introduced as an application of resolution in Section 8.3. The coverage of parsing algorithms has been dropped.

Over 125 examples with named headings have been added. There are now more than 550 such headings that contain over 650 individual examples. In addition to the examples that occur under named headings, the book now has more than 1000 examples that occur within the prose, most of which are introduced by the phrase For example.

More than 300 new exercises have been added so that the book now contains over 2250 exercises. Answers are provided for about half of the exercises; these exercises are identified with bold numbers.