习题 7, 附录 0

令$R_1, R_2, \ldots, R_n$在理论$\mathscr{T}_0$中是不同的逻辑不可约关系（习题6）。令 $A_1, A_2, \ldots, A_m$ 为逻辑构造与基 $R_1, R_2, \ldots, R_n$。假设每个$R_j$被赋予了符号0、1之一。那么我们根据以下规则赋予每个$A_i$符号0、1之一： (1)如果$A_i$与$R_j$相同，则赋予$A_i$与$R_j$相同的符号； (2) 如果 $A_i$ 与 $\neg A_j$ 相同，其中 $A_j$ 先于 $A_i$，则如果 $A_j$ 的符号为 0（或 1），则给 $A_i$ 符号 1（或 0）； (3) 如果$A_i$与$\vee A_jA_k$相同，如果$A_j$和$A_k$都有符号1，则给$A_i$符号1；否则给$A_i$符号0。（我们是应用以下“符号规则”：

(a) 证明根据这些规则，只有一种方法可以为每个 $A_i$ 分配一个符号。

(b) 如果$R$是由$R_1, R_2, \ldots, R_n$逻辑构造而成，则$R$携带的符号与逻辑构造无关，基

其中出现$R$。

(c) 如果$R$和$S$是由$R_1, R_2, \ldots, R_n$逻辑构造出来的，并且如果$R$和$\Rightarrow RS$携带的符号为0，则$S$携带的符号为0。

(d) 假设从现在开始，$\mathscr{T}_0$ 的唯一公理是概形 S1 到 S4 提供的公理。令$R$为$\mathscr{T}_0$中的定理，并令$R_1, R_2, \ldots, R_n$为其逻辑分量。然而，证明$R_1, R_2, \ldots, R_n$的符号为0和1，$R$携带的符号为0。（首先证明$R$是$\mathscr{T}_0$公理的情况；一般情况下，考虑$R$的证明，并应用(c)） $\mathscr{T}_0$。

(e) 设$R$是$\mathscr{T}_0$中逻辑上不可约的关系。证明$R$和“非$R$”都不是$\mathscr{T}_0$中的定理。特别是，$\mathscr{T}_0$是不矛盾的（使用（d））。

(f) 令$R_1, R_2, \ldots, R_n$在$\mathscr{T}_0$中是不同的、逻辑上不可约的关系。考虑形式的所有关系“$R'_1$或$R'_2$或$\ldots$或$R'_n$”，其中对于每个$i$，$R'_i$是两个关系$R_i$之一，“不是$R_i$”。令 $S_1, S_2, \ldots, S_p$ 为关系。设$T_1, T_2, \ldots, T_q$为形式中的关系

“$S_{i_1}$ 和 $S_{i_2}$ 和 ... 和 $S_{i_r}$”，其中 $i_1$、$i_2$、...、$i_r$ 是指标中的任意严格递增的序列。最后，令$T_0$为关系“$R_1$或（不是$R_1$）”，即$\mathscr{T}$中的定理。证明从 $R_1$, $R_2$, ..., $R_n$ 逻辑构造的每个关系在 $\mathscr{T}$ 中都等价于关系 $T_0$, $T_1$, ..., $T_q$ 之一。 （首先证明$\mathscr{T}$中的每个关系$R_i$等价于关系$T_0$、$T_1$、...、$T_q$之一。如果$R$逻辑上是由$R_1$、$R_2$、...构建的， $R_n$，逐步论证一个逻辑构造与基$R_1$，$R_2$，...，$R_n$其中包含$R$。最后用(d)证明唯一性。）

(g) 令$\mathscr{T}$中的$R$为关系，并令$R_1$、$R_2$、...、$R_n$为其逻辑分量。那么$R$在$\mathscr{T}$中是定理当且仅当，然而符号0和1被分配给$R_1$，$R_2$，...，$R_n$，相应的，$R$携带的符号是0。