17.1 命题和联结词
命题：可以判定真假的陈述句。（则悖论，祈使句，疑问句都不是命题）
原子命题：不能被分割为更小的命题的命题
例如：
-
2既是素数又是偶数
可以由$p: 2 是素数， 2是素数， 2是素数，q: 2 是偶数，由 2是偶数，由 2是偶数，由p\land q$联结得来
-
只有在天晴时，我们才去郊游
可以有 p : p: p:天晴， q : q: q:去郊游，由 q → p q\rightarrow p q→p联结得来(q蕴含p，郊游时一定天晴，但天晴时不一定去郊游)
常用的联结词
- 非： ¬ \neg ¬,表示否定
- 合取： ∧ \land ∧，表示并且
- 析取： ∨ \lor ∨，表示或
- 蕴含： → \rightarrow →,表示“如果…,则…”的意思
- 等价： ↔ \leftrightarrow ↔，表示当且仅当
命题
形式化的递归定义，
命题是一个符号串，满足：
- 字母集中每个元素都是命题
- 如果 P , Q P,Q P,Q是命题，那么 ¬ P , P ∧ Q , P ∨ Q , P → Q , P ↔ Q \neg P,P\land Q,P\lor Q,P\rightarrow Q,P\leftrightarrow Q ¬P,P∧Q,P∨Q,P→Q,P↔Q也是命题
- 有限次使用1和2
但我们注意到，如此定义，会出现形如 P ¬ , ∧ Q P\neg ,\land Q P¬,∧Q的命题，这在日常生活中是不存在的，但从代数的角度是可以的，为此需要引入泛代数的概念
17.2 泛代数
困难的一节。
元：在群论中，我们指出，集合 A A A上的 n n n元运算实际上就是一个 n n n元单值函数 t : A n → A t: A^n\rightarrow A t:An→A,其中 n n n在之后就称为 t t t的元。
在群G中，定义一个一元运算 i : G → G i:G\rightarrow G i:G→G求逆元，即 i ( a ) = a − 1 i(a)=a^{-1} i(a)=a−1
对于0元运算，实际上是从集合 A 0 A^0 A0(只有一个元素，通常记为 ∅ \varnothing ∅到A上的函数),即 t 0 : ∅ → A t_0:\varnothing\rightarrow A t0:∅→A,因此0元运算实质上是唯一对应了 A A A上的某个元素，故0元运算通常可视为 A A A中的一个特殊元素。
在群论中，定义0元运算 e ∗ : ∅ → G , e ∗ ( ∅ ) = e e^*:\varnothing \rightarrow G,e^*(\varnothing) =e e∗:∅→G,e∗(∅)=e,其中 e e e为单位元，实际上 e ∗ e^* e∗给出了群G的单位元，之后我们将 e ∗ e^* e∗看作单位元 e e e，也可以把 e e e看作0元运算。
定义1 类型
设 a r ar ar为集合 T T T到非负整数集 N N N的函数，则称集合 T T T和函数 a r ar ar为一个类型，记为 T = ( T , a r ) T=(T,ar) T=(T,ar),简记为 T T 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 t t对应于 A A A上的一个函数： t A : A a r ( t ) → A t_A:A^{ar(t)}\rightarrow A tA:Aar(t)→A，则称集合 A A A和 { t A ∣ t ∈ T } \{t_A|t\in T\} {tA∣t∈T}构成类型 T T T的一个代数 A A A,称为T-代数，元素 t ∈ T n t\in T_n t∈Tn称为 n n n元T-代数运算
定义3 T-代数相等
T-代数A,B相等 ⟺ ∀ t ∈ T , t A = t B \Longleftrightarrow \forall t\in T,t_A=t_B ⟺∀t∈T,tA=tB，记为 T A = T B T_A=T_B TA=TB
定义4 T-子代数
设A是一个T-代数，B为A的子集，如果将A上的运算限制在B上仍然构成一个T-代数，即：对任意的非负整数n，任意的 t ∈ T n . b 1 , b 2 , ⋯ , b n ∈ B t\in T_n.b_1,b_2,\cdots,b_n\in B t∈Tn.b1,b2,⋯,bn∈B，有 t A ( b 1 , ⋯ , b n ) ∈ B t_A(b_1,\cdots,b_n)\in B tA(b1,⋯,bn)∈B成立(封闭的)，则称B是A的一个T-子代数
定义5 T-代数同态
设A,B是T-代数， φ \varphi φ是从A到B的映射，若对任意 t ∈ T , a 1 , ⋯ , a n ∈ A ( n = a r ( t ) ) t\in T,a_1,\cdots,a_n\in A(n=ar(t)) t∈T,a1,⋯,an∈A(n=ar(t)),有 φ ( t A ( a 1 , ⋯ , a n ) ) = t B ( φ ( a 1 ) , ⋯ , φ ( a n ) ) \varphi(t_A(a_1,\cdots,a_n))=t_B(\varphi(a_1),\cdots,\varphi(a_n)) φ(tA(a1,⋯,an))=tB(φ(a1),⋯,φ(an))，则称 φ \varphi φ为从 A A A到 B B B的同态映射，当 φ \varphi φ是满射时，称A和B市同态的。
特别地，当 φ \varphi φ是同态映射，且可逆时，称 φ \varphi φ为同构映射，称 A , B A,B A,B是同构的，此时逆函数 φ − 1 \varphi ^{-1} φ−1是从B到A的同构映射。
定义6 自由T代数
设X是集合，G是一个T-代数， σ \sigma σ为X到G的函数，若对每个T-代数A和X到A的函数 τ \tau τ,都存在唯一的G到A的同态映射 φ \varphi φ，使得 φ σ = τ \varphi \sigma = \tau φσ=τ,则称 G G G(更严格地说是 ( G , σ ) (G,\sigma) (G,σ))是生成集X上的自由T-代数。X中的元素为生成元。
引理1 自由T-代数中的内射
若 ( G , σ ) (G,\sigma) (G,σ)是X上的自由T-代数，则 σ \sigma σ是内射
定理1 自由T-代数存在性
对任何集合X和类型T，存在X上的自由T-代数，并且这种T-代数在同构意义下是唯一的。
证明是复杂的， P227
其中，出现了T-代数的构造方式：
T-代数的构造方式
- G 0 = T 0 ∪ X G_0 =T_0\cup X G0=T0∪X,假定 T 0 ∩ X = ∅ T_0\cap X =\varnothing T0∩X=∅
- 假定 G r G_r Gr已经确定，则
G n = { ( t , a 1 , ⋯ , a k ) ∣ t ∈ T k , k > 0 , a i ∈ G r i , ∑ k r i = n − 1 } 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\} Gn={(t,a1,⋯,ak)∣t∈Tk,k>0,ai∈Gri,∑kri=n−1}
其中 G 0 G_0 G0可理解为原子命题， G n G_n Gn可理解为做了一些逻辑运算的若干个命题。
例如：
p , q ∈ G 0 , ¬ p ∈ G 1 , p ∧ q ∈ G 2 p,q\in G_0,\neg p \in G_1,p\land q \in G_2 p,q∈G0,¬p∈G1,p∧q∈G2
一个例子
注意，第一个元素为运算，例子中的 → \rightarrow →为二元运算，所以后面要选择两个元素，而由于 F F F是零元的，所以在 n > 0 n>0 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-代数的自由生成集的元素。
