The McGraw-Hill Companies Mc Succeed CRETE MATHEMATICS AND ITS APPLICATIONS,SEVENTH EDITION Published by McGraw-Hill,a business unit of The MeGraw-Hill Companies,Ine,1221 Avenue of the ious editi s02007.2003.amd1999.Nop of this publication may be re or transmission,or broadcast for distance leamning Samia,iaedingehetoaeadpmnompomeas,agkeaahheouthnesoeike This book is printedncidree paper. 1234567890D0wD0wW10987654321 7023g30m Global Pu ng nt edit Brenda A roles Cover Designer. All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page Library of Congress Cataloging-in-Publication Data 850 puter science-Mathematics I.Title 2011011060 www.mhhe.com DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York, NY 10020. Copyright © 2012 by The McGraw-Hill Companies, Inc. All rights reserved. Previous editions © 2007, 2003, and 1999. No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written consent of The McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic storage or transmission, or broadcast for distance learning. Some ancillaries, including electronic and print components, may not be available to customers outside the United States. This book is printed on acid-free paper. 1 2 3 4 5 6 7 8 9 0 DOW/DOW 1 0 9 8 7 6 5 4 3 2 1 ISBN 978-0-07-338309-5 MHID 0-07-338309-0 Vice President & Editor-in-Chief: Marty Lange Editorial Director: Michael Lange Global Publisher: Raghothaman Srinivasan Executive Editor: Bill Stenquist Development Editors: Lorraine K. Buczek/Rose Kernan Senior Marketing Manager: Curt Reynolds Project Manager: Robin A. Reed Buyer: Sandy Ludovissy Design Coordinator: Brenda A. Rolwes Cover painting: Jasper Johns, Between the Clock and the Bed, 1981. Oil on Canvas (72 × 126 1/4 inches) Collection of the artist. Photograph by Glenn Stiegelman. Cover Art © Jasper Johns/Licensed by VAGA, New York, NY Cover Designer: Studio Montage, St. Louis, Missouri Lead Photo Research Coordinator: Carrie K. Burger Media Project Manager: Tammy Juran Production Services/Compositor: RPK Editorial Services/PreTeX, Inc. Typeface: 10.5/12 Times Roman Printer: R.R. Donnelley All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page. Library of Congress Cataloging-in-Publication Data Rosen, Kenneth H. Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed. p. cm. Includes index. ISBN 0–07–338309–0 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012 511–dc22 2011011060 www.mhhe.com