[PDF] Discrete Mathematics for Computer Science

View - Download Discrete Mathematics for Computer Science

Previous PDF

Next PDF

I. =ý. 1. !

|~ilH

Terms Meaning Section

Sets, Proof Templates, and Induction

x e A x is an element ofA 1.1 x f A x is not an element ofA 1.1

Ix x E A and P(x)} Set notation 1.1

N Natural numbers 1.1.1l

2 Integers 1.1.1

Q Rationals 1.1.1

R Real numbers I.1.1

A = B Sets A and B are equal 1.1.3

A C B A is a subset of B 1.1.5

A g B A is nota subset of B 1.1.5

A C B A is a proper subset of B 1.1.5

A 5 B A is nota proper subset of B 1.1.5

b=a bimplies a i.1.5 a b a if and only if b 1.1.5

AUB A union B 1.3.1

AFnB A intersect B 1.3.1

UX Generalized union of family of sets X 1.3.1

nX Generalized intersection of family of sets X 1.3.1

Um Xi Xm U ...UXn 1.3.1

nt=Mxi Xm n ... n Xn 1.3.1

A -B Elements of A not in B 1.3.2

A Elements not in A 1.3.2

A D B (A U B) -(A n B) 1.3.2

P(X) Power set of X 1.3.4

X x Y Product of X and Y 1.3.4

x A y Meet ofx and y 1.3.5 x v y Join ofx and y 1.3.5 -x Complement of x 1.3.5

T Top 1.15

I Bottom 1.3.5

JAI Cardinality of A 1.5.1

Si a,, + " -". + a,, 1.7.1

Terms Meaning Section

Formal Logic

"--p Not p 2.1 pAq p and q 2.1 pvq p or q 2.1 p q p implies q 2.1 p q p is equivalent to q 2.1

S X S logically implies X 2.3.3

P 3 AKP Conjecture about complexity 2.5.6

(Vx)P(x) For all x, P(x) 2.7.2 (3x)P(x) There exists an x such that P(x) 2.7.2 (VxE V)P(x) For all X EV, P(x) 2.7.3 (3x E V)P(x) There exists an x E V such that P(x) 2.7.3

A[i ..j] Array with elements Ail, ..., A[j] 2.7.3

1 Sheffer stroke 2.4

V Exclusive or 2.4

4, Pierce arrow 2.9

(x, y) E R or xRy x is R-related to y 3.1

R-1 The inverse of the relation R 3.2.1

RoS Composition of relations R and S 3.2.2

R+ U°° Ri 3.4.4

R* URO R' 3.4.4

n =- m(modp) n -m = kp for some k E N 3.6

Idx Identity relation 3.1

Lex Less than or equal relation 3.1

Gtx Greater than relation 3.1

Gex Greater than or equal relation 3.1

[x] Equivalence class of x 3.6 min m divides n 3.8.1

R D. S Equijoin of relations R and S 3.10.2

www.brookscole.com www.brookscole.com is the World Wide Web site for Brooks/Cole and is your direct source to dozens of online resources.

At www.brookscole.com you can find out about

supplements, demonstration software, and student resources. You can also send email to many of our authors and preview new publications and exciting new technologies. www.brookscole.com

Changing the way the world learns

Discrete Mathematics

for Computer Science fo Copue Science

Gary Haggard

Bucknell University

John Schlipf

University of Cincinnati

Sue Whitesides

McGill University

THOrVIMSO3N

BROOGKS/COLE Australia Canada Mexico • Singapore • Spain

United Kingdom • United States

THOIMSO>N

BROOKS/COLE

Publisher: Bob Pirtle Production Service: Hearthside Publishing Service;

Assistant Editor: Stacy Green Anne Seitz

Editorial Assistant: Katherine Cook Text Designer: Roy Neuhaus Technology Project Manager: Earl Perry Copy Editor: Hearthside Publishing Service;

Marketing Manager: Tom Ziolkowski Wesley Morrison

Marketing Assistant: Erin Mitchell Illustrator: Hearthside Publishing Service; Advertising Project Manager: Bryan Vann Jade Myers Signing Representative: Stephanie Shedlock Cover Designer: Roy R. Neuhaus Project Manager, Editorial Production: Cover Image: DigitalVision Cheryll Linthicum Cover Printer: Phoenix Color Corp

Art Director: Vernon Boes Compositor: ATLIS

Print/Media Buyer: Doreen Suruki Printer: Phoenix Color Corp

Permissions Editor: Chelsea Junget

COPYRIGHT ® 2006 Thomson Brooks/Cole, a part of Thomson Higher Education The Thomson Corporation. Thomson, the Star logo, and 10 Davis Drive Brooks/Cole are trademarks used herein under license. Belmont, CA 94002-3098 ALL RIGHTS RESERVED. No part of this work covered USA by the copyright hereon may be reproduced or used in any Asia form or by any means-graphic, electronic, or mechanical, Thomson Learning including photocopying, recording, taping, Web distribution, 5 Shenton Way #01-01 information storage and retrieval systems, or in any other UIC Building manner-without the written permission of the publisher. Singapore 068808

Australia/New Zealand

Printed in the United States of America Thomson Learning

1 2 3 4 5 6 7 09 08 07 06 05 102 Dodds Street

Southbank, Victoria 3006

Australia

For more information about our products, Canada

contact us at: Nelson Thomson Learning Academic Resource Center 1120 Birchmount Road

1-800-423-0563 Toronto, Ontario MIK 5G4

Canada

For permission to use material from this text or

product, submit a request online at Europe/Middle East/Africa http://www.thomsonrights.com.

Thomson Learning

Any additional questions about permissions can be High Holbom House submitted by email to thomsonrights@thomson.com. 50/51 Bedford Row

London, WC1R 4LR

United Kingdom

Library of Congress Control Number: 2004113828 Latin America

Thomson Learning

ISBN 0-534-49501-X Seneca, 53

Colonia Polanco

°° .%11560 Mexico D.F.

Spain/Portugal

4 EcyO'- Paraninfo

Calle Magallanes, 25

28015 Madrid

Spain

Contents

CHAPTER 1

Sets, Proof Templates, and Induction

1.1 Basic Definitions 1

1.1.1 Describing Sets Mathematically 2

1.1.2 Set Membership 4

1.1.3 Equality of Sets 4

1.1.4 Finite and Infinite Sets 5

1.1.5 Relations Between Sets 5

1.1.6 Venn Diagrams 7

1.1.7 Templates 8

1.2 Exercises 13

1.3 Operations on Sets 15

1.3.1 Union and Intersection 15

1.3.2 Set Difference, Complements, and DeMorgan's Laws 20

1.3.3 New Proof Templates 26

1.3.4 Power Sets and Products 28

1.3.5 Lattices and Boolean Algebras 28

1.4 Exercises 31

1.5 The Principle of Inclusion-Exclusion 34

1.5.1 Finite Cardinality 34

1.5.2 Principle of Inclusion-Exclusion for Two Sets 36

1.5.3 Principle of Inclusion-Exclusion for Three Sets 37

1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets 41

1.6 Exercises 42

vii viii Contents

1.7 Mathematical Induction 45

1.71 A First Form of Induction 45

1.72 A Template for Constructing Proofs by Induction 49

1.73 Application: Fibonacci Numbers 51

1.74 Application: Size of a Power Set 53

1.75 Application: Geometric Series 54

1.8 Program Correctness 56

1.8.1 Pseudocode Conventions 56

1.8.2 An Algorithm to Generate Perfect Squares 58

1.8.3 Two Algorithms for Computing Square Roots 58

1.9 Exercises 62

1.10 Strong Form of Mathematical Induction 66

1.10.1 Using the Strong Form of Mathematical Induction 69

1.10.2 Application: Algorithm to Compute Powers 72

1.10.3 Application: Finding Factorizations 75

1.10.4 Application: Binary Search 77

1.11 Exercises 79

1.12 Chapter Review 81

1.12.1 Summary 82

1.12.2 Starting to Review 84

1.12.3 Review Questions 85

1.12.4 Using Discrete Mathematics in Computer Science 87

CHAPTER 2

Formal Logic 89

2.1 Introduction to Propositional Logic 89

2.1.1 Formulas 92

2.1.2 Expression Trees for Formulas 94

2.1.3 Abbreviated Notation for Formulas 97

2.1.4 Using Gates to Represent Formulas 98

2.2 Exercises 99

2.3 Truth and Logical Truth 102

2.3.1 Tautologies 106

Contents ix

2.3.2 Substitutions into Tautologies 109

2.3.3 Logically Valid Inferences 109

2.3.4 Combinatorial Networks 112

2.3.5 Substituting Equivalent Subformulas 114

2.3.6 Simplifying Negations 115

2.4 Exercises 116

2.5 Normal Forms 121

2.5.1 Disjunctive Normal Form 122

2.5.2 Application: DNF and Combinatorial Networks 124

2.5.3 Conjunctive Normal Form 125

2.5.4 Application: CNF and Combinatorial Networks 127

2.5.5 Testing Satisfiability and Validity 127

2.5.6 The Famous 'P Af r Conjecture 129

2.5.7 Resolution Proofs: Automating Logic 129

2.6 Exercises 131

2.7 Predicates and Quantification 134

2.71 Predicates 135

2.72 Quantification 135

2.73 Restricted Quantification 136

2.74 Nested Quantifiers 137

2.75 Negation and Quantification 138

2.76 Quantification with Conjunction and Disjunction 139

2.77 Application: Loop Invariant Assertions 141

2.8 Exercises 143

2.9 Chapter Review 147

2.9.1 Summary 148

2.9.2 Starting to Review 149

quotesdbs_dbs47.pdfusesText_47

[PDF] maths prépa ece exercices

[PDF] maths prepa exercices corrigés

[PDF] Maths probabilité !!

[PDF] Maths probabilité 3 è m e

[PDF] Maths Probabilité ES

[PDF] maths probabilité pour dem

[PDF] maths probabilités

[PDF] MATHS PROBLEME

[PDF] MATHS PROBLEME 4ème

[PDF] Maths problème avec des fractions !

[PDF] maths problème calculer expression

[PDF] Maths problème de géométrie

[PDF] Maths Problème Equations

[PDF] Maths probleme parabole fonction second degres

[PDF] Maths problème parenthèse