tailieunhanh - Bài giảng Tin học lý thuyết - Chương 1: Bổ túc toán
Chương 1 nhắc lại các dạng toán cơ bản như: Tập hợp (Set), ký hiệu tập hợp, một số dạng tập hợp đặc biệt, các phép toán trên tập hợp, quan hệ, các tính chất của quan hệ, quan hệ tương đương, bao đóng của quan hệ, đồ thị (Graph), đồ thị (Graph),. . | 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: 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ử 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 } 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 } 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} } 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 } 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 } 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} } R ( A B ) = aRb miền xác định (domain) miền giá trị (range) Quan hệ S 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)} 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 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 . | 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: 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ử 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 } 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 } 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} } 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 } Các phép toán trên tập hợp Phép trừ .
đang nạp các trang xem trước
