Đại số Boolean và
cổng luận lý
Bộ môn Kỹ thuật máy tính
Bùi Văn Hiếu

Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
2
Đại số Boolean
Cơ sở toán học cho các hệ thống số là đại số Boolean
(Boolean algebra)
George Boole giới thiệu vào năm 1854
Tương tự các hệ đại số khác, được xây dựng thông qua
việc xác định nghĩa những vấn đề cơ bản sau:
Miền (domain), là tập hợp (set) các phần tử (element)
mà trên đó định nghĩa nên hệ đại số
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)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
3
Định đề Huntington
1. 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
Phép toán (+) được gọi là phép cộng luận lý
(logical addition)
Phép toán (• ) được gọi là phép nhân luận lý
(logical multiplication)

theo cặp
Mỗi định đề trong 1 cặp có thể được xây dựng từ định đề
còn lại bằng cách
Hoán đổi các phép toán 2 ngôi
Hoán đổi các phần tử đồng nhất
Như vậy đại số Boolean mang tính đối ngẫu
Phép toán (+) và (•) đối ngẫu
Phần tử đồng nhất 0 và 1 đối ngẫu
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
7
Các định lý cơ bản (fundamental
theorems)
Các định lý được chứng minh từ các định đề Huntington
và các định đề đối ngẫu theo 2 phương pháp
Phương pháp phản chứng (contradiction)
Giả sử kết quả đối ngược là đúng
Chứng minh mâu thuẫn với sự thật
Phương pháp quy nạp (induction)
Chứng minh định luật đúng với trường hợp k = 1
Giả sử định luật đúng vơí trương hợp k = n
Chứng minh định luật đúng với k = n +1
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Các định lý cơ bản (tt)
Định lý 1. (Null Law)
x + 1 = 1
x • 0 = 0
Định lý 2. (Involution)
(x’ )’ = x
Định lý 3. (Idempotency)
x + x = x

Chuyển mạch là thiết bị có 2 vị trí: tắt (off) hay mở (on)
2 vị trí này biểu diễn cho 0 hay 1
Đại số Boolean 2 phần tử được gọi là đại số chuyển
mạch
Các phần tử đồng nhất được gọi là các hằng chuyển
mạch (switching constant)
Các biến (variable) biểu diễn các hằng chuyển mạch
được gọi là các biến chuyển mạch (switching variable)
hay tín hiệu (signal)
11
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
12
Các phép toán chuyển mạch
Đại số chuyển mạch sử
dụng các phép toán trong
luận lý mệnh đề với tên gọi
khác
Phép toán AND: tương
đương với phép nhân luận
lý
Phép toán OR: tương
đương với phép cộng luận
lý
Phép toán NOT: tương
đương với phép bù luận lý
Bảng sự thật
x y x y x + y x’
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0

Biểu thức chuyển mạch
Biểu thức chuyển mạch (switching expression) là một
quan hệ hữu hạn giữa các hằng, biến, và các phép toán
y + 1
xx’ + x
z (x + y’)’
(x + yz)(x + y’) + (x + y)’
Biến hay bù của biến được gọi chung là literal
Quy ước:
Không cần ghi kí hiệu của phép nhân
Phép nhân thực hiện trước phép cộng
14
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
15
Biểu thức chuyển mạch
Một biểu thức có thể được chuyển thành nhiều dạng
tương đương bằng cách sử dụng các luật Boolean
E = (x + yz)(x + y’) + (x + y)’
E1 = xx + xy’ + xyz + yy’z + x’y’
E2 = x + x(y’ + yz) + x’y’
E3 = x + x’y’
E4 = x + y’
Tại sao phải biến đổi các biểu thức ?
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Sự dư thừa (redundant)
Một biểu thức gọi là dư thừa nếu nó có chứa
Literal lặp: xx hay x+x
Biến và bù của biến: xx’ hay x+x’
Hằng: 0 hay 1
Các thành phần dư thừa có thể loại bỏ khỏi biểu thức

Maxterm: một tổng không dư thừa các literal của dạng
chính tắc
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Định lý De Morgan tổng quát
(x
1
+ x
2
+ … + x
n
)’A =A x
1
’x
2
’ … x
n
’
(x
1
x
2
… x
n
)’AA =A x
1
’ + x
2
’ + … + x
n
’

2 biểu thức (x + x’ y’) và (x + y’) có tương đương ?
Hàm chuyển mạch (switching function) là một phép gán
xác định và duy nhất của những giá trị 0 và 1 cho tất cả
các tổ hợp giá trị của các biến thành phần
Số lượng hàm chuyển mạch của n biến là
BT: SV liệt kê các 16 hàm chuyển mạch với 2 biến.
x y x’ y’ x’ y’ x + x’ y’ x + y’
0 0 1 1 1 1 1
0 1 1 0 0 0 0
1 0 0 1 0 1 1
1 1 0 0 0 1 1
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Hàm chuyển mạch (tt)
Sự khác nhau giữa hàm và biểu thức chuyển mạch ?
Nếu mọi giá trị của biểu thức trùng với giá trị của hàm,
ta gọi biểu thức biểu diễn (represent) hàm
Tồn tại nhiều biểu thức cùng biểu diễn cho 1 hàm
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Hàm chuyển mạch (tt)
Biểu diễn hàm dưới dạng danh sách minterm/maxterm
Chuyển đổi dạng chuẩn s-o-p sang p-o-s
Xử dụng De Morgan cho phần bù của các minterm
không có trong biểu thức
22
Decimal x y z Maxterms f Minterms
0 0 0 0 x + y + z 0 x’ y’ z’
1 0 0 1 x + y + z’ 0 x’ y’ z
2 0 1 0 x + y’ + z 1 x’ y z’
3 0 1 1 x + y’ + z’ 1 x’ y z
4 1 0 0 x’ + y + z 1 x y’ z’

’.f(0, x
2
, ..., x
n
)
Một hàm chuyển mạch bất kỳ n biến luôn có thể được
biểu diễn dưới dạng s-o-p n literal, mỗi literal ứng với 1
biến
Dạng p-o-s: sv tự đọc