Bài giảng về ĐẠI SỐ BOOLE

Trong máy tính điện tử và các dụng cụ điện tử khác các mạch điện tử đều có các đầu vào, mỗi đầu vào là số 0 hoặc số 1 và tạo ra các đầu ra cũng là các số 0 và 1. Các mạch điện đó đều có thể được xây dựng bằng cách dùng bất kỳ một phần tử cơ bản nào có hai trạng thái khác nhau. Chúng bao gồm các chuyển mạch có thể ở hai vị trí mở hoặc đóng và các dụng cụ quang học có thể là sáng hoặc tối. Các chuyển mạch...
Nội dung trích xuất từ tài liệu:
Bài giảng về ĐẠI SỐ BOOLEĐẠI SỐ BOOLEĐ i s Boole Nguy n Th Vinh-ĐHKH CHƯƠNG VI ĐẠI SỐ BOOLE Trong máy tính điện tử và các dụng cụ điện tử khác các mạch điện tửđều có các đầu vào, mỗi đầu vào là số 0 hoặc số 1 và tạo ra các đầu ra cũng làcác số 0 và 1. Các mạch điện đó đều có thể được xây dựng bằng cách dùng bấtkỳ một phần tử cơ bản nào có hai trạng thái khác nhau. Chúng bao gồm cácchuyển mạch có thể ở hai vị trí mở hoặc đóng và các dụng cụ quang học cóthể là sáng hoặc tối. Các chuyển mạch điện tử quang học có thể nghiên cứubằng cách dùng tập {0,1} và các qui tắc của đại số Boole. Năm 1938 ClaudeShannon chứng tỏ rằng có thể dùng các quy tắc cơ bản của lôgic do GeorgeBoole đưa ra vào năm 1854 trong cuốn “Các quy luật của tư duy” của ông đểthiết kế các mạch điện. Các quy tắc này đã tạo nên cơ sở của đại số Boole. Sựhoạt động của một mạch điện được xác định bởi một hàm Boole chỉ rõ giá trịcủa đầu ra đối với mỗi tập đầu vào. Bước đầu tiên trong việc xây dựng mộtmạch điện là biểu diễn hàm Boole của nó bằng một biểu thức được lập bằngcách dùng các phép toán cơ bản của đại số Boole. Trong chương này chúng tasẽ tìm hiểu các phương pháp để tìm một biểu thức với số tối thiểu các phéptính tổng và tích được dùng để biểu diễn một hàm Boole. 6.1. KHÁI NIỆM ĐẠI SỐ BOOLE Trước hết ta làm quen với các phép toán và qui tắc làm việc trên tập{0,1}. Phép toán được dùng nhiều nhất là phép lấy phần bù, phép lấy tổng vàphép lấy tích. Phần bù của một phần tử được kí hiệu bởi ¬ hoặc NOT ¬0=1 và ¬1=0 Tổng Boole được kí hiệu và + hoặc OR có các giá trị sau 1 + 1=1; 1 + 0=1; 0 + 1=1; 0 + 0=0; Tích Boole được kí hiệu là . hoặc AND có các giá trị sau 1 . 1 =1; 1 . 0=0; 0 . 1 =0; 0 . 0=0; 137Đ i s Boole Nguy n Th Vinh-ĐHKH Ví dụ: Tìm giá trị của 1.0 + ¬(1+0) 1.0 + ¬(1+0)= 1.0 + ¬1= 1.0 + 0= 0+0=0 Đại số Boole là các phép toán và quy tắc làm việc với tập {0,1} được ápdụng trong các nghiên cứu về máy tính, dụng cụ điện tử quang học và ba phéptoán phần bù, tổng boole và tích boole ở trên. 6.1.1. Biến Boole và hàm Boole Định nghĩa: Cho B={0,1}. Khi đó Bn ={(x1,x2,x3,..xn) | xi ∈B} là tập tấtcả các bộ n giá trị 0 và 1. Biến x được gọi là một biến Boole nếu nó nhận chỉnhận các giá trị từ B. Một hàm từ Bn tới B được gọi là hàm Boole bậc n Ví dụ: Hàm F(x,y)= x + ¬ y từ tập các cặp có thứ tự là hàm Boole bậc 2với F(1,1)=1; F(1,0)=1; F(0,1)=0; F(0,0)=1; 6.1.2. Các hằng đẳng thức của đại số Boole Trong quá trình thiết kế mạch một trong những việc cần làm là đơn giảnhóa các mạch đó hay tạm gọi đó là tối ưu hóa các mạch, thường được dựa trênmột số hằng đẳng thức Boole còn được gọi là các luật. 1. Luật giao hoán a) a.b = b.a b) a+b = b+a 2. Luật kết hợp a) (a.b).c = a.(b.c) b) (a+b)+c = a+(b+c) 3. Luật phân phối a) a.(b+c) = (a.b)+(a.c) b) a+(b.c) = (a+b).(a+c) 4. Luật đồng nhất a) a.1 = a b) a+0 = a 5. Luật trội a+1=1 a.0=0 6. Luật tồn tại phần tử bù: 138Đ i s Boole Nguy n Th Vinh-ĐHKH a) a.¬a = 0 (tính chất 0) b) a+¬a =1.(tính chất đơn vị) 7. Luật luỹ đẳng a) a.a = a, b) a+a = a. 8. Luật De Morgan a) ¬(a.b) = ¬a + ¬b b) ¬(a+b) = ¬a .¬b 9. Luật bù kép ¬¬(a) = a. 10. Luật hút a) a.(a+b) = a b) a+(a.b) = a. Việc chứng minh các luật trên có dựa vào việc lập bảng chân trị chẳnghạn chứng minh luật hút dựa vào bảng sau Giá trị a b a+b a. (a+b) 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 Nhìn vào cột 1 và cột 4 ta thấy các giá trị hoàn toàn phù hợp với nhaudo vậy a. (a+b) = a; tương tự với ý b Ngoài ra ta có thể chứng minh bằng cách dùng các hằng đẳng thức củađại số Boole. theo luật đồng nhất a(a+b)= (a+0)(a+b) theo luật phân phối = a +0. b theo luật giao hoán = a+ b.0 theo luật trội =a+0 139Đ i s Boole Nguy n Th Vinh-ĐHKH ...