习题 6, 附录 0

关系在理论中，如果$\mathscr{T}$以关系符号开头，则被认为是“逻辑上不可约”。令 $R_1$, $R_2$, ..., $R_n$ 与 $\mathscr{T}$ 中逻辑上不可约的关系不同。具有基 $R_1$、$R_2$、...、$R_n$ 的*逻辑构造* 是 $\mathscr{T}$ 中组合的任意序列 $A_1$、$A_2$、...、$A_p$，使得每个$A_i$满足以下条件之一： (1) $A_i$是关系$R_1$、$R_2$、...、$R_n$之一； (2) 在$A_i$之前存在集合$A_j$，使得$A_i$为$\neg A_j$； (3) 在$A_i$之前存在两个组合、$A_j$和$A_k$，使得$\vee A_i$是$A_j A_k$。

(a) 证明组合在逻辑构造和基中

关系位于 $\mathscr{T}$ 中。出现在这样的逻辑构造中的关系据说是由$R_1$，$R_2$，...，$R_n$“逻辑构造”的。

(b) 如果$R$和$S$是由$R_1$、$R_2$、...、$R_n$逻辑构造而成，那么$\neg R$、$\vee RS$、$\Rightarrow RS$、“$R$和$S$”也是如此， $R \Leftrightarrow S$。

(c) 设$\mathscr{T}$中的$R$为关系。考虑序列或关系定义如下。首先，写$R$。如果 $R$ 逻辑上不可约，就到此为止。如果没有，则写下一个汇编或 $R$ 的先行词组合 （这是明确确定的 关系）。然后写出前面的组合的集合或组合先行词，这些集合或组合在逻辑上不是不可约的；等等。令 $R_1$, $R_2$, ..., $R_n$ 成为从该构造产生的明显逻辑上不可约的关系；它们被称为$R$的*逻辑组件*。证明 $R$ 是由其逻辑组件逻辑构造的，但是如果关系或序列之一

省略了$R_1, R_2, \ldots, R_n$，那么$R$就不是从剩余的$(n-1)$关系逻辑上构造出来的。

(d) 设 $R$ 为关系，并令 $R_1, R_2, \ldots, R_n$ 为逻辑上不可约的关系，使得 (1) $R$ 逻辑上由 $R_1, R_2, \ldots, R_n$ 构造而成，(2) 如果我们从序列 $R_1, R_2, \ldots, R_n$ 中省略一个关系，则$R$ 不是从剩余的关系逻辑上构造出来的。证明$R_1, R_2, \ldots, R_n$是$R$的逻辑分量。