Năm 1937, Claude Shannon, khi đó là học viên cao học 21 tuổi ở MIT, viết luận văn thạc sĩ chỉ ra rằng mọi mạch gồm công tắc và rơ-le đều có thể mô tả bằng đại số Boole: nối tiếp là "và", song song là "hoặc", tiếp điểm thường đóng là "không". Nhờ đó, thiết kế mạch chuyển mạch thôi là nghề thử – sai, trở thành phép tính rút gọn được trên giấy. Luận văn công bố năm 1938 với tên A Symbolic Analysis of Relay and Switching Circuits, và là gốc của cách mọi con chip ngày nay được thiết kế.
Bối cảnh: một cỗ máy đầy rơ-le và một môn logic "vô dụng"
Đầu thập niên 1930, hai thứ tồn tại song song mà gần như không ai nối với nhau.
Một bên là đại số Boole. George Boole công bố The Mathematical Analysis of Logic năm 1847 và An Investigation of the Laws of Thought năm 1854, biến các phán đoán "đúng/sai" thành phép tính với hai giá trị 1 và 0. Tới đầu thế kỷ 20, môn này chủ yếu nằm trong giáo trình triết học và toán, được coi là đẹp nhưng ít dùng.
Bên kia là kỹ thuật chuyển mạch: tổng đài điện thoại, hệ thống tín hiệu đường sắt, tủ điều khiển máy công nghiệp. Những mạch này có hàng trăm, hàng nghìn rơ-le. Kỹ sư thiết kế chúng bằng kinh nghiệm, vẽ sơ đồ rồi thử, sửa. Không ai có cách chắc chắn để biết một mạch đã gọn nhất chưa, hay hai sơ đồ khác nhau có làm cùng một việc không.
Shannon đứng ở giao điểm. Thời đại học ở Michigan, ông học cả kỹ thuật điện lẫn toán, và đã gặp đại số Boole. Năm 1936 ông tới MIT, làm trợ lý cho cỗ máy phân tích vi phân của Vannevar Bush — một máy tính cơ học khổng lồ, có phần mạch điều khiển bằng rơ-le. Nhìn mớ rơ-le ấy với cái đầu đã quen đại số Boole, ông nhận ra hai thứ thật ra là một.
Ý tưởng cốt lõi: công tắc là một biến logic
Một công tắc chỉ có hai trạng thái: đóng (dòng điện đi qua) hoặc mở (dòng điện bị chặn). Một mệnh đề trong logic Boole cũng chỉ có hai giá trị: đúng hoặc sai. Shannon cho mỗi tiếp điểm ứng với một biến, rồi chỉ ra rằng cách nối dây ứng với phép toán logic.
Lấy ví dụ đời thường trước. Một bình nóng lạnh chỉ chạy khi cầu dao tổng bật và công tắc trên tường bật: hai công tắc nối tiếp. Một hành lang có đèn sáng khi có người bấm nút ở đầu này hoặc bấm nút ở đầu kia: hai nút nối song song. Còn đèn báo kiểu "sáng khi cửa không đóng" dùng tiếp điểm thường đóng: cửa đóng thì tiếp điểm mở ra.
Ghi bằng ký hiệu theo quy ước ngày nay — 1 là "dẫn điện / đúng", 0 là "không dẫn / sai", · là "và", + là "hoặc", dấu phẩy trên x' là "không x":
| Trong mạch điện | Trong đại số Boole | Lời nói thường |
|---|---|---|
| Tiếp điểm x đóng | x = 1 | "x đúng" |
| Hai tiếp điểm nối tiếp | x · y | "x và y" |
| Hai tiếp điểm song song | x + y | "x hoặc y" |
| Tiếp điểm thường đóng của rơ-le x | x' | "không x" |
| Dây nối thẳng (luôn dẫn) | 1 | hằng đúng |
| Mạch hở hẳn | 0 | mâu thuẫn |
Một chi tiết lịch sử hay bị bỏ qua: trong luận văn gốc, Shannon dùng quy ước ngược với bảng trên. Ông đo "độ cản trở" (hindrance) của mạch: 0 nghĩa là mạch đóng, 1 nghĩa là mạch hở. Với quy ước đó, nối tiếp ứng với phép cộng và song song ứng với phép nhân. Hai cách quy ước là đối ngẫu của nhau, cho kết quả tương đương; giới kỹ thuật về sau chọn cách "1 là dẫn điện" vì dễ đọc hơn.
Ví dụ giải đầy đủ: rút gọn mạch bằng phép tính
Điểm mạnh nhất của luận văn không nằm ở bảng đối chiếu, mà ở chỗ: khi mạch đã thành biểu thức, mọi luật của đại số Boole đều dùng được để rút gọn mạch. Ba ví dụ dưới đây là ví dụ minh hoạ tự đặt, theo đúng tinh thần đó.
Ví dụ 1: bốn tiếp điểm hoá ra chỉ cần một
Một mạch có hai nhánh song song. Nhánh trên: tiếp điểm x nối tiếp tiếp điểm y. Nhánh dưới: tiếp điểm x nối tiếp tiếp điểm thường đóng y'. Biểu thức:
f = x·y + x·y'
Rút gọn từng bước:
- Đặt x làm nhân tử chung (luật phân phối): f = x·(y + y').
- y + y' luôn bằng 1 (luật bù, bản đại số của quy luật bài trung: y đúng hoặc không đúng): f = x·1.
- x·1 = x: f = x.
Kết luận: cả mạch bốn tiếp điểm chỉ làm đúng việc của một tiếp điểm x. Rơ-le y hoàn toàn thừa. Thử lại bằng giá trị cụ thể: x = 1, y = 0 thì nhánh trên hở (y = 0), nhánh dưới dẫn (x = 1, y' = 1), mạch dẫn — đúng bằng x = 1. x = 0 thì cả hai nhánh đều có x hở, mạch không dẫn — đúng bằng x = 0.
Ví dụ 2: bớt một tiếp điểm nhờ đặt nhân tử chung
f = x·y + x·z (hai nhánh song song, mỗi nhánh hai tiếp điểm, tổng bốn). Theo luật phân phối: f = x·(y + z), tức x nối tiếp với cụm y song song z — chỉ còn ba tiếp điểm. Kiểm đủ 8 trường hợp:
| x | y | z | x·y + x·z | x·(y + z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Hai cột cuối trùng nhau ở cả 8 dòng, nên hai mạch tương đương.
Ví dụ 3: mạch biểu quyết ba người
Ban giám khảo ba người, mỗi người một nút bấm x, y, z. Đèn "thông qua" sáng khi có ít nhất hai người bấm. Viết thẳng từ lời: "x và y, hoặc y và z, hoặc x và z":
f = x·y + y·z + x·z (ba nhánh, sáu tiếp điểm).
Gom hai hạng tử có x: x·y + x·z = x·(y + z). Vậy f = x·(y + z) + y·z — năm tiếp điểm. Thử lại: x = 1, y = 0, z = 1 (hai người bấm): x·(y + z) = 1·1 = 1, đèn sáng — đúng. x = 1, y = 0, z = 0 (một người): x·(y + z) = 1·0 = 0 và y·z = 0, đèn tắt — đúng. x = 0, y = 1, z = 1: x·(y + z) = 0 nhưng y·z = 1, đèn sáng — đúng.
Với vài rơ-le, tiết kiệm một tiếp điểm có vẻ nhỏ. Với tổng đài hàng nghìn rơ-le, mỗi rơ-le là tiền, là chỗ có thể hỏng, là điện năng — nên phép rút gọn trên giấy đáng giá thật.
Luận văn còn làm được gì nữa
Shannon không dừng ở rút gọn. Luận văn đi theo cả hai chiều:
- Phân tích: cho một mạch, viết ra biểu thức, biết chính xác khi nào nó dẫn điện.
- Tổng hợp: cho một yêu cầu bằng lời ("đèn sáng khi…"), viết biểu thức, rút gọn, rồi mới vẽ mạch. Đây là chiều quan trọng hơn: kỹ sư bắt đầu từ logic chứ không từ dây điện.
Trong số các ví dụ ứng dụng, luận văn có thiết kế một mạch cộng hai số nhị phân bằng rơ-le và một ổ khoá điện tổ hợp. Mạch cộng là chi tiết đáng nhớ: nó cho thấy máy móc làm được số học bằng chính phép logic, ý tưởng sẽ thành bộ số học trong mọi bộ vi xử lý.
Dòng thời gian từ Boole tới con chip
| Năm | Sự kiện |
|---|---|
| 1847 | George Boole công bố The Mathematical Analysis of Logic |
| 1854 | Boole công bố An Investigation of the Laws of Thought |
| Thập niên 1930 | Ở Nhật, kỹ sư Akira Nakashima cũng phát triển lý thuyết mạch chuyển mạch, độc lập với Shannon |
| 1937 | Shannon hoàn thành luận văn ở MIT; cùng năm, George Stibitz ở Bell Labs ghép rơ-le thành một mạch cộng nhị phân nhỏ ngay tại bàn bếp nhà mình |
| 1938 | Luận văn được đăng thành bài báo "A Symbolic Analysis of Relay and Switching Circuits" |
| 1948 | Shannon công bố lý thuyết thông tin (một hướng khác hẳn, xem các bài về bit) |
| 1953 | Maurice Karnaugh đưa ra bìa Karnaugh để rút gọn biểu thức logic bằng hình |
Điều cần nói rõ: Shannon không phát minh ra máy tính, cũng không phải người duy nhất thấy mối liên hệ giữa logic và mạch. Đóng góp của ông là trình bày trọn vẹn, có hệ thống và dùng được ngay, đúng lúc ngành điện tín, điện thoại cần nó. Vì vậy luận văn này thường được nhắc đến như một trong những luận văn thạc sĩ có ảnh hưởng nhất thế kỷ 20.
Vì sao ý tưởng này sống lâu đến vậy
Rơ-le sau đó bị đèn điện tử thay, rồi tới bóng bán dẫn, rồi mạch tích hợp chứa hàng tỉ bóng bán dẫn. Vật liệu đổi liên tục, nhưng lớp logic nằm trên vẫn y nguyên: một bóng bán dẫn trong chip vẫn chỉ là một công tắc đóng/mở, và kỹ sư vẫn thiết kế bằng biểu thức Boole trước khi phần mềm chuyển nó thành hình học trên tấm silicon.
Ý nghĩa logic sâu hơn: luận văn tách chức năng khỏi vật liệu. Hai mạch khác hẳn nhau về dây dẫn mà cùng biểu thức thì làm cùng một việc. Đây cũng là tinh thần của logic hình thức: lập luận đúng hay sai do khuôn của nó, không do nội dung cụ thể.
Dùng vào đâu
- Học sinh, sinh viên kỹ thuật: môn Kỹ thuật số, Điện tử số bắt đầu đúng từ bảng đối chiếu ở trên. Nắm chắc luật phân phối, luật De Morgan, luật bài trung là rút gọn được phần lớn bài tập.
- Người làm điện dân dụng, tủ điều khiển: sơ đồ điều khiển bằng contactor, rơ-le trung gian vẫn đọc được bằng logic Boole. Viết biểu thức ra giấy giúp phát hiện tiếp điểm thừa hoặc trường hợp bị bỏ sót. Phần thi công thực tế thì luôn để thợ có chứng chỉ làm.
- Người học lập trình: câu điều kiện if (a && b || c) chính là mạch song song – nối tiếp của Shannon viết bằng chữ.
- Đọc thêm: bản luận văn gốc khá dễ đọc với người đã biết đại số Boole; sau đó nên tìm hiểu bìa Karnaugh và các cổng NAND, NOR — những bước tiếp theo của cùng một mạch ý tưởng.
Câu hỏi thường gặp
Luận văn thạc sĩ của Claude Shannon năm 1937 nói về gì?
Luận văn chỉ ra rằng mạch gồm công tắc và rơ-le có thể mô tả và tính toán bằng đại số Boole: nối tiếp ứng với "và", song song ứng với "hoặc", tiếp điểm thường đóng ứng với "không". Nhờ vậy, kỹ sư có thể phân tích, rút gọn và thiết kế mạch bằng phép tính thay vì thử – sai.
Tên luận văn của Shannon là gì và công bố năm nào?
Tên là "A Symbolic Analysis of Relay and Switching Circuits". Shannon hoàn thành ở MIT năm 1937 và nội dung được đăng thành bài báo năm 1938.
Ai nghĩ ra đại số Boole, Boole hay Shannon?
George Boole xây dựng đại số logic từ giữa thế kỷ 19 (sách năm 1847 và 1854). Shannon không phát minh đại số này; ông là người đem nó áp vào mạch điện một cách có hệ thống, gần một thế kỷ sau.
Vì sao mạch nối tiếp lại ứng với phép "và"?
Hai công tắc nối tiếp chỉ cho dòng điện qua khi cả hai cùng đóng; chỉ cần một cái mở là mạch đứt. Đó đúng là điều kiện của "p và q": chỉ đúng khi cả p lẫn q đúng.
Luận văn của Shannon khác lý thuyết thông tin năm 1948 thế nào?
Luận văn 1937 nói về cách dùng logic để thiết kế mạch chuyển mạch. Lý thuyết thông tin 1948 là công trình khác, đo lượng thông tin bằng bit và tìm giới hạn truyền tin qua kênh có nhiễu. Hai công trình cùng một tác giả nhưng giải hai bài toán khác nhau.
