Bài giảng Toán rời rạc - Chương 6: Đại số Boole

Chương VI.Đại số BooleChương VI. Đại số BooleGiới thiệu chungHàm BooleCách biểu diễn hàm BooleThuật toán Quine McCluskey1. Giới thiệu chungPhần chính của các hệ thống xử lý thông tin số thường là mạch logic số.Năm 1938, Claude Shannon chứng tỏ rằng có thể dung các quy tắc cơ bản của Logic để thiết kế các mạch điện -> Cơ sở của đại số Boole.Bước đầu tiên trong việc xây dựng một mạch điện là biểu diễn hàm Boole của nó bằng các phép toán cơ bản.Nội dung chính của chương: 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ép toán để biểu diễn một hàm Boole1. Giới thiệu chungCác mệnh đề logic đều có thể biểu diễn thông qua 3 phép toán AND, OR, NOT“I will take un umbrella with me if it is raining or the weather forecast is bad”“If I don’t take the car then I will take un umbrella with me if it is raining or the weather forecast is bad ”2. Hàm BooleĐại số Boole đưa ra các quy tắc làm việc với tập:B = {0, 1}3 phép toán cơ bản:+ Phép tổng Boole+ Phép tích Boole+ Phép lấy phần bù2. Hàm Boole3 phép toán cơ bản:xyx.yx + yx’000010101110010111102. Hàm BooleCác hằng đẳng thức Boole:Hằng đẳng thứcTên gọiLuật phần bù képLuật lũy đẳngLuật đồng nhấtLuật nuốtLuật giao hoánLuật kết hợpLuật phân phốiLuật De Morgan2. Hàm BooleBiến x được gọi là biến Boole nếu nó nhận giá trị thuộc B.Một ánh xạ f: Bn → B được gọi là hàm Boole bậc n.Biểu thức Boole:Các ký hiệu 0,1 và các biến Boole x1, x2, , xn là các biểu thức BooleNếu X1, X2 là các biểu thức Boole thì X1’, X1.X2, X1 + X2 cũng là biểu thức Boole.2. Hàm Boole3. Cách biểu diễn hàm BooleBiểu diễn bằng bảng giá trị chân lý:Biểu diễn bằng các phép toán cơ bản:3. Cách biểu diễn hàm Boole 3. Cách biểu diễn hàm Boole 3. Cách biểu diễn hàm BooleTìm dạng tuyển chuẩn tắc hoàn toàn từ bảng giá trị chân lý:3. Cách biểu diễn hàm Boole 3. Cách biểu diễn hàm BooleĐộ phức tạp của một dạng chuẩn tắc là số các ký hiệu biến xuất hiện trong dạng chuẩn tắc đó.Dạng tuyển chuẩn tắc của f có độ phức tạp bé nhất được gọi là dạng tuyển chuẩn tắc tối thiểu của f.Độ phức tạp là 6Độ phức tạp là 23. Cách biểu diễn hàm BooleCho f, g là hai hàm Boole của n biến: Ký hiệu: Một hàm g được gọi là nguyên nhân (Implicant) của hàm f nếu g → f = 1. Nguyên nhân nguyên tố (Prime Implicant) là một nguyên nhân sao cho ta không thể xóa đi bất cứ biến nào để A vẫn còn là nguyên nhân (là nguyên nhân không thể suy ra từ nguyên nhân khác)Tuyển của tất cả các nguyên nhân nguyên tố của f được gọi là dạng tuyển chuẩn tắc thu gọn của f3. Cách biểu diễn hàm Boole Tìm dạng tuyển chuẩn tắc hoàn toàn của các hàm Boole sau:4. Thuật toán Quine McCluskeyThuật toán tìm dạng tuyển chuẩn tắc tối thiểu của hàm Boole f:Bước 1: Tìm dạng tuyển chuẩn tắc hoàn toàn của f.Bước 2: Tìm dạng tuyển chuẩn tắc thu gọn từ dạng tuyển chuẩn tắc hoàn toàn.Bước 3: Tìm dạng tuyển chuẩn tắc tối thiểu từ dạng tuyển chuẩn tắc thu gọn.4. Thuật toán Quine McCluskeyTìm dạng tuyển chuẩn tắc thu gọn4. Thuật toán Quine McCluskeyTìm dạng tuyển chuẩn tắc tối thiểu4. Thuật toán Quine McCluskeyTìm dạng tuyển chuẩn tắc tối thiểu4. Thuật toán Quine McCluskeyTìm dạng tuyển chuẩn tắc tối thiểu của các hàm Boole sau: