LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG VIII ĐẠI SỐ BOOLE": http://123doc.vn/document/536743-giao-trinh-toan-roi-rac-chuong-viii-dai-so-boole.htm
x y F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
F
9
F
10
F
11
F
12
F
13
F
14
F
15
F
16
0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0
0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1
1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0
1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0
trong đó có một số hàm thông dụng như sau:
- Hàm F
1
là hàm hằng 0,
- Hàm F
2
là hàm hằng 1,
- Hàm F
3
là hàm hội, F
3
(x,y) được viết là xy (hay x
∧
y),
- Hàm F
4
là hàm tuyển, F
4
(x,y) được viết là x+y (hay x
∨
y),
- Hàm F
5
là hàm tuyển loại, F
5
(x,y) được viết là x
⊕
y,
- Hàm F
6
là hàm kéo theo, F
6
(x,y) được viết là x
⇒
y,
- Hàm F
7
là hàm tương đương, F
7
(x,y) được viết là x
⇔
y,
- Hàm F
8
là hàm Vebb, F
8
(x,y) được viết là x
↓
y,
- Hàm F
9
là hàm Sheffer, F
9
(x,y) được viết là x
↑
y.
Thí dụ 3: Các giá trị của hàm Boole bậc 3 F(x, y, z) = xy+
z
được cho bởi bảng sau:
8.2.2. Định nghĩa: Cho x là một biến Boole và
σ
∈
B. Ký hiệu:
=
=
=
.0
,1
σ
σ
σ
khix
khix
x
Dễ thấy rằng
σ
σ
=⇔=
xx 1
. Với mỗi hàm Boole F bậc n, ký hiệu:
T
F
= {(x
1
, x
2
, …, x
n
)
∈
B
n
| F(x
1
, x
2
, …, x
n
)=1}
Và gọi nó là tập đặc trưng của hàm F. Khi đó ta có:
F
F
TT
=
, T
F+G
= T
F
∪
T
G
, T
FG
= T
F
∩
T
G
.
Cho n biến Boole x
1
, x
2
, …, x
n
. Một biểu thức dạng:
k
k
iii
xxx
σ
σσ
2
2
1
1
118
x y z xy
z
F(x, y, z) = xy+
z
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1
trong đó
∈
k
σσσ
,,,
21
B, 1
niii
k
≤<<<≤
21
được gọi là một hội sơ cấp của n biến x
1
,
x
2
, …, x
n
. Số các biến xuất hiện trong một hội sơ cấp đựoc gọi là hạng của của hội sơ cấp
đó.
Cho F là một hàm Boole bậc n. Nếu F được biểu diễn dưới dạng tổng (tuyển) của
một số hội sơ cấp khác nhau của n biến thì biểu diễn đó được gọi là dạng tổng (tuyển)
chuẩn tắc của F. Dạng tổng (tuyển) chuẩn tắc hoàn toàn là dạng chuẩn tắc duy nhất của F
mà trong đó các hội sơ cấp đều có hạng n.
Thí dụ 4:
yxyx
+
là một dạng tổng chuẩn tắc của hàm x
⊕
y.
yx
+
và
yxyxyx
++
là các dạng tổng chuẩn tắc của hàm Sheffer x
↑
y.
8.2.3. Mệnh đề: Mọi hàm Boole F bậc n đều có thể biểu diễn dưới dạng:
∑
∈
+
=
i
n
i
B
nii
i
n
xxFxxxxxF
),,(
11
1
21
1
1
),,,,,(),,,(
σσ
σ
σ
σσ
(1),
trong đó i là số tự nhiên bất kỳ, 1 ≤ i ≤ n.
Chứng minh: Gọi G là hàm Boole ở vế phải của (1). Cho (x
1
, x
2
, …, x
n
)
∈
T
F
. Khi đó số
hạng ứng với bộ giá trị
σ
1
= x
1
, …,
σ
i
= x
i
trong tổng ở vế phải của (1) bằng 1, do đó (x
1
,
x
2
, …, x
n
)
∈
T
G
. Đảo lại, nếu (x
1
, x
2
, …, x
n
)
∈
T
G
tức là vế phải bằng 1 thì phải xảy ra bằng
1 tại một số hạng nào đó, chẳng hạn tại số hạng ứng với bộ giá trị (
σ
1
, …,
σ
i
), khi đó
x
1
=
σ
1
, …, x
i
=
σ
i
và f(
σ
1
,…,
σ
i
, x
i+1
,…, x
n
)=1 hay (x
1
, x
2
, …, x
n
)
∈
T
F
. Vậy T
F
=T
G
hay
F=G.
Cho i=1 trong mệnh đề trên và nhận xét rằng vai trò của các biến x
i
là như nhau, ta
được hệ quả sau.
8.2.4. Hệ quả: Mọi hàm Boole F bậc n đều có thể được khai triển theo một biến x
i
:
),,,1,,,(),,,0,,,(),,(
1111111 niiiniiin
xxxxFxxxxxFxxxF
+−+−
+=
.
Cho i=n trong mệnh đề trên và bỏ đi các nhân tử bằng 1 trong tích, các số hạng
bằng 0 trong tổng, ta được hệ quả sau.
8.2.5. Hệ quả: Mọi hàm Boole F bậc n đều có thể được khai triển dưới dạng:
∑
∈
=
Fn
n
T
nn
xxxxF
),,(
1
1
1
1
),,(
σσ
σ
σ
.
8.2.6. Chú ý: Từ Hệ quả 8.2.5, ta suy ra rằng mọi hàm Boole đều có thể biểu diễn dưới
dạng tổng (tuyển) chuẩn tắc hoàn toàn. Như vậy mọi hàm Boole đều có thể biểu diễn
bằng một biểu thức Boole chỉ chứa ba phép tích (hội), tổng (tuyển), bù (phủ định). Ta nói
rằng hệ {tích, tổng, bù} là đầy đủ.
Bằng đối ngẫu, ta có thể chứng minh một kết quả tương tự bằng việc thay tích bởi
tổng và ngược lại, từ đó dẫn tới việc biểu diễn F qua một tích các tổng. Biểu diễn này
được gọi là dạng tích (hội) chuẩn tắc hoàn toàn của F:
∏
∈
++=
Fn
n
T
nn
xxxxF
),,(
1
1
1
1
)(),,(
σσ
σ
σ
Thí dụ 5: Dạng tổng chuẩn tắc hoàn toàn của hàm F cho trong Thí dụ 3 là:
119
xyzzxyzyxzyxzyxzyxF
++++=
),,(
,
và dạng tích chuẩn tắc hoàn toàn của nó là:
))()((),,( zyxzyxzyxzyxF
++++++=
.
8.3. MẠCH LÔGIC.
8.3.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
khi
xxF
Chẳng hạn, xâu bit 100101011 qua cổng NOT cho xâu bit 011010100.
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.
120
x
1
x
2
x
n-1
x
n
F(x
1
, x
2
, …, x
n
)
F(x)=
x
trong các trường hợp khác.
x
F(x,y)=xy
x
y
F(x,y,z)=xyz
z
y
==
==
=+=
.00
,111
),(
yxkhi
yhayxkhi
yxyxF
Chẳng hạn, hai xâu bit 101001101 và 111010100 qua cổng OR cho 111011101.
8.3.2. Mạch lôgic:
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ỳ.
Thí dụ 6: Xây dựng một mạch lôgic thực hiện hàm Boole cho bởi bảng sau.
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:
zyxzxyxyzF ++=
121
z
F(x,y)=x+y
x
y
F=x+y+z+t
x
y
t
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
zyxxyzyxzzxyzyxzxyxyz
+=++=++
)(
.
Hình dưới đây cho ta mạch lôgic thực hiện hàm
zyxxy
+
.
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é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.
zyxxyF +=
yx ↑
yx
↓
122
•
x
•
y
z
x
O
y
x
O
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.
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
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
,
yx
⊕
yxs ⊕=
xyc
=
12
12
bb
aa
123
x
y
x
1
F
1
(x
1
, x
2
, …, x
n
)
x
2
F
2
(x
1
, x
2
, …, x
n
)
x
n-1
F
k
(x
1
, x
2
, …, x
n
)
x
n
x y c s
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
s
x
DA
c
y
•
•
x
y
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
+++=
.
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.
124
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
z
s
•
•
•
•
x
y c
z
x
s
AD
s
x
DADA
y
c
y
z
c
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
.
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.
8.4. 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
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:
125
b
1
b
2
a
2
a
1
DAAD
c
1
c
2
s
2
s
1
b
4
a
4
b
3
a
3
b
2
a
2
b
1
a
1
AD DAAD AD
s
1
c
1
s
2
c
4
c
2
c
3
s
3
s
4
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).
8.4.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.
Thí dụ 7: Tìm các bản đồ Karnaugh cho các biểu thức:
a)
yxxy
+
b)
yxyx
+
c)
yxyxyx
++
và rút gọn chúng.
Ta ghi số 1 vào ô vuông khi hội sơ cấp được biểu diễn bởi ô đó có mặt trong khai
triển tổng các tích. Ba bản đồ Karnaugh được cho trên hình sau.
Việc nhóm các hội sơ cấp được chỉ ra trong hình trên bằng cách sử dụng bản đồ
Karnaugh cho các khai triển đó. Khai triển cực tiểu của tổng các tích này tương ứng là:
a) y, b)
yxyx
+
, c)
yx
+
.
Bản đồ Karnaugh ba biến là một hình chữ nhật được chia thành tám ô. Các ô đó
biểu diễn tám hội sơ cấp có được. Hai ô đượ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. Một trong
các cách để lập bản đồ Karnaugh ba biến được
cho trong hình bên.
y
x
y
x
x
zy
zy
zy
yz
x
126
y
xy
yx
yx
yx
x
y
y
1
1
1
1
1
x
x
1
1
xyz
zxy
zyx
zyx
yzx
zyx
zyx
zyx
x
Để rút gọn khai triển tổng các tích ba biến, ta sẽ dùng bản đồ Karnaugh để nhận
dạng các hội sơ cấp có thể tổ hợp lại. Các khối gồm hai ô kề nhau biểu diễn cặp các hội
sơ cấp có thể được tổ hợp lại thành một tích của hai biến; các khối 2 x 2 và 4 x 1 biểu
diễn các hội sơ cấp có thể tổ hợp lại thành một biến duy nhất; còn khối gồm tất cả tám ô
biểu diễn một tích không có một biến nào, cụ thể đây là biểu thức 1.
Thí dụ 8: Dùng các bản đồ Karnaugh ba biến để rút gọn các khai triển tổng các tích sau:
a)
,zyxyzxzyxzxy
+++
b)
zyxzyxyzxzyxzyx
++++
,
c)
zyxzyxyzxzyxzyxzxyxyz
++++++
.
Bản đồ Karnaugh cho những khai triển tổng các tích này được cho trong hình sau:
Việc nhóm thành các khối cho thấy rằng các khai triển cực tiểu thành các tổng Boole của
các tích Boole là:
a)
yzxzyzx
++
, b)
zxy
+
, c)
zyx
++
.
Bản đồ Karnaugh bốn biến là một hình vuông được chia làm 16 ô. Các ô này biểu
diễn 16 hội sơ cấp có được. Một trong những cách lập bản đồ Karnaugh bốn biến được
cho trong hình dưới đây.
Hai ô đượ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. Do đó, mỗi một ô kề với bốn ô khác. Sự rút gọn một khai triển tổng các tích
bốn biến được thực hiện bằng cách nhận dạng các khối gồm 2, 4, 8 hoặc 16 ô biểu diễn
các hội sơ cấp có thể tổ hợp lại được. Mỗi ô biểu diễn một hội sơ cấp hoặc được dùng để
lập một tích có ít biến hơn hoặc được đưa vào trong khai triển. Cũng như trong trường
yz
zy
zy
zy
zy
zy
zy
yz
xx
zy
zy
zy
yz
x
zy
zyzy
yz
wx
xw
xw
xw
127
x x
1 1
1
1 1
1 1 1
1
1 1 1 1
1 1 1
x
wxyz
zwxy
zywx
zywx
yzxw
zyxw
zyxw
zywx
yzxw
zyxw
zyxw
zyxw
xyzw
zxyw
zyxw
zyxw
Không có nhận xét nào:
Đăng nhận xét