Chủ đề này có 3 trả lời

[Ispectorgadget]

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.

[Kool LL]

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.

 

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$.

[DOTOANNANG]

Đại số Boole Veroff:

1. $x\mid y= y\mid x$ (tính giao hoán)
2. $\left ( x\mid y \right )\mid\left ( x\mid \left ( y\mid z \right ) \right )= x$

Robert Veroff đã giải quyết trọn vẹn câu hỏi thứ hai của Stephen Wolfram: Có thể viết Đại số Boole chỉ với hai tiên đề, và "Robert Veroff đã viết ra với ít nhất số lượng thành phần". Nhìn thấy tính không kết hợp của $\mid$ (NAND) với hai instructions:

1. $\left ( x\mid y \right )\mid\left ( y\mid y \right )= y$ (dấu *, ins.-22, trang 4)
2. $x\mid\left (  y\mid\left ( y\mid y \right ) \right )= x\mid x$ (dấu *, ins.-64, trang 5)

Nhận xét: Sử dụng tính đối ngẫu (Dual principle) của Đại số Boole (Đại số Veroff), NAND đầy đủ nên kết luận NOR đầy đủ.

[DOTOANNANG]

Định nghĩa

Ta có thể tạo một digital logic cho majority function $\mathfrak{M}$ yêu cầu $3$ đầu vào chỉ với NAND-gates bằng cách thay mọi toán tử của dạng chuẩn tắc (AND và OR) $\mathfrak{M}= \bigvee\left ( x\wedge y \right )$ bằng NAND. Đồng nhất thức đại số Boole là
$$\mathfrak{M}\left ( \mathfrak{M}\left ( x, {x}', y \right ), {\mathfrak{M}\left ( \mathfrak{M}\left ( z, u, v \right ), w, \mathfrak{M}\left ( z, u, v_{6} \right ) \right )}', \mathfrak{M}\left ( u, \mathfrak{M}\left ( v_{6}, w, v \right ), z \right ) \right )= y$$

—Padmanabhan, R. and W. McCune: 1995, ‘Single Identities for Ternary Boolean Algebras’. Computers and Mathematics with Applications 29(2), 13–16.

Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 31-10-2023 - 14:41