Giáo trình Toán rời rạc - Đại số Boole

Download miễn phí Giáo trình Toán rời rạc - Đại số Boole

Để 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 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.


http://cloud.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-02-giao_trinh_toan_roi_rac_dai_so_boole.2jgk2PBOfy.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53441/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

a (tiên đề 4b))
8. Ta chứng minh rằng a’+b’ là bù của a.b bằng cách chứng minh rằng:
(a.b).(a’+b’) = 0 (theo 5a)) và (a.b)+(a’+b’) = 1 (theo 5b)).
Thật vậy, (a.b).(a’+b’) = (a.b.a’)+(a.b.b’) = (a.a’.b)+(a.b.b’) = (0.b)+(a.0) = 0+0 = 0,
(a.b)+(a’+b’) = (a’+b’)+(a.b) = (a’+b’+a).(a’+b’+b) = (1+b’).(a’+1) = 1.1 = 1.
Vì a.b chỉ có một phần tử bù duy nhất nên (a.b)’ = a’+b’.
9. Có ngay từ tiên đề 5.
10. Có từ các hệ thức 1.0 = 0 và 1+0 = 1.
11. a.(a+b) = (a+0).(a+b) = a+(0.b) = a+0 = a.
8.1.4. Chú ý: Hệ tiên đề của đại số Boole nêu ra ở đây không phải là một hệ tối thiểu.
Chẳng hạn, các tiên đề về tính kết hợp có thể suy ra từ các tiên đề khác. Thật vậy, với
A=(a.b).c và B=a.(b.c), ta có: a+A = a+((a.b).c) = (a+(a.b)).(a+c) = a.(a+c) = a, a+B =
a+(a.(b.c)) = (a+a).(a+(b.c)) = a.(a+(b.c)) = a, a’+A = a’+((a.b).c) = (a’+(a.b)).(a’+c) =
((a’+a).(a’+b)).(a’+c) = (1.(a’+b)).(a’+c) = (a’+b).(a’+c) = a’+(b.c), a’+B = a’+(a.(b.c))
= (a’+a).(a’+(b.c)) = 1.(a’+(b.c)) = a’+(b.c).
Do đó a+A = a+B và a’+A = a’+B. Từ đó suy ra rằng:
117
A = A+0 = A+(a.a’) = (A+a).(A+a’) = (a+A).(a’+A) = (a+B).(a’+B)=(a.a’)+B=0+B= B
hay ta có 2a) và đối ngẫu ta có 2b). Ngoài ra, tính duy nhất của phần tử bù cũng được
suy ra từ các tiên đề khác.
Tương tự trong đại số lôgic, trong đại số Boole ta cũng xét các công thức, được
thành lập từ các biến a, b, c, … nhờ các phép toán . , +, ’. Trong công thức, ta quy ước
thực hiện các phép toán theo thứ tự: ’, ., +; a.b được viết là ab, gọi là tích của a và b còn
a+b gọi là tổng của a và b. Ta có thể biến đổi công thức, rút gọn công thức tương tự
trong đại số lôgic. Ta cũng xét các tích sơ cấp và tổng sơ cấp tương tự “hội sơ cấp” và
“tuyển sơ cấp”. Mọi công thức đều có thể đưa về dạng tích chuẩn tắc hoàn toàn hay về
dạng tổng chuẩn tắc hoàn toàn tương tự dạng “hội và tuyển chuẩn tắc hoàn toàn”. Mỗi
công thức trong đại số Boole cũng được gọi là biểu diễn một hàm Boole.
8.2. HÀM BOOLE.
8.2.1. Định nghĩa: Ký hiệu B = {0, 1} và Bn = {(x1, x2, …, xn) | xiB, 1≤ i ≤ n}, ở đây
B và Bn là các đại số Boole (xem 2) và 3) của Thí dụ 1). Biến x được gọi là một biến
Boole nếu nó nhận các giá trị chỉ từ B. Một hàm từ Bn vào B được gọi là một hàm Boole
(hay hàm đại số lôgic) bậc n.
Các hàm Boole cũng có thể được biểu diễn bằng cách dùng các biểu thức được
tạo bởi các biến và các phép toán Boole (xem Bảng 1 trong Thí dụ 1). Các biểu thức
Boole với các biến x1, x2, …, xn được định nghĩa bằng đệ quy như sau:
- 0, 1, x1, x2, …, xn là các biểu thức Boole.
- Nếu P và Q là các biểu thức Boole thì P , PQ và P+Q cũng là các biểu thức Boole.
Mỗi một biểu thức Boole biểu diễn một hàm Boole. Các giá trị của hàm này nhận
được bằng cách thay 0 và 1 cho các biến trong biểu thức đó.
Hai hàm n biến F và G được gọi là bằng nhau nếu F(a1, a2, …, an)=G(a1, a2, …,an)
với mọi a1, a2, …, anB. Hai biểu thức Boole khác nhau biểu diễn cùng một hàm Boole
được gọi là tương đương. Phần bù của hàm Boole F là hàm F với F (x1, x2, …, xn) =
),...,,( 21 nxxxF . Giả sử F và G là các hàm Boole bậc n. Tổng Boole F+G và tích Boole
FG được định nghĩa bởi:
(F+G)(x1, x2, …, xn) = F(x1, x2, …, xn)+G(x1, x2, …, xn),
(FG)(x1, x2, …, xn) = F(x1, x2, …, xn)G(x1, x2, …, xn).
Thí dụ 2:
Bậc Số các hàm Boole
1 4
2 16
3 256
4 65.536
5 4.294.967.296
6 18.446.744.073.709.551.616
Theo quy tắc nhân của phép đếm ta suy
ra rằng có 2n bộ n phần tử khác nhau gồm
các số 0 và 1. Vì hàm Boole là việc gán 0
hay 1 cho mỗi bộ trong số 2n bộ n phần
tử đó, nên lại theo quy tắc nhân sẽ có
n22 các hàm Boole khác nhau.
118
Bảng sau cho giá trị của 16 hàm Boole bậc 2 phân biệt:
x y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16
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 F1 là hàm hằng 0,
- Hàm F2 là hàm hằng 1,
- Hàm F3 là hàm hội, F3(x,y) được viết là xy (hay xy),
- Hàm F4 là hàm tuyển, F4(x,y) được viết là x+y (hay x y),
- Hàm F5 là hàm tuyển loại, F5(x,y) được viết là xy,
- Hàm F6 là hàm kéo theo, F6(x,y) được viết là xy,
- Hàm F7 là hàm tương đương, F7(x,y) được viết là x y,
- Hàm F8 là hàm Vebb, F8(x,y) được viết là xy,
- Hàm F9 là hàm Sheffer, F9(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:
TF = {(x1, x2, …, xn)B
n | F(x1, x2, …, xn)=1}
Và gọi nó là tập đặc trưng của hàm F. Khi đó ta có:
FF TT  , TF+G = TFTG, TFG = TFTG.
Cho n biến Boole x1, x2, …, xn. Một biểu thức dạng:
k
kiii
xxx

2
2
1
1
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
119
trong đó k ,,, 21  B, 1 niii k  21 được gọi là một hội sơ cấp của n
biến x1, x2, …, xn. 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
niiin xxFxxxxxF
),,(
11121
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 (x1, x2, …, xn)TF. Khi đó số
hạng ứng với bộ giá trị  1= x1, …,  i= xi trong tổng ở vế phải của (1) bằng 1, do đó
(x1, x2, …, xn)TG. Đảo lại, nếu (x1, x2, …, xn)TG 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 đó x1= 1, …, xi= i và f( 1,…, i, xi+1,…, xn)=1 hay (x1, x2, …, xn)TF. Vậy
TF=TG 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 xi 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 xi:
),,,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
),,(
11
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 ...