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.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Đại số Boole - Chương VI
- Chương VI.
Đại số Boole
- Chương VI. Đại số Boole
1. Giớithiệu chung
2. Hàm Boole
3. Cách biểu diễn hàm Boole
4. Thuật toán Quine McCluskey
- 1. Giới thiệu chung
n 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 Boole
- 1. Giới thiệu chung
n 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 Boole
n Đạ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 Boole
n 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 0
- 2. Hàm Boole
n Các hằng đẳng thức Boole:
- 2. Hàm Boole
n 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 Boole
- 3. Cách biểu diễn hàm Boole
n 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 Boole
- 3. Cách biểu diễn hàm Boole
- 3. Cách biểu diễn hàm Boole
n 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.z
- 3. Cách biểu diễn hàm Boole
n Độ 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. y
n 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 Boole
n Cho f, g là hai hàm Boole của n biến: x1 , x2 ,..., xn
n 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 + z
n 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 + y
n 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 f
- 3. Cách biểu diễn hàm Boole
n 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 McCluskey
n 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ọn
f ( 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 y.u
x. y.z.u
x. y.z.u y.z
x. y.z.u
x. y.z.u x. y
- 4. Thuật toán Quine McCluskey
n Tìm dạng tuyển chuẩn tắc tối thiể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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
