17.1 命題和聯結詞

? 命題：可以判定真假的陳述句。（則悖論，祈使句，疑問句都不是命題）

? 原子命題：不能被分割為更小的命題的命題

例如：

1. 2既是素數又是偶數

   可以由$p:$2是素數，$q:$2是偶數，由$p\land q$聯結得來

2. 只有在天晴時，我們才去郊游

   可以有$p:$天晴，$q:$去郊游，由$q\to p$聯結得來(q蘊含p，郊游時一定天晴，但天晴時不一定去郊游)

常用的聯結詞

1. 非：$?$,表示否定
2. 合取：$\wedge$，表示并且
3. 析取：$\vee$，表示或
4. 蘊含：$\to$,表示“如果…,則…”的意思
5. 等價：$?$，表示當且僅當

命題

? 形式化的遞歸定義，

? 命題是一個符號串，滿足：

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

但我們注意到，如此定義，會出現形如$P?,\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$(只有一個元素，通常記為$?$到A上的函數),即$t_0:?\to A$,因此0元運算實質上是唯一對應了$A$上的某個元素，故0元運算通常可視為$A$中的一個特殊元素。

? 在群論中，定義0元運算$e^{?}:?\to G,e^{?}(?)=e$,其中$e$為單位元，實際上$e^{?}$給出了群G的單位元，之后我們將$e^{?}$看作單位元$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相等$??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,?,b_n\in B$，有$t_A(b_1,?,b_n)\in B$成立(封閉的)，則稱B是A的一個T-子代數

定義5 T-代數同態

? 設A,B是T-代數，$\phi$是從A到B的映射，若對任意$t\in T,a_1,?,a_n\in A(n=ar(t))$,有$\phi (t_A(a_1,?,a_n))=t_B(\phi (a_1),?,\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=?$
2. 假定$G_r$已經確定，則

$$G_n=\{(t,a_1,?,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,?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-代數的自由生成集的元素。