Bài giảng Automata và ngôn ngữ hình thức - Chương 1: Bổ túc toán

1 
Bổ túc toán 
Nội dung: 
• Tập hợp 
• Quan hệ 
• Phép chứng minh quy nạp 
• Đồ thị và cây 
Chương 1: 
2 
Tập hợp (Set) 
Ví dụ: 
• D = {Mon, Tue, Wed, Thu, Fri, Sat, Sun} 
Định nghĩa: 
• Tập hợp là tập các đối tượng không 
có sự lặp lại 
• Tập các đối tượng rời rạc 
• Không trùng lắp 
Phần tử 
3 
Ký hiệu tập hợp 
Liệt kê phần tử: 
• D = {1, 2, 3} 
Đặc tả tính chất đặc trưng: 
• D = { x | x là một ngày trong tuần } 
4 
Một số dạng tập hợp đặc biệt 
Tập rỗng: 
• Ký hiệu:  hoặc { } 
Tập hợp con: 
• Ký hiệu: A  B (Ngược lại: A  B ) 
• { 1, 2, 4 }  { 1, 2, 3, 4, 5 } 
• { 2, 4, 6 }  { 1, 2, 3, 4, 5 } 
5 
Một số dạng tập hợp đặc biệt 
Tập hợp bằng nhau: 
• Ký hiệu: A = B (Ngược lại: A  B ) 
• { 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 }  { 2, 1 } 
Tập lũy thừa: 
• Ký hiệu: 2A 
• A = { 1, 2, 3 } thì 2A = {, {1}, {2}, {3}, {1, 2}, 
{2, 3}, {3, 1}, {1, 2, 3} } 
6 
Các phép toán trên tập hợp 
Phần bù (complement): 
• A’ = { x | x  A } 
Phép hợp (Union): 
• A  B = { x | x  A hoặc x  B } 
Phép giao (intersection): 
• A  B = { x | x A và x  B } 
7 
Các phép toán trên tập hợp 
Phép trừ (difference): 
• A \ B = { x | x  A nhưng x  B } 
Tích Đềcác: 
• A x B = { (a,b) | a  A và b  B } 
8 
Các phép toán trên tập hợp 
Ví dụ: cho A = {1, 2} và B = {2, 3} 
• A  B = { 1, 2, 3 } 
• A  B = { 2 } 
• A \ B = { 1 } 
• A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) } 
• 2A = { , {1}, {2}, {1, 2} } 
9 
R ( A  B ) = aRb 
miền xác định (domain)  miền giá trị (range) 
Quan hệ 
S 
10 
Quan hệ 
Ví dụ: cho S = {0, 1, 2, 3} 
• Quan hệ ‘thứ tự nhỏ hơn’ 
L = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } 
• Quan hệ ‘bằng’ 
E = { (0, 0), (1, 1), (2, 2), (3, 3) } 
• Quan hệ ‘chẵn lẻ’ 
P = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)} 
11 
Các tính chất của quan hệ 
Phản xạ (reflexive): nếu aRa là đúng với 
aS 
Đối xứng (symmetric): nếu aRb thì bRa 
Bắc cầu (transitive): nếu aRb và bRc thì 
aRc 
Ví dụ: 
• L không là quan hệ phản xạ hay đối xứng 
• E và P mang tính phản xạ, đối xứng và bắc cầu 
12 
Quan hệ tương đương 
Quan hệ tương đương = Quan hệ phản xạ, 
đối xứng và bắc cầu 
Ví dụ: 
• E và P là quan hệ tương đương 
• L không là quan hệ tương đương 
13 
Lớp tương đương 
Nếu R là quan hệ tương đương trên S thì R 
phân hoạch S thành các lớp tương đương 
không rỗng và rời nhau: S = S1  S2   
Tính chất: 
• Si  Sj =  
• Nếu a, b cùng thuộc Si thì aRb đúng 
• Nếu a  Si và b  Sj thì aRb sai 
Ví dụ: P có 2 lớp tương đương {0, 2} và {1, 3} 
14 
Bao đóng của quan hệ 
P-closure = quan hệ nhỏ nhất thỏa các tính 
chất trong P 
Bao đóng bắc cầu R+: 
• Nếu (a,b)  R thì (a,b) R+ 
• Nếu (a,b)  R và (b,c)  R thì (a,c)  R+ 
• Không còn gì thêm trong R+ 
Bao đóng phản xạ và bắc cầu R*: 
• R* = R+  { (a, a)  a  S } 
15 
Bao đóng của quan hệ 
Ví dụ: R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3} 
• R+ = { (1, 2), (2, 2), (2, 3), (1, 3) } 
• R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) } 
16 
Nguyên lý quy nạp 
Bước 1 (cơ sở quy nạp): chứng minh P(0) 
Bước 2 (giả thiết quy nạp): giả sử P(n-1) 
Bước 3 (quy nạp): P(n - 1)  P(n),  n  1. 
Ví dụ: chứng minh 6
)1n2)(1n(n
i
n
0i
2 

17 
Đồ thị G = (V, E) 
• V : tập các đỉnh (nút) 
• E : tập các cạnh nối giữa 2 nút 
Ví dụ: đồ thị G = (V, E) 
• V = { 1, 2, 3, 4, 5 } 
• E = { (n, m) | n+m = 4 hoặc n+m = 7} 
Đồ thị (Graph) 
 
 
 
 
 
18 
Đồ thị G = (V, E) 
• V : tập các đỉnh (nút) 
• E : tập các cung có hướng v  w 
Ví dụ: đồ thị G = (V, E) 
• V = { 1, 2, 3, 4 } 
• E = { i  j  i < j } 
Đồ thị có hướng (Directed graph) 
19 
Cây: là đồ thị có hướng 
• 1 nút gốc 
• Nút trung gian (nút trong) 
• Nút lá: không dẫn ra nút con 
• Thứ tự duyệt trên cây: trái  phải 
Cây (Trees) 
20 
Ví dụ: cây minh họa cấu trúc cú pháp câu ‘An là 
sinh viên giỏi’ 
Cây (Trees) 
Câu đơn 
Chủ ngữ Vị ngữ 
Danh từ Động từ Bổ ngữ 
Danh từ Tính từ 
An là sinh viên giỏi