Discrete Mathematics for Computer Science PDF

Discrete Mathematics for Computer Science

4.10.4 Using Discrete Mathematics in Computer Science 280. CHAPTER 5. Analysis of Algorithms. 283. 5.1 Comparing Growth Rates of Functions 284.

North Carolina Standard Course of Study Discrete Mathematics for

Note on Numbering: Discrete Math for Computer Science (DCS) Number and Quantity (N) Functions (F) Statistics and. Probability (SP) Graph Theory (GT) Logic

Discrete Mathematics for Computer Science

CS 441 Discrete Mathematics for CS. Milos Hauskrecht milos@cs.pitt.edu. 5329 Sennott Square. Discrete Mathematics for. Computer Science. M. Hauskrecht.

Propositional Logic Discrete Mathematics

Computer Sci & Eng Dept. SUNY Buffalo c Xin He (University at Buffalo). CSE 191 Discrete Structures. 1 / 37. Discrete Mathematics.

Discrete Mathematics

(2) Discrete Mathematics provides the tools used in most areas of computer science. Exposure to the mathematical concepts and discrete structures.

DIGITAL NOTES ON Discrete Mathematics B.TECH II YEAR - I SEM

Logic and Discrete Mathematics Grass Man & Trembley

A Course in Discrete Structures

Why study discrete mathematics in computer science? It does not directly help us write programs. At the same time it is the mathematics underlying.

Notes on Discrete Mathematics

Jun 8 2022 These are the notes for the Fall 2017 semester version of the Yale course. CPSC 202a

Discrete Mathematics

Rationale. : This course introduces the basic concepts of discrete mathematics in the field of computer science. It covers sets logic

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 068808quotesdbs_dbs3.pdfusesText_6

[PDF] Discrete Mathematics for Computer Science

I. =ý. 1. !

Terms Meaning Section

Sets, Proof Templates, and Induction

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

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

Um Xi Xm U ...UXn 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

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

S X S logically implies X 2.3.3

P 3 AKP Conjecture about complexity 2.5.6

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

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

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

R D. S Equijoin of relations R and S 3.10.2

At www.brookscole.com you can find out about

Changing the way the world learns

Discrete Mathematics

Gary Haggard

Bucknell University

John Schlipf

University of Cincinnati

Sue Whitesides

McGill University

THOrVIMSO3N

United Kingdom • United States

THOIMSO>N

BROOKS/COLE

Assistant Editor: Stacy Green Anne Seitz

Marketing Manager: Tom Ziolkowski Wesley Morrison

Art Director: Vernon Boes Compositor: ATLIS

Permissions Editor: Chelsea Junget