Bộ môn Khoa học Dữ liệu
Thực hành Toán rời rạc Trang 1
THỰC HÀNH TOÁN RỜI RẠC
TÀI LIỆU PHỤC VỤ SINH VIÊN NGÀNH KHOA HỌC DỮ LIỆU
Nhóm Giảng viên biên soạn: TS. Hoàng Lê Minh – Hoàng Thị Kiều Anh – Khưu Minh Cảnh –
Phạm Trọng Nghĩa –Nguyễn Công Nhựt – Trần Ngọc Việt – Lê Ngọc Thành – Đỗ Đình Thủ –
Nguyễn Hữu Trí Nhật – Lê Công Hiếu – Nguyễn Thị Thanh Bình – Nguyễn Thái Hải – Huỳnh
Thái Học và các Giảng viên khác
TP.HCM – Năm 2020
Bộ môn Khoa học Dữ liệu
Thực hành Toán rời rạc Trang 2
MỤC LỤC
CHƯƠNG 6: CƠ BẢN VỀ ĐẠI SỐ BOOL, FINITE STATE MACHINE ................................................ 3
1. Cơ bản về đại số Bool với Python......................................................................................................... 3
2. Khái niệm về Máy trạng thái hữu hạn FSM (Finite State Machines) ................................................... 5
2.1. Mô hình toán học: ......................................................................................................................... 6
2.2. Ví dụ: Mạch điện đèn điều khiển tín hiệu giao thông ................................................................... 6
3. Xây dựng chương trình kiểm tra ngữ pháp đơn giản ............................................................................ 8
BÀI TẬP CHƯƠNG 6 ................................................................................................................................ 17
Bộ môn Khoa học Dữ liệu
Thực hành Toán rời rạc Trang 3
CHƯƠNG 6: CƠ BẢN VỀ ĐẠI SỐ BOOL,
FINITE STATE MACHINE
Mục tiêu:
- Khái niệm về đại số Bool
- Biểu diễn Finite State Machine trong Python
Nội dung chính:
1. Cơ bản về đại số Bool với Python
Tóm tắt lý thuyết: Cho = {0,1}, biến được gọi là biến bool nếu nó nhận giá trị 0 hoặc 1
trong . Khi đó, một hàm số (, , … , ) được gọi là hàm bool nếu nó xác định trên tập
= {(, , … , )|∈ , = 1,
}
Các đặc tính: cho hai hàm số bool, phép toán hội (∧), phép toán tuyển (∨) cho hai hàm số và
phép toán phủ định cho một hàm số đều sẽ cho kết quả là một hàm số bool. Các kí hiệu:
- Hội của hai hàm bool: ( ∧ ).
- Tuyển của hai hàm bool: ( ∨ ).
- Phủ định của hàm bool: .
Ví dụ 1: Cho hàm bool theo bảng sau và hãy xác định biểu thức bool và thể hiện bằng ngôn ngữ
Python:
x y Hàm f(x,y)
1 1 0
1 0 1
0 1 0
0 0 0
Nhận xét: f(x,y)=1 khi và chỉ khi x=1, y=0 và f(x,y)=0 trong các trường hợp còn lại của giá trị x,
y. Từ đó, chúng ta có thể kết luận biểu thức bool của hàm f(x,y) là ∧ .
Với Python, chúng ta có thể viết các hàm thể hiện hàm bool. Một cách đơn giản là liệt kê tất cả
các trường hợp tương ứng với giá trị của hàm bool cho trong bảng:
Sinh viên thực hiện thể hiện của hàm f như bên dưới:
>>> def bool_xy(x, y):
kq = 0
if (x==1) and (y==1):
Bộ môn Khoa học Dữ liệu
Thực hành Toán rời rạc Trang 4
kq = 0
if (x==1) and (y==0):
kq = 1
if (x==0) and (y==1):
kq = 0
if (x==0) and (y==0):
kq = 0
return kq
Thực hiện chạy chương trình:
>>> for x in [1,0]:
for y in [1,0]:
print (bool_xy(x,y))
………………………………………..
Cải tiến hàm theo phân tích:
>>> def bool_xy1(x,y):
kq = 0
if (x == 1) and (y==0):
kq = 1
return kq
Thực hiện chạy chương trình lần nữa:
>>> for x in [1,0]:
for y in [1,0]:
print (bool_xy(x,y))
Bộ môn Khoa học Dữ liệu
Thực hành Toán rời rạc Trang 5
………………………………………..
Ví dụ 2: Trong hình bên dưới, hai mạch được thiết kế với cùng một chức năng. Trong đó, mạch
bên trái nhiều linh kiện hơn mạch bên phải nhưng cùng một tính năng.
Sinh viên hãy viết chương trình bằng Python để mô tả hai mạch bên trên.
Lưu ý: Trong thực tế, mặc dù mong muốn ban đầu của đại số Bool là tối thiểu một thiết kế
“mạch” nhưng việc thiết kế mạch trong thực tế là một vấn đề lớn. Vì việc thiết kế mạch sẽ ảnh
hưởng đến độ bền của thiết bị, linh kiện, mức độ “chịu đựng” về điện áp hoặc các hiệu ứng
nhiễu (trong các thiết bị âm thanh, thu phát sóng,…trong các môi trường khác nhau), cũng như
năng lượng tiêu thụ và các yếu tố khác... Do đó, mặc dù việc sử dụng các giải pháp đại số Bool
để làm đơn giản hóa mạch là một vấn đề khác. Đôi khi, với các thiết kế phức tạp thì mạch trở
nên ổn định, bền và chống nhiễu khi đưa vào sử dụng.
2. Khái niệm về Máy trạng thái hữu hạn FSM (Finite State Machines)
Một “Finite State Machine” viết tắt là FSM còn được gọi là “máy trạng thái” hoặc “Finite State
Automaton” là máy ảo gồm tập các trạng thái (bao gồm trạng thái khởi đầu và một hoặc nhiều
trạng thái cuối), một tập các sự kiện nhập, 1 tập sự kiện xuất và 1 hàm chuyển đổi trạng thái.
Hàm chuyển đổi trạng thái lấy state và sự kiện nhập là đầu vào và trả về tập các sự kiện xuất mới
và trạng thái tiếp theo (trạng thái mới). Một số trạng thái được gọi là trạng thái “chấm dứt”
(terminal states) khi không thể chuyển sang trạng thái khác.
Hoạt động của một FSM bắt đầu bằng một trạng thái gọi là trạng thái khởi đầu và xử lý xuyên
suốt các dịch chuyển phụ thuộc vào các trạng thái khác nhau và thông thường kết thúc khi ở
trạng thái cuối. Một trạng thái đánh dấu một dòng thành công của hoạt động được gọi là một
trạng thái được chấp nhận (accept state). Kỹ thuật state machine hiện tại được sử dụng trong các
ứng dụng: trò chơi (games), giao diện người sử dụng, giao thức mạng và các chương trình phân
tích.