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

Một quan hệ trong một lý thuyết $\mathscr{T}$ được gọi là bất khả quy lôgic nếu nó bắt đầu bằng một dấu quan hệ. Cho $R_1$, $R_2$, ..., $R_n$ là các quan hệ bất khả quy lôgic phân biệt trong $\mathscr{T}$. Một phép dựng lôgic có cơ sở là $R_1$, $R_2$, ..., $R_n$ là mọi dãy $A_1$, $A_2$, ..., $A_p$ các dãy ký hiệu trong $\mathscr{T}$ sao cho mỗi $A_i$ thỏa mãn một trong các điều kiện sau đây : (1) $A_i$ là một trong các quan hệ $R_1$, $R_2$, ..., $R_n$; (2) tồn tại một dãy ký hiệu $A_j$ đứng trước $A_i$ sao cho $A_i$ là $\neg A_j$; (3) tồn tại hai dãy ký hiệu $A_j$ và $A_k$ đứng trước $A_i$ sao cho $\vee A_i$ là $A_j A_k$.

(a) Chứng minh rằng các dãy ký hiệu trong một phép dựng lôgic có cơ sở

là các quan hệ trong $\mathscr{T}$. Một quan hệ xuất hiện trong một phép dựng lôgic như vậy được gọi là được dựng một cách lôgic từ $R_1$, $R_2$, ..., $R_n$.

(b) Nếu $R$ và $S$ được xây dựng một cách lôgic từ $R_1$, $R_2$, ..., $R_n$, thì $\neg R$, $\vee RS$, $\Rightarrow RS$, "$R$ và $S$", $R \Leftrightarrow S$ cũng vậy.

(c) Cho $R$ là một quan hệ trong $\mathscr{T}$. Xét dãy các quan hệ được xác định như sau. Trước hết, viết $R$. Nếu $R$ là bất khả quy về mặt lôgic, thì dừng ở đó. Nếu không, tiếp đó viết dãy ký hiệu hoặc các dãy ký hiệu đi trước $R$ (chúng là những quan hệ được xác định rõ ràng). Sau đó viết dãy ký hiệu hoặc các dãy ký hiệu đi trước những dãy ký hiệu ở trước mà không bất khả quy về mặt lôgic; và cứ tiếp tục như vậy. Gọi $R_1$, $R_2$, ..., $R_n$ là các quan hệ bất khả quy về mặt lôgic phân biệt thu được từ phép dựng này; chúng được gọi là các thành phần lôgic của $R$. Hãy chỉ ra rằng $R$ được dựng một cách lôgic từ các thành phần lôgic của nó, nhưng rằng nếu một trong các quan hệ của dãy

$R_1, R_2, \ldots, R_n$ bị bỏ đi, thì $R$ không được dựng một cách lôgic từ $(n-1)$ quan hệ còn lại.

(d) Cho $R$ là một quan hệ và cho $R_1, R_2, \ldots, R_n$ là các quan hệ bất khả quy về mặt lôgic phân biệt sao cho (1) $R$ được xây dựng về mặt lôgic từ $R_1, R_2, \ldots, R_n$, (2) nếu ta bỏ đi một quan hệ khỏi dãy $R_1, R_2, \ldots, R_n$, thì $R$ không được xây dựng về mặt lôgic từ các quan hệ còn lại. Hãy chỉ ra rằng $R_1, R_2, \ldots, R_n$ là các thành phần lôgic của $R$.