Bài giảng Nhập môn tin học - Chương 6: Đại số Boole
Đại số boole là gì?
Là phép toán đại số liên quan đến
Do nhà toán học người Anh đưa ra năm 1815-1864 nhằm
Đơn giản hóa việc trình bày
Thao tác với logic mệnh đề
1938 Claude đề xuất sử dụng đại số Boole trong thiết kế
mạch
Cung cấp cách tiếp cận tiết kiệm và đơn giản
Được sử dụng rộng rãi trong thiết kế mạch điện tử trong
máy tính
Khái niệm cơ bản về Đại số Boole
Các phép toán trong đại số Boole thực hiện trên các biến
có 2 giá trị 0 và 1, gồm
Cộng logic: ‘+’ hay OR
Nhân logic: ‘ . ‘ hay AND
Phép bù: ‘-’ hay NOT
Khái niệm cơ bản về Đại số Boole
Bảng chân trị:
A
0
0
1
1
B
0
1
0
1
A AND B A OR B NOT A
0
0
0
1
0
1
1
1
1
1
0
0
Độ ưu tiên của các toán tử
Toán tử có độ ưu tiên cao nhất được định trị đầu tiên.
Biểu thức được tính từ trái sang phải
Độ ưu tiên
Toán tử
1
( ) Biểu thức trong ngoặc
2
3
4
_ (NOT)
. (AND)
+ (OR)
Độ ưu tiên của các toán tử
Các tiên đề của đại số Boole
Tiên đề 2:
Tiên đề 3:
Tiên đề 1:
Phần tử đồng
nhất
Tính giao hoán
A = 0 khi và chỉ
khi A không
bằng 1
X + Y = Y + X
X + 0 = X
X . 1 = X
A = 1 khi và chỉ
khi A không
bằng 0
X . Y = Y . X
Các tiên đề của đại số Boole
Tiên đề 4:
x + (y + z) = (x + y) + z
Tính kết hợp
x . (y . z) = (x . y) . z
Tiên đề 5:
x . (y +z) = x . y + x . z
Tính phân phối
x + y . z = (x + y) . (x + z)
Tiên đề 6:
X + X = 1
X. X = 0
Tính bù
Nguyên lý đối ngẫu
Có sự đối ngẫu giữa toán tử AND, OR và bit 0, 1
Các định lý của đại số Boole
Định lí 1
Định lí 2
Định lí 3
(Luật lũy đẳng)
(Luật nuốt)
(Luật hấp thu)
Các định lý của đại số Boole
Định lí 4
ധ
푋 = 푋
(Luật bù kép)
푋. 푋 + 푌 = 푋. 푌
푋 + 푋 . 푌 = 푋 + 푌
푋 + 푌 = 푋 . 푌
Định lí 5
Định lí 6
(De Morgan)
푋. 푌 = 푋 + 푌
Hàm Boole
Một hàm Boole là mộbiểu thức được thực hiện với:
Các biến nhị phân
Các toán tử AND, OR, NOT
Các dấu ngoặc và đấu =
Giá trị của hàm Boole có thể là hoặc
Một hàm Boole có thể được biểu diễn dạng:
Một biểu thức đại số
Một bảng chân trị
Hàm Boole
Hàm Boole biểu diễn dưới dạng biểu thức đại số:
Hoặc
Với: X, Y và Z được gọi là các biến của hàm.
Hàm Boole
Hàm Boole biểu diễn
dưới dạng bảng chân
trị
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
W
0
1
Số hàng của bảng là
2n, n là số các biến nhị
phân được sử dụng
trong hàm.
0
0
1
1
1
1
Sự dư thừa
: là các biến trong hàm Boole
là sự kết hợp của các biến mà mỗi
biến chỉ xuất hiện một lần duy nhất.
Ví dụ: term của 3 biến A, B, C là A.B.C
Literal lặp: XX hay X+X
Biến và bù của biến: XX’ hay X+X’
Hằng: 0 hay 1
Tối thiểu hóa hàm Boole
:
Giảm số phần tử (Term)
Giảm số biến (Literal)
:
Sử dụng phương pháp đại số
Áp dụng các định lý, tiên đề, các luật nhiều lần để tối
thiểu hàm Boolean tới mức thấp nhất.
Tối thiểu hóa hàm Boole
Ví dụ: tối thiểu hóa hàm sau:
ത ത
ത
ത
퐹 = 푋. 푌. 푍 + 푋. 푌. 푍 + 푋. 푌
1
ഥ ത
ത ഥ
ത
Kết quả: 퐹 = 푋. 푍. 푌 + 푌 + X. 푌 = 푋. 푍 + X. 푌
1
Bài tập: tối thiểu hóa các hàm sau:
ത
a) X + 푋.Y
ത
b) X. (푋 + Y)
ത
c) X . Y + 푋 . Z + Y . Z
ത
d) (X + Y) . (푋 + Z) . ( Y + Z)
Phần bù của hàm Boole
ത
Phần bù của hàm F là F có được bằng cách:
Chuyển toán tử AND thành OR
Lấy phần bù của các biến
Áp dụng định lí De Morgan
Phần bù của hàm Boole
Ví dụ: tính phần bù của hàm sau:
Bước 1: Chuyển toán tử AND thành OR và ngược lại.
Bước 2: tính phần bù của các biến
Dạng chính tắc của hàm Boole
Một hàm n biến luôn được biểu diễn dưới 2 dạng:
Dạng tổng các tích (sum-of-product SOP): biểu thức
được biểu diễn dưới dạng tổng (sum) các toán hạng
(term), mỗi toán hạng là tích (product) của các literal
Dạng tích các tổng (product-of-sum POS): biểu thức
được biểu diễn dưới dạng tích các toán hạng, mỗi toán
hạng là tổng của các literal
Tải về để xem bản đầy đủ
32 trang
19620
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn tin học - Chương 6: Đại số Boole", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_tin_hoc_chuong_6_dai_so_boole.pptx
