Bài giảng Tin học: 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

58
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 - 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. Hi vọng đây sẽ là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tinvà những ai quan tâm dùng tham khảo phục vụ học tập.

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: 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