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

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

60
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

• Tập hợp • 1, 2, 3 • Quan hệ • Phép chứng minh quy nạp • x x là một ngày trong tuần • ðồ thị và cây 1 3 Phần tử • Mon, Tue, Wed, Thu, Fri, Sat, Sun • Ký hiệu: ∅ hoặc • Tập các ñối tượng rời rạc • Không trùng lắp • Ký hiệu: ⊂ (Ngược lại: ⊄ ) • { 1, 2, 4 } ⊂ { 1, 2, 3, 4, 5 } • { 2, 4, 6 } ⊄ { 1, 2, 3, 4, 5 } • Tập hợp là tập các ñối tượng không có sự lặp lại 2 4 Printed with FinePrint - purchase at www.fineprint.com
: • Ký hiệu: (Ngược lại: ≠ ) • A \ B = { x | x ∈ A nhưng x ∉ B } • { 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 } ≠ { 2, 1 } : • A x B = { (a,b) | a ∈ A và b ∈ B } • Ký hiệu: A • A = { 1, 2, 3 } thì ∅, {1}, {2}, {3}, {1, 2}, A = {∅ {2, 3}, {3, 1}, {1, 2, 3} } 5 7 : cho A = {1, 2} và B = {2, 3} • A’ = { x | x ∉ A } • A ∪ B = { 1, 2, 3 } : • A∩B={2} • A ∪ B = { x | x ∈ A hoặc x ∈ B } • A\B={1} • A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) } • 2A = { ∅, {1}, {2}, {1, 2} } • A ∩ B = { x | x ∈A và x ∈ B } 6 8 Printed with FinePrint - purchase at www.fineprint.com
S nếu aRa là ñúng với ∀a∈ ∈S ( A × B ) = aRb nếu aRb thì bRa × nếu aRb và bRc thì á ( ) á ( ) i ñ h d i i i t m n c n o m a n m n g r r a n g e x aRc : • L không là quan hệ phản xạ hay ñối xứng 9 • E và P mang tính phản xạ, ñối xứng và bắc cầu 11 cho S = {0, 1, 2, 3} • Quan hệ ‘thứ tự nhỏ hơn’ = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } • Quan hệ ‘bằng’ • E và P là quan hệ tương ñương = { (0, 0), (1, 1), (2, 2), (3, 3) } • L không là quan hệ tương ñương • Quan hệ ‘chẵn lẻ’ = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)} 10 12 Printed with FinePrint - purchase at www.fineprint.com
R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3} ∪ ∪ • R+ = { (1, 2), (2, 2), (2, 3), (1, 3) } 1 2 • R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) } • Si ∩ Sj = ∅ • Nếu a, b cùng thuộc Si thì a b ñúng • Nếu a ∈ Si và b ∈ Sj thì a b sai 13 15 P có 2 lớp tương ñương {0, 2} và {1, 3} chứng minh giả sử + ⇒ ∀ ≥ • Nếu (a,b) ∈ R thì (a,b) ∈R + n n (n + 1)(2n + 1) • Nếu (a,b) ∈ R và (b,c) ∈ R thì (a,c) ∈ R + + chứng minh ∑ i 2 = i =0 6 • Không còn gì thêm trong R+ • R* = R+ ∪ { (a, a)  a ∈ S } 14 16 Printed with FinePrint - purchase at www.fineprint.com
là ñồ thị có hướng • V : tập các ñỉnh (nút) • 1 nút gốc • E : tập các cạnh nối giữa 2 nút • Nút trung gian (nút trong) ñồ thị G = (V, E) • Nút lá: không dẫn ra nút con • V = { 1, 2, 3, 4, 5 } • Thứ tự duyệt trên cây: → • E = { (n, m) | n+m = 4 hoặc n+m = 7} 17 19 cây minh họa cấu trúc cú pháp câu ‘An là sinh viên giỏi’ • V : tập các ñỉnh (nút) • E : tập các cung có hướng → C â ñ u ơ n ñồ thị G = (V, E) Chủ ngữ Vị ngữ • V = { 1, 2, 3, 4 } Danh từ ðộng từ Bổ ngữ • E={i→ji