Ktl-icon-tai-lieu

toán logic

Được đăng lên bởi Gà Con
Số trang: 7 trang   |   Lượt xem: 1677 lần   |   Lượt tải: 4 lần
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic

CHƯƠNG 5. MỘT SỐ KIẾN THỨC VỀ ĐẠI SỐ LOGIC
Người đặt nền móng cho ngành toán học này là D. Boole (1815-1864). Do v ậy đ ại
số logic còn có tên gọi là đại số Boole. Đại s ố logic có nhi ều ứng d ụng, ở đây,
chúng ta quan tâm đến các khía cạnh liên quan đ ến thi ết k ế các m ạch logic bên
trong MTĐT. Như đã thấy, kết quả thực hiện các phép toán s ố h ọc v ới các s ố nh ị
phân là một số nhị phân mới. Do vậy, ta có thể hình dung thi ết b ị th ực hi ện các
phép toán trong MTĐT như là thành phần chức năng bi ến đ ổi nh ị phân. Thi ết b ị
đặc biệt đó cho phép nạp số liệu dạng nhị phân ở đầu vào và l ấy kết qu ả có
dạng nhị phân ở đầu ra. Vậy có thể xem bộ biến đ ổi ch ức năng đó nh ư là m ột
thiết bị có nhiều đầu vào và nhiều đầu ra. Tại một thời điểm xác đ ịnh, ở m ỗi đ ầu
vào chỉ nạp được một bit và từ mỗi đầu ra chỉ cho ra đ ược m ột bit d ữ li ệu. Đ ể
hiểu rõ hơn về nguyên lý xây dựng các bộ biến đổi nhị phân ta s ẽ tìm hi ểu m ột
số vấn đề có liên quan dưới đây.

5.1. CÁC HÀM ĐẠI SỐ LOGIC
Xét tập D = {0, 1}, các giá trị của tập D còn g ọi là giá tr ị logic hay nh ị phân. Đ ại
lượng x chỉ có thể nhận giá trị trong tập D gọi là bi ến Boole (hay bi ến logic, bi ến
nhị phân). Hàm của n biến nhị phân F(x 1, x2, ..., xn) chỉ nhận hai giá trị 0 và 1 gọi
là hàm Boole (hoặc hàm logic). Mỗi hàm boole n bi ến có th ể cho b ằng m ột b ảng
có n+1 cột, n cột đầu là giá trị của các bi ến x 1, x2, ..., xn tương ứng. Cột cuối cùng
là giá trị của hàm ứng với các giá trị của biến. Ví d ụ n = 2, các giá tr ị x1, x2 và
các hàm tương ứng f(x1, x2) được cho như trong Bảng 5.1
x1

x2

f(x1,x2)

0

0

1

0

1

0

1

0

0

1

1

1

Bảng 5.1. Hàm logic 2 biến
Dễ dàng thấy, với mỗi n có đúng 2 n cách tổ hợp khác nhau giá trị các biến x 1,
x2, ..., xn. Một hàm Boole là một cách cho tương ứng mỗi một trong số 2 n với một
trong hai giá trị 0 và 1. Vì thế nó sẽ tương ứng v ới m ột cách phân ho ạch t ập 2 n bộ
giá trị này thành 2 nhóm, một nhóm hàm có giá tr ị 1, m ột nhóm hàm có giá tr ị 0.
Như vậy mọi hàm boole n biến hoàn toàn được xác định b ởi m ột t ập con trong 2 n
bộ giá trị để giá trị của hàm là 1. Ta đã bi ết đ ối v ới m ột t ập có k ph ần t ử thì t ập
tất cả các tập con của nó sẽ có 2k phần tử. Do vậy có đúng 2n hàm Boole n biến.
Với n = 1, có 4 hàm nhị phân. Các hàm đó được cho trong B ảng 5.2

37

Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic

x

F1

F2

F3

F4

0

0

1

0

1

1

0

1

1

0

Bảng 5.2. Các hàm logic 1 biến
Hàm F1 và F2 l...
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic
CH NG 5. M T S KI N TH C V Đ I S LOGICƯƠ
Ng i đ t n n móng cho ngành toán h c này là D. Boole (1815-1864). Do v y đ iườ
s logic còn tên g i đ i s Boole. Đ i s logic nhi u ng d ng, đây,
chúng ta quan tâm đ n các khía c nh liên quan đ n thi t k các m ch logic bênế ế ế ế
trong MTĐT. Nh đã th y, k t qu th c hi n các phép toán s h c v i các s như ế
phân là m t s nh phân m i. Do v y, ta th hình dung thi t b th c hi n các ế
phép toán trong MTĐT nh thành ph n ch c năng bi n đ i nh phân. Thi t bư ế ế
đ c bi t đó cho phép n p s li u d ng nh phân đ u vào l y k t qu ế
d ng nh phân đ u ra. V y th xem b bi n đ i ch c năng đó nh m t ế ư
thi t b có nhi u đ u vàonhi u đ u ra. T i m t th i đi m xác đ nh, m i đ uế
vào ch n p đ c m t bit t m i đ u ra ch cho ra đ c m t bit d li u. Đ ượ ượ
hi u h n v nguyên xây d ng các b bi n đ i nh phân ta s tìm hi u m t ơ ế
s v n đ có liên quan d i đây. ướ
5.1. CÁC M Đ I S LOGIC
Xét t p D = {0, 1}, các giá tr c a t p D còn g i là giá tr logic hay nh phân. Đ i
l ng x ch th nh n giá tr trong t p D g i bi n Boole (hay bi n logic, bi nượ ế ế ế
nh phân). Hàm c a n bi n nh phân F(x ế
1
, x
2
, ..., x
n
) ch nh n hai gtr 0 và 1 g i
hàm Boole (ho c hàm logic). M i hàm boole n bi n th cho b ng m t b ng ế
có n+1 c t, n c t đ u là giá tr c a các bi n x ế
1
, x
2
, ..., x
n
t ng ng. C t cu i cùngươ
giá tr c a hàm ng v i các giá tr c a bi n. d n = 2, các giá tr x1, x2 ế
các hàm t ng ng f(x1, x2) đ c cho nh trong B ng 5.1ươ ượ ư
x
1
x
2
f(x
1
,x
2
)
0 0 1
0 1 0
1 0 0
1 1 1
B ng 5.1. Hàm logic 2 bi n ế
D dàng th y, v i m i n đúng 2
n
cách t h p khác nhau giá tr các bi n x ế
1
,
x
2
, ..., x
n
. M t hàm Boole là m t cách cho t ng ng m i m t trong s 2 ươ
n
v i m t
trong hai giá tr 0 và 1. Vì th nó s t ng ng v i m t ch phân ho ch t p 2 ế ươ
n
b
giá tr này thành 2 nhóm, m t nhóm hàm giá tr 1, m t nhóm hàm giá tr 0.
Nh v y m i hàm boole n bi n hoàn toàn đ c xác đ nh b i m t t p con trong 2ư ế ượ
n
b giá tr đ giá tr c a hàm 1. Ta đã bi t đ i v i m t t p k ph n t thì t p ế
t t c các t p con c a nó s có 2
k
ph n t . Do v y có đúng 2
n
hàm Boole n bi n.ế
V i n = 1, có 4 hàm nh phân. Các hàm đó đ c cho trong B ng 5.2 ượ
37
toán logic - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
toán logic - Người đăng: Gà Con
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
7 Vietnamese
toán logic 9 10 255