BÀI GI NGẢ
TIN H C C SỌ Ơ Ở
Gi ng viên: ĐÀO KI N QU Cả Ế Ố
Mobile 098.91.93.980
Email: dkquoc@vnu.edu.vn
BÀI 5. CÁC HÀM Đ I S LOGIC Ạ Ố
VÀ NG D NG Ứ Ụ
Đ I H C QU C GIA HÀ N IẠ Ọ Ố Ộ
TR NG Đ I H C CÔNG NGHƯỜ Ạ Ọ Ệ
N I DUNGỘ
Các hàm đ i s logicạ ố
Bi u di n các hàm đ i s logicể ễ ạ ố
Áp dung vào thi t k m chế ế ạ
Ví d v thi t k m t b c ngụ ề ế ế ộ ộ ộ
CÁC HÀM Đ I S LOGIC Ạ Ố
Đ i l ng ch nh n giá tr trên t p D = {0,1} ạ ượ ỉ ậ ị ậ
đ c g i là bi n boole, bi n nh phân hay bi n ượ ọ ế ế ị ế
logic
Hàm c a các bi n boole và có giá tr trên t p ủ ế ị ậ
D {0,1} đ c g i là hàm đ i s logic ho c hàm ượ ọ ạ ố ặ
boole. S bi n c a hàm cũng g i là s ngôi.ố ế ủ ọ ố
Do tính h u h n c a mi n xác đ nh nên luôn ữ ạ ủ ề ị
luôn có th cho hàm boole d i d ng b ng ể ướ ạ ả
tr c ti p giá tr c a nó đ i v i các đ i (các giá ự ế ị ủ ố ớ ố
tr c a bi n) t ng ng. ị ủ ế ươ ứ
V i s ngôi n đã xác đ nh, có th ch ng minh ớ ố ị ể ứ
đ c có đúng ượ 22n hàm n ngôi. M i hàm đ i s ỗ ạ ố
logic n ngôi cũng đ c xem nh m t phép ượ ư ộ
toán n ngôi.
x1x2f(x1,x2)
0 0 1
0 1 0
1 0 0
1 1 1
M T S HÀM Đ I S LOGIC QUAN Ộ Ố Ạ Ố
TR NGỌ
V i s ngôi n=0 có đúng hai hàm (đây là các ớ ố
hàm h ng) : ằ
–f0 ≡ 0
–f1 ≡ 1
V i n=1 có đúng 4 hàm 1 ngôi. Ngoài các ớ
hàm h ng f0(x) ≡0, f1(x) ≡1 còn hàm f2(x) = x ằ
và hàm ph đ nh f3(x) = ┐x. Phép toán ph ủ ị ủ
đ nh ┐ đ c xác đ nh nh sau: ┐0=1, ┐1=0ị ượ ị ư
M T S HÀM Đ I S LOGIC QUAN Ộ Ố Ạ Ố
TR NGỌ
V i n= 2 có đúng 16 hàm hai ngôi. Sau đây là m t s ớ ộ ố
hàm quan tr ng:ọ
Hàm tuy n, đ c xem nh m t phép toán 2 ngôi, ký ể ượ ư ộ
hi u qua V, f(x,y)=xVy, còn g i là phép c ng logicệ ọ ộ
0V0 = 0, 0V1=1V0=1V1 = 1
Hàm tuy n là s th hi n c a “ho c” trong logic m nh ể ự ể ệ ủ ặ ệ
đề
Hàm h i đ c xem nh m t phép toán 2 ngôi, ký hi u ộ ượ ư ộ ệ
qua ∧ , f(x,y)=x ∧ y, còn g i là phép nhân logicọ
0 ∧1=1 ∧0 = 0 ∧0 = 0, 1 ∧1=1
Hàm tuy n là s th hi n c a “và” trong logic m nh để ự ể ệ ủ ệ ề