Tài liệu Giáo trình toán rời rạc đặng ngọc hoàng thành

GIÁO TRÌNH Hu , 2011 M C L C .......................................................................................................... 4 ..................................................................................................................................... 4 . .......................................................................... 10 ............................................................................................................... 16 . .......................................................................................... 29 .............................................................................................................. 29 ................................................................................................................. 31 ............................................................................................................. 33 ................................................................................... 41 .............................................................................................................. 41 .............................................................................................. 44 3.2. Nguyên lý Dirichlet ............................................................................................................ 46 .................................................................................... 48 .............................................................................................................. 48 ............................................................................................................. 49 ..................................................................................... 53 .............................................................................................................. 53 . ................................................................................................. 53 6. .................................................................................. 72 .............................................................................................. 72 6.1.1. 6. 6.1.3. ........................................................................................ 73 .................................................................................................................... 76 ........................................................................... 81 6.1.4. Hành trình và chu trình ........................................................................................ 82 6.2. 6. ..................................................................................................... 90 . ........................................................................................... 90 ............................................................................................ 93 . ................................................................................................. 95 6.3. ................................................................................... 96 6. 6. 6.4 ................................................................................................................ 96 ........................................................................................................ 97 .......................................................................................................................... 98 2 .................................................................................................. 101 3 U 1.1. T p h p các t là t p. Ví d t p h p A hay t p A. Cho m t t p h p A, và m t ph n t a c a t p h p A. Ta nói r ng, ph n t a thu c t p h p A. Kí hi u t p h p A thì ta nói r ng, ph n t b không thu c t p h p A và kí hi u a) t c ho c m t ph n các ph n t trong t p h p - T p các s t nhiên ch n b) không li t kê t t c các ph n t c a nó mà ch nêu các tính ch a t p h p. Hay bao trùm i ph n t c a t p h p A thu c vào t p h p B. Kí hi u . N u t p h p A là con c a t p h u s g i t p h p B là cha c a t p h p A. c thay b ng kí hi u . N u t p h p và N u t p h p ho c Trong nhi thì ta nói r ng t p . thì ta nói A là t p con ho c b ng B và kí hi u . ng h i ta s g i t p A là con c a t p B và . bao trùm (hay t ). T p h p bao c kí hi u là . a t p h p r ng và t p bao trùm, ta có m t s + T p h p r ng là con c a m i t p h p b i t p h p r ng không ch a ph n t nào. là t p con c a t p bao trùm. 5 L ng c a t p h p. S c a t p h p. Kí hi u - ng các ph n t c a m t t p h c là l M t t p h p có n ph n t , thì có c g i là l ng ng c a t p h p A. có t p con c a A. Các t p h p này bao g m: T p các t p h p con c a t p h c kí hi u là 1.1.3. . . A B 1 3 2 Hình 1.1 p B. Kí hi u . Trong hình minh h a trên, h p c a hai t p h p A và B là t p h p ch a ba ph n 1, 2 và 3. Ví d : Gi s ta có t p h p A và B. Yêu c u tìm h p c a hai t p h p A và B. 6 l b. Phép toán giao chung p h p. Kí hi u Trong hình minh h a trên, giao c a hai t p h p A và B là t p h p ch a ph n 3. Ví d : Gi s ta có t p h p A và B. Yêu c u tìm h p c a hai t p h p A và B. A. B \ . Trong phân bi t gi a hai kí hi u này1. Trong hình minh h a trên, hi u c a hai t p h p A và B là t p h p ch a ph n 1. Ví d : Gi s ta có t p h p A và B. Yêu c u tìm hi u c a hai t p h p A và B. N u t p h p A là con c a t p h p B, thì hi u c a hai t p h p A và B là t p h p r ng. Ph n bù t p h p. Gi s t p h p A là con c a t p h p B và n m l t h n trong t p h p B. 1 N uA N u thì hi u c c kí hi u là A\B. -B. 7 B A 2 1 Hình 1.2 Minh h a ph n bù trên T p h p n bù c a t p h p A gi n là ph n bù c a B). Kí hi u i v i t p h p . N u t p h p B là t p bao trùm, ta có th kí hi u ph n bù c a t p h p A là . h a các ph n t thu c t p h p A mà không thu c t p h p B và các ph n t thu c t p h p B mà không thu c t p h p A. Kí hi u . 1 1 và 2. ta có t p h p A và B. Yêu c u tìm hi u i x ng c a hai t p h p A và B. . 8 Gi s A, B, C là các t p h p. E là t có các tính ch t a) Lu t giao hoán b) Lu t k t h p c) Lu t phân ph i + Phân ph i trái + Phân ph i ph i d) Lu ng nh t e) Lu t nu t f) Lu y g) Lu ng 9 h i) Lu t bù j) Lu t De-Morgan 1.1.5. Khái ni m v tích Descartes . Gi s A và B là hai t p h p. M t t p h p g m các c p (a, b) v i , sao cho v i hai c p (a, b)=(c, d) khi và ch và c g i là tích Descartes c a hai t p h p A và B. Kí hi u AxB hay A.B. Ví d a hai t p A và B g m các c p T ng quát, tích Descartes c a n t p h p v i là t p h p g m các c p và và ch khi khi . Kí hi u Gi s t p l n t p h p trên t có . ph n t s có a , hay ta có th vi t . 1.2. Phép ch ng minh quy n p toán h c 1.2.1. P 10 2 n=k+1. sai. S i n0 i n=k i n=k+1 S CT sai Hình 1.3 th c c 1. V i n = 0. Ta có V trái VT = V ph i VP = 0 Công th i n=0. 11 c 2. Gi s công th i n=k, t c là Ta c n ch ng minh, công th i n = k+1, t c là Ta có b i vì K t h p v i gi thi t quy n p (*), ta có c 3. V y, công th Bài t p. Ch ng minh các công th c sau b ng quy n p toán h c. 12 ng th c t pháp khác có th áp d i ta s d ng m n t m t cách d pháp quy n p hoàn toàn. Gi s ta c n ch i các giá tr . áp quy n p hoàn toàn s th c hi n ki P(n) = Q(n) v i m i giá tr n c a bài toán . sau: bool QuyNapHoanToan(int n0, int n1) { for (int i=n0; i<=n1; i++) if (P(i)!=Q(i)) return true; } return false; Ví d , ta s s d ng thu t toán quy n a) v i giá tr ki n c a câu #include #include using namespace std; double P(int n) { double S = 0; for (int i=0; i<=n; i++) S+=powl(i, 2); return S; } double Q(int n) { return (double)(n)*(n+1)*(2*n+1)/6; 13 } bool QuyNapHoanToan(int n0, int n1) { for (int i=n0; i<=n1; i++) if (P(i)!=Q(i)) return false; return true; } int main() { if(QuyNapHoanToan(0, 9999)) cout<<"Dang thuc dung voi moi 0<=n<=9999"; else cout<<"Dang thuc sai"; return 0; } Hãy vi t gi i thu t quy n p hoàn toàn cho các bài t p còn l i. 1.2.3. xác Khái ni g qua ph n t th c truy h i trong toán h c. M t ví d mô hình tính giai th a. nh c - - - - -1)! 14 ng h p suy bi n, thì th c hi c 2. N ng h p suy bi n. c l i, ta ti n hành th c hi n gi i thu t g i l quy. Ví d 1. Tính t ng -1) long S(int n) { if(n==1) return 1; else return n+S(n-1); } ->data == x. ->next. struct Link { int data; Link* next; }; Link* head; Link* search(int x, Link* head) { if(head->data==x) return head; else return search(int x, head->next); } 15 T . 1.3 c v t h p 1.3.1.1 ng l th c hi n công vi c th cách. th c hi n m t công vi c trong n công vi c trên, ta s có cách. xét Bài 1. bao nhiêu node. Bài 2. t . 16 i. . - - . g viên c a t b môn công ngh ph n m m, B là t p h p các gi ng viên c a t b t l ng c a t p ng vi c ch n c a chúng ta s chính là l c . Ta có . Bài 3. và . H . Bài 4. Cho - - - 17 - - - - - V y có 1+3+3+1 = 8 t p con c a t p A. 1.3.1.2. Quy t c nhân Quy t c nhân. Gi s c n th c hi n m t công vi c. Công vi c này có th chia ra làm n th c hi n công vi c c th n, ta s có cách. nhân ) nhân. Bài 1. có bao nhau. am C có 3 cách; có 3 cách; 18 C có 2 cách; C có 2 cách. ta có Bài 2. nh . - - c Bài 3. c nhân, ta có 20.20.20.20.20=32.105 1.3.2.1. tính 19 - - ). - u: hai cách s p x p là khác nhau khi hai ph n t cùng ch s là khác nhau. V y theo quy t c nhân, ta có n.(ns p x p. Bài toán hoán v c a n ph n t có n! cách s p x p. Công th c tính s hoán v . Hoán v c kí hi u là , tr ho th quy v hoán v tuy n tính c a n-1 ph n t vòng c a n ph n t s có (n-1)! cách s p x p. Công th c tính s hoán v vòng. Hoán v c kí hi u là . Chú ý. C : - 20