Bài giảng Toán rời rạc - Chương 1: Cơ sở logic

Nắm vững kiến thức toán học với "Bài giảng Toán rời rạc - Chương 1: Cơ sở logic" gồm các kiến thức mệnh đề, nguyên lý qui nạp toán học, công thức truy hồi.

Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Chương 1: Cơ sở logic TOÁN RỜI RẠC1 CƠ SỞ LOGIC 2 tiết2 QUAN HỆ 2 tiết3 MỘT SỐ BÀI TOÁN CƠ BẢN 8 tiết4 LÝ THUYẾT ĐỒ THỊ 12 tiết5 ĐẠI SỐ BOOLE 6 tiếtChương 1Chương 1: CƠ SỞ LOGIC 1.1 Mệnh đề 1.2 Nguyên lý qui nạp toán học 1.3 Công thức truy hồi 1.1 Nguyên lí qui nạp toán họcGiả sử cần chứng minh mệnh đề có dạng: “n  no, P(n) ” đúngTa thực hiện theo các bước sau: + B1: Chứng minh P(no) đúng + B2: Giả sử P(k), no k đúng. Ta chứng minh mệnh đề P(k+1) cũng đúng. Khi đó mệnh đề P(n) đúng với n  no Ví dụ Dùng phương pháp qui nạp chứng minh: 1 2 n 1a)   ...   1 (1), n  1 2! 3! (n  1)! (n  1)!b) n3 + 11n chia hết cho 6, n  1 HDa) Với n = 1: 1 1 1 VT  , VP  1    (1) đúng với n = 1 2 (1  1)! 2 Giả sử: 1 2 k 1   ...   1 , k  1 2! 3! (k  1)! (k  1)! Ta chứng minh (1) đúng với n = k+1, tức là cm: 1 2 k k 1 1   ...    1 , k  1 2! 3! (k  1)! ( k  2)! (k  2)!Ta có: 1 2 k k 1 1 k 1 vt    ...    1  2! 3! (k  1)! (k  2)! (k  1)! (k  2)! ( k  2  k  1) 1  1  1  vp (k  2)! ( k  2)! Vậy: 1 2 n 1   ...   1 , n  1 2! 3! (n  1)! (n  1)!b) Đặt: P(n) = n3 + 11n Với n = 1: P(1) = 13 + 11.1= 12 chia hết cho 6 Giả sử: P(k) = (k3 + k) chia hết cho 6 Ta chứng minh (1) đúng với n = k+1, tức là cm: P(k  1)  ((k  1)3  11(k  1)) chia hết cho 6Ta có: P( k  1)  k 3  3k 2  3k  1  11k  11  (k 3  11k )  3k ( k  1)  12  P ( k  1) chia hết cho 6 Vậy: (n3 + 11n) chia hết cho 6, n  1 1.3 CÔNG THỨC TRUY HỒI 1. Định nghĩa Công thức truy hồi của dãy s0, s1, s2, … là côngthức xác định sn qua một hay nhiều số hạng đitrước của dãy. Điều kiện ban đầu là các giá trị gán cho một sốhữu hạn các phần tử đầu. Ví dụ 1:a. Công thức truy hồi của n!: sn = n.sn-1, với n  1 & s(0) = 1b. Dãy số Fibonacci được định nghĩa như sau: fn = fn-1 + fn-2 , với n  2 & f0 = f1 = 1 (1, 1, 2, 3, 5, 8, 13, …)c. Sn = 6sn-1 – 11sn-2 + 6sn-3 với s0 = 2, s1 = 5, s2 = 15 2. Giải công thức truy hồi Giải công thức truy hồi là tìm một công thức rõràng cho sn mà không phải tính thông qua cácphần tử trước nó.a. Giải công thức truy hồi bằng phương pháp lặp: Giải CTTH bằng pp lặp là thay thế liên tiếp côngthức truy hồi vào chính nó, mỗi lần thay bậc ngiảm đi ít nhất một đơn vị, cho đến khi đạt giá trịban đầu. Bài toán : Tháp Hà Nội Có 3 cọc a, b, c. Trên cọc a có n đĩa xếp chồnglên nhau sao cho đĩa nhỏ trên đĩa lớn. Cần chuyển chồng đĩa từ cọc a sang cọc c tuânthủ quy tắc: Mỗi lần chỉ chuyển được một đĩa, luônđảm bảo đĩa nhỏ trên đĩa lớn, có thể sử dụng cọc blàm trung gian.Phương pháp di chuyển đĩa như sau:  Chuyển n – 1 đĩa từ cọc a sang cọc b sử dụng cọc c làm trung gian.  Chuyển đĩa lớn nhất từ cọc a sang cọc c.  Chuyển n – 1 đĩa từ cọc b sang cọc c sử dụng cọc a làm trung gian. Đếm số lần di chuyển của n đĩa trên?Công thức truy hồi tính số lần di chuyển đĩa: Sn = 2.sn-1 + 1, với n  2 & s1 = 1 Bài toánTrên mặt phẳng kẻ n đường thẳng sao cho khôngcó hai đường nào song song hay ba đường nàođồng quy. Hỏi mặt phẳng chia làm mấy phần? Giải Gọi số phần mặt phẳng chia bởi n đườngthẳng là s(n). Giả sử đã kẻ (n-1) đường thẳng.Bây giờ kẻ thêm đường thẳng thứ n thì số phầnmặt phẳng mặt phẳng được thêm sẽ bằng số giaođiểm cộng 1 (n – 1 + 1 = n) phần.Vậy ta có công thức truy hồi sau: s(n) = s(n – 1) + n với n  2 & s(1) = 2Giải công thức truy hồi trên bằng phương pháplặp, ta có: s(n) = 1 + n(n+1)/2b. Giải công thức truy hồi bằng phương trình đặc trưng:Định nghĩa Một hệ thức truy hồi tuyến tính thuần nhất bậc k hệ số hằng là hệ thức truy hồi có dạng: sn = c1s1 + c2s2 + ... + cnsn , (1) trong đó c1, c2, ..., ck là các số thực và ck  0. Điều kiện đầu là: s0 = C0, s1 = C1, …, sn = CnPhương trình sau gọi là phương trình đặc trưng củacông thức truy hồi (1): rk – c1rk-1 – c2rk-2 – … – ck = 0 Định lí 1 Giả sử phương trình đặc trưng: rk  c1rk-1  c2 ...