e T o RT TS e A So tg elB R e ISRL o e RA R ORL R VNGT VTA da P R2 OW yL ez v S I S RI RFI F R 808 OP NR AW y V T T GRA yR 2 2 ao[ te T R i S E R S 2BS S 22 02 R R Vg B tA S T G R NI e R e RO AT R e & oiR BRI kAS2 IR L % S e Math Companion for Computer Science Math Companion for Computer Science Zamir Bavel RESTON PUBLISHING COMPANY, INC. A Prentice-Hall Company Reston, Virginia Library of Congress Cataloging in Publication Data Bavel, Zamir, 1929- Math companion for computer science. Bibliography: p. Includes index. 1. Mathematics—1961- . 2. Electronic data processing —Mathematics. I. Title. QA39.2.B38 510 81-22650 ISBN 0-8359-4300-3 AACR2 ISBN 0-8359-4299-6 (pbk.) Interior design and editing/production supervision by Ginger Sasser © 1982 by Reston Publishing Company, Inc. A Prentice-Hall Company Reston, Virginia All rights reserved. No part of this book may be reproduced in any way, or by any means, without permission in writing from the publisher. 10 9 8 7 6 5 4 3 2 Printed in the United States of America Dedicated to my father and to the memory of my mother Contents List 0f SYMDOIS........ooiiiirieiiieineeeeece et xv Preface....ouoieieeiieeee ettt xvii Chapter 1 How to Use This Book 1 1.1 The Purposes of this Companion, 1 1.2 Finding the Meaning of Things, 3 1.3 Learning for the First Time, 3 1.4 Recalling, or Brushing Up, 4 1.5 IsItTrueThat...?,4 1.6 What Else Should One Know About...?,5 1.7 Reading the Book Sequentially, 5 1.8 The Companion as a Handbook, 6 1.9 The Companion as a Textbook, 6 Chapter 2 Sets and Subsets 8 2.1 Sets, Elements and Membership, 8 2.2 Difficulties in Describing Sets, 9 2.3 Describing Sets, 10 2.4 The Empty Set; Finite and Infinite Sets, 11 2.5 Equality of Sets; Subsets and Supersets, 12 2.6 The Power Set, 14 2.7 Indexing Sets, 15 Chapter 3 Basic Relations and Operations on Sets .......c.cccceecereceeccnece 16 3.1 Complements and Set Difference (Relative Complement), 16 3.2 Venn Diagrams, 17 3.3 The Law of Involution, 18 3.4 Union and Intersection, 19 3.5 The Subsets Generated by Two Sets, 21 3.6 Disjointness and Inclusion, 21 vii viii CONTENTS 3.7 Union and Intersection Are Commutative and Associative, 23 3.8 Both Distributive Laws Hold, 25 3.9 Idempotent Laws, 25 3.10 Laws of Complements, 25 3.11 Laws of Operating with ¢ and U, 26 3.12 DeMorgan’s Laws, 27 Chapter 4 The Principle of Duality; Further Properties of Sets............ 28 4.1 Absorption Laws, 28 4.2 The Principle of Duality, 29 4.3 Summary of Set Laws, 31 4.4 Laws of Set Difference (Relative Complement), 33 4.5 The Symmetric Difference, 33 4.6 Describing-Properties and Operations on Sets; Constructing Set Expressions from Complicated Descriptions, 35 4.7 Verifying Set-Expression Identities; Modified Venn Diagrams, 39 4.8 Counting Arguments for Finite Sets, 43 4.9 The Principle of Inclusion and Exclusion, 45 4.10 Concatenation, Strings and Languages, 47 * 411 Infinite Intersection and Union, 53 * 412 Closure of Families of Sets, 55 * 413 Defining Sets by Closure, 57 ** 4.14 Closure under Countable Unions and Intersections, 60 4.15 Set Product; More About Strings, 64 4.16 Set Closure Revisited; Yet More About Strings, 68 Chapter § Discrete Probability and Combinatorial Analysis ................ 72 5.1 Background: Theory vs. Practice, 72 5.2 Sample Points, Sample Space, Events and Probability, 73 5.3 Combinations of Events, 74 54 Probability Defined, 75 5.5 Basic Results, 76 *These sections are somewhat more demanding in mathematical maturity, or somewhat less likely to be encountered by the computer scientist, or both. **This section requires considerable mathematical maturity on the part of the reader. The topics here may be encountered infrequently.