Thực hành Toán rời rạc - Chương 6: Cơ bản về đại số Bool, Finite State Machine

Thực hành Toán rời rạc - Chương 6: Cơ bản về đại số Bool, Finite state machine. Chương này cung cấp cho học viên những nội dung về: cơ bản đại số Bool với Python; khái niệm về Máy trạng thái hữu hạn FSM (Finite State Machines); xây dựng chương trình kiểm tra ngữ pháp đơn giản;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Thực hành Toán rời rạc - Chương 6: Cơ bản về đại số Bool, Finite State MachineBộ môn Khoa học Dữ liệuTHỰC HÀNH TOÁN RỜI RẠCTÀI LIỆU PHỤC VỤ SINH VIÊN NGÀNH KHOA HỌC DỮ LIỆUNhó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ỳnhThái Học và các Giảng viên khác TP.HCM – Năm 2020Thực hành Toán rời rạc Trang 1Bộ môn Khoa học Dữ liệuMỤC LỤCCHƯƠNG 6: CƠ BẢN VỀ ĐẠI SỐ BOOL, FINITE STATE MACHINE ................................................ 31. Cơ bản về đại số Bool với Python......................................................................................................... 32. 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................................................................... 63. Xây dựng chương trình kiểm tra ngữ pháp đơn giản ............................................................................ 8BÀI TẬP CHƯƠNG 6 ................................................................................................................................ 17Thực hành Toán rời rạc Trang 2Bộ môn Khoa học Dữ liệu CHƯƠNG 6: CƠ BẢN VỀ ĐẠI SỐ BOOL, FINITE STATE MACHINEMục tiêu: - Khái niệm về đại số Bool - Biểu diễn Finite State Machine trong PythonNội dung chính:1. Cơ bản về đại số Bool với PythonTó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 1trong . 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 0Nhậ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):Thực hành Toán rời rạc Trang 3Bộ môn Khoa học Dữ liệu 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 kqThự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 kqThự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))Thực hành Toán rời rạc Trang 4Bộ môn Khoa học Dữ liệu………………………………………..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ạchbê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ẽ ảnhhưở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 ứngnhiễ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 ...