Đại số Boole Nguyễn Thế Vinh-ĐHKH
141
Với hàm G(x,y,z) nhận giá trị 1 khi x=z=0 và y=1 hoặc x=y=1 và z=0.
Tương tự như ở trên tích x.y.¬z=1 hoặc tích ¬x.y.¬z=1 sau đó xét tổng của
chúng. Vậy hàm G(x,y,z) sẽ là tổng của 2 tích này G(x,y,z)=x.y.¬z + ¬x.y.¬z
Như vậy việc tìm một biểu thức boole biểu diễn một hàm Boole có giá
trị đã cho ta dựa trên các giá trị 1 từ đó sẽ dẫn tới tích của các biến hoặc các
phần bù của nó.
6.1.3.2. Định nghĩa: Một biến boole hoặc phần bù của nó được gọi là
một tục biến. Tích của n tục biến đó được gọi là một tiểu hạng.
Ví dụ: Tìm tiểu hạng có giá trị là 1 nếu x
1
=x
3
=1 và x
2
=0
Tiểu hạng x
1
. ¬x
2
. x
3
có các tập giá trị đáp ứng được yêu cầu
Bằng cách lấy tổng Boole của các tiểu hạng phân biệt ta lập được biểu
thức Boole với tập giá trị đã được xác định. Kết quả của tổng bằng 1 khi và
chỉ khi tồn tại ít nhất 1 tiểu hạng nhận giá trị là 1, kết quả của tổng bằng 0 khi
mọi tiểu hạng đều bằng 0. Tổng các tiểu hạng để biểu diễn hàm được gọi là
triển khai tổng các tích của hàm Boole.
Ví dụ: Tìm triển khai tổng các tích của hàm sau: F(x,y,z)= ¬x.(y+z)
Ta có thể triển khai tổng này dựa vào hai phương pháp cơ bản sau
Phương pháp 1: Lập bảng chân trị
Giá trị
x y z ¬x y+z ¬x.(y+z)
0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 0 0 0
1 0 1 0 1 0
1 1 0 0 1 0
1 1 1 0 1 0
Dựa vào bảng ta có
F(x,y,z) = ¬x.¬y.z +¬x.¬z.y+ ¬x.z.y
Đại số Boole Nguyễn Thế Vinh-ĐHKH
142
Phương pháp 2: Sử dụng các luật
= ¬x.(y+z)
= ¬x.y + ¬x.z theo luật phân phối
= ¬x.1.y + ¬x.1.z theo luật đồng nhất
= ¬x.(z+¬z).y + ¬x.(y+¬y).z theo luật phần tử bù
=¬x.z.y + ¬x.¬z.y + ¬x.y.z + ¬x.¬y.z theo luật phân phối
= ¬ x.z.y + ¬x.¬z.y + ¬x.¬y.z theo luật lũy đẳng
6.2. MẠCH LÔGIC.
6.2.1. Cổng lôgic:
Xét một thiết bị như hình trên, có một số đường vào (dẫn tín hiệu vào)
và chỉ có một đường ra (phát tín hiệu ra). Giả sử các tín hiệu vào x
1
, x
2
, …, x
n
(ta gọi là đầu vào hay input) cũng như tín hiệu ra F (đầu ra hay output) đều chỉ
có hai trạng thái khác nhau, tức là mang một bit thông tin, mà ta ký hiệu là 0
và 1.
Ta gọi một thiết bị với các đầu vào và đầu ra mang giá trị 0, 1 như vậy
là một mạch lôgic.
Đầu ra của một mạch lôgic là một hàm Boole F của các đầu vào x
1
, x
2
,
…, x
n
. Ta nói mạch lôgic trong hình trên thực hiện hàm F.
Các mạch lôgic được tạo thành từ một số mạch cơ sở, gọi là cổng lôgic.
Các cổng lôgic sau đây thực hiện các hàm phủ định, hội và tuyển.
1. Cổng NOT: Cổng NOT thực hiện hàm phủ định. Cổng chỉ có một
đầu vào. Đầu ra F(x) là phủ định của đầu vào x.
=
=
==
.01
,10
)(
xkhi
xkhi
xxF
Chẳng hạn, xâu bit 100101011 qua cổng NOT cho xâu bit 011010100.
x
1
x
2
x
n-1
x
n
M
F(x
1
, x
2
, …, x
n
)
x
F(x)= x
Đại số Boole Nguyễn Thế Vinh-ĐHKH
143
2. Cổng AND: Cổng AND thực hiện hàm hội. Đầu ra F(x,y) là hội
(tích) của các đầu vào.
==
==
0
,11
),(
yxkhi
xyyxF
Chẳng hạn, hai xâu bit 101001101 và 111010110 qua cổng AND cho
101000100.
3. Cổng OR: Cổng OR thực hiện hàm tuyển (tổng). Đầu ra F(x,y) là
tuyển (tổng) của các đầu vào.
==
==
=+=
.00
,111
),(
yxkhi
yhayxkhi
yxyxF
Chẳng hạn, hai xâu bit 101001101 và 111010100 qua cổng OR cho
111011101.
6.2.2. Mạch lôgic
6.2.2.1. Tổ hợp các cổng: Các cổng lôgic có thể lắp ghép để được
những mạch lôgic thực hiện các hàm Boole phức tạp hơn. Như ta đã biết rằng
một hàm Boole bất kỳ có thể biểu diễn bằng một biểu thức chỉ chứa các phép
¬, ., +. Từ đó suy ra rằng có thể lắp ghép thích hợp các cổng NOT, AND, OR
để được một mạch lôgic thực hiện một hàm Boole bất kỳ.
Ví dụ: Xây dựng một mạch lôgic thực hiện hàm Boole cho bởi bảng
sau.
trong các trường hợp khác.
F(x,y)=xy
x
y
F(x,y,z)=xyz
x
y
z
F(x,y)=x+y
x
y
F=x+y+z+t
x
y
z
t
Đại số Boole Nguyễn Thế Vinh-ĐHKH
144
Theo bảng này, hàm F có dạng tổng (tuyển) chuẩn tắc hoàn toàn là:
zyxzxyxyzzyxF ++=),,( .
Hình dưới đây vẽ mạch lôgic thực hiện hàm F đã cho.
Biểu thức của F(x, y, z) có thể rút gọn:
zyxxyzyxzzxyzyxzxyxyz +=++=++ )( .
Hình dưới đây cho ta mạch lôgic thực hiện hàm zyxxy + .
x y z F(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
x
y
z
zyxzxyxyzF ++=
Đại số Boole Nguyễn Thế Vinh-ĐHKH
145
Hai mạch lôgic trong hai hình trên thực hiện cùng một hàm Boole, ta
nói đó là hai mạch lôgic tương đương, nhưng mạch lôgic thứ hai đơn giản
hơn.
Vấn đề tìm mạch lôgic đơn giản thực hiện một hàm Boole F cho trước
gắn liền với vấn đề tìm biểu thức đơn giản nhất biểu diễn hàm ấy. Đây là vấn
đề khó và lý thú, tuy ý nghĩa thực tiễn của nó không còn như mấy chục năm
về trước.
Ta vừa xét việc thực hiện một hàm Boole bất kỳ bằng một mạch lôgic
chỉ gồm các cổng NOT, AND, OR.
Dựa vào đẳng thức yxyx .=+ cũng như yxxy += , cho ta biết hệ {., −}
và hệ {+, −} cũng là các hệ đầy đủ. Do đó có thể thực hiện một hàm Boole bất
kỳ bằng một mạch lôgic chỉ gồm có các cổng NOT, AND hoặc NOT, OR.
Xét hàm Sheffer
==
==
=↑=
.001
,10
),(
yhayxkhi
yxkhi
yxyxF Mạch lôgic thực
hiện hàm ↑ gọi là cổng NAND, được vẽ như hình dưới đây.
Dựa vào các đẳng thức )()(),()(, yyxxyxyxyxxyxxx ↑↑↑=+↑↑↑=↑= ,
cho ta biết hệ {↑ } là đầy đủ, nên bất kỳ một hàm Boole nào cũng có thể thực
hiện được bằng một mạch lôgic chỉ gồm có cổng NAND.
x
y
z
•
•
zyxxyF +=
O
x
y
yx ↑
Đại số Boole Nguyễn Thế Vinh-ĐHKH
146
Xét hàm Vebb
==
==
=↓=
.01
,110
),(
yxkhi
yhayxkhi
yxyxF Mạch lôgic thực
hiện hàm ↓ gọi là cổng NOR, được vẽ như hình dưới đây.
Tương tự hệ {↓ } là đầy đủ nên bất kỳ hàm Boole nào cũng có thể thực
hiện được bằng một mạch lôgic chỉ gồm có cổng NOR.
Một phép toán lôgic quan trọng khác là phép tuyển loại:
≠
=
=⊕=
.1
,0
),(
yxkhi
yxkhi
yxyxF
Mạch lôgic này là một cổng lôgic, gọi là cổng XOR, được vẽ như hình dưới
đây.
6.2.2.2. Mạch cộng: Nhiều bài toán đòi hỏi phải xây dựng những mạch
lôgic có nhiều đường ra, cho các đầu ra F
1
, F
2
, …, F
k
là các hàm Boole của các
đầu vào x
1
, x
2
, …, x
n
.
Chẳng hạn, ta xét phép cộng hai số tự nhiên từ các khai triển nhị phân
của chúng. Trước hết, ta sẽ xây dựng một mạch có thể duợc dùng để tìm x+y
với x, y là hai số 1-bit. Đầu vào mạch này sẽ là x và y. Đầu ra sẽ là một số 2-
bit cs , trong đó s là bit tổng và c là bit nhớ.
0+0 = 00
0+1 = 01
1+0 = 01
1+1 = 10
O
yx ↓
x
y
x
y
yx ⊕
x
2
x
n-1
x
n
M
F
1
(x
1
, x
2
, …, x
n
)
x
1
F
2
(x
1
, x
2
, …, x
n
)
M
F
k
(x
1
, x
2
, …, x
n
)
x y c s
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Đại số Boole Nguyễn Thế Vinh-ĐHKH
147
Từ bảng trên, ta thấy ngay xycyxs =⊕= , . Ta vẽ được mạch thực hiện
hai hàm yxs ⊕= và xyc = như hình dưới đây. Mạch này gọi là mạch cộng
hai số 1-bit hay mạch cộng bán phần, ký hiệu là DA.
Xét phép cộng hai số 2-bit
12
aa và
12
bb ,
Thực hiện phép cộng theo từng cột, ở cột thứ nhất (từ phải sang trái) ta
tính
11
ba + được bit tổng s
1
và bit nhớ c
1
; ở cột thứ hai, ta tính
122
cba ++ , tức
là phải cộng ba số 1-bit.
Cho x, y, z là ba số 1-bit. Tổng x+y+z là một số 2-bit cs , trong đó s là
bit tổng của x+y+z và c là bit nhớ của x+y+z. Các hàm Boole s và c theo các
biến x, y, z được xác định bằng bảng sau:
Từ bảng này, dễ dàng thấy rằng:
zyxs ⊕⊕= .
Hàm c có thể viết dưới dạng tổng chuẩn tắc hoàn toàn là:
xyzzxyzyxyzxc +++= .
•
•
x
y
yxs ⊕=
xyc =
DA
x
y
s
c
12
12
bb
aa
x y z c s
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Đại số Boole Nguyễn Thế Vinh-ĐHKH
148
Công thức của c có thể rút gọn:
xyyxzzzxyyxyxzc +⊕=+++= )()()( .
Ta vẽ được mạch thực hiện hai hàm Boole zyxs ⊕⊕= và
xyyxzc +⊕= )( như hình dưới đây, mạch này là ghép nối của hai mạch cộng
bán phần (DA) và một cổng OR. Đây là mạch cộng ba số 1-bit hay mạch cộng
toàn phần, ký hiệu là AD.
Trở lại phép cộng hai số 2-bit
12
aa và
12
bb . Tổng
12
aa +
12
bb là một số
3-bit
122
ssc , trong đó s
1
là bit tổng của a
1
+b
1
:
111
bas ⊕= , s
2
là bit tổng của
a
2
+b
2
+c
1
, với c
1
là bit nhớ của a
1
+b
1
:
1222
cbas ⊕⊕= và c
2
là bit nhớ của
a
2
+b
2
+c
1
.
•
•
x
y
s
c
z
•
•
DA
DA
x
y
z
s
c
AD
s
c
x
y
z
Đại số Boole Nguyễn Thế Vinh-ĐHKH
149
Ta có được mạch thực hiện ba hàm Boole s
1
, s
2
, c
2
như hình dưới đây.
Dễ dàng suy ra mạch cộng hai số n-bit, với n là một số nguyên dương
bất kỳ. Hình sau cho một mạch cộng hai số 4-bit.
6.3. CỰC TIỂU HOÁ CÁC MẠCH LÔGIC
Hiệu quả của một mạch tổ hợp phụ thuộc vào số các cổng và sự bố trí
các cổng đó. Quá trình thiết kế một mạch tổ hợp được bắt đầu bằng một bảng
chỉ rõ các giá trị đầu ra đối với mỗi một tổ hợp các giá trị đầu vào. Ta luôn
luôn có thể sử dụng khai triển tổng các tích của mạch để tìm tập các cổng
lôgic thực hiện mạch đó. Tuy nhiên,khai triển tổng các tích có thể chứa các số
hạng nhiều hơn mức cần thiết. Các số hạng trong khai triển tổng các tích chỉ
khác nhau ở một biến, sao cho trong số hạng này xuất hiện biến đó và trong số
hạng kia xuất hiện phần bù của nó, đều có thể được tổ hợp lại. Chẳng hạn, xét
AD
DA
a
1
b
1
a
2
b
2
s
1
c
1
s
2
c
2
AD
DA
a
1
b
1
a
2
b
2
s
1
c
1
s
2
c
4
AD
c
2
c
3
s
3
a
3
b
3
AD
s
4
b
4
a
4
Đại số Boole Nguyễn Thế Vinh-ĐHKH
150
mạch có đầu ra bằng 1 khi và chỉ khi x = y = z = 1 hoặc x = z = 1 và y = 0.
Khai triển tổng các tích của mạch này là zyxxyz + . Hai tích trong khai triển
này chỉ khác nhau ở một biến, đó là biến y. Ta có thể tổ hợp lại như sau:
xzxzxzyyzyxxyz ==+=+ 1)( .
Do đó xz là biểu thức với ít phép toán hơn biểu diễn mạch đã cho. Mạch thứ
hai chỉ dùng một cổng, trong khi mạch thứ nhất phải dùng ba cổng và một bộ
đảo (cổng NOT).
6.3.1. Bản đồ Karnaugh
Để làm giảm số các số hạng trong một biểu thức Boole biểu diễn một
mạch, ta cần phải tìm các số hạng để tổ hợp lại. Có một phương pháp đồ thị,
gọi là bản đồ Karnaugh, được dùng để tìm các số hạng tổ hợp được đối với
các hàm Boole có số biến tương đối nhỏ. Phương pháp mà ta mô tả dưới đây
đã được Maurice Karnaugh đưa ra vào năm 1953. Phương pháp này dựa trên
một công trình trước đó của E.W. Veitch. Các bản đồ Karnaugh cho ta một
phương pháp trực quan để rút gọn các khai triển tổng các tích, nhưng chúng
không thích hợp với việc cơ khí hoá quá trình này. Trước hết, ta sẽ minh hoạ
cách dùng các bản đồ Karnaugh để rút gọn biểu thức của các hàm Boole hai
biến.
Có bốn hội sơ cấp khác nhau trong khai triển tổng các tích của một hàm
Boole có hai biến x và y. Một bản đồ Karnaugh đối với một hàm Boole hai
biến này gồm bốn ô vuông, trong đó hình vuông biểu diễn hội sơ cấp có mặt
trong khai triển được ghi số 1.
Các hình ô được gọi là kề nhau nếu các hội sơ cấp mà chúng biểu diễn
chỉ khác nhau một biến.
xy
yx
yx yx
y
y
x
x
Không có nhận xét nào:
Đăng nhận xét