数理逻辑 数理逻辑的内容可分为五部分： 逻辑演算 证明论 公理集合论 递归论 模型论 介绍命题逻辑和谓词逻辑的逻辑演算

第十七章　数理逻辑预备知识 §1 命题和联结词

命题 是指客观上能够判断真或假的陈述句。 (2)3 + 4 = 8。 (4)明天是晴天。 (5)本句话是错的。 (7)走，到图书馆去！ (8)你明天下午出去吗? (9)2既是素数又是偶数。 (10)雪不是白的。

基本的，原始的命题称为原子命题 语句(9)可由“ 2是素数”与“ 2是偶数” 这两个命题用“与”这个词联结组合而成 由更小的命题组合而成的命题称为复合命题。 将几个命题联结组合起来的方式称为联结词。

常用的联结词有下列5个: (1)联结词“非”，记为“”，表示“否定”的意思。 (2)联结词“合取”，记为“”，表示“并且”的意思。 (3)联结词“析取”，记为“”，表示“或”的意思。 (4)联结词“蕴含”，记为“→”，表示“如果…，则…”的意思。 (5)联结词“等价”，记为“”，表示“当且仅当”的意思。

由于命题是能够判断真假的陈述句，因此给定一个命题就可确定其是真或假。真和假是命题的值(或真假值)。 P为真当且仅当P为假； PQ为真当且仅当P、Q皆为真； PQ为真当且仅当P、Q中至少有一个为真； P→Q除P为真且Q为假这种情况外，皆为真； PQ为真当且仅当P、Q有相同真假值。

把组成一个复合命题的若干个原子命题用符号表示，那么就可用这些符号和联结词符号一起来表达该复合命题，这样的方式称为命题符号化。 例: 李明今天下午看电影或者看录像”， 用P表示“李明今天下午看电影”，用Q表示“李明今天下午看录像”，则原语句应表示成：PQ 明天中午12:00,他或者去北京或者去广州 只有在天晴时，我们才去郊游

利用联结词,我们可以把日常的命题写成符号串.那么是否任何符号串都是某个日常命题的符号化呢?回答是否定的. 例如:p,q就不是. 那么什么样的符号串才是合适的呢? 通常采用递归的方式: p,q是命题,则p,pq,pq, p→q,pq 也是命题 我们希望能够找到其他方式来定义.

如果把联结词看作为运算,把p,q看作为日常生活这个集合中的元素,那么利用运算的封闭性, 可以发现所谓p,q不对应某个日常命题,实质是p,q不在日常生活这个集合中. 因此我们就可以考虑能否从代数角度来引进有关逻辑的概念.这就需要引进泛代数的概念.

§2　泛代数

A上的n元运算实质上就是An→A的函数，t: An→A，n称为函数t的元。 例如：在群G中，可以定义一个一元运算i: G→G用来求逆元，即i(a)=a-1。 集合A上的0元运算为从集合A0(由于A0只有一个元素, 规定A0={})到集合A 的函数，即t0: {}→A。 A上的0元运算实质上是唯一对应了A中的某个元素，即给出A上的一个0元运算就是给出了A中的一个元素。

例如：A={1,2,3,4},t0(1)=1, t0(2)=2 把0元运算看作为A中的一个特定元素。 例如在群G中，定义0元运算e*:{}→G，使得e*()=e(这里e为群G的单位元) 0元运算e*实际上就给出了群G的单位元 不加区分地把0元运算e*就看作为单位元e，同样把e看作为0元运算。 必须说明的是: 0元运算实质上是一 个函数,但因唯一对应了A中某个元素a,才把该0元运算等同于元素a.

运算的定义存在一些缺陷。 设群G，H的乘法运算分别为：*G:GGG，*H:HHH， 实际使用时通常用同一记号*来表示 环R是一种带两个二元运算+,的代数系统 零环就是R={0}，这时+和同是二元函数RRR，但在环中应视为不同的运算 怎样既区分它们又表达它们共性的问题。

定义17.1:设ar为集合T到非负整数集N的函数，则称集合T和函数ar为一个类型(type)，记为T =(T,ar)，也可简记为T。 T既可表示类型T又可表示集合T。 构造T的子集Tn={tT|ar(t)=n}。 定义17.2:设A是一个集合，T为一个类型，T中每个元素t对应于A上的一个函数 tA:Aar(t)→A，则称集合A和{tA|tT}构成类型为T的一个代数A(Algebra)，或称为T-代数。元素tTn称为n元T-代数运算

注意: tA:Aar(t)→A,因此tA就是集合A上的ar(t)元运算。通常将函数即运算tA(a1,a2,, aar(T)),简写为t(a1,a2,, aar(T))，且用A同时表示集合A和类型T的一个代数A。

例:设T=({e,-,*},ar)。这里ar(e)=0,ar(-)=1, ar(*)=2 群G可以看作为上述类型的代数。 当e所对应的G中的元素e满足: 对G中任意元素a成立a*e=e*x=a,*满足结合律,对G中任意元素a,-(a)*a=a*(-(a))=e, 即为群. 当然并不是上述类型的T-代数都是群.

环可看作为类型T=({,-,+,*},ar)的代数 这里ar()=0,ar(-)=1,ar(+)=2,ar(*)=2 定义17.3:T-代数A,B相等当且仅当A=B，并且对所有的tT,有tA=tB，记为TA=TB

定义17.4：设A是一个T-代数，B为A的子集，如果将A上的运算限制在B上仍然构成一个T-代数，即：对任意的非负整数n，任意的tT以及b1,b2,,bar(t)B,有 tA(b1,, bar(t))B 成立(通常称子集B关于A上的运算是封闭的)，则称B是A的一个T-子代数。 由定义易知，任何子代数的交仍是子代数，而T-代数A的子集X，则不一定是A的子代数。

设A为T-代数，XA (1)U为A的一个T-子代数 (2)XU (3)若U'为A的一个T子代数，且XU',则UU'. 称U为包含X的最小子代数，通常称为由X生成的子代数,记为<X>T,在不引起误会时可记为 <X> 容易证明，一定存在唯一的包含X的最小子代数，即： <X>T=∩{U|U为A的子代数XU}。

定义17.5:设A,B是T-代数，是从A到B的映射，若对任意tT,a1,,anA(这里n=ar(t))，有： (tA(a1,,an))= tB((a1),,(an)),则称为从A到B的同态映射，当是满射时，称A和B是同态的。 两个同态映射的复合仍是同态映射 若是同态映射，而且是可逆的，则称为同构映射，称A,B是同构的。此时，逆函数-1是从B到A的同构映射。

定义17.6:设X是集合，G是一个T-代数，为X到G的函数,若对每个T-代数A和X到A的函数，都存在唯一的G到A的同态映射,使得=，则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变， 变 变， 也变 对给定的 和A，是唯一的

X G A   

引理17.1:若(G,)是X上的自由T-代数，则是内射。