Chương 4. ĐẠI SỐ BOOL
I. HÀM BOOL
Nhiều mô hình tính toán trên thực tế chỉ làm việc trên 2 giá trị cụ thể là 0 và
1. Ví dụ các hệ toán mệnh đề, tập hợp các tập con của A với 3 phép toán lấy phần
bù, hợp và giao, trong đó A đóng vai trò 1 và  tương ứng với 0, các mạch máy
tính … Vì vậy cần nghiên cứu đại số Bool là đại số làm việc trên tập các giá trị
{0,1} và với 3 phép toán theo thứ tự ưu tiên là phần bù (-), nhân (.), cộng (+) được
định nghĩa giống các phép toán NOT, AND, OR trong đại số mệnh đề với T = 1, F
= 0. Cụ thể các phép toán phần bù (hoặc phủ định), nhân và cộng trong đại số Bool
được định nghĩa như sau :
0 = 1

0.0 = 0

0+0=0

1 = 0

0.1 = 0

0+1=1

1.0 = 0

1+1=1

1.1 = 1

1+0=1

Ví dụ : áp dụng bảng giá trị các phép toán Bool ở trên ta có thể tính được giá

trị của biểu thức : 0.1 + (1 + 0)(1 + 1) = 0.1 + (1.1) = 0 + 0 = 0.
1. Biểu thức và Hàm Bool
a. Biểu thức Bool

 Biến Bool : Cho tập B = {0,1}, và X = {x} là tập các biến nhận giá trị
trên B. Khi đó x được gọi là biến bool.
 Biểu thức Bool : Được định nghĩa đệ qui :
 0, 1, x1, ..., xn là các biểu thức Bool (xi là các biến Bool).
 Nếu B1, B2 là các biểu thức Bool thì B1, (B1B2), (B1+B2) cũng là các
biểu thức Bool.
Từ định nghĩa trên ta thấy giá trị của biểu thức cũng sẽ là 0 hoặc 1. Bằng
cách thay giá trị 0, 1 cho các biến trong biểu thức ta sẽ tính được giá trị của biểu
thức. Ví dụ : (x + y) z + xy là biểu thức Bool nhận giá trị 0 nếu với bộ giá trị của
các biến x, y, z là (0, 0, 0) và nhận giá trị 1 với bộ giá trị biến (0, 1, 0). Cũng giống
như trong đại số, để ngắn gọn ta có thể bỏ dấu nhân trong tích x.y và viết xy thay
cho x.y.
Vì đại số Bool là mô hình tổng quát của đại số mệnh đề nên các thảo luận


trong chương này liên quan đến biểu thức Bool cũng hoàn toàn đúng đối với các
công thức mệnh đề, trong đó các giá trị 0, 1 và các biến xi của đại số Bool tương
ứng với các giá trị T, F và các mệnh đề sơ cấp Xi trong đại số mệnh đề.
Tương tự trong đại số mệnh đề hai biểu thức Bool nếu có giá trị bằng nhau
trên mọi bộ giá trị của biến sẽ được gọi là 2 biểu thức tương đương.
b. Hàm Bool

Hàm Bool bậc n : Hàm fn : Bn  B được gọi là hàm Bool bậc n. Tức hàm có
n biến x1, x2, …, xn nhận giá trị 0, 1 và cho lại giá trị của hàm cũng là 0 hoặc 1.
Trong trường hợp không xảy ra nhầm lẫn, để đơn giản kí hiệu ta thường viết
f thay cho fn, và gọi ngắn gọn là hàm Bool thay cho hàm Bool bậc n.

Như vậy với n đầu vào có giá trị 0, 1 hàm f sẽ cho 1 đầu ra với giá trị 0, 1.
Giá trị của hàm Bool thường được cho trong các bảng, giống như các bảng chân trị
của các công thức mệnh đề.
n

Với hàm n biến sẽ có tất cả 2 2 hàm. Ví dụ ta có tất cả 4 hàm 1 biến và 16
hàm 2 biến được cho dưới dạng bảng như sau :
4 hàm bool 1 biến
x

f1

f2

f3

f4

0

0

0

1

1

1


0

1

0

1

trong đó f1 = 0, f2 = x, f3 = x, f4 = 1, nói cách khác các biểu thức Bool 0, x,
x, 1 biểu diễn các hàm Bool f1, f2, f3, f4.
Từ các hàm Bool có sẵn ta có thể tạo thành các hàm khác thông qua các phép
toán Bool. Ví dụ từ các hàm một biến f1, f2, f3, f4 ở trên ta có thể tạo thành các hàm
mới : f1, f2.f3, f1 + f4, … mà giá trị của nó có thể tính được và được liệt kê trong
bảng sau :
x

f1

f2

f3

f4

f1

f2.f3

f1 + f4


0

0

0

1

1

1

0

1

1

0

1

0

1

1

0


1

Hai hàm có cùng bảng giá trị sẽ được gọi là bằng nhau. Ví dụ trên cho ta thấy
f1 = f1 + f4.
c. Biểu diễn hàm bởi biểu thức

Một biểu thức được gọi là biểu diễn của một hàm nếu giá trị của chúng bằng


nhau trên mọi bộ giá trị của biến. Biểu thức biểu diễn hàm f được kí hiệu E(f), E f
hoặc E. Như vậy việc xét tính chất của hàm có thể được làm việc thông qua biểu
thức.
Chú ý rằng có thể có nhiều biểu thức cùng biểu diễn một hàm. Khi đó các
biểu thức cùng biểu diễn một hàm được gọi là các biểu thức tương đương. Ví dụ :
xy, xy + 0 và xy.1 là các biểu thức tương đương. Với E và E' tương đương ta viết
E  E'. Vì cùng biểu diễn một hàm nên các biểu thức tương đương là bằng nhau
trên mọi bộ giá trị của các biến.
Về mặt hình thức, để đơn giản nếu E và E' cùng biểu diễn hàm Bool f ta viết
f = E = E'
Bảng sau đây liệt kê 16 hàm Bool 2 biến cùng các biểu thức biểu diễn chúng.
Xy 00

01

10

11

E(f)


f1

0

0

0

0

0

f2

0

0

0

1

xy

f3

0

0


1

0

f4

0

0

1

1

f5

0

1

0

0

f6

0

1


0

1

y

f7

0

1

1

0

xy

f8

0

1

1

1

x+y


f9

1

0

0

0

xy

f10 1

0

0

1

xy

f11 1

0

1

0


f12 1

0

1

1

f13 1

1

0

0

f14 1

1

0

1

xy

f15 1

1


1

0

x|y

f16 1

1

1

1

1

x

trong đó để ngắn gọn ta đã dùng một số kí hiệu phép toán mới như , , ,
|, . Các kí hiệu này độc giả có thể liên tưởng lại các phép toán tương tự trong đại
số mệnh đề và đã được định nghĩa thông qua các phép toán phủ định, hội, tuyển
như sau :
 Phép toán kéo theo 

:

x  y = x  y


 Phép toán tương đương 


:

x  y = (x  y)  (y  x)

 Phép toán cộng loại trừ  (XOR)

:

x  y = xy + xy

 Phép toán | (NAND)

:

x | y = (x  y)

 Phép toán  (NOR)

:

x  y = ( x  y)

Có thể chứng minh dễ dàng các biểu thức trên là biểu diễn của các hàm f
tương ứng. Chúng tôi dành lại phần chứng minh cho độc giả như một bài tập.
2. Các hằng đẳng thức

Tên gọi

Hằng đẳng thức


Luật phần bù

x = x

Luật lũy đẳng

xx = x; x + x = x

Luật đồng nhất

x + 0 = x1 = x

Luật nuốt

x0 = 0; x + 1 = 1

Luật giao hoán

xy = yx; x + y = y + x

Luật kết hợp

x(yz) = (xy)z; x + (y + z) = (x + y) + z

Luật phân phối

x(y + z) = xy + xz; x + yz = (x + y)(x + z)

Luật De Morgan


(xy) = x + y; (x + y) = xy

Dùng bảng các hằng đẳng thức để chứng minh tính tương đương của các
biểu thức.
Ví dụ : Chứng minh x(x + y) = x

(x + 0)(x + y) : đồng nhất
x + 0.y

: phân phối ((x+0)(x+y) = x + 0y rút gọn)

x + y.0

: giao hoán

x+0

: nuốt

x

: đồng nhất

3. Tính đối ngẫu
a. Định nghĩa

Đối ngẫu của biểu thức : Cho biểu thức E. Đổi chỗ (0, 1), (+, .) ta được biểu
thức E* được gọi là biểu thức đối ngẫu của biểu thức E. Khi đó hàm được biểu
diễn bởi E* được gọi là hàm đối ngẫu của f, và được kí hiệu là f*.

Ví dụ : Cho hàm f(x,y,z) = x(y + 0)x.1 + (y + z) có đối ngẫu x + (y1) +


(x+0)(yz)
b. Nguyên lý đối ngẫu

Đối ngẫu 2 hàm (biểu thức) bằng nhau cho ra 2 hàm (biểu thức) bằng
nhau. Tức nếu f = g thì f* = g*.
Chứng minh điều trên bằng cách chứng minh thông qua định nghĩa biểu thức
và biểu thức đối ngẫu như chứng minh đối với các công thức mệnh đề.
Ví dụ : x(x + y) = x Luật hấp thụ


cũng đúng và là hấp thụ

x + xy = x

II. BIỂU DIỄN CÁC HÀM BOOL
1. Dạng chuẩn tắc của hàm Bool
a. Đặt vấn đề

 Cho một hàm bool bất kỳ, liệu có biểu thức bool nào biểu diễn nó.
 Nếu biểu diễn được thì dùng bao nhiêu phép toán để biểu diễn nó.
Ví dụ : Một uỷ ban 3 người biểu quyết về một vấn đề nào đó. Giả sử nếu có ít
nhất 2 người chấp thuận thì vấn đề được xem là thông qua và ngược lại. Hãy xây
dựng một biểu thức Bool để phản ánh kết quả của cuộc biểu quyết trên.
Giải : Gọi các thành viên uỷ ban là x, y, z và các giá trị 0, 1 biểu thị cho kết
quả bỏ phiếu của từng thành viên trong đó 1 là chấp thuận và 0 là ngược lại. Khi
đó kết quả cuộc bỏ phiếu được phản ánh thông qua hàm Bool f cho trong bảng
sau:

X
1

y
1

z
1

f
1*

Các tiểu hạng tương ứng
xyz

1

1

0

1*

xyz

1

0

1


1*

xyz

1

0

0

0

0

1

1

1*

0
1
0
0
0
0
1
0
0

0
0
0
Dạng tổng tích

xyz

F = xyz + xyz + xyz + xyz


Theo bảng trên ta thấy kết quả là thuận (1) nếu và chỉ nếu các thành viên bỏ
phiếu theo một trong các cách thể hiện trên các dòng 1, 2, 3, 5 tức cách bỏ phiếu
phải rơi vào một trong các bộ giá trị tương ứng của (x, y, z) là (1, 1, 1) hoặc (1, 1,
0) hoặc (1, 0, 1) hoặc (0, 1, 1). Từ đó hàm được tạo thành từ tổng các biểu thức
con sao cho mỗi biểu thức con biểu thị một khả năng bỏ phiếu ở trên tức biểu thức
con có giá trị 1 khi và chỉ khi bộ (x, y, z) nhận giá trị theo bộ số mà nó tương ứng.
Từ đó dễ thấy các biểu thức con được tạo :
 Tương ứng với (1, 1, 1) : xyz
 Tương ứng với (1, 1, 0) : xyz
 Tương ứng với (1, 0, 1) : xyz
 Tương ứng với (1, 1, 0) : xyz
Và do đó hàm f được thiết lập thành xyz + xyz + xyz + xyz. Ví dụ trên
có thể được tổng quát hoá cho ta một phương pháp tìm biểu thức đề biểu diễn một
hàm Bool bất kỳ, như trong phần tiếp theo
b. Các định nghĩa

 xi hoặc xi được gọi là biến hạng (term, literal) và kí hiệu là xi'
 tích x1' ... xn' gọi là các tiểu hạng (minterm, conjunction clause) hay hội
sơ cấp
 tổng : x1' + x2' + ... + xn' gọi là các đại hạng (maxterm, disjunction clause)

hay tuyển sơ cấp
Từ các định nghĩa trên có thể thấy :
 tiểu hạng = 1 khi và chỉ khi mọi xi' = 1  xi = 1 nếu xi' = xi và xi = 0 nếu
xi' = xi
 đại hạng = 0 khi và chỉ khi mọi xi' = 0  xi = 0 nếu xi' = xi và xi = 1 nếu
xi' =  xi
Ví dụ :
 Tiểu hạng x1 x2 x3 x4 x5 = 1 khi và chỉ khi (x1, x2, x3, x4, x5) = (1,
1, 0, 0, 1).
 Đại hạng x1 + x2 + x3 + x4 + x5 = 0 khi và chỉ khi (x1, x2, x3, x4,
x5) = (0,1,1,0,1)
c. Định lý

Mọi hàm Bool bất kỳ cấp n f(x1, x2, ..., xn) đều có thể biểu diễn được dưới
dạng :


 Tổng của các tiểu hạng hay còn gọi là dạng chuẩn tắc tuyển, tức
f = + (x11. . . xn1)
 Tích của các đại hạng hay còn gọi là dạng chuẩn tắc hội, tức
f = * (x11 + . . . + xn1)
Việc chứng minh định lý trên một cách không hình thức, có thể dễ dàng xây
dựng được dựa theo việc lập tổng các tiểu hạng với mỗi tiểu hạng dựa trên các
dòng giá trị có f = 1, hoặc lập tích của các đại hạng dựa trên các dòng có giá trị 0
như trong ví dụ mở đầu đã chỉ ra. Tuy nhiên, trong phần sau chúng ta sẽ phát biểu
lại định lý và chứng minh một cách chặt chẽ hơn.
Ví dụ : Cho f là hàm XOR () với bảng giá trị (xem định nghĩa ở trên) :
x
1


Y
1

f
0

tiểu hạng

1

0

1

xy

0

1

1

xy

0

0

0


Đại hạng
x + y

X+y

sẽ tương ứng với dạng chuẩn tắc tuyển : xy + xy hoặc chuẩn tắc hội : (x
+ y)(x + y)
Chú ý :
 Việc biểu diễn hàm f dưới dạng chuẩn tắc như trên còn được gọi là
khai triển f thành tổng các tích hoặc tích các tổng.
 Các dạng chuẩn tắc ở trên còn được gọi là dạng chuẩn tắc hoàn toàn vì
các tiểu hạng và đại hạng chứa đúng n hạng biến, phân biệt với các dạng
chuẩn tắc khác không chứa đủ n hạng biến (ví dụ : xyz + z hoặc (x+y)z),
tuy nhiên để đơn giản ta gọi chung chúng là dạng chuẩn tắc.
Để phục vụ việc chứng minh định lý trên một cách chặt chẽ về mặt toán học
ta sử dụng kí hiệu sau :
x

 xi i   i
 xi

if  i  1
if  i  0

 Tf = {(x1, x2, …, xn) : f(x1, x2, …, xn) = 1}
từ kí hiệu này có thể thấy: x i

i

= 1 khi và chỉ khi x i  i .


(Giả sử i = 1, theo định nghĩa x i

i

= xi, có giá trị 1 khi và chỉ khi xi = 1 tức


xi = i. Tương tự, giả sử i = 0 do định nghĩa nên x i
khi xi = 0 tức xi = i)

i

= xi, có giá trị 1 khi và chỉ

Khi đó định lý trên có thể phát biểu lại như sau :
Mọi hàm Bool cấp n f(x1, x2, …, xn) đều biểu diễn được dưới dạng :
 Chuẩn tắc tuyển :

f(x1, x2, …, xn)

 x1

=

1

( x1 , x 2 , ..., x n )Tf

 Chuẩn tắc hội :


f(x1, x2, …, xn)

=

x2

x

2

1
2
1  x2
( x1 , x 2 , . . ., x n )  Tf

... x n

n

 . . .  x n n

Chứng minh : Ở đây ta chỉ chứng minh cho trường hợp dạng chuẩn tắc tuyển. Khi
đó có thể chứng minh dạng chuẩn tắc hội một cách tương tự hoặc suy từ dạng
chuẩn tắc tuyển và nguyên lý đối ngẫu.
Để đơn giản ta gọi tổng các tiểu hạng ở vế phải là g(x1, x2, …, xn). Cần
chứng minh f = g với mọi (x1, x2, …, xn)  Bn. Lấy bộ giá trị bất kỳ của (x1, x2, …,
xn) = (1, 2, …, n)  Bn.
Giả sử f(1, 2, …, n) = 1  (1, 2, …, n)  Tf  x1 x 2 . . . x n là một
tiểu hạng của g(x1, x2, …, xn). Thay giá trị cụ thể của (x1, x2, …, xn) bởi

(1, 2, …, n) ta được tiểu hạng này bằng 1 (vì xi = i, i). Do đó g(1,
2, …, n) = 1 = f(1, 2, …, n).
Nếu f(1, 2, …, n) = 0 ta sẽ chứng minh mọi tiểu hạng của g cũng bằng
0, do đó g = 0. Thật vậy lấy bất kỳ tiểu hạng x1 x 2 . . . x n của g(x1, x2,
…, xn), tức f(1, 2, …, n) = 1. Tiểu hạng này bằng 1 (với (x1, x2, …, xn)
= (1, 2, …, n)) nếu i = xi = i, i. Do đó f(1, 2, …, n) = f(1, 2,
…, n) = 1, mâu thuẫn với giả thiết.
1

1

2

2

n

n

Vậy mọi f(x1, x2, …, xn) = g(x1, x2, …, xn) (x1, x2, …, xn)  Bn.
Tóm lại, từ các thảo luận trên ta thấy mọi hàm Bool đều biểu diễn được bởi
một biểu thức và mọi biểu thức đều biểu diễn một hàm Bool nào đó.
2. Tính đầy đủ
a. Định nghĩa : Một hệ đầy đủ là một tập hợp phép toán có khả năng biểu

diễn được mọi hàm.
Theo định lý khai triển hàm Bool thành dạng chuẩn tắc ta thấy hệ các phép
toán {, +, .} là một hệ đầy đủ. Vấn đề đặt ra liệu có thể biểu diễn mọi hàm Bool
với hệ đầy đủ có ít phép toán hơn ? Định lý sau đây cho thấy mọi hàm Bool đều có
thể biểu diễn được bằng biểu thức chỉ cần dùng 2 hoặc 1 phép toán.

b. Định lý : Các hệ sau : {+, }, {., }, {|}, {} là đầy đủ.

Chứng minh:




 Do hệ { , ., + } là đầy đủ và theo công thức De Morgan phép . có thể
biểu diễn thông qua {+, }, tương tự phép + biểu diễn được thông qua {.,
} nên các hệ trên là đầy đủ.
 Tương tự để chứng minh các hệ {|}, {} là đầy đủ, ta cần chứng minh các
phép toán ., +,  là biểu diễn được thông qua các phép toán |, . Cụ thể:
x = x | x

xy = (x | y) | (x | y)

x + y = (x | x) | (y | y)

x = x  x

x+y = (x  y)  (x  y)

xy = (x  x)  (y  y)

Để chứng minh hệ không đầy đủ (ví dụ hệ { +, . } là không đầy đủ) cần :
i. tìm một tính chất  nào đó sao cho nếu A và B có tính chất  thì A  B
cũng có tính chất  với  là các phép toán của hệ.  được gọi là tính
chất bảo toàn của hệ.
ii. chỉ ra một hàm nào đó không có tính chất , tức không thể biểu diễn
được qua các phép toán của hệ.

Ví dụ : { . } không phải là hệ đầy đủ. Vì, do x . x = x, nên nếu tiếp tục làm
toán với phép . ta luôn luôn được x, do đó không biểu diễn được hàm x. Ở đây
tính chất  là "hàm = x" và hàm không có tính chất đối với phép nhân là hàm x
III. RÚT GỌN CÁC HÀM BOOL
Trong các tiết trên chúng ta đã chứng minh được mọi hàm đều có thể biểu
diễn được bằng các biểu thức Bool. Tuy nhiên phương pháp khai triển hàm về
dạng chuẩn tắc hoàn toàn sẽ tạo ra biểu thức chứa nhiều phép toán và các toán
hạng (biến) nhiều khi nhiều hơn mức cần thiết. Ví dụ : bài toán biểu quyết quá bán
ở trên đã xây dựng được dạng chuẩn tắc tuyển là xyz + xyz + xyz + xyz dùng
3 biến và 14 phép toán. Tuy nhiên, ta có thể liệt kê một số biểu thức khác rút gọn
hơn và cũng biểu diễn hàm nói trên như :
Biểu thức

Số phép toán

xyz + xyz + xyz + xyz

14

xy + xyz + xyz

9

xy + z(xy + xy)
xy + xz + yz
xy + z(x + y)
…
…

8

5 (chuẩn tắc tối thiểu)
4 (tối thiểu)
4 (tối thiểu)
4 (tối thiểu)

Dạng biểu thức chuẩn tắc với số phép toán ít nhất được gọi là dạng chuẩn tắc


tối thiểu của hàm. Chú ý rằng một hàm có thể có nhiều dạng chuẩn tắc tối thiểu.
Thực tế dạng chuẩn tắc tối thiểu vẫn chưa phải là dạng tối thiểu của hàm (tức ít
phép toán nhất và không cần chuẩn tắc).
Từ đó một bài toán thực tế đặt ra là thiết kế các mạch thực hiện hàm Bool
sao cho sử dụng các loại mạch cơ bản là ít nhất và số lần sử dụng nó là ít nhất. Tức
cần biểu diễn các hàm dưới dạng các biểu thức tối thiểu. Đây là bài toán khó và
cho đến nay vẫn chưa được giải một cách có hiệu quả. Chỉ riêng các thuật toán tìm
dạng chuẩn tắc tối thiểu vẫn còn mang độ phức tạp rất lớn và việc mở rộng kết quả
của bài toán này cho hệ nhiều hàm hoặc xét trên hệ đầy đủ bất kỳ là vẫn còn nhiều
hạn chế.
Trong tiết này ta đưa ra thuật toán tìm dạng chuẩn tắc tối thiểu của hàm bất
kỳ theo phương pháp Quine-McCluskey. Hàm ban đầu được biểu diễn dưới dạng
chuẩn tắc tuyển (hoàn toàn) và được tìm theo định lý trong II.2 ở trên.
Để đơn giản ta xét hàm f = wxyz + wxy z = wxy(z + z ) = wxy.
Trong biểu thức trên ta có 2 tiểu hạng cấp 4 (chứa 4 biến), 2 tiểu hạng này
giống nhau ở 3 vị trí (wxy) và vị trí còn lại đối nghịch với nhau (z và z ), do đó nó
được rút gọn thành 1 tiểu hạng và đồng thời giảm được 1 cấp (từ cấp 4 xuống
thành cấp 3). Từ ý tưởng cơ bản này ta triển khai thuật toán cho trường hợp phức
tạp (tổng quát) hơn như sau.
Ví dụ : Rút gọn hàm được biểu diễn bởi :
wxy z + w x yz + w xyz + w x y z + w x y z + w x yz + w x y z
1.


Biểu diễn mỗi tiểu hạng cấp n bằng xâu bit độ dài n, trong đó bit thứ i =1 nếu
xi xuất hiện trong tiểu hạng và ngược lại. Để thuận tiện nên sắp xếp các tiểu
hạng giảm dần theo số số 1.
Bước 1

2.

1

wxy z

1110

2

w x yz

1011

3

w xyz

0111

4

wx yz


1010

5

w xy z

0101

6

w x yz

0011

7

w x yz

0001

Tạo tất cả các tích cấp n-1 bằng cách nhóm các tích cấp n chỉ khác nhau một
vị trí và loại bỏ biến hạng khác nhau này (bằng cách so sánh lần lượt từ xâu


đầu tiên với các xâu còn lại mà có số số 1 cách nhau không quá 1, tiếp tục lặp
lại với xâu thứ 2 , …). Xâu biểu diễn tích cấp n-1 được tạo bằng cách thay bit
bị loại bởi dấu - từ xâu tích cấp n.
Bước 1

3.


Bước 2

1

wxy z

1110

(1,4)

1-10

wy z

2

w x yz

1011

(2,4)

101-

wx y

3

w xyz


0111

(2,6)

-011

x yz

4

wx yz

1010

(3,5)

01-1

w xz

5

w xy z

0101

(3,6)

0-11


w yz

6

w x yz

0011

(5,7)

0-01

w yz

7

w x yz

0001

(6,7)

00-1

w xz

Tiếp tục tạo các tích có cấp nhỏ dần cho đến khi không tạo được nữa. Chú ý
chỉ nhóm các tích có dấu - cùng vị trí.
Bước 2


4.

Bước 3

(1,4)

1-10

wy z

((3,5),(6,7))

(2,4)

101-

wx y

(2,6)

-011

x yz

(3,5)

01-1

w xz


(3,6)

0-11

w yz

(5,7)

0-01

w yz

(6,7)

00-1

w xz

0--1

wz

Lập bảng các tích rút gọn và đánh dấu x vào ô các tiểu hạng (ban đầu) đã
được phủ bởi tích rút gọn này. Các tích được liệt kê từ cấp nhỏ nhất đến các
cấp lớn hơn cho đến khi tất cả các tiểu hạng đều được đánh dấu.
wxy z
1
a


wz

b

wy z

w x yz
2

w xyz

3
x

X

w x y z w x y z w x yz w x y z
4
6
5
7
x
x
x
x


c

wx y


x

d

x yz

x

e

w xz

x
x
x

x

…
Từ bảng lập được ta chọn các tích rút gọn theo chiến lược tham lam: tại mỗi
bước chọn tích rút gọn sao cho nó phủ được nhiều tiểu hạng nhất trong số các tiểu
hạng chưa được phủ. Theo ví dụ trên, đầu tiên ta chọn a phủ 3, 5, 6 và 7, tiếp theo
chọn b phủ được 1và 4. Để phủ tiểu hạng cuối cùng (2) ta có thể chọn tiếp c hoặc
d. Từ đó ta được dạng chuẩn tắc tối thiểu :
f = w z + wy z + w x y hoặc f = w z + wy z + x yz.


BÀI TẬP
I. HÀM BOOL

1.

Giải phương trình x + y = xy với x, y là các biến Bool.

2.

Chứng minh luật hấp thụ x + xy = x

3.

Chứng minh hàm f(x, y, z) = xy + yz + zx có giá trị 1 nếu và chỉ nếu có ít nhất
2 biến nhận giá trị 1.
Chứng minh rằng x y + y z + z x = x y + y z + z x

4.

Chứng minh: x y (z + z ) + y z (x + x ) + z x (y + y ) = x y + y z + z x.
5.
6.

Rút gọn các biểu thức : x  0, x  1, x  x, x  x
Chứng minh : x  y = (x+y)(xy) = (x y ) + ( x y)

7.

Có bao nhiêu hàm Bool f(x, y, z) khác nhau sao cho f( x , y , z ) = f(x, y, z)



Chứng minh : 8 bộ giá trị của x, y, z tạo thành 4 cặp giá trị (x, y, z) và ( x , y , z ).

Hàm f tại mỗi cặp này có giá trị giống nhau. Vì có 4 cặp, mỗi cặp có thể nhận 2
giá trị 0,1 nên có thể tạo được 16 hàm như vậy.
1
1
1

1
1
0

1
0
1

a
b
c

1

0

0

d

0
0
0
0


1
1
0
0

1
0
1
0

d
c
b
a


8.

Có bao nhiêu hàm Bool f(x, y, z) khác nhau sao cho f( x , y, z) = f(x, y , z) =
f(x, y, z ).

Chứng minh: Tương tự bài trên, có thể phân hoạch 8 bộ số của (x, y, z) thành 2
nhóm gồm (1, 1, 1), (0, 0, 1), (0, 1, 0), (1, 0, 0) và nhóm còn lại (trên mỗi nhóm
này f lấy cùng một giá trị). Vì có hai nhóm nên có thể tạo được 4 hàm f như vậy.
1
1
1
1


1
1
0
0

1
0
1
0

a
b
b
a


9.

0
0

1
1

1
0

b
a


0
0

0
0

1
0

a
b

Tìm khai triển tổng tích của hàm f(x, y, z, t) biết rằng hàm nhận giá trị 1 khi
và chỉ khi có ít nhất 3 trong 4 biến nhận giá trị 1.

10. Tìm khai triển tích tổng của hàm f(x, y, z, u, v) biết rằng hàm nhận giá trị 0
khi và chỉ khi các biến ở vị trí lẻ bằng 1.
11. Chứng minh các hệ sau là đầy đủ { | } và {  }.
12. Chứng minh hệ { . , + } là không đầy đủ
13. Các hệ sau đầy đủ / không đầy đủ ?
a. { ,  }

b. { . ,  }

c. { +,  }

14. Bằng phương pháp Quine – Mc Cluskey hãy rút gọn hàm Bool sau:
a. xyz + x y z + x yz + x y z + x y z
b. xyz + x y z + x y z + x yz + x y z + x y z
Các bài tập sau đây dựa trên định nghĩa tổng quát về đại số Bool như sau :

Một hệ gồm tập B bất kỳ có chứa 2 phần tử đặc biệt 0, 1, các phép toán 1 ngôi
, và 2 ngôi ,  được gọi là đại số Bool nếu các tính chất sau thoả với bất kỳ x,
y, z  B:
Luật đồng nhất
Luật nuốt
Luật kết hợp
Luật giao hoán
Luật phân phối

x0=x
x1=x
x x =1
x x =0
(x  y)  z = x  (y  z)
(x  y)  z = x  (y  z)
xy=yx
xy=yx
x  (y  z) = (x  y)  (x  z)
x  (y  z) = (x  y)  (x  z)


15. Chứng minh 0 = 1, 1 = 0,  x = x.
16. Chứng minh mọi đại số Bool đều thỏa luật De Morgan: (x  y) = x  y,
(x  y) = x  y.
17. Gọi X là tập vũ trụ. Chứng minh họ tất cả các tập hợp trong X với tập , tập
X và các phép toán phần bù, hợp, giao tạo thành một đại số Bool.