Hãy chứng minh tập $\{|\}$ và $\{\downarrow \}$ là đầy đủ trong đại số boole.

Ta định nghĩa phép toán $|$ (hay NAND) và phép toán $ \downarrow $ (hay NOR) như sau:

$1|1=0,1|0=0|1=0|0=1$ và $1\downarrow  1=1\downarrow 0=0\downarrow 1=0,0\downarrow 0=1$

Hãy chứng minh tập $\{|\}$ và $\{\downarrow \}$ là đầy đủ trong đại số boole.

Giải

Một tập là đầy đủ trong đại số Boole nếu tất cả các hàm Boole đều có thể biểu diễn bằng các phép toán trong tập đó.

Như ta đã biết ${.,\ +,\ -}$ là đầy đủ trong đại số Boole (do định nghĩa đại số Boole với 3 phép toán : Tích Boole, Tổng Boole, Phần bù).

Tập $\{.,-\}$ là đầy đủ vì có thể thay thế phép toán $+$ như sau : $x+y=\overline{\overline{x}.\overline{y}}$

Tập $\{+,-\}$ là đầy đủ vì có thể thay thế phép toán $.$ như sau : $x.y=\overline{x+y}$

Tập $\{.,+\}$ là không đầy đủ vì không thể biểu diễn thay thế phép toán $-$ được và hai phép toán $.$ và $+$ còn có thể thay thế lẫn nhau.

Tập $\{|\}$ là đầy đủ vì có thể thay thế hai phép toán $\{.,-\}$ như sau : $x.y=(x|y)|(y|x)\ ;\ \overline{x}=x|x$.

Tập $\{\downarrow\}$ là đầy đủ vì có thể thay thế hai phép toán $\{+,-\}$ như sau : $x+y=(x\downarrow y)\downarrow(x\downarrow y)\ ;\ \overline{x}=x\downarrow x$.