没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义Building Blocks for Theoretical Computer Science (UIUC CS173)

Building Blocks for Theoretical Computer Science (UIUC CS173)

Computer

Science

UIUC

CS173

需积分: 10 9 下载量 194 浏览量 2017-03-07 16:41:38 上传评论 1 收藏 1.14MB PDF 举报

温馨提示

试读

271页

Building Blocks for Theoretical Computer Science (UIUC CS173)

资源详情

资源评论

Building Blocks

for

Theoretical Computer Science

(Version 1.3)

Margaret M. Fleck

January 1, 2013

Contents

Preface xi

1 Math review 1

1.1 Some sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Pairs of reals . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Exp onentials and logs . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Some handy functions . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Summations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.6 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.7 Variation in notation . . . . . . . . . . . . . . . . . . . . . . . 9

2 Logic 10

2.1 A bit about style . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3 Complex propositions . . . . . . . . . . . . . . . . . . . . . . . 11

2.4 Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 Converse, contrapositive, biconditional . . . . . . . . . . . . . 14

2.6 Complex statements . . . . . . . . . . . . . . . . . . . . . . . 15

2.7 Logical Equiva lence . . . . . . . . . . . . . . . . . . . . . . . . 16

CONTENTS ii

2.8 Some useful logical equivalences . . . . . . . . . . . . . . . . . 18

2.9 Negating propositions . . . . . . . . . . . . . . . . . . . . . . . 18

2.10 Predicates and Variables . . . . . . . . . . . . . . . . . . . . . 19

2.11 Other quantiﬁers . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.12 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.13 Useful notation . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.14 Notation for 2D points . . . . . . . . . . . . . . . . . . . . . . 23

2.15 Negating statements with quantiﬁers . . . . . . . . . . . . . . 24

2.16 Binding and scope . . . . . . . . . . . . . . . . . . . . . . . . 25

2.17 Variations in Notation . . . . . . . . . . . . . . . . . . . . . . 26

3 Proofs 27

3.1 Proving a universal statement . . . . . . . . . . . . . . . . . . 27

3.2 Another example of direct proof involving odd and even . . . . 29

3.3 Direct proof outline . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4 Proving existential statements . . . . . . . . . . . . . . . . . . 31

3.5 Disproving a universal statement . . . . . . . . . . . . . . . . 31

3.6 Disproving an existential statement . . . . . . . . . . . . . . . 32

3.7 Recap of proof methods . . . . . . . . . . . . . . . . . . . . . 33

3.8 Direct proof: example with two variables . . . . . . . . . . . . 33

3.9 Another example with two variables . . . . . . . . . . . . . . . 34

3.10 Proof by cases . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.11 Rephrasing claims . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.12 Proof by contrapositive . . . . . . . . . . . . . . . . . . . . . . 37

3.13 Another example of proof by contrapositive . . . . . . . . . . 38

CONTENTS iii

4 Number Theory 39

4.1 Factors and multiples . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 Direct proof with divisibility . . . . . . . . . . . . . . . . . . . 40

4.3 Stay in the Set . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.4 Prime numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.5 GCD and LCM . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.6 The division algorithm . . . . . . . . . . . . . . . . . . . . . . 43

4.7 Euclidean algorithm . . . . . . . . . . . . . . . . . . . . . . . 44

4.8 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.9 A recursive version of gcd . . . . . . . . . . . . . . . . . . . . 46

4.10 Congruence mod k . . . . . . . . . . . . . . . . . . . . . . . . 47

4.11 Proofs with congruence mod k . . . . . . . . . . . . . . . . . . 48

4.12 Equivalence classes . . . . . . . . . . . . . . . . . . . . . . . . 48

4.13 Wider perspective on equivalence . . . . . . . . . . . . . . . . 50

4.14 Variation in Terminology . . . . . . . . . . . . . . . . . . . . . 51

5 Sets 52

5.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.2 Things to be careful about . . . . . . . . . . . . . . . . . . . . 53

5.3 Cardinality, inclusion . . . . . . . . . . . . . . . . . . . . . . . 54

5.4 Vacuous truth . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.5 Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.6 Set identit ies . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.7 Size of set union . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.8 Product rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.9 Combining these basic rules . . . . . . . . . . . . . . . . . . . 60

CONTENTS iv

5.10 Proving f acts about set inclusion . . . . . . . . . . . . . . . . 61

5.11 An abstract example . . . . . . . . . . . . . . . . . . . . . . . 63

5.12 An example with products . . . . . . . . . . . . . . . . . . . . 64

5.13 A proof using sets and contrapositive . . . . . . . . . . . . . . 65

5.14 Variation in notation . . . . . . . . . . . . . . . . . . . . . . . 66

6 Relations 67

6.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2 Properties of relations: reﬂexive . . . . . . . . . . . . . . . . . 69

6.3 Symmetric and a ntisymmetric . . . . . . . . . . . . . . . . . . 70

6.4 Transitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.5 Types of relations . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.6 Proving that a relat ion is an equivalence relation . . . . . . . . 74

6.7 Proving antisymmetry . . . . . . . . . . . . . . . . . . . . . . 75

7 Functions and onto 77

7.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.2 When are functions equal? . . . . . . . . . . . . . . . . . . . . 79

7.3 What isn’t a function? . . . . . . . . . . . . . . . . . . . . . . 80

7.4 Images and Onto . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.5 Why are some functions not onto? . . . . . . . . . . . . . . . . 82

7.6 Negating onto . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.7 Nested quantiﬁers . . . . . . . . . . . . . . . . . . . . . . . . . 83

7.8 Proving that a f unction is onto . . . . . . . . . . . . . . . . . 85

7.9 A 2D example . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6

7.10 Composing two functions . . . . . . . . . . . . . . . . . . . . . 87

剩余270页未读，继续阅读

评论收藏

内容反馈

Building Blocks for Theoretical Computer Science (UIUC CS173)

评论0

最新资源

Building Blocks for Theoretical Computer Science (UIUC CS173)

评论0

最新资源

相关推荐

Theoretical Computer Science

理论计算机科学的构建块（1.3版）Building Blocks for Theoretical Computer Science (Version 1.3)

Templates for the Solution of Linear Systems - Building Blocks for Iterative Methods.ps

Built-In Building Blocks.dotx

intel thread building blocks

Embedded Systems Building Blocks

Building Blocks.dotx

intel threading building blocks(outfitting c++ for multicore processor parallelism)

tbb库Thread Building Blocks

Intel® Threading Building Blocks Tutorial

Building Blocks.dotx office 2007页码模板

Common Building Blocks

Threading building blocks 编程指南

[eBook] Embedded Systems Building Blocks, Second Edition uCos.pdf

Eight Building Blocks of CRM: A Framework for Success

J2ME Building Blocks for Mobile Device

Using OpenMP vs. Threading Building Blocks for Medical Imaging on Multi-cores

intel threading building blocks

Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks

Vector Davinci官方帮助配置使用手册（AutoSAR）.pdf

c++入门，核心，提高讲义笔记

离散数学及其应用 第八版 奇数编号练习答案.pdf

数字图像处理 冈萨雷斯 课后习题

科研伦理与学术规范 期末考试2 （40题）.pdf

最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx

软件著作权设计说明书模板（含填写说明）.docx

AUTOSAR培训教材.rar

菜菜sklearn课程讲义.rar

“互联网+”大学生创新创业大赛项目计划书

离散数学及其应用第八版奇数编号练习答案.pdf

数字图像处理冈萨雷斯课后习题

科研伦理与学术规范期末考试2 （40题）.pdf

最值得收藏的考研线性代数全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx