计算理论：数学基础

Mathematical Preliminaries

Sets

集合根据元素数量可分为 finite set 和 infinite set

Universal set: all possible elements

集合的操作： (Union), (Intersection), (Difference), (Complement)

De Morgan's Law:

Null set:

Subset: , 如果 即为 proper subset，记为

Disjoint Sets:

集合中元素的数量称为集合的势（Cardinality），记为

Power set: a set of sets, 是所有子集的集合，记为 或 ，有

Cartesian Product: 笛卡尔积，

Functions

给定集合 ，函数 ，函数将每个 中的元素映射到至多一个 中的元素，记为

total function:

injective function:

surjective function:

bijective function: total, injective and surjective

Big O notation: 参见 Asymptotic

Relations

Given two sets, , a relation is any subset of

Equivalence Relations: Reflexive, Symmetric and Transitive

对于一个等价关系 ，可定义 Equivalence Class

两个等价类之间的关系只有相等或 disjoint

对于 上的关系 ，有

• Partial order: Reflexive, Transitive and Antisymmetric
• Total order: partial order and , either or , also called linear order

Graphs

a directive graph

• Walk: a sequence of adjacent edges
• Path: a walk where no edge is repeated
• Simple path: a path where no node is repeated
• Cycle: a walk from a node to itself
• Simple cycle: only the base node is repeated

A tree is a directed graph that has no cycle.

Proof Techniques

归纳法 or 归谬法

鸽笼原理

String and Languages

Alphabet and string

Alphabet: 符号的有限集合，记为

String: alphabet 中的符号组成的序列

空串即没有符号的 string ，记为 或是

: the set of all possible strings from alphabet (including )

: the set of all possible strings from alphabet except ,

string 有几种运算，对于 string

• concatenation:
• reverse:
• length: The length of a string is the number of symbols contained in the string , denoted by .
• substring: is a substring of if there exist strings and such that ( can be empty string)
• prefix: when , is called a prefix of
• suffix: when , is called a suffix of

解决字符串相关的问题时，一般根据其长度进行分情况讨论

Languages

Language 是 string 的集合，即 的子集

e.g. ，这个 Language 不能通过正则描述

由于 Language 本质是集合，故集合的操作同样适用于 Language（Union，Intersection，Difference，Complement），

除此之外还有一些 Language 独有的操作

• reverse:
• concatenation:
• Kleene Closure:
• Positive Closure: