Bài giảng Tin học lý thuyết - Chương 1 Bổ túc toán

Bổ túc toánNội dung:Tập hợpQuan hệPhép chứng minh quy nạpĐồ thị và câyChương 1:1Tậ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ạiTập các đối tượng rời rạcKhông trùng lắpPhần tử2Ký hiệu tập hợpLiệ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 }3Một số dạng tập hợp đặc biệtTậ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 }4Một số dạng tập hợp đặc biệtTậ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: 2AA = { 1, 2, 3 } thì 2A = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} } 5Các phép toán trên tập hợpPhầ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 } 6Các phép toán trên tập hợpPhé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 }7Các phép toán trên tập hợpVí 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} } 8R ( A  B ) = aRbmiền xác định (domain)  miền giá trị (range) Quan hệS9Quan 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)}10Cá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ì bRaBắc cầu (transitive): nếu aRb và bRc thì aRcVí dụ:L không là quan hệ phản xạ hay đối xứngE và P mang tính phản xạ, đối xứng và bắc cầu 11Quan hệ tương đươngQuan hệ tương đương = Quan hệ phản xạ, đối xứng và bắc cầuVí dụ:E và P là quan hệ tương đươngL không là quan hệ tương đương12Lớp tương đươngNế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 đúngNếu a  Si và b  Sj thì aRb saiVí dụ: P có 2 lớp tương đương {0, 2} và {1, 3}13Bao đóng của quan hệP-closure = quan hệ nhỏ nhất thỏa các tính chất trong PBao đó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 } 14Bao đó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) }15Nguyên lý quy nạpBướ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 minh16Đồ 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útVí dụ: đồ thị G = (V, E)V = { 1, 2, 3, 4, 5 }E = { (n, m) | n+m = 4 hoặc n+m = 7} Đồ thị (Graph)17Đồ 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)18Cây: là đồ thị có hướng1 nút gốcNút trung gian (nút trong)Nút lá: không dẫn ra nút conThứ tự duyệt trên cây: trái  phảiCây (Trees)19Ví 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 đơnChủ ngữVị ngữDanh từĐộng từBổ ngữDanh từTính từAnlàsinh viêngiỏi20