Page 2 : NA, , al! Tata McGraw-Hill, , , , , , , , Discrete Mathematical Structures with, Applications to Computer Science, , Copyright © 1975 by McGraw-Hill, Inc., , All rights reserved. No part of this publication may be reproduced or distributed, in any form or by any means, or stored in a data base or retrieval system, without, the prior written permission of the publisher, , Tata McGraw-Hill Edition 1997, , 35th reprint 2008, RYLYYDLXRZQXX, , Reprinted in India by arrangement with The McGraw-Hill Companies,, Inc., New York, , For,Sale in India Only, Library of Congress Cataloging-in-Publication Data, , Tremblay, Jean-Paul, date, Discrete mathematical structures with applications to computer science., (McGraw-Hill computer science series), Includes bibliographies, 1. Mathematics.—1961 2. Electronic data processing. 3. Machine, theory. I., Manohar, R., date joint author. II. Title., QA39.2.T72 510’.2'40901 74-23954, ISBN 0-07-065 142-6, , ISBN-13: 978-0-07-463 113-3, ISBN-10: 0-07-463113-6, , Published by Tata McGraw-Hill Publishing Company Limited,, 7 West Patel Nagar, New Delhi 110 008, and printed at, Sai Printo Pack Pvt. Ltd., New Delhi 110.020, , The McGraw-Hill Companies

Page 3 : CONTENTS, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Pref xili, 1_ Mathematical Logic i, Introduction 1, , {-! Statements and Notation 2, 1-2 Connectives Z, 1-2.1 Negation 8, 1-2.2 Conjunction 9, 1-2.3 Disjunction 10, 1-2.4 Statement Formulas and Truth Tables li, Exercises [-2.4 Bev 14, i-2.5__ Logieal Capabilities of Programming Languages 14, Exercises [-2.6 22, , 1-2.8 Tautologies , 24, Exercises {-2.8 26, , 1-2.9 Equivalence of Formulas 26, 1-2.10 Duality Law 30, 1-2.11 Tautological Implications 32, , , , Copyrighted materia

Page 4 : Exercises 1-2.11 34, 1-2.13 Functionally Complete Sets of Connectives 37, Exercises {-2.13 38, 1-2.14 Other Connectives 39, Exercises 1-2,14 41, 1-2.16 Two-state Devices and Statement Logic 41, Exercises {-2.15 au, Exercises 1-2 49, 1-3 Normal Forms 50, 1-3.1_ Disjunctive Normal Forms 50, 1-3.2_Conjunctive Normal Forms 52, 1-3.3__Principal Disjunctive Normal Forms 53, 1-3.4 Principal Conjunctive Normal! Forms 56, 1-3.6 Ordering and Uniqueness of Normal Forms 58, Exercises 1-3.5 60, 1-3.6 Completely Parenthesized Infix Notation and Polish Notation 61, Exercises /-3.6 64, 1-4 The Theory of Inference for the Statement Caleulus 65, 1-4.1 Validity Using Truth Tables 66, Exercises 1-4.1 67, 1-4.2 Rules of Inference 68, 1-4.3 Consistency of Premises and Indirect. Method of Proof 72, 1-4.4 Automatic Theorem Proving 74, Exercises 1-4 79, 1-5 The Predicate Caleulus 79, 1-5.1 Predicates 80, 1-5.2 The Statement Function, Variables, and Quantifiers 82, 1-65.83 Predicate Formulas 85, 1-§.4 Free and Bound Variables 86, 5.5 The Uni Di 28, Exercises 1-8 89, 1-6 Inference Theory of the Predicate Calculus 90, 1-6.1 Valid Formulas and Equivalences 90, , , , , , , , , , , , , , , , , , , , 1-6.3_ Special Valid Formulas Involving Quantifiers 94, 1-6.4 Theory of Inference for the Predicate Calculus 96, 16.5 Formulas Involving More Than One Quantifier 99, Exercises 1-6 101, Bibliography 102, , 2 Set Theory 104, Introduction 104, , 2-1 Basic Concepts of Set Theory 105, 2-11 Notation 105, , , , , , Copyrighted material

Page 5 : CONTENTS ix, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 21.2 Inclusion and Equality of Sets 107, 2-1,8 The Power Set 109, Exercises 2-1.3 L11, 2-1.4 Some Operations on Sets 111, Exercises 8-1.4 / 115, 2-1.6 Venn Diagrams 116, Exercises 2-1,6 118, 2-1.7 The Principle of Specification 121, 2-1.8 Ordered Pairs and n-tuples 122, 2-1.9 Cartesian Products 123, Exercises 2-1 125, 8-2 Representation of Discrete Structures 126, 2-2.1 Data Structures 126, 2-2.2 Storage Structures 1, 2-2.3 Sequential Allocation 130, 8-2.4 Pointers and Linked Allocation 132, 2-2.6 An Application of Bit Represented Sets 141, Exercises 2-2 147, 2-8 Relations and Ordering 148, 2-3.1 Relations 149, Exercises 2-3. 153, 2-3.2 Properties of Binary Relations in a Set 154, Exercises 9-3.2 155, 2-3.8 Relation Matrix and the Graph of a Relation 156, 2-3.4 Partition and Covering of a Set 162, Exercises 2-3.4 164, 9-3.5 Equivalence Relations 164, 2-3.6 Compatibility Relations 171, Exercises 2-3.6 175, 2-3.7 Composition of Binary Relations 176, Exercises 2-3.7 182, 23.8 Partial Ordering 183, 2-8.9 Partially Ordered Set: Representation and Associated, Terminology 186, Exercises 2-3.9 191, 2-4 Functions 192, 2-4.1 Definition and Introduction 192, Exercises 2-4.1 197, 2-4.2 Composition of Functions 198, 2-4.38 Inverse Functions 201, Exercises 2-4.3 204, 2-4.4 Binary and n-ary Operations 205, Exercises 2-4.4 210, 2-4.5 Characteristic Function of a Set 210, , , , Copyrighted m, , ateria