0.2 数学概念和记号

SETS

定义

• object：number, symbol等原子对象, 或者set
• set：a group of objects
• subset：子集
• proper subset：真子集
• multiset：可包含重复元素的set
• 按照元素个数，set可分别记为：empty set, singleton set, unordered pair, infinite set

图形表示法：Venn diagram

SEQUENCES AND TUPLES

定义

• tuple：元素个数有限的sequence

• 按照元素个数，tuple可分别记为：1-tuple, ordered pair, k-tuple

• Cartesian product / cross product：集合的叉乘。集合A连着叉乘k次可记为 $A^k$

FUNCTIONS

定义：A function is an object that sets up an input-output relationship.

注：function也是object，本质上跟data并无区别，everything is object

性质：She same input always produces the same output.

注：所以数学中的function对应于程序语言中没有side-effect的pure fuction，而程序语言中的function则称为method更准确。

notion：$f: D\rightarrow R$， 其中D是domain，R是range。比如， $Z\rightarrow Z$代表了从正整数到正整数的fuction

注：看来很多程序语言用$\rightarrow$来描述返回值类型是一种很符合数学的写法，返回uint其实就是代表range是Z

R可以是range的超集，而domain则必须等于D。程序语言的function/method在这个角度是相同的，参数为int代表该function必须对所有int值都能正常工作，而返回类型int则即使只返回偶数也是合法的。

function的domain实际上是一个k-tuple，能统一地解释不同参数特殊，而参数个数记为arity，该function记为k-ary function。本质上function总能以prefix notion，infix notion只是一种便于理解的notion糖而已。

注：所以Lisp总是写成以list来调用function，list能代表一切

RELATIONS

A predicate or property is a function whose range is {TRUE, FALSE}.

A property whose domain is $A^k$ is called a relation, or a k-ary relation, or a k-ary relation on A.

注：Relation描述相同类型的若干值之间的关系，类似于程序语言中的expression

GRAPHS

（用到再补）

STRINGS AND LANGUAGES

alphabet：Any nonempty finite set

symbols：alphabet中的元素

a string over an alphabet：a finite sequence of aymbols from that alphabet

proper prefix：真前缀子串关系

a language：a set of strings

a prefix-free language：其中的任意两个string之间不是proper prefix的language

BOOLEAN LOGIC

negation （NOT，$\neg$）,conjunction（AND，$\land$）是meta-operation，能组合出所有其他bool operation，比如：