Bài giảng Thiết kế luận lý 1 - Chương 2: Đại số Boole & các cổng luận lý - Nguyễn Quang Huy
dce
2014
Khoa KH & KTMT
Bộ môn Kỹ Thuật Máy Tính
dce Tài liệu tham khảo
2014
• “Digital Systems, Principles and Applications”,
11th Edition, Ronald J. Tocci, Neal S. Widmer,
Gregory L. Moss
09/03/2014
©2014, CE Department
2
dce Nội dung
2014
• Đại số Boole
• Đại số chuyển mạch
• Các cổng luận lý
09/03/2014
©2014, CE Department
4
dce Đại số Boole
2014
• Đại số Boole được thế giới biết đến lần đầu tiên bởi
George Boole qua tác phẩm “An Investigation of the
Laws of Thought” vào năm 1854
• Các hằng và biến Boole chỉ được mang 2 giá trị 0
hoặc 1 ( LOW / HIGH )
– Các biến Boole biểu diễn cho một khoảng điện áp trên
đường dây hoặc tại ngõ nhập/ngõ xuất của mạch
A
x
F
y
Mạch
luận lý
ngõ nhập
ngõ xuất
09/03/2014
©2014, CE Department
5
dce Đại số Boole
2014
• Đại số Boole, cũng tương tự như các hệ đại số khác,
được xây dựng thông qua việc xác định nghĩa một
số 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ố
– Tập hợp chực hiện được trên
miền
(independe
– Một tập hợp các hệ quả (consequence) được gọi là định lý
(theorem), định luật (law) hay quy tắc (rule)
09/03/2014
©2014, CE Department
6
dce Định đề Huntington
2014
• Phát biểu bởi nhà toán học Anh E.V.Huntington trên
cơ sở hệ thống hóa các công trình của G. Boole
– Sử dụng các phép toán trong luận lý mệnh đề
(propositional logic)
• 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:
1 phần tử thuộc B (phép nhân luận lý - logical
multiplication)
09/03/2014
©2014, CE Department
7
dce Định đề Huntington …
2014
• Tính đồng nhất (identity)
Nếu x là một phần tử trong miền B thì
– Tồn tại 1 phần tử 0 trong B , gọi là phần tử đồng nhất với
phép toán + , thỏa mãn tính chất x + 0 = x
– Tồn tại 1 phần tử 1 trong B , gọi là phần tử đồng nhất với
phép toán 1 = x
• Tính giao hoán (commutative)
– Giao hoán của phép + :
x + y = y + x
– Giao hoán của phép • :
x • y = y • x
09/03/2014
©2014, CE Department
8
dce Định đề Huntington …
2014
• Tính phân phối (distributive)
– Phép • có tính phân phối trên phép +
x • (y + z) = (x • y) + (x • z)
– Phép + có tính phân phối trên phép •
x + (y • z) = (x + y) • (x + z)
• Bù (complementation)
– x + x’
– x • x’ = 0
09/03/2014
©2014, CE Department
9
dce Tính đối ngẫu (duality)
2014
• Quan sát các định đề Hungtinton, ta thấy chúng
mang tính đối xứng (symmetry) tức là các định đề
xuất hiện 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
– Thay đổi các phép toán 2 ngôi ( + | • )
– Thay đổi các phần tử đồng nhất ( 0 | 1 )
bằng cách
– Hoán đổi phép toán + với phép toán •
– Hoán đổi phần tử đồng nhất 0 với phần tử đồng nhất 1
• Điều này thể hiện tính đối ngẫu ở đại số Boole
09/03/2014
©2014, CE Department
10
dce
2014
Các định lý cơ bản (fundamental theorem)
• Các định lý được chứng minh từ các định đề
Huntington và các định đề đối ngẫu theo 2 cách
– Chứng minh bằng phản chứng (contradiction)
– Chứng minh bằng quy nạp (induction)
• Định lý 1 (Null Law)
– x + 1 = 1
• Định lý 2 (Involution)
– (x’ )’ = x
– x • 0 = 0
• Định lý 3 (Idempotency)
– x + x =
x = x
• Định lý 4 (Absorption)
– x + x • y = x
– x • (x + y) = x
09/03/2014
©2014, CE Department
11
dce Các định lý cơ bản …
2014
• Định lý 5
– x + x’ y = x + y
– x (x’ + y ) = x y
• Định lý 6 (Associative Law)
(Simplification)
– x + (y + z) = (x + y ) + z = x + y + z
– x (y z) = (x y) z = x y z
• Định lý 7
(Consensus)
– x y + x’ z + y z = x y + x’ z
– (x + y) (x’ + z) (y + z) = (x + y) (x’ + z)
• Định lý 8
– (x + y)’ = x’ y’
– (x y)’ = x’ + y’
(De Morgan’s Law)
09/03/2014
©2014, CE Department
12
dce Bảng sự thật (Truth table)
2014
• Phương tiện mô tả sự phụ thuộc của ngõ xuất vào mức luận
lý (logic level) tại các ngõ nhập của mạch
– Liệt kê tất cả các tổ hợp có thể của mức luận lý tại các ngõ
nhập và kết quả mức luận lý tương ứng tại ngõ xuất của mạch
– Số tổ hợp của bảng N-ngõ nhập: 2N
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
x
0
1
1
0
0
0
0
1
A
0
0
1
1
B
0
1
0
1
x
1
0
1
0
A
B
x
?
09/03/2014
©2014, CE Department
13
dce
2014
Đại số chuyển mạch (switching algebra)
• Đối với đại số Boole, miền không bị hạn chế (không có giới
hạn đặt ra đối với số lượng các phần tử trong miền)
• Các định đề Huntington giới hạn xem xét đại số Boole với 2
phần tử đồng nhất mà thôi
Ù Đại số Boole 2 phần tử
• Năm 1937, Claude Shannon hiện thực đại số Boole 2 phần
tử bằng mạch điện với các chuyển mạch (switch)
– 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) ˜ tín hiệu
09/03/2014
©2014, CE Department
14
dce Các phép toán chuyển mạch
2014
• Đạ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
x
0
0
1
1
y x • y x + y x’
0
1
0
1
0
0
0
1
0
1
1
1
1
1
0
0
• Phép toán AND
– Phép toán
đương với phép nhân
luận lý
Bảng sự thật các phép
• Phép toán OR
– Phép toán 2 ngôi tương
đương với phép cộng
luận lý
tương đương với
phép bù luận lý
09/03/2014
©2014, CE Department
15
dce Các phép toán chuyển mạch …
2014
• Các phép toán chuyển mạch có thể được hiện thực bởi
mạch phần cứng
• Bảng sự thật có thể sử dụng như 1 công cụ dùng để xác
minh quan hệ giữa các phép toán chuyển mạch
• Sử dụng bảng sự thật để chứng minh định lý De Morgan
(x + y)’ = x’ y’
x
0
0
1
1
y
0
1
0
1
x’
1
1
0
0
y’
1
0
1
0
x + y (x + y)’ x’ y’
0
1
1
1
1
0
0
0
1
0
0
0
09/03/2014
©2014, CE Department
16
dce
2014
Biểu thức (expression) chuyển mạch
• Biểu thức chuyển mạch là một quan hệ hữu hạn các
hằng, biến, biểu thức chuyển mạch liên kết với nhau
bởi các phép toán AND, OR và NOT
• Ví dụ
y + 1 , x x’ + x ,
z ( x + y’ )’
E = ( x + y z ) ( x + y’ ) + ( x + y )’
09/03/2014
©2014, CE Department
17
dce
2014
Biểu thức (expression) 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 Boole
E = (x + y z) (x + y’) + (x + y)’
E1 = x x + x y’ + x y z + y y’ z + x’ y’
E2 = x + x (y’ + y z) + x’ y’
E3 =x + x’ y’
E4 =x + y’
• Tại sao phải chuyển đổi dạng của các biểu thức ?
– literal lặp ( x x hay x + x)
– biến và bù ( x x’ hay x + x’)
– hằng (0 hay 1)
• Không hiện thực các thành phần thừa của biểu
thức vào mạch
09/03/2014
©2014, CE Department
18
dce Hàm (function) chuyển mạch
2014
• 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
• Hàm được xác định bởi danh sách các trị hàm tại mỗi tổ hợp
giá trị của biến (bảng sự thật)
– Tồn tại nhiều biểu thức biểu diễn cho 1 hàm
• Số lượng hàm chuyển mạch với n biến là 2 luỹ thừa 2n
x
0
0
1
y x’ y’
0 1 1
1
0 0 1
1 0 0
x’ y’
1
1
1
1
1
0
1
0
1
0
1
09/03/2014
©2014, CE Department
19
dce Các phép toán chuyển mạch khác
2014
• Phép toán NAND
• Phép toán Exclusive OR
– Phép toán 2 ngôi tương
đương với (NOT AND)
– E = x y = x’ y + x y’
• Phép toán NOR
• Phép toán XNOR (Ex. NOR)
– Phép toán 2 ngôi tương
đương với (NOT OR)
– E = ( x y )’ = x y + x’ y’
Biến
NAND
NOR
XNOR
x
0
0
1
1
y
0
1
0
1
(x . y)’
(x + y)’
x y
(x y)’
1
1
0
1
0
0
1
1
0
1
0
0
1
09/03/2014
©2014, CE Department
20
Tải về để xem bản đầy đủ
32 trang
13940
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết kế luận lý 1 - Chương 2: Đại số Boole & các cổng luận lý - Nguyễn Quang Huy", để 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_thiet_ke_luan_ly_1_chuong_2_dai_so_boole_cac_cong.pdf
