Toán Rời Rạc Đại Số Bool - 123doc

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

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 đề

Với hàm n biến sẽ có tất cả 2 n

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

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

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), Ef 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)

f2 0 0 0 1 xy

f3 0 0 1 0

f5 0 1 0 0

f7 0 1 1 0 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

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

Luật lũy đẳng xx = x; x + x = x

Luật đồng nhất x + 0 = x1 = x

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

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ụ

 x + xy = x cũng đúng và là hấp thụ

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 y z f Các tiểu hạng tương ứng

1 1 1 1* xyz

1 1 0 1* xyz

1 0 1 1* xyz

0 1 1 1* xyz

Dạng tổng tích 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 Y f tiểu hạng Đại hạng

1 0 1 xy

0 1 1 xy

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 :





















0 if

x

1 if

x x

i i

i i

i

i

 Tf = {(x1, x2, …, xn) : f(x1, x2, …, xn) = 1}

từ kí hiệu này có thể thấy: i

i

x  = 1 khi và chỉ khi xi  i (Giả sử i = 1, theo định nghĩa i

i

x  = 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 i

i

x  = xi, có giá trị 1 khi và chỉ khi xi = 0 tức xi = i)

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) = 









f n 2 1

n 1

T ) x x , x (

n

2 2

x

 Chuẩn tắc hội : f(x1, x2, …, xn) = 







f n

n T

) x , x , x (

n x x x 2 1

2 1 2 1

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  n

n x x

x1 2  2

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 n

n x x

x1 2  2

1 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

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ư :

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

xy + xz + yz 5 (chuẩn tắc 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 + wxyz = 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 :

wxyz + wx yz + wxyz + wxyz + wxyz + w xyz + w x yz

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

1 wxyz 1110

2 wxyz 1011

3 wxyz 0111

4 wxyz 1010

5 wxyz 0101

6 w xyz 0011

7 w x yz 0001

2 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