Giáo trình Chương 2: Các công luận lý tối giản mạch bằng Phương pháp đại số Boolean và bản đồ Karnaugh môn Kiến trúc máy tính | Trường Đại học Cần Thơ

CHƯƠNG 2 CÁC CỔNG LUẬN LÝ
TỐI GIẢN MẠCH BẰNG PHƯƠNG PHÁP ĐẠI SỐ BOOLEAN
VÀ BẢN ĐỒ KARNAUGH
❖ M ục tiêu học tập: Sau khi học xong bài này, người học có thể:
- Mô tả khái niệm về mạch số.
- Xác định bảng chân trị, lược đồ luận lý của các cổng, vẽ giản đồ thời gian của các cổng.
- Rút gọn hàm luận lý bằng đại số Boolean.
- Rút gọn hàm luận lý bằng biểu đồ Karnaugh.
- Vẽ sơ đồ mạch (lược đồ luận lý) qua biểu thức hàm Boolean.
2.1. Mô tả đại cương mạch số, cổng luận lý
2.1.1. Khái niệm
Việc phân tích thiết kế các hệ thống mạch điện tử trong máy tính (computer) do vận dụng đại
số toán gọi là đại số Boolean do một nhà toán học người Anh, George Boolean đề xuất vào năm 1854.
Năm 1938, Claude Shannon chứng tỏ rằng có thể dùng các qui tắc đại số Boolean để phân tích và thiết
kế các mạch điện. Bước đầu tiên trong việc xây dựng một mạch điện là biển diễn hàm Boolean của nó
bằng một biểu thức được lập bằng cách dùng các phép toán cơ bản của đại số Boolean.
Các biến số trong đại số Boolean là biến biểu thị trạng thái của một giá trị điện thế và ta gọi là
mức logic 0 hoặc 1. Thường được sử dụng để biểu diễn mức điện thế có trên dây hay tại các đầu vào / ra (IO: input/output). Logic 0 Logic 1 Sai Đúng Tắt Mở Không Có Công tắt đóng (off) Công tắc mở (on)
Mức điện thế thấp (0 - 2.4 v)ol
Mức điện thế cao (5v-3.3 vol)
Hình 2.1 Biểu diễn mức logic trong đại số Boolean
Các khái niệm liên quan với đại số Boolean:
- Tín hiệu tương tự (analog signal): là tín hiệu có biên độ liên tục theo thời gian, thường
do các hiện tượng tự nhiên sinh ra.
Hình 2.2 Biểu diễn tín hiệu tương tự
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 24
- Tín hiệu số (digital signal): là tín hiệu có dạng xung gián đoạn về thời gian biên độ chỉ
có 2 mức rõ rệt: mức cao và mức thấp. 1 0
Hình 2.3 Biểu diễn tín hiệu số
Mạch điện xử lý tín hiệu tương tự gọi là mạch tương tự. Mạch điện xử lý tín hiệu số gọi là mạch
số. Việc vận dụng đại số Boolean thiết kế mạch số có một số ưu điểm sau:
- Dễ thiết kế, phân tích.
- Hoạt động theo chương trình lập sẵn.
- Ít bị ảnh hưởng của nhiễu.
- Dễ chế tạo thành mạch tích hợp.
2.1.2. Cổng luận lý
Cổng (hay cổng luận lý): cơ sở phần cứng, từ đó chế tạo ra mọi máy tính số. Cổng có một hoặc
nhiều ngõ vào, nhưng chỉ có 1 ngõ ra. Các giá trị vào hoặc ra chỉ có thể nhận 1 trong 2 giá trị là 1 hoặc
0. Gọi là cổng luận lý vì nó cho kết quả lý luận của đại số logic như nếu A đúng và B đúng thì C đúng.
Hãy xem xét những ý tưởng cơ bản chế tạo các cổng này để hiểu rõ bản chất của mạch số. Mọi
logic số hiện đại cũng dựa trên việc chế tạo transistor vận hành như một công tắc nhị phân cực nhanh.
Hình 2.4 minh họa mạch transistor lưỡng cực đặt vào mạch đơn giản. Transistor này có 3 nối
kết với thế giới bên ngoài: cực góp (collector), cực nền (base) và cực phát (emitter). Khi điện áp vào
Vin thấp hơn giá trị tới hạn nào đó (0.8V), transistor sẽ tắt và đóng vai trò như điện trở vô hạn, khiến
đầu ra của mạch Vout nhận giá trị gần với Vcc (điện áp ngoài thường là +3V). Lúc Vin vượt quá giá trị
tới hạn, transistor bật và đóng vai trò như dây dẫn, kéo Vout xuống tới đất (theo qui ước là 0 V). Vcc collector Vout Vin base Emitter
Hình 2.4 Cấu tạo mạch transistor cổng NOT A Y=A’
Thấy rằng khi Vin thấp thì Vout cao, và ngược lại. Do đó, mạch này là bộ nghịch đảo (converter
hoặc NOT), chuyển logic 0 sang logic 1, và logic 1 sang logic 0, hay tương ứng với một cổng gọi là
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 25
cổng NOT. Cần điện trở để giới hạn dòng điện do transistor kéo qua. Thời gian cần thiết để chuyến từ
trạng thái này sang trạng thái khác thường mất vài nano giây tùy theo loại transistor. Vcc Vout V1 V2
Hình 2.5 Cấu tạo mạch transistor cổng NAND A Y B
Trong Hình 2.5 hai transistor được gắnnối tiếp. Nếu V1 và V2 đều cao, cả hai transistor sẽ dẫn
điện, lúc này Vout sẽ bị kéo xuống thấp. Giả sử một trong hai đầu vào thấp, transistor tương ứng sẽ
tắt, và đầu ra sẽ cao. Nói tóm lại Vout sẽ thấp khi và chỉ khi V1 và V2 đều cao. Mạch này là một cổng NAND.
Trong Hình 2.6 hai transistor được gắn song song. Nếu một trong hai đầu vào cao, transistor
tương ứng sẽ kéo đầu ra xuống tới đất. Còn như cả hai đầu vào đều thấp, đầu ra sẽ vẫn cao. Mạch này
tương ứng với cổng gọi là NOR. Vcc Vout V1 V2
Hình 2.6 Cấu tạo mạch transistor cổng NOR
Cổng là một mạch số gồm một hoặc nhiều tín hiệu vào và một tín hiệu ra. Một mạch số sẽ
được tạo ra từ tập hợp các cổng cơ bản. Mỗi cổng cơ bản có ký hiệu riêng và hoạt động của nó được
mô tả qua một bảng gọi là bảng chân trị (truthtable).
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 26
2.1.2.1. Cổng đệm (buffer)
Khái niệm: Là cổng có một ngõ vào và một ngõ ra. Ngõ ra bằng ngõ vào (Tín hiệu qua cổng
đệm không làm thay đổi trạng thái logic).
Cổng đệm thông thường dùng để sửa dạng tín hiệu vuông hơn, đưa điện thế tín hiệu về đúng mức logic.
Hàm boolean: Y=A A Y=A A Y=A’ A Y=A’
a) Lược đồ luận lý A Y=A 0 0 1 1
b) Bảng chân trị A Y Y t
c)Giản đồ thời gian
Hình 2.7 Lược đồ luận lý – bảng chân trị - giản đồ thời gian cổng BUFFER
2.1.2.2. Cổng đảo (NOT)
Khái niệm: Là cổng có một ngõ vào và một ngõ ra. Ngõ ra ngược lại ngõ vào (còn gọi là cổng INVERTER).
Khi cổng đảo được ghép chung với cổng khác thì ký hiệu được đơn giản thành 1 dấu tròn nhỏ
Hàm boolean: Y=A’ A Y=A’
a) Lược đồ luận lý A Y=A’ 0 1 1 0
b) Bảng chân trị
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 27 A 1 0 Y 1 0 Y t
c)Giản đồ thời gian
Hình 2.8 Lược đồ luận lý – bảng chân trị - giản đồ thời gian cổng NOT
2.1.2.3. Cổng AND
Khái niệm: Là cổng có ít nhất hai ngõ vào và một ngõ ra. Ngõ ra có giá trị cao khi tất cả ngõ vào có giá trị cao.
Dùng thực hiện phép nhân logic giữa hai hay nhiều biến nhị phân.
Hàm boolean: Y=A.B (hoặc Y=AB) A Y B
a) Lược đồ luận lý A B Y=A.B 0 0 0 0 1 0 1 0 0 1 1 1
b) Bảng chân trị A B Y t
c) Giản đồ thời gian
Hình 2.9 Lược đồ luận lý – bảng chân trị - giản đồ thời gian cổng AND
2.1.2.4. Cổng OR
Khái niệm: Là cổng có ít nhất hai ngõ vào và một ngõ ra. Ngõ ra có giá trị cao khi có ít nhất
một ngõ vào có giá trị cao.
Dùng thực hiện phép cộng logic giữa hai hay nhiều biến nhị phân.
Hàm boolean: Y=A+B
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 28 A Y B
a) Lược đồ luận lý A B Y=A+B 0 0 0 0 1 1 1 0 1 1 1 1
b) Bảng chân trị A B Y t
c) Giản đồ thời gian
Hình 2.10 Lược đồ luận lý – bảng chân trị - giản đồ thời gian cổng OR
2.1.2.5. Cổng NAND
Khái niệm: Là cổng có ít nhất hai ngõ vào và một ngõ ra. Ngõ ra có giá trị thấp khi tất cả ngõ vào có giá trị cao.
Thực hiện cùng 1 lúc 2 chức năng: AND và NOT.
Hàm boolean: Y=(A.B)’hoặc Y=(AB)’ A A Y Y B B
a) Lược đồ luận lý A B Y=(A.B)’ 0 0 1 0 1 1 1 0 1 1 1 0
b) Bảng chân trị
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 29 A B Y t
c) Giản đồ thời gian cổng NAND
Hình 2.11Lược đồ luận lý – bảng chân trị - giản đồ thời gian cổng NAND
2.1.2.6. Cổng NOR
Khái niệm: Là cổng có ít nhất hai ngõ vào và một ngõ ra. Ngõ ra có giá trị thấp khi có ít nhất
một ngõ vào có giá trị cao.
Thực hiện cùng 1 lúc 2 chức năng: OR và NOT.
Hàm boolean: Y=(A+B)’ A A Y Y B B
a) Lược đồ luận lý A B Y=(A+B)’ 0 0 1 0 1 0 1 0 0 1 1 0
b) Bảng chân trị
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 30 A B Y t
c) Giản đồ thời gian cổng NOR
Hình 2.12Lược đồ luận lý – bảng chân trị - giản đồ thời gian NOR
2.1.2.7. Cổng XOR
Khái niệm: Là cổng có ít nhất hai ngõ vào và một ngõ ra. Ngõ ra có giá trị cao (1) khi số ngõ
vào có giá trị cao (một) là số lẻ (1, 3, 5, …)
Thực hiện phép toán EX-OR (cộng ngoại trừ - cộng bỏ qua số nhớ) giữa 2 biến nhị phân.
Hàm boolean: Y=AB = A’.B+A.B’
Y=0 khi A và B cùng mức logic
Y=1 khi A và B cùng mức logic A Y B
a) Lược đồ luận lý A B Y= AB 0 0 0 0 1 1 1 0 1 1 1 0
b) Bảng chân trị
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 31 A B Y t
c Giản đồ thời gian cổng XOR
Hình 2.13 Lược đồ luận lý – bảng chân trị - giản đồ thời gian XOR
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 32
2.2. Tối giản mạch số
2.2.1. Phương pháp Boolean
Các mạch số được thiết kế từ những nguyên tố nhỏ nhất gọi là cổng logic (gate). Các cổng này
được ấu hành từ diod, transistor và điện trở, để rồi đầu ra của nó sẽ có giá trị như các phép toán logic
cơ bản (NOT, OR, AND).Việc dùngđại số Booleanđể mô tả và phân tích các cổng logic cơ bản này,
sau đó sẽ mở rộng ra phân tích và thiết kế cách nối các công lại với nhau để tạo thành các mạch số cần thiết.
Ví dụ hàm Boolean: F = x + y’z có bảng chân trị (Hình 2.14a) và biểu diễn giản đồ luận lý (Hình 2.14b). X y z y’ y’z F=x+y’z 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1
a)Bảng chân trị hàm F = x + y’z x F y z
b)Lược đồ luận lý của hàm F = x + y’z
Hình 2.14 Bảng chân trị - lược đồ luận lý của hàm F = x + y’z
Để tận dụng các phương pháp đơn giản, cần một số đồng nhất thức trong đại số Boolean. Điểm
đáng lưu ý là mỗi định luật có hai dạng đối ngẫu của nhau. Bằng cách hoán đối AND và OR, cũng như
0 và 1, có thể tạo dạng này bằng dạng kia. Bảng sau liệt kê các đẳng thức cơ bản nhất của đại số Boolean
(Hình 2.15) và chứng minh tất cả định luật thông qua xây dựng bảng chân trị.
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 33 TT TÊN DẠNG AND DẠNG OR 1.
Định luật thống nhất 1.X =X 0+X=X 2. Định luật không 0.X=0 1+X=1 3. Định luật Idempotent X.X=X X+X=X 4.
Định luật nghịch đảo X.X’=0 X+X’=1 5. Định luật giao hoán X.Y=Y.X X+Y=Y+X 6. Định luật kết hợp X.(YC)=(XY).C (X+Y)+C=X+(Y+C) 7. Định luật phân bố X+(YC)=(X+Y)(X+C) X(Y+C)=XY+XC 8. Định luật hấp thụ X(X+Y)=X X+XY=X 9. Định luật Demorgan (XY)’=X’+Y’ (X+Y)’=X’.Y’
Hình 2.15 Bảng liệt kê các đẳng thức cơ bản nhất của đại số Boolean
Định luật De Morgan đưa ra ký pháp thay thế và rất quan trọng đối với các cổng NOR và
NAND. Nó cho phép ta thay thế từ cổng OR sang AND và ngược lại. Hình 2.16 cho ta thấy cách chuyển
từ cổng AND sang cổng OR nhờ định lý DeMorgan (AB)’=A’+B’. Ta có cổng NAND biểu diễn hàm
F=(A.B)’sẽ tương đương với cổng OR vớiđầu vào được nghịch đảo biểu diễn cho hàmF=A’+B’ hay
nói cách khác cổng NAND được biểu diễn bằng 2 cách.
Tương tự như vậy ta cũng có cổng NOR tươngđương như trong Hình 2.17 nhờ vào định lý
DeMorgan cho dạng OR, F=A’+B’=(AB)’ A A A F F F B B B
Hình 2.16 Lược đồ luận lý F=(AB)= A’ + B’ A A A F F F B B B
Hình 2.17 Lược đồ luận lý F=A’ + B’ = (AB)’
Dạng tổng quát của định lý DeMorgan có dạng sau:
(x1+x2+….+ xn)’ = x’1.x’2.….. x’n
(x1.x2.…..xn)’ = x’1+x’2+….+ x’n
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 34
Phân tích và thiết kế: (Mô tả bổ sung trang 38)
Ngõ vào X: cửa lái, (X cửa hở; X’ cửa đóng)
Ngõ vào Y: bộ phận đánh lửa (Y: máy chạy; Y’: máy tắt)
Ngõ vào Z: đèn pha (Z: đèn sáng; Z’ đèn tắt)
Ngõ ra là hàm F: báo động
Theo yêu cầu ví dụ 2:
- Đèn pha sáng trong lúc (bộ phận đánh lửa tắt) xe tắt máy -> báo động F=1 (Z: đèn sáng, Y’: tắt )
- Cửa mở (ô tô ) trong lúc (bộ phận đánh lửa hoạt động) xe đang chạy -> báo động F=1 (X cửa hở, Y: máy chạy)
Suy ra: F=ZY’+XY
Bảng chân trị của hàm ra như Hình 2.20 và lược đồ luận lý Hình 2.21 X Y Z Y’ ZY’ XY F Đếm Ý nghĩa (cửa (đánh (đèn (đánh (đp sáng (cl mở lái) lửa) pha) lửa- Và đl tắt) và dl tắt) bật) 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1
Đèn sáng khi động cơ tắt (nổ) 0 1 0 0 0 0 0 2 0 1 1 0 0 0 0 3 1 0 0 1 0 0 0 4 1 0 1 1 1 0 1 5
Đèn sáng khi động cơ tắt (nổ) 1 1 0 0 0 1 1 6
động cơ hoạt động (nổ) trong khi cửa mở 1 1 1 0 0 1 1 7
động cơ hoạt động (nổ) trong khi cửa mở
Hình 2.20 Bảng chân trị mạch logic X Y XY F Y’Z Z
Hình 2.21. F= XY + Y’Z -> Lược đồ luận lý mạch logic (báo động)
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 35
2.2.2. Phương pháp Karnaugh
Một mạch số phức tạp sẽ tạo ra một biểu thức đại số rất phức tạp. Bảng chân trị biểu thị của
một hàm là duy nhất, nhưng hàm có thể có nhiều dạng khác nhau hay có thể có nhiều mạch số khác
nhau cho cùng một chức năng. Biết rằng biểu thức có thể đơn giản hóa dựa vào đại số Boolean. Tuy
nhiên qui trình này thường chỉ áp dụng được đối với các bài toán đơn giản, còn đối với các bài toán
phức tạp thì nó không có những qui tắc cho phép ta tiên đoán trước bước đi tiếp theo trong quá trình
đơn giản. Phương pháp dùng bản đồ Karnaugh giúp đơn giản các biểu thức một cách nhanh chóng, dễ hiểu và hiệu quả hơn.
Để tối thiểu hóa hàm Boolean bằng phương pháp bảngKarnaugh phải tuân thủ theo qui tắc về ô kế cận:
Hai ô được gọi là kế cận nhau là hai ô mà khi ta chuyển từ ô này sang ô kia chỉ làm thay đổi giá
trị của 1 biến. Quy tắc chung của phương pháp rút gọn bằng bảng Karnaugh là gom (kết hợp) các ô kế
cận lại với nhau. Khi gom 2 ô kế cận nhau sẽ loại được 1 biến, gom 4 ô kế cận sẽ loại được 2 biến, gom
8 ô kế cận sẽ loại được 3 biến
Tổng quát:, khi gom 2nô kế cận sẽ loại được n biến. Những biến bị loại là những biến khi ta đi
vòng qua các ô kế cận mà giá trị của chúng thay đổi.
Những điều cần lưu ý:
- Vòng gom được gọi là hợp lệ khi trong vòng gom đó có ít nhất 1 ô chưa thuộc vòng gom nào.
- Những ô nào có giá trị tùy ý ta biểu diễn trong ô đó bằng ký hiệu x, và những ô đó được gọi là tùy định.
- Việc kết hợp những ô kế cận với nhau còn tùy thuộc vào phương pháp biểu diễn hàm
Boolean theo dạng tổng các tích (còn gọi là dạng 1) hay theo dạng tích các tổng (còn
gọi là dạng 2). Điều này có nghĩa là: nếu ta biểu diễn hàm Boolean theo dạng 1 thì ta
chỉ quan tâm những ô kế cận nào có giá trị bằng 1 và tùy định, ngược lại nếu ta biểu
diễn hàm Boolean dưới dạng 2 thì ta chỉ quan tâm những ô kế cận nào có giá trị bằng 0
và tùy định. Ta quan tâm những ô tùy định sao cho những ô này kết hợp với những ô có
giá trị bằng 1 (nếu biểu diễn theo dạng 1) hoặc bằng 0 (nếu biểu diễn theo dạng 2) sẽ
làm cho số lượng ô kếcận là 2n lớn nhất.
- Các ô kế cận muốn gom được phải là kế cận vòng tròn nghĩalà ô kế cận cuối cũng là ô kế cận đầu tiên.
- Các vòng phải được gom sao cho số ô có thể vào trong vònglà lớn nhất và nhớ là để đạt
được điều đó, thường ta phải gom cả những ô đã gom vào trong các vòng khác.
Mục đích cần đạt
- Biểu thức có chứa ít nhất các thừa số và mỗi thừa số chứa ít nhất các biến.
- Mạch logic thực hiện có chứa ít nhất các vi mạch số.
Tóm lại:Phương pháp dùng bản đồ Karnaugh sẽ được dùng hầu như trong thiết kế mọi mạch
số vì vậy có một tầm quan trọng đặc biệt mà các sinh viên phải hiểu rõ thật chắc chắn.
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 36
2.2.2.1. Bản đồ Karnaugh 2 biến
Bản đồ Karnaugh (gọi tắt là bản đồ K) 2 biến là một bản đồ có 4 ô, vị trí trong mỗi ô tương ứng
với tổ hợp biến đầu vào. Ở ngoài các cột và dòng ta ghi các giá trị tương ứng của các biến. Ở đây có2
hàng biểu thị cho 2 giá trị của biến A (0 và 1) và 2 cộtbiểu thị cho 2 giá trị của biến B. Tọa độ của mổi
ô tương ứng với tổ hợp nhị phân của các biến đầu vào. Ví dụ như trong (Hình 2.22), tại tọa độ A=0 và
B=0 tương ứng với tổ hợp AB=00 hay ta ghi làA’B’ là giá trị đầu ra f=1. Tại tọa độAB=01 giá trị đầu
ra tương ứng x=0 nên ta ghi vào ô tương ứng giá trị 0. Tương tự như vậy cho các ô còn lại ta sẽ có được
bản đồ K như trong (Hình 2.22 c). A B f B 0 0 1 A 0 1 0 1 0 f=A’B’+AB 0 1 0 1 0 0 1 1 1 1 0 1
a.Bảng chân trị
b.Hàm biểu diễn c.Bản đồ K
Hình 2.22 Mô tả bản đồ K 2 biến
Ngoài ra, một dạng khác để biểu diễn K 2 biến là: A B Thập phân B 0 0 0 A 0 1 0 1 1 0 0 1 1 0 2 1 1 3 1 2 3
a.Bảng chân trị so với hệ thập phân
c.Bộ trị K 2 biến
Hình 2.23 Mô tả bản đồ K 2 biến với dạng thập phân
Vậy, f=A’B’+AB được ghi làf(A,B) = (0,3). Suy ra, biểu đồ K được thể hiện như: B B A 1 0 A 0 1
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 37
2.2.2.2. Bản đồ Karnaugh 3 biến
Cách điền vào bản đồ K 3 biến với bảng chân trị hệ thập phân.Bộ trị bản đồ K 3 biến sẽ có dạng (Hình 2.24) Y Y’ Y 00 01 11 10 0 0 1 3 2 0 000 001 011 010 X 1 4 5 7 6 1 100 101 111 110 Z Z
Hình 2.24 Bộ trị bản đồ K 3 biến
2.2.2.3. Bản đồ Karnaugh 4 biến
Tương tự, cách điền bản đồ K 4 biến sẽ có dạng(Hình 2.25) C 00 01 11 10 00 0 1 3 2 01 4 5 7 6 B 11 12 13 15 14 A 10 8 9 11 10 D
Hình 2.25 Bộ trị bản đồ K 4 biến
Trong thực tếchỉ dùng các bản đồ cho từ 3 biến trở lên, và cũng chỉ dùng cho đến 5 biến vì
nhiều hơn nữa thì sẽ rất phức tạp vì ở đây dùng phương pháp trực quan. Để hiểu rõ cách dùng bản đồ
Karnaugh hãy xem xét các ví dụ cụ thể sau:
Ví dụ 3: Để làm một bộ báo hiệu cho lái xe biết một số điều kiện, với thiết kế 1 mạch báo động như sau:
Với tín hiệu F= 0 (kèn không kêu), lúc này trạng thái: cửa đóng (X=0); bộ phận đánh lửa
tắt/động cơ ô tô không chạy (Y=0) ; đèn pha tắt (Z=0).
Thiết kế mạch báo động làm sao cho bộ phận báo động sẽ hoạt động (báo động = 1: kêu beep)
khi tồn tại một trong 2 trạng thái sau:
- Cửa mở (X=1) trong lúc bộ phận đánh lửa hoạt động/ động cơ hoạt động → BÁO ĐỘNG
(Y=1) (KÈN). Cho dù đèn có sáng hoặc tắt (Z=1/ Z=0).
- Đèn pha sáng (Z=1) trong lúc bộ phận đánh lửa tắt=động cơ KHÔNG hoạt động (Y=0)
→ (Y=1) BÁO ĐỘNG (KÈN), Cho dù CỬA có mở/đóng (Z=1/ Z=0) X 0 & Cửa lái Mạch F Y 0 Báo 0 Bộ phận đánh lửa Báo động Động Đèn pha Z 0
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 38
hãy sẽ đơn giản bằng bản đồ K (Karnaugh) 3 biến: F(A,B,C)=Σ(0,2,4,5,6)
Giải: Trước hết đề bài ghi như vậy có nghĩa là tại các giá trị mà tổ hợp đầu vàoΣ(0,2,4,5,6):
0nghĩa là (ABC=000), 2 nghĩa là (ABC=010), 4 nghĩa là(ABC=100),5 nghĩa là(ABC=101), 6 nghĩa là
(ABC=110) thì giá trị của hàm F sẽ bằng 1 hay nói cách khác giá trị đầu ra bằng 1.
Bước 1: Điền giá trị 1 (bộ trị) bản đồ Karnaugh
Hàm F biểu diễn các ô cho giá trị hàm bằng 1, mỗi ô tương ứng với một tổ hợp các biến đầu
vào. Như vậy ở các ô có giá trị đầu vào là 0(ABC=000),2(ABC=010), 4(ABC=100), 5(ABC=101) và
6(ABC=110) sẽ có giá trị là 1 (Hàm F =1) B 00 01 11 10 0 1 1 A 1 1 1 1 C
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 39
Bước 2: Nhóm các phần tử gần nhau theo từng nhóm, từ bản đồ chính ta có 2 nhóm . Nhóm 1 B 1 1 A 1 1 1 Nhóm 2 C
Từ bản đồ trên sẽ nhóm được 2 nhóm. (nhóm 1: 4 ô
- Nhóm 1: ta nhóm tối đa được 4 ô, và 4 ô này cho ta biểu thức C’ (trong 4 ô này thì chỉ
có biến C là không đổi và C=0 nên ta biểu diễn dưới dạng C’ ). -
Nhóm 2: nhóm ô còn lại với 1 ô đã nhóm ở nhóm 1 và cho ta biểu thứcAB’.
Bước 3: Viết lại hàm theo các nhóm ở bản đồ Karnaugh, ta sẽ có: F(A,B,C) = AB’+C’
Bước 4: Vẽ lược đồ luận lý sau khi đơn giản A B F C
Ví dụ 4:hãy sẽ đơn giản bằng bản đồ K 4 biến: F(A,B,C,D) =Σ(0,1,2,6,8,9,10)
Bước 1: Điền giá trị 1 (bộ trị) bản đồ Karnaugh C 1 1 1 1 B A 1 1 1 D B’C’, A’CD’
Bước2:Nhóm các phần tử gần nhau 1 1 1 1 1 1 1
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 40
Việc điền bộ trị 1 trên bản đồ K nêu trên ta có được 3 nhóm. Để dễ dàng trong việc viết phân
trình từ một bộ trị trên ta có thể tách ra là 3 nhóm rời rạc như sau: 1 1 1 1 1 1 Bước 1 1 1 1 B’D’ B’C’ A’CD’
3: Viết lại hàm theocác nhómởbản đồ Karnaugh, ta sẽcó:
F(A,B,C,D) = B’D’+B’C’+A’CD’
Bước 4: Vẽ lược đồ luận lý sau khi đơn giản, F(A,B,C,D) = B’D’+B’C’+A’CD’ A B C D F
2.2.2.4. Bản đồ Karnaugh 4 biến dạng tích các tổng:
Biểu thức Boolean xuất phát từ bản đồ của các ví dụ trên biểu diễn dưới dạng tổng các
tích.Trong một số trường hợp cần biểu diễn hàm đơn giản dưới dạng tích các tổng.
Qui trình tạo hàm dạng tích các tổng như sau:
Đánh 0 vào các ô trống và nhóm lại các ô liền kề, ta sẽ nhận được F’
Lấy bù F’ được F là tích các tổng.
Ví dụ 5: hãy đơn giản F bằng bản đồ K 4 biến theo dạng tích các tổng:
F(A,B,C,D) = (0,1,2,5,8,9,10) VD4 (bài toán trên, tổng các tích):
F(A,B,C,D) =Σ(0,1,2,6,8,9,10)
TÍCH CÁC TỔNG -> F(A,B,C,D) = (0,1,2,6,8,9,10)
Bước 1: Điền giá trị 1 (bộ trị) bản đồ Karnaugh C 1 1 1 1 B A 1 1 1 D
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 41
Các giá trị bỏ trống còn lại điền giá trị 0, nhận giá trị F’ như hình sau (F’ , VD 4) C 0 1 1 0 1 0 0 0 1 0 0 0 B 0 0 0 0 0 0 0 0 A 0 1 1 0 1 D Vd4:F’=BC’+CD+AB
Bước 2: Nhóm các phần tử gần nhau của F’ 0 0 0 0 0 0 0 0 0
Để dễ dàng trong việc viết phân trình từ một bộ trị trên ta có thể tách ra là 3 nhóm rời rạc sau: 0 0 0 0 0 0 0 0 0 0 0 0 AB BD’ CD
Bước 3: Viết lại hàm F’ theo các nhóm ở bản đồ Karnaugh, ta sẽ có:
F’(A,B,C,D) = AB + BD’+ CD
Vd4:F’=BC’+CD+AB//F(A,B,C,D) =Σ(0,1,2,6,8,9,10)
F=(F’)’=( BC’+CD+AB)’ ~ (X+Y+Z)’ Lấy bù F’ ta được F.
(X+Y+Z)’= X’.Y’.Z’~(BC’)’ . (CD)’ . (AB)’
F=(BC’)’ . (CD)’ . (AB)’
(F’)’= F=( AB + BD’+ CD)’
F=(B’+(C’)’) . (C’+D’) . (A’+B’)
F=(AB)’(BD’)’(CD)’
F= (B+C).(C’+D’).(A’+B’); vẽ luận lý
F=(A’+B’)( (B’+D)(C’+D’)
Bước 4: Vẽ lược đồ luận lý sau khi đơn giản F=(A’+B’) (B’+D) (C’+D’) như sau: A B C F D
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 42
Tài liệu giảng dạy học phần Kiến Trúc Máy tính (110079) ......................................................... 43