基本数学对象.doc

语言与计算理论导引 基本数学对象第一部分 数学记号和技术本书一开始复习一些基本的数学知识：集合、函数和逻辑符号。后面讨论的抽象机的元件是集合，工作方式可以总结成规则，规则可以看成将一个集合映射到另一个集合的函数。在第一章还介绍了一个概念关系，关系是函数的概括，可以用来形式化集合中各个元素的关系。在第一章的最后节，我们关注的焦点从任意集合转移到语言，语言是只以符号串为元素的集合。本节引入的记号将用在后面讨论语言分类和相应的各种抽象机的章节中。有关集合和函数的推理涉及到证明，这是第2章讨论的主题。我们重点介绍了一个特别的证明技术：数学归纳法。与此紧密相关的一个想法就是归纳的、或者递归的、定义的想法。归纳定义常常是定义语言有效的工具，使用数学归纳法使得建立语言的属性变得容易。1 基本数学对象1.1 集合讨论集合首先碰到的问题是如何描述一个集合。有两种常用的方法：一是枚举元素（或是完全枚举，或是部分枚举但清楚地说明未枚举的元素是什么），二是描述元素的特性。两种方法示例如下：A = 11, 12, 21, 22B = 3, 3.1, 3.14, 3.141, 3.1415, 3.14159, C = x | x是由数字1或2组成的两位十进制正整数集合A有4个元素，B是一个无限集合，它的元素是逐渐逼近p，取p前面有限长度所得到。C等同于A，因为符合描述特征的数值x就是11, 12, 21和22。元素x属于集合A的记号是xA。利用这个记号，集合3, 3.1, 3.14, 3.141可以写成D = xB | x=0, x = 3i + 7jE = 3i + 7j | i, j 是非负整数E = 3i + 7j | i, j N，N是非负整数集合。记号AB，A是B的子集，A中的元素都是B中的元素。如果两个集合有相同的元素，则称两个集合相等，记为A=B，等同于AB且BA。A的补集记为A，包括所有不属于A的元素。这个定义隐含着一个包罗所有我们关心的元素的全集U，因此A = xU | xA全集U对补集的定义很重要。对任意两个集合A和B，它们的并集、交集和差集定义如下：AB = x | xA 或 xBAB = x | xA 且 xBA-B = x | xA 且 xB注意：A-B = ABA = U-A空集f是没有任何元素的集合，如果AB=f，则说明A和B不相交，既它们没有共同的元素。使用并集、交集、差集和补集可以构造很复杂的表达式。一些基本的规则用于处理和简化表达式。交换律（commutative）：AB = BAAB = BA结合律（associative）：A(BC) = (AB)CA(BC) = (AB)C分配律（distributive）：A(BC) = (AB)(AC)A(BC) = (AB)(AC)幂等律（idempotent）：AA = AAA = A吸收律（absorptive）：A(AB) = AA(AB) = ADe Morgan律：(AB) = AB(AB) = AB涉及补集的其他定律：(A) = AAA = fAA = U涉及空集的其他定律：Af = AAf = f涉及全集的其他定律：AU = UAU = ADe Morgan律特别有用，这里证明(AB) = AB。1）(AB) AB任给x(AB) xAB xA or xB xA or xB xAB2）AB (AB)任给x AB xA or xB xA or xB xAB x(AB)集合运算可以用Venn图表示。并集、交集运算的扩展：-_i=1 A_i = x | xA_i for at least one i = 1-n_i=1 A_i = x | xA_i for every i with 1=i=n更通用的扩展：_P(i) A_i = x | xA_i for at least one i satisfying P(i)集合本身还可以作为其他集合的元素。集合A的所有子集组成的集合称为A的幂集，记为2-A。如果A有n个元素，则2-A有2-n个元素。空集是所有集合的子集，每个集合都是自身的子集。集合A和B的Cartesian积记为AxB，其元素是一个有序对(a, b)，aA且bB。如果A有n个元素，B有m个元素，则AxB有nm个元素。更一般的情况是，多个集合的Cartesian积记为A_1xA_2xxA_n。1.2 逻辑1.2.1 命题和逻辑关联本书我们使用逻辑陈述和逻辑参数，本节简短地讨论逻辑命题和一些记号。大致而言，命题是一个有真值的客观的说明性陈述，真值有真和假两种值。为了研究逻辑参数，应用逻辑关联可以构造复杂的复合命题，逻辑参数基于复合命题中的关系。最熟悉的逻辑关联是“与”（conjunction），命题p和q，它们的连接命题记为pq。用真值表定义连接。其他两个基本的逻辑关联是“或（disjunction）”和“非（negation）”。另一个重要的逻辑关联是“条件（conditional）”，记为pq，读作如果p成立，则q也成立。命题(pq)(qp)简写成pq，读作p成立当且仅当q成立。复合命题如果有谓词变量，则只有知道谓词变量的真值后，才能确定整个命题的真值。(pq)(pq)的两种真值表，见书13页。如果命题在任何情况下都为真，则称为永真命题（tautology），如pp；如果任何情况下都为假，则称为永假命题（contradiction），如pp。true和false是两个特殊的命题，前者永真，后者永假。1.2.2 逻辑蕴含和相等假设P和Q都是复合命题，由谓词和逻辑关联构成。在P和Q的真值表中，当P为真时，则Q也为真，称为P蕴含Q，记为PQ；如果P和Q有相同的真值表，则称P和Q逻辑等同，记为PQ。PQ意味着命题PQ永真，PQ意味着命题PQ永真。集合的交、并、补与逻辑的与、或、非的关系。集合的成员表（membership table）与逻辑的真值表（truth table）的对比。空集是永假命题false，全集U是永真命题。由此可从前面的一组集合等式得到逻辑等式。另外还有许多其它逻辑等式，下面列出一些带逻辑条件的等式：(pq)(pq)(pq)(qp)(pq)(pq)第一条等式提供了用三个基本的逻辑关联消解逻辑条件的方法，第二条等式说明了命题与逆否命题的关系。1.2.3 逻辑量词和含量词的命题（Quantified Statements）含自由变量的命题，如x24，x取值空间是自然数；如果表达存在一个自然数，其平方值小于4，则命题不再与一个值相关，而与一个域相关。$x(x24)$是存在量词（existential quantifier），x是受限变量（bound variable）。另一个是通用量词（universal quantifier），表达“任给”的含义。量词后面的括号说明了量词的使用范围，当有多个量词时，括号尤其重要。x(P(x)等同于$x(P(x)$x(P(x)等同于x(P(x)1.3 函数将一个集合中的元素映射到另一个集合中的元素，前一个集合称为函数域，后一个集合称为值域，记为f: AB。通常为了方便，我们假设函数域是使得函数有意义的最大集合。集合A上的部分函数（partial function），其函数域是A的子集，对应的概念是全域函数。1.3.1 一一映射和满射（onto）函数如果f(A)=B，则称函数f是满射函数。如果A中不同的元素映射到B中不同的元素，则称f是一一映射函数。既是满射，又是一一映射函数，则是双射函数1.3.2 复合函数和逆函数函数复合运算满足结合律，保持了函数的一一映射、满射和双射性质。双射函数有逆函数。1.3.3 集合上的操作如果函数有两个或多个变量，则函数域则是两个或多个集合的Cartesian积。双项运算（binary operation）一般采用中缀记号。单项操作是一个函数。单项操作和双项操作的封闭性。如果是集合S上的双项操作，T是S的子集，值域TT是T的子集；同理单项操作u(T)是T的子集。1.4 关系两个对象的关系可以用数学关系精确的描述。先给函数一个更精确的定义，f: AB，f是AxB的一个子集。对于每个aA，只存在一个bB，使得(a, b)，通常b写成f(a)。关系是将函数定义的放松得到，允许多对多映射，记为(a, b)R，或aRb。一个例子，余等关系（congruence），n是一个固定的值，如果a和b除以n得到相同的余数，则数对(a, b)属于余等关系。1.4.1 等价关系和等价类我们感兴趣的关系具备下面三个特点：反身（reflexivity）、对称（symmetry）、传递（transitivity）。定义如下：1）R是反身的，即任给aA，aRa。2）R是对称的，即如果aRb，则bRa。3）R是传递的，即如果aRb且bRc，则aRc。4）如果R是反身、对称、传递的，则是等价关系。余等关系是等价关系。集合A的划分C是一个由A的子集组成的集合，满足两个条件：1）C中任意两个元素的交集为空。2）C中所有元素的并集是A。C中每个元素称为一个桶（bin），A中每个元素属于且只属于某个桶。划分定义了一个A上的等价关系E：A中的元素a和b属于同一个桶，则属于关系E。设R是A上的等价关系，a是A的一个元素，含a的等价类定义如下：aR = xA | xRa每个桶就是一个等价类。证明两个等价类的交集为空。反证法，如果abf，则存在一个元素x既属于a，又属于b，则a=x=b。定理1.1 集合A的划分C，关系R定义为：xRy当且仅当x和y属于C中同一个元素。反之，如果R是A上的等价关系，则R的等价类组成的集合是A的一个划分。并且两个元素等价当且仅当属于同一个等价类。如果S是A的一个子集，为了证明S是一个等价类，只有证明下面两条：1）S中任意两个元素等价2）不存在S中的元素与S外的元素等价。1.5 语言先看看有关词典里对语言的解释定义。（1）The use by human beings of voice sounds, and often written symbols representing these sounds, in organized combinations and patterns in order to express and communicate thoughts and feelings.语言人类声音的使用，并且经常是代表这些声音的文字符号，并以有条理的组合和形式出现，目的是为了表达和交流思想和感情（2）A system of words formed from such combinations and patterns, used by the people of a particular country or by a group of people with a shared history or set of traditions.（某民族，某国的）语言，文字这样的组合和形式形成的一系列词语，被一个特定国家的人或有共同历史或一套传统的一群人所使用（3）A nonverbal method of communicating ideas, as by a system of signs, symbols, gestures, or rules:表意语交流思想的一种非口头的方法，例如用一系列信号、符号、手势或规则。（4）A set of characters, conventions, and rules, that is used for conveying informa- tion. The three aspects of language are pragmatics, semantics, and syntax.一种用于传递信息的字符、约定和规则的集合。语言的三个方面是语用学、语义学和语法。人工语言举例：algebraic language, algorithmic language, application-orientedlanguage, artificial language, assembly language, command language, computer language, computer-oriented language, control language, high-level language, job control language, linear language, low-level language, machine language, multidimensional language, natural language, object language, one-dimensional language, problem language, problem-oriented language, programming language, source language, symbolic language, syntax language, target language, unstratified language, pragmatics, syntax语言是由符号串组成的集合，符号一般是字母。通用的定义允许语言可以是一组随机产生、无关的符号串，也可以是紧密相关的符号串，可以是高级程序设计语言，也可以是自然语言。比如我们可以说英语是字符串的集合，当然更进一步说，英语是合法字符串的集合。语言中的单词一般不符合语言的语法，不属于语言。讨论语言之前，首先要定义字母表，包括所有构成语言的字符串的符号。字母表是一个有限的符号集。例如英语，字母表包括26个大小写英文字母、空格和标点符号。而程序设计语言则还要包括数字。字符串的定义，如果是字母表，则上的字符串是中元素的有序排列。空串记为L，与字母表无关。字符串x的长度是字符串的符