Bài giảng Nhập môn tin học: Chương 6 - Trần Thị Kim Chi

Bài giảng "Nhập môn tin học - Chương 6: Đại số Boolean và mạch logic" trình bày các nội dung: Giới thiệu, đại số Boolean, hàm Boolean, các cổng luận lý, thiết kế của mạch kết hợp, câu hỏi và bài tập. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn tin học: Chương 6 - Trần Thị Kim Chi Chương 6 ĐẠI SỐ BOOLEAN VÀ MẠCH LOGIC 1 Nội dung 6.1. Giới thiệu 6.2. Đại số Boolean 6.3. Hàm Boolean 6.4. Các cổng luận lý 6.5. Mạch Logic 6.6. Thiết kế của mạch kết hợp 6.7. Câu hỏi và bài tập 2 GIỚI THIỆU  Đại số Boole được phát minh bởi nhà toán học Anh George Boole vào năm 1854.  Đại số Boole nghiên cứu các phép toán thực hiện trên các biến chỉ có 2 giá trị 0 và 1, tương ứng với hai trạng thái luận lý 'sai' và 'đúng' (hay 'không' và 'có') của đời thường. 3 GIỚI THIỆU  Tương tự các hệ đại số khác được xây dựng thông qua những vấn đề cơ bản sau:  Miền (domain) là tập hợp (set) các phần tử (element)  Các phép toán (operation) thực hiện được trên miền  Các định đề (postulate), hay tiên đề (axiom) được công nhận không qua chứng minh  Tập các hệ quả (set of consequences) được suy ra từ định đề, định lý (theorem), định luật (law) hay luật(rule) 4 NHỮNG NGUYÊN TẮC CƠ BẢN  Sử dụng hệ cơ số nhị phân.  Các phép toán:  Phép cộng luận lí (logical addition) : (+) hay (OR )  Phép nhân luận lí (logical multiplication): (.) hay ( AND )  Phép bù ( NOT )  Độ ưu tiên của các phép toán  Tính đóng (closure): tồn tại miền B với ít nhất 2 phần tử phân biệt và 2 phép toán (+) và (•) sao cho: Nếu x và y là các phần tử thuộc B thì (x + y), (x•y) cũng là 1 phần tử thuộc B 5 PHÉP CỘNG LUẬN LÍ Phép toán: Dấu ‘+’ hay OR Biểu thức : A+B =C Hay A OR B = C Nguyên tắc: • Kết quả trả về 0 (FALSE) khi và chỉ khi tất cả giá trị đầu vào là 0 (FALSE). • Kết quả là 1 (TRUE) khi có bất kì một giá trị nhập vào có giá trị là 1 (TRUE). Ví dụ: 10011010 A B 11001001 A + B hay A OR B 1 1 0 1 1 0 1 1 6 PHÉP NHÂN LUẬN LÍ Phép toán: Dấu ‘.’ hay AND Biểu thức : A.B =C Hay A AND B = C Nguyên tắc: • Kết quả trả về 1 (TRUE) khi và chỉ khi tất cả giá trị đầu vào là 1 (TRUE). • Kết quả là 0 (FALSE) khi có bất kì một giá trị nhập vào có giá trị là 0 (FALSE). Ví dụ: 10011010 A B 11001001 A . B hay A 1 0 0 0 1 0 0 0 7 AND B PHÉP BÙ Phép toán: Dấu ‘-’ hay NOT (phép toán một ngôi) Biểu thức : Ā Hay NOT A Nguyên tắc: • Kết quả trả về 1 (TRUE) nếu giá trị đầu vào là 0 (FALSE). • Ngược lại, kết quả là 0 (FALSE) nếu giá trị nhập vào là 1 (TRUE). Ví dụ: 10011010 A Ā hay NOT A 01100101 8 ĐỘ ƯU TIÊN CỦA CÁC PHÉP TOÁN  Biểu thức được tính từ trái sang phải.  Biểu thức trong ngoặc đơn được đánh giá trước.  Các phép toán bù (NOT) được ưu tiên tiếp theo.  Tiếp theo là các phép toán ‘.’ (AND).  Cuối cùng là các phép toán ‘+’ (OR). Ví dụ: C = A Or B Not A A 10011010 B 11001001 C ?????????? 9 CÁC ĐỊNH ĐỀ Huntington CỦA ĐẠI SỐ BOOLEAN  Định đề 1:  Định đề 4: Tính kết hợp  A = 0 khi và chỉ khi A không bằng 1 • x + (y + z) = (x + y) + z  A = 1 khi và chỉ khi A không bằng 0 • x . (y . z) = (x . y) . z  Định đề 2: Phần tử đồng nhất  Định đề 5: Tính phân phối  x+0=x • x . (y +z) = x . y + x . z  x.1 =x • x + y . z = (x + y) . (x + z)  Định đề 3: Tính giao hoán  Định đề 6: Tính bù  x+y=y+x • x+x=1  x.y =y.x • x.x=0 10 NGUYÊN LÍ ĐỐI NGẪU • Đại số Boolean mang tính đối ngẫu • Đổi phép toán (+) thành (•) • Đổi phần tử đồng nhất 0 thành 1 Cột 1 Cột 2 Column 3 Row 1 1+1=1 1+0=0+1=1 0+0=0 Row 2 0.0 =0 0.1 =1.0 =0 1.1 =1 11 CÁC ĐỊNH LÍ CỦA ĐẠI SỐ BOOLEAN  Định lí 1 (Luật lũy đẳng)  Định lí 4 (Định luật bù kép)  x+x=x  x.x=x  Định lí 2 (Định luật nuốt)  Định lí 5  x+1=1  x.0=0  Định lí 3 (Định luật hấp thu)  Định lí 6 (Định luật De Morgan)  x+x.y=x  x . (x + y) = x 12 HÀM BOOLEAN  Một hàm Boolean là một biểu thức được tạo từ:  Các biến nhị phân,  Các phép toán hai ngôi OR và AND, phép toán một ngôi NOT,  Các cặp dấu ngoặc đơn và dấu bằng.  Với giá trị cho trước của các biến, giá trị của hàm chỉ có thể là 0 hoặc 1.  Phương trình Hay W = f(X, Y, Z) Với: X, Y và Z được gọi là các biến của hàm. 13 HÀM BOOLEA ...