数理逻辑：1、预备知识

17.1 命题和联结词

​ 命题：可以判定真假的陈述句。（则悖论，祈使句，疑问句都不是命题）

​ 原子命题：不能被分割为更小的命题的命题

例如：

1. 2既是素数又是偶数

   可以由$p:$2是素数，$q:$2是偶数，由$p\land q$联结得来

2. 只有在天晴时，我们才去郊游

   可以有$p:$天晴，$q:$去郊游，由$q\to p$联结得来(q蕴含p，郊游时一定天晴，但天晴时不一定去郊游)

常用的联结词

1. 非：$\neg$,表示否定
2. 合取：$\wedge$，表示并且
3. 析取：$\vee$，表示或
4. 蕴含：$\to$,表示“如果…,则…”的意思
5. 等价：$\leftrightarrow$，表示当且仅当

命题

​ 形式化的递归定义，

​ 命题是一个符号串，满足：

1. 字母集中每个元素都是命题
2. 如果$P,Q$是命题，那么$\neg P,P\wedge Q,P\vee Q,P\to Q,P\leftrightarrow Q$也是命题
3. 有限次使用1和2

但我们注意到，如此定义，会出现形如$P\neg ,\wedge Q$的命题，这在日常生活中是不存在的，但从代数的角度是可以的，为此需要引入泛代数的概念

17.2 泛代数

​ 困难的一节。

元：在群论中，我们指出，集合$A$上的$n$元运算实际上就是一个$n$元单值函数$t:A^n\to A$,其中$n$在之后就称为$t$的元。

​ 在群G中，定义一个一元运算$i:G\to G$求逆元，即$i(a)=a^{-1}$

​ 对于0元运算，实际上是从集合$A^0$(只有一个元素，通常记为$\varnothing$到A上的函数),即$t_0:\varnothing \to A$,因此0元运算实质上是唯一对应了$A$上的某个元素，故0元运算通常可视为$A$中的一个特殊元素。

​ 在群论中，定义0元运算$e^{\ast }:\varnothing \to G,e^{\ast }(\varnothing )=e$,其中$e$为单位元，实际上$e^{\ast }$给出了群G的单位元，之后我们将$e^{\ast }$看作单位元$e$，也可以把$e$看作0元运算。

定义1 类型

​ 设$ar$为集合$T$到非负整数集$N$的函数，则称集合$T$和函数$ar$为一个类型，记为$T=(T,ar)$,简记为$T$。此外，令 T n = { t ∈ T ∣ a r ( t ) = n } T_n=\{t\in T| ar(t) =n\} Tn​={t∈T∣ar(t)=n}

定义2 T-代数

​ A是一个集合，T是一个类型，T中每个元素$t$对应于$A$上的一个函数：$t_A:A^{ar(t)}\to A$，则称集合$A$和 { t A ∣ t ∈ T } \{t_A|t\in T\} {tA​∣t∈T}构成类型$T$的一个代数$A$,称为T-代数，元素$t\in T_n$称为$n$元T-代数运算

定义3 T-代数相等

​ T-代数A,B相等$⟺\forall t\in T,t_A=t_B$，记为$T_A=T_B$

定义4 T-子代数

​ 设A是一个T-代数，B为A的子集，如果将A上的运算限制在B上仍然构成一个T-代数，即：对任意的非负整数n，任意的$t\in T_n.b_1,b_2,\cdots ,b_n\in B$，有$t_A(b_1,\cdots ,b_n)\in B$成立(封闭的)，则称B是A的一个T-子代数

定义5 T-代数同态

​ 设A,B是T-代数，$\phi$是从A到B的映射，若对任意$t\in T,a_1,\cdots ,a_n\in A(n=ar(t))$,有$\phi (t_A(a_1,\cdots ,a_n))=t_B(\phi (a_1),\cdots ,\phi (a_n))$，则称$\phi$为从$A$到$B$的同态映射，当$\phi$是满射时，称A和B市同态的。

​ 特别地，当$\phi$是同态映射，且可逆时，称$\phi$为同构映射，称$A,B$是同构的，此时逆函数${\phi }^{-1}$是从B到A的同构映射。

定义6 自由T代数

​ 设X是集合，G是一个T-代数，$\sigma$为X到G的函数，若对每个T-代数A和X到A的函数$\tau$,都存在唯一的G到A的同态映射$\phi$，使得$\phi \sigma =\tau$,则称$G$(更严格地说是$(G,\sigma )$)是生成集X上的自由T-代数。X中的元素为生成元。

引理1 自由T-代数中的内射

​ 若$(G,\sigma )$是X上的自由T-代数，则$\sigma$是内射

定理1 自由T-代数存在性

​ 对任何集合X和类型T，存在X上的自由T-代数，并且这种T-代数在同构意义下是唯一的。

​ 证明是复杂的， P227

​ 其中，出现了T-代数的构造方式：

T-代数的构造方式

1. $G_0=T_0\cup X$,假定$T_0\cap X=\varnothing$
2. 假定$G_r$已经确定，则

$$G_n=\{(t,a_1,\cdots ,a_k)|t\in T_k,k>0,a_i\in G_{r_i},\sum ^k{r}_i=n-1\}$$

​ 其中$G_0$可理解为原子命题，$G_n$可理解为做了一些逻辑运算的若干个命题。

​ 例如：

​ $p,q\in G_0,\neg p\in G_1,p\wedge q\in G_2$

​ 一个例子

注意，第一个元素为运算，例子中的$\to$为二元运算，所以后面要选择两个元素，而由于$F$是零元的，所以在$n>0$时，不能取F

由这种构造方式，我们可以自然地得到一个推论

推论1

​ 设G是可列集 X = { x 1 , x 2 , ⋯ } X=\{x_1,x_2,\cdots\} X={x1​,x2​,⋯}上地自由T-代数，则G中每个元素都是某个有限子集 X n = { x 1 , ⋯ , x n } X_n=\{x_1,\cdots,x_n\} Xn​={x1​,⋯,xn​}所生成地自由T-代数中的元素。

定义 7 T-代数变量

​ 一个T-代数变量是一个自由T-代数的自由生成集的元素。