tailieunhanh - Bài giảng Tin học lí thuyết: Chương 1 - Võ Huỳnh Trâm

Bài giảng "Tin học lí thuyết - Chương 1: Bổ túc toán" cung cấp cho người học các kiến thức: Tập hợp, quan hệ, phép chứng minh quy nạp, đồ thị và cây. nội dung chi tiết. | Chương 1 X Bo túc toán Ký hiệu tập hợp Nôi dung Tập hợp Quan hệ Phép chứng minh quy nạp Đồ thị và cây 1 Liêt kê phàn tử D 1 2 3 Đăc tà tính chát đăc trưng D x 1 x là một ngày trong tuần 3 Tập hợp Set Ví du D Mon Tue Wed Thu Fri Sat Sun Tập các đối tượng rời rạc Không trùng lắp Đinh nghía Tập hợp là tập các đối tượng không có sự lặp lại 2 Một số dạng tập hợp đặc biệt Tâp rỗng Ký hiệu 0 hoặc Tâp hơp con Ký hiệu AcB Ngược lại A B 1 2 4 c 1 2 3 4 5 2 4 6 c 1 2 3 4 5 4 Printed with FinePrint - purchase at 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 0 1 2 3 1 2 2 3 3 1 1 2 3 5 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 u B x x e A hoặc x e B Phép giao intersection A n B x x eA và x e B Các phép toán trên tập hợp Phép trử difference A B x x e A nhưng x Ể B Tích Đềcác A x B a b a e A và b e B 7 Các phép toán trên tập hợp Ví du cho A 1 2 và B 2 3 A u B 1 2 3 A n B 2 A B 1 A x B 1 2 1 3 2 2 2 3 2A 0 1 2 1 2 Printed with FinePrint - purchase at Quan hệ Các tính chất của quan hệ jT2 Z R A X B aRb miền xác định domain X miền giá trị range 9 Phàn xa reflexive nếu aRa là đúng với VaeS Đối xứng symmetric nếu aRb thì bRa Bắc cầu transitive nếu aRb và bRc thì aRc Ví du 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 11 Quan hệ Quan hệ tương đương Ví du 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 10 Quan hệ tương đương Quan hệ phản xạ đối xứng và bắc cầu Ví du E và P là quan hệ tương đương L không là quan hệ tương đương 12 Printed with FinePrint - purchase at .