Đại số Boole và bản đồ Karnaugh

Luận văn thạc sĩ đã xây dựng nên kỷ nguyên số

• Năm 1937, một sinh viên 21 tuổi tên Claude Shannon nhận thấy rằng các rơ-le điện thoại mà anh đang nghiên cứu đang làm giống hệt những gì George Boole đã sáng tạo ra algebra vào tám mươi năm trước để suy luận về đúng và sai.
• Nếu một công tắc là biến Boolean, thì một mạch điện là một biểu thức, và việc đơn giản hóa biểu thức loại bỏ các cổng từ mạch. Ít cổng hơn có nghĩa là rẻ hơn, nhanh hơn và tiêu thụ ít năng lượng hơn.
• Luận văn của ông được gọi là quan trọng nhất trong thế kỷ. Mọi thứ trên trang này đều là một ý tưởng duy nhất đó được sử dụng như một công cụ.
• Bài học này là algebra Boolean, định luật De Morgan, và bản đồ Karnaugh thực hiện cùng chức năng bằng mắt thường.

Ký hiệu và các định luật

• + có nghĩa là OR, · có nghĩa là AND và thường bị bỏ qua, và một đường gạch ngang ở trên có nghĩa là NOT. Một bảng chân lý mô tả đầy đủ cùng một đối tượng.
• Identity (Bất biến): $A + 0 = A$ và $A \cdot 1 = A$. Null (Zero): $A + 1 = 1$ và $A \cdot 0 = 0$.
• Idempotent (Lũy thừa): $A + A = A$. Inverse (Ngược): $A + \overline{A} = 1$ và $A \cdot \overline{A} = 0$.
• Absorption (Hấp thụ): $A + A\cdot B = A$, bởi vì nếu $A$ là đúng thì toàn bộ biểu thức là đúng bất kể $B$ là gì.

Định luật De Morgan

• Định luật De Morgan là hai định luật mà đề thi yêu cầu bạn sử dụng bằng tên gọi:

• Công thức bằng lời: phủ định toàn bộ, hoán đổi AND và OR, phủ định từng toán hạng.
• Chúng quan trọng về mặt thực tiễn vì chúng cho phép bất kỳ biểu thức nào được viết lại chỉ sử dụng các cổng NAND hoặc chỉ sử dụng các cổng NOR, và một chip được chế tạo từ một loại cổng lặp đi lặp lại sẽ rẻ hơn để sản xuất.

Hai biểu thức, một bảng chân lý

Ví dụ minh họa: đơn giản hóa và đếm số cổng

Bản đồ Karnaugh

• Một bản đồ Karnaugh đơn giản hóa biểu thức bằng cách nhóm các số 1 liền kề lấy từ bảng chân lý.
• Các hàng và cột được gán nhãn theo thứ tự Gray code, 00, 01, 11, 10, sao cho các ô liền kề chỉ khác nhau đúng một biến. Đó chính là mấu chốt: nó khiến đại số trở thành sự liền kề trực quan.
• Đặt số 1 vào mỗi ô nơi đầu ra là 1, sau đó tìm các nhóm hình chữ nhật gồm các số 1 có cạnh là lũy thừa của hai: 1, 2, 4, 8. Các nhóm có thể vòng quanh các cạnh.

Hình chữ nhật càng lớn, thuật ngữ càng đơn giản

Đọc một nhóm

• Bên trong một nhóm, một biến không thay đổi sẽ tồn tại trong thuật ngữ; một biến thay đổi sẽ biến mất.
• Vì vậy, một nhóm gồm 2 loại bỏ một biến, một nhóm gồm 4 loại bỏ hai biến, và một nhóm gồm 8 loại bỏ ba biến. Nhóm càng lớn, thuật ngữ càng đơn giản.
• Phủ kín mọi số 1 bằng cách sử dụng càng ít và càng lớn các nhóm có thể, sau đó OR các thuật ngữ nhóm lại với nhau. Các nhóm có thể chồng lên nhau, và việc chồng lên nhau thường là yếu tố cho phép tạo ra một nhóm lớn hơn.

Ví dụ minh họa: đọc bản đồ hai biến

Chọn phương pháp nào

• Algebra Boolean là chính xác và hoạt động với bất kỳ số lượng biến nào, nhưng bạn phải nhận ra định luật nào áp dụng.
• Một bản đồ Karnaugh mang tính cơ giới và khó sai sót đối với hai đến bốn biến, đây là phạm vi mà đề thi đặt ra, và nó hiển thị trực tiếp nhóm lớn nhất.
• Cả hai đều đưa ra cùng một đáp án. Lợi ích của bản đồ K là việc đơn giản hóa trở thành nhìn thấy, chứ không phải tìm kiếm một định luật.

Điểm số dễ mất

Bạn đã nắm vững