Bài giảng Đại số Boole - Chương VI

Bài giảng Đại số Boole - Chương VI trình bày nội dung: giới thiệu chung, hàm Boole, cách biểu diễn hàm Boole, thuật toán Quine McCluskey,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Đại số Boole - Chương VIChương VI.Đại số BooleChương VI. Đại số Boole1. Giớithiệu chung2. Hàm Boole3. Cách biểu diễn hàm Boole4. Thuật toán Quine McCluskey1. Giới thiệu chungn Phần chính của các hệ thống xử lý thông tin số thường là mạch logic số.n 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.n 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 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 chungn Cá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 Boolen Đại số Boole đưa ra các quy tắc làm việc với tập: B = {0, 1}n 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 Boolen 3 phép toán cơ bản: x y x.y x+y x’ 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 02. Hàm Boolen Các hằng đẳng thức Boole:2. Hàm Boolen Biến x được gọi là biến Boole nếu nó nhận giá trị thuộc B.n Một ánh xạ f: Bn → B được gọi là hàm Boole bậc n.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 Boole ¨ Nế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 Boolen Biểu diễn bằng bảng giá trị chân lý:n Biểu diễn bằng các phép toán cơ bản:3. Cách biểu diễn hàm Boole3. Cách biểu diễn hàm Boole3. Cách biểu diễn hàm Boolen Tì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 f ( x, y, z ) = x. y + z f ( x, y, z ) = x. y.z + x. y.z3. Cách biểu diễn hàm Boolen Độ 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 đó. Độ phức tạp là 6 f ( x, y ) = x. y + x. y + x. y Độ phức tạp là 2 f ( x, y ) = x. yn 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.3. Cách biểu diễn hàm Boolen Cho f, g là hai hàm Boole của n biến: x1 , x2 ,..., xnn Ký hiệu: T f = { ( x1 , x2 ,..., xn ) �B | f ( x1 , x2 ,..., xn ) = 1}n Một hàm g được gọi là nguyên nhân (Implicant) của hàm f nếu g → f = 1. Tg T f f ( x, y, z ) = x. y + zn 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) f ( x, y ) = x + yn 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 Boolen Tìm dạng tuyển chuẩn tắc hoàn toàn của các hàm Boole sau: f ( x, y , z ) = x (y ( x + z) z) + � � ( y + z) � � � �x ( y z) � g ( x, y, z ) = Ů��� (x � � � y) | ( y z) � �4. Thuật toán Quine McCluskeyn Thuậ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 McCluskey n Tìm dạng tuyển chuẩn tắc thu gọnf ( x, y, z, u ) = x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y.z.u + x. y. z.u + x. y. z.u x. y.z.u y.u x. y.z.u x. y.z.u z.u x. y.z.u x. y.z.u x.u x. y.z.u x. y.z.u ...