Bài tập 7, Phụ lục 0

Cho $R_1, R_2, \ldots, R_n$ là các quan hệ lôgic bất khả quy phân biệt (Bài tập 6) trong một lý thuyết $\mathscr{T}_0$. Cho $A_1, A_2, \ldots, A_m$ là một phép dựng lôgic có cơ sở là $R_1, R_2, \ldots, R_n$. Giả sử rằng mỗi $R_j$ được trang bị một trong hai dấu 0, 1. Khi đó ta gán cho mỗi $A_i$ một trong hai dấu 0, 1 theo các quy tắc sau đây: (1) nếu $A_i$ đồng nhất với $R_j$, thì gán cho $A_i$ cùng dấu như $R_j$; (2) nếu $A_i$ đồng nhất với $\neg A_j$, trong đó $A_j$ đứng trước $A_i$, thì gán cho $A_i$ dấu 1 (tương ứng 0) nếu $A_j$ mang dấu 0 (tương ứng 1); (3) nếu $A_i$ đồng nhất với $\vee A_jA_k$, thì gán cho $A_i$ dấu 1 nếu $A_j$ và $A_k$ đều mang dấu 1; nếu không thì gán cho $A_i$ dấu 0. (Ở đây ta áp dụng “quy tắc ký hiệu” sau đây:

(a) Chỉ ra rằng chỉ có một cách duy nhất gán một dấu cho mỗi $A_i$ phù hợp với các quy tắc này.

(b) Nếu $R$ được dựng theo lôgic từ $R_1, R_2, \ldots, R_n$, thì dấu mang bởi $R$ là độc lập với phép dựng lôgic, với cơ sở

trong đó $R$ xuất hiện.

(c) Nếu $R$ và $S$ được dựng theo lôgic từ $R_1, R_2, \ldots, R_n$, và nếu các dấu mang bởi $R$ và $\Rightarrow RS$ là 0, thì dấu mang bởi $S$ là 0.

(d) Giả sử từ nay rằng các tiên đề duy nhất của $\mathscr{T}_0$ là những tiên đề được cho bởi các lược đồ S1 đến S4. Cho $R$ là một định lý của $\mathscr{T}_0$, và cho $R_1, R_2, \ldots, R_n$ là các thành phần lôgic của nó. Tuy nhiên, hãy chứng minh rằng các dấu 0 và 1 được gán cho $R_1, R_2, \ldots, R_n$, và dấu mà $R$ mang là 0. (Trước hết hãy chứng minh điều này trong trường hợp $R$ là một tiên đề của $\mathscr{T}_0$; trong trường hợp tổng quát, hãy xét một chứng minh của $R$, và áp dụng (c)) $\mathscr{T}_0$.

(e) Cho $R$ là một quan hệ bất khả quy về mặt lôgic trong $\mathscr{T}_0$. Chứng minh rằng cả $R$ lẫn “không $R$” đều không là định lý trong $\mathscr{T}_0$. Đặc biệt, $\mathscr{T}_0$ là phi mâu thuẫn (dùng (d)).

(f) Cho $R_1, R_2, \ldots, R_n$ là các quan hệ phân biệt, bất khả quy về mặt lôgic trong $\mathscr{T}_0$. Xét tất cả các quan hệ có dạng “$R'_1$ hoặc $R'_2$ hoặc $\ldots$ hoặc $R'_n$” trong đó, với mỗi $i$, $R'_i$ là một trong hai quan hệ $R_i$, “không $R_i$”. Gọi $S_1, S_2, \ldots, S_p$ là các quan hệ đó. Gọi $T_1, T_2, \ldots, T_q$ là các quan hệ có dạng

`"$S_{i_1}$ và $S_{i_2}$ và ... và $S_{i_r}$", trong đó $i_1$, $i_2$, ..., $i_r$ là một dãy chỉ số tăng ngặt bất kỳ. Sau cùng, đặt $T_0$ là quan hệ "$R_1$ hoặc (không $R_1$)", là một định lý trong $\mathscr{T}$. Hãy chỉ ra rằng mọi quan hệ được dựng một cách lôgic từ $R_1$, $R_2$, ..., $R_n$ đều tương đương trong $\mathscr{T}$ với đúng một trong các quan hệ $T_0$, $T_1$, ..., $T_q$. (Trước hết hãy chỉ ra rằng mọi quan hệ $R_i$ đều tương đương trong $\mathscr{T}$ với một trong các quan hệ $T_0$, $T_1$, ..., $T_q$. Nếu $R$ được dựng một cách lôgic từ $R_1$, $R_2$, ..., $R_n$, hãy lập luận từng bước theo một phép dựng lôgic có cơ sở $R_1$, $R_2$, ..., $R_n$ mà chứa $R$. Sau cùng, dùng (d) để chứng minh tính duy nhất.)`

(g) Cho $R$ là một quan hệ trong $\mathscr{T}$, và gọi $R_1$, $R_2$, ..., $R_n$ là các thành phần lôgic của nó. Khi đó $R$ là một định lý trong $\mathscr{T}$ khi và chỉ khi, dù các dấu 0 và 1 được gán cho $R_1$, $R_2$, ..., $R_n$ như thế nào, dấu tương ứng mà $R$ mang là 0.