5. 形式系统
·形式系统的定义：一个形式系统S由下列4个集合构成：
·一个非空集合SS，称为形式系统S的字母表或说符号(Symbol)表；
·一个由SS中字母的有限序列（字符串）所构成的集合FS，称为形式系统S的公式(Formula)集；
·从FS中选取一个子集AS，称为形式系统S的公理(Axiom)集；
·FS上有一个部分函数集RS = {Rn | Rn : FS ´ FS ´…´ FS ®FS , n = 1, 2, …}，称为形式系统S的规则(Rule)集，其中Rn : FS ´ FS ´…´ FS ®FS是n元的部分函数，我们称其为n元规则。
·形式系统中的定理(Theorem)：
·归纳基：t Î AS 是形式系统S中的定理。
· 归纳步：t1, t2, …, tn是形式系统S中的定理，而RnÎ是S中的规则，那么Rn(t1, t2, …, tn)也是形式系统S中的定理。
·对于形式系统中的规则Rn : FS ´ FS ´…´ FS ®FS，通常表示成下面的形式：
t1, t2, …, tn
Rn(t1, t2, …, tn)
·形式系统具有两个特征：
·形式化实际上是一个可机械实现的过程，在它里面，符号、规则和演算等被表示得严密、精确。在形式系统S中，只能使用字母表SS中的符号，只承认公式集FS中的符号串的合理性，只能由公理集，根据规则推出有意义的东西来。
·形式系统一旦完成，就成了符号串及根据规则进行的符号串的改写，系统与一切实际意义就毫不相干，或者说已经通过这种符号，从实际问题中抽象出了我们所需要研究的内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号串及规则赋予意义。
·对象语言(Object language)与元语言(Meta language)：
·数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必要区分这两个层次的推理。
·把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等，这种形式语言是我们所研究的对象语言。
·另一方面，关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达，这个语言称为研究的元语言，通常使用半数学化的自然语言。
·形式语言的语法(Syntax)与语义(Semantic)：
·形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。
·形式语言的语义是关于形式系统的解释和意思。
·形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。
6. 习题
1. 令集合A = { n | n £ 10且n 是奇数}，B = {n | n £ 10且n是素数}，请回答下列问题：
a) 请用列元素的方法列出集合A和集合B，请问集合B是否是集合A的子集？
b) 请计算AÈB、AÇB、A-B、A´B以及P(A)(即A的幂集)。
2. 设关系R = {<a, b> | a和b是互质的自然数}，请问R是自反的吗？对称的吗？传递的吗？为什么？
3. 设f : A®B是函数，R是A上的如下二元关系：R = {<a, b> | a, bÎA, f (a) = f (b) }， 证明R是A上的一个等价关系。
4. 使用数学归纳法证明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6
5. 设有函数f : N®N ´ N，f(n) = <n, n+1>，请问f是不是单射、满射或双射？
*6.设R1和R2都是A上的等价关系，请问R1ÈR2和R1ÇR2是否还是A上的等价关系？如果是请证明，否则请举一反例。
*7.设R是集合A上的等价关系，aÎA，可定义：
a) [a] = {bÎA | aRb }，称[a]为a关于R的等价类；
b) A/R = {[a] | aÎA}，称A关于R的商集。
设函数f : A®A/R定义为对任意aÎA有f(a) = [a]，请问R满足怎样的条件时f是单射？
*8 请给出<x, y, z>的集合方式的定义。若定义：[x, y, z] = {{x}, {x, y}, {x, y, z}}，则如果有[x1, y1, z1] = [x2, y2, z2]是否意味着有x1 = x2且y1 = y2且z1 = z2？
·形式系统的定义：一个形式系统S由下列4个集合构成：
·一个非空集合SS，称为形式系统S的字母表或说符号(Symbol)表；
·一个由SS中字母的有限序列（字符串）所构成的集合FS，称为形式系统S的公式(Formula)集；
·从FS中选取一个子集AS，称为形式系统S的公理(Axiom)集；
·FS上有一个部分函数集RS = {Rn | Rn : FS ´ FS ´…´ FS ®FS , n = 1, 2, …}，称为形式系统S的规则(Rule)集，其中Rn : FS ´ FS ´…´ FS ®FS是n元的部分函数，我们称其为n元规则。
·形式系统中的定理(Theorem)：
·归纳基：t Î AS 是形式系统S中的定理。
· 归纳步：t1, t2, …, tn是形式系统S中的定理，而RnÎ是S中的规则，那么Rn(t1, t2, …, tn)也是形式系统S中的定理。
·对于形式系统中的规则Rn : FS ´ FS ´…´ FS ®FS，通常表示成下面的形式：
t1, t2, …, tn
Rn(t1, t2, …, tn)
·形式系统具有两个特征：
·形式化实际上是一个可机械实现的过程，在它里面，符号、规则和演算等被表示得严密、精确。在形式系统S中，只能使用字母表SS中的符号，只承认公式集FS中的符号串的合理性，只能由公理集，根据规则推出有意义的东西来。
·形式系统一旦完成，就成了符号串及根据规则进行的符号串的改写，系统与一切实际意义就毫不相干，或者说已经通过这种符号，从实际问题中抽象出了我们所需要研究的内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号串及规则赋予意义。
·对象语言(Object language)与元语言(Meta language)：
·数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必要区分这两个层次的推理。
·把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等，这种形式语言是我们所研究的对象语言。
·另一方面，关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达，这个语言称为研究的元语言，通常使用半数学化的自然语言。
·形式语言的语法(Syntax)与语义(Semantic)：
·形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。
·形式语言的语义是关于形式系统的解释和意思。
·形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。
6. 习题
1. 令集合A = { n | n £ 10且n 是奇数}，B = {n | n £ 10且n是素数}，请回答下列问题：
a) 请用列元素的方法列出集合A和集合B，请问集合B是否是集合A的子集？
b) 请计算AÈB、AÇB、A-B、A´B以及P(A)(即A的幂集)。
2. 设关系R = {<a, b> | a和b是互质的自然数}，请问R是自反的吗？对称的吗？传递的吗？为什么？
3. 设f : A®B是函数，R是A上的如下二元关系：R = {<a, b> | a, bÎA, f (a) = f (b) }， 证明R是A上的一个等价关系。
4. 使用数学归纳法证明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6
5. 设有函数f : N®N ´ N，f(n) = <n, n+1>，请问f是不是单射、满射或双射？
*6.设R1和R2都是A上的等价关系，请问R1ÈR2和R1ÇR2是否还是A上的等价关系？如果是请证明，否则请举一反例。
*7.设R是集合A上的等价关系，aÎA，可定义：
a) [a] = {bÎA | aRb }，称[a]为a关于R的等价类；
b) A/R = {[a] | aÎA}，称A关于R的商集。
设函数f : A®A/R定义为对任意aÎA有f(a) = [a]，请问R满足怎样的条件时f是单射？
*8 请给出<x, y, z>的集合方式的定义。若定义：[x, y, z] = {{x}, {x, y}, {x, y, z}}，则如果有[x1, y1, z1] = [x2, y2, z2]是否意味着有x1 = x2且y1 = y2且z1 = z2？
