Cổng NAND (và cổng NOR) có tính đầy đủ chức năng: chỉ dùng một loại cổng này, ghép đủ nhiều cái, là dựng được NOT, AND, OR — và vì mọi bảng chân trị đều viết được bằng ba phép đó, nên dựng được mọi mạch logic, kể cả cả một bộ vi xử lý. Trong công nghệ chip CMOS, NAND hai đầu vào chỉ cần 4 bóng bán dẫn, ít hơn AND (6 bóng), nên nó thật sự là viên gạch rẻ và được dùng nhiều.
NAND và NOR là gì
Nói bằng lời trước. Một máy bơm tưới cây có hai cảm biến: "đất đã ẩm" và "đang mưa". Bộ điều khiển cho bơm chạy trừ khi cả hai cùng báo. Đó là NAND: "không phải (ẩm và mưa)". Còn chuông báo "cửa đang khoá" chỉ kêu khi không cửa nào mở: "không phải (cửa trước mở hoặc cửa sau mở)" — đó là NOR.
Ký hiệu: a, b nhận 0 (sai) hoặc 1 (đúng); · là AND (và), + là OR (hoặc), dấu phẩy trên a' là NOT (không a); a ↑ b là NAND, a ↓ b là NOR.
| a | b | a · b | NAND: a ↑ b = (a·b)' | a + b | NOR: a ↓ b = (a+b)' |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 |
Cách nhớ nhanh: NAND chỉ ra 0 khi mọi đầu vào bằng 1; NOR chỉ ra 1 khi mọi đầu vào bằng 0.
"Đầy đủ chức năng" nghĩa là gì
Một tập phép toán được gọi là đầy đủ chức năng nếu với bất kỳ bảng chân trị nào, ta đều viết được một biểu thức chỉ dùng các phép trong tập đó cho ra đúng bảng ấy.
Bước một: tập {AND, OR, NOT} là đầy đủ. Lý do rất cụ thể — với mỗi dòng có kết quả 1 trong bảng chân trị, viết một tích "khớp đúng dòng đó", rồi OR tất cả lại. Ví dụ hàm f(a, b) bằng 1 ở hai dòng (a = 0, b = 1) và (a = 1, b = 0): f = a'·b + a·b'. Mọi bảng đều làm được như vậy (bảng toàn 0 thì viết a·a').
Bước hai: nếu dựng được NOT, AND, OR chỉ bằng NAND thì NAND cũng đầy đủ — vì cứ thay từng phép trong biểu thức trên bằng "cụm NAND" tương ứng.
Dựng NOT, AND, OR chỉ bằng NAND (hoặc chỉ bằng NOR)
NOT: nối chập hai đầu vào
a ↑ a = (a·a)' = a'. Kiểm: a = 0 thì 0 ↑ 0 = 1; a = 1 thì 1 ↑ 1 = 0. Đúng là phủ định. 1 cổng.
AND: NAND rồi đảo lại
a·b = ((a·b)')' = (a ↑ b)'. Dùng NOT vừa dựng: a·b = (a ↑ b) ↑ (a ↑ b). 2 cổng.
OR: nhờ luật De Morgan
Luật De Morgan nói: (a'·b')' = a + b — "không phải (cả hai đều không)" chính là "có ít nhất một". Mà (a'·b')' = a' ↑ b'. Thay a' = a ↑ a, b' = b ↑ b:
a + b = (a ↑ a) ↑ (b ↑ b). 3 cổng.
Kiểm OR đủ bốn dòng:
| a | b | a ↑ a | b ↑ b | (a↑a) ↑ (b↑b) | a + b |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
Hai cột cuối trùng nhau ở mọi dòng. Vậy {NAND} đầy đủ chức năng.
Làm tương tự với NOR
NOR là "bản đối ngẫu" của NAND: đổi vai AND với OR, đổi 0 với 1, mọi công thức vẫn đúng.
- NOT: a ↓ a = (a + a)' = a'. 1 cổng.
- OR: a + b = (a ↓ b) ↓ (a ↓ b). 2 cổng.
- AND: a·b = (a ↓ a) ↓ (b ↓ b), vì theo De Morgan (a' + b')' = a·b. 3 cổng.
Thử lại AND bằng NOR với a = 1, b = 0: a ↓ a = 0, b ↓ b = 1, rồi 0 ↓ 1 = (0 + 1)' = 0. Đúng 1·0 = 0. Với a = b = 1: a ↓ a = 0, b ↓ b = 0, 0 ↓ 0 = 1. Đúng 1·1 = 1.
Ví dụ giải đầy đủ: XOR bằng bốn cổng NAND
Thay thẳng a ⊕ b = a·b' + a'·b bằng các cụm ở trên sẽ tốn khá nhiều cổng. Có một cách gọn chỉ 4 cổng:
- t = a ↑ b
- u = a ↑ t
- v = b ↑ t
- kết quả = u ↑ v
| a | b | t = a↑b | u = a↑t | v = b↑t | u↑v | a ⊕ b |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
Vì sao đúng? Rút gọn bằng đại số: u = (a·t)' = (a·(a·b)')' = (a·(a' + b'))' = (a·b')' (vì a·a' = 0). Tương tự v = (a'·b)'. Khi đó u ↑ v = (u·v)' = u' + v' = a·b' + a'·b = a ⊕ b.
Thêm một bước: cổng t = a ↑ b đã có sẵn, nên số nhớ a·b của bộ cộng bán phần chỉ cần thêm một cổng t ↑ t. Cả bộ cộng bán phần (tổng và nhớ) dựng bằng 5 cổng NAND.
Vì sao chỉ AND và OR thì không đủ
Đây là phần logic đáng giá nhất của bài: chứng minh một tập phép toán không đầy đủ.
Khẳng định: mọi mạch chỉ gồm AND và OR, khi tất cả đầu vào bằng 1, thì đầu ra bằng 1. Lý do: 1·1 = 1 và 1 + 1 = 1, nên đi qua cổng nào thì giá trị 1 cũng giữ nguyên, tầng này sang tầng khác. Nhưng NOT cần biến đầu vào 1 thành 0. Vậy không mạch AND–OR nào làm được NOT, và {AND, OR} không đầy đủ.
Cùng kiểu lập luận "tìm một tính chất được bảo toàn" cho nhiều kết luận khác:
| Tập phép toán | Đầy đủ? | Lý do ngắn |
|---|---|---|
| {AND, OR, NOT} | Có | Viết mọi bảng dưới dạng tổng các tích |
| {AND, NOT} | Có | Dựng OR bằng De Morgan: a + b = (a'·b')' |
| {OR, NOT} | Có | Dựng AND bằng De Morgan: a·b = (a' + b')' |
| {NAND}, {NOR} | Có | Dựng được NOT, AND, OR như trên |
| {AND, OR} | Không | Toàn 1 vào thì toàn 1 ra, không dựng được NOT |
| {kéo theo →} | Không | 1 → 1 = 1, cũng bảo toàn "toàn 1" |
| {XOR} | Không | Toàn 0 vào thì ra 0 (0 ⊕ 0 = 0), không dựng được hằng 1 hay NOT |
Nhà logic Emil Post về sau phân loại trọn vẹn khi nào một tập phép toán hai giá trị là đầy đủ, dựa đúng trên những tính chất "được bảo toàn" kiểu này.
Từ bản thảo của Peirce tới con tàu lên Mặt Trăng
| Thời điểm | Mốc |
|---|---|
| Khoảng 1880 | Charles S. Peirce nhận ra một phép toán duy nhất (kiểu NOR, và cả NAND) đủ biểu diễn mọi phép logic; bản thảo chỉ được in sau khi ông mất. |
| 1913 | Henry Sheffer công bố bài báo xây dựng đại số Boole từ một phép toán duy nhất, ký hiệu nét gạch đứng — ngày nay gọi là "nét Sheffer" và thường hiểu là NAND (bài gốc diễn giải theo NOR; hai cách đối ngẫu, cho kết quả tương đương). |
| Thập niên 1960 | Máy tính dẫn đường của tàu Apollo được dựng từ vài nghìn vi mạch giống hệt nhau, mỗi vi mạch là hai cổng NOR ba đầu vào — một cách dùng đúng nghĩa đen tính đầy đủ của NOR. |
| Ngày nay | Thư viện cổng của nhà máy chip lấy NAND, NOR, NOT làm nền; bộ nhớ flash kiểu "NAND" cũng mang tên theo cách các ô nhớ được nối giống cổng NAND. |
Vì sao kỹ sư thích NAND hơn cả AND? Trong CMOS, cổng tự nhiên nhất là cổng có đảo: NOT cần 2 bóng bán dẫn, NAND và NOR hai đầu vào cần 4. Muốn AND thì phải lấy NAND rồi đảo thêm, thành 6. Giữa NAND và NOR, NAND thường được ưu tiên vì các bóng bán dẫn loại N (nhanh hơn) nằm nối tiếp, còn NOR thì loại P (chậm hơn) phải nối tiếp.
Bài tập
- Dựng a·b·c (AND ba đầu vào) chỉ bằng NAND hai đầu vào. — Đáp án: dựng x = a·b bằng 2 cổng, rồi x·c bằng 2 cổng nữa: 4 cổng.
- Tính (1 ↑ 0) ↑ (1 ↑ 1). — Đáp án: 1 ↑ 0 = 1; 1 ↑ 1 = 0; 1 ↑ 0 = 1.
- Vì sao {kéo theo, NOT} lại đầy đủ? — Đáp án: a + b tương đương a' → b, nên có OR và NOT; mà {OR, NOT} đầy đủ.
- Dựng NOT chỉ bằng NOR rồi kiểm với a = 1. — Đáp án: a ↓ a; 1 ↓ 1 = (1 + 1)' = 0.
- Một mạch chỉ gồm cổng AND và OR nhận đầu vào (1, 1, 1). Đầu ra có thể bằng 0 không? — Đáp án: không, vì AND và OR bảo toàn giá trị 1.
Dùng vào đâu
- Thi môn Kỹ thuật số: dạng "thực hiện hàm f chỉ bằng cổng NAND" gặp rất thường; quy trình là rút gọn f về dạng tổng các tích, rồi đổi theo De Morgan thành hai tầng NAND.
- Logic học: kỹ thuật chứng minh "không đầy đủ bằng tính chất bảo toàn" là một mẫu lập luận đẹp, dùng được cả ngoài mạch điện.
- Tự học: có những khoá học trực tuyến miễn phí dựng cả một máy tính đơn giản từ cổng NAND đi lên — lối vào rất tốt cho người thích nhìn thấy từng tầng.
Câu hỏi thường gặp
Cổng NAND là gì?
NAND là phép "không phải (a và b)": cho ra 0 chỉ khi mọi đầu vào bằng 1, các trường hợp khác cho ra 1. Nó là phủ định của cổng AND.
Vì sao cổng NAND được gọi là cổng vạn năng?
Vì chỉ dùng NAND là dựng được NOT, AND và OR, mà ba phép này đủ biểu diễn mọi bảng chân trị. Do đó mọi mạch logic, dù phức tạp tới đâu, đều dựng được chỉ bằng cổng NAND.
Dựng cổng OR từ NAND thế nào?
Dùng luật De Morgan: a + b = (a'·b')'. Đảo a và b bằng hai cổng NAND nối chập đầu vào, rồi đưa hai kết quả vào cổng NAND thứ ba: a + b = (a ↑ a) ↑ (b ↑ b).
Cổng NOR có vạn năng như NAND không?
Có. NOR là bản đối ngẫu của NAND: a ↓ a cho NOT, (a ↓ b) ↓ (a ↓ b) cho OR, (a ↓ a) ↓ (b ↓ b) cho AND. Máy tính dẫn đường của tàu Apollo được dựng chủ yếu từ cổng NOR.
Vì sao chỉ có AND và OR thì không dựng được mọi mạch?
Vì khi mọi đầu vào bằng 1, cổng AND và OR luôn cho ra 1, nên mọi mạch ghép từ chúng cũng cho ra 1. Phép NOT cần biến 1 thành 0, nên không thể dựng được.
