Bài tập cấu trúc rời rạc nguyen huu anh năm 2024

Nội dung Text: Bài tập Cấu trúc rời rạc

1. Bài t p chương 1 Bài 1.1. G i P, Q, R là các m nh đ : P := “Bình đang h c Toán” Q := “Bình đang h c Tin h c” R := “Bình đang h c Anh văn” Hãy vi t l i các m nh đ dư i đây dư i d ng hình th c trong đó s d ng các phép toán a] Bình đang h c Toán và Anh văn nhưng không h c Tin h c b] Bình đang h c Toán và Tin h c nhưng không h c cùng m t lúc Tin h c và Anh văn c] Không đúng là Bình đang h c Anh văn mà không h c Toán d] Không đúng là Bình đang h c Anh văn hay Tin h c mà không h c Toán e] Bình không h c Tin h c l n Anh văn nhưng đang h c Toán Bài 1.2. Ph đ nh các m nh đ sau a] Ngày mai n u tr i mưa hay tr i l nh thì tôi s không ra ngoài b] 15 chia h t cho 3 nhưng không chia h t cho 4 c] Hình t giác này không ph i là hình ch nh t mà cũng không ph i là hình thoi d] N u An không đi làm ngày mai thì s b đu i vi c e] M i tam giác đ u có các góc b ng 60 đ Bài 1.3. . G i P, Q, R là các m nh đ sau: P : ABC là tam giác cân Q : ABC là tam giác đ u R : Tam giác ABC có ba góc b ng nhau Hãy vi t các m nh đ sau theo ngôn ng thông thư ng a] Q → P b] ¬P → Q 1
2. c] P ∧ ¬ Q d] R → P Bài 1.4. Hãy ki m tra các suy lu n sau p∧q p p→q p → [q → r] p∨q p→q p → [r ∧ q ] ¯ q→p q∨r q ¯ ¯ ¯ ¯ [q ∧ r ] → s r → [s ∨ t] r ¯ p r ¯ t→r s ¯ ∴p∨r ∴r ∴q ¯ ∴s→t ∴t ¯ Bài 1.5. a] Cho p, q, r là các bi n m nh đ . Ch ng minh [p → q ] ∧ q ∧ [q → r ] ⇔ q ∧ p ¯ ¯¯ b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ N, ∀y ∈ R, [x2 + y > 5] ∨ [x + y < 4]”. Bài 1.6. a] Cho p, q, r là các bi n m nh đ . Ch ng minh [p ∧ q ∧ r] ⇔ [p → q ∨ [p ∧ r]] ¯ b] Ph đ nh và tìm chân tr c a m nh đ P = ”∀x ∈ R, ∃y ∈ R, [x2 > y 2 ] → [x < y ]”. Bài 1.7. a] Ch ng minh [[p → q ] ∧ r] ∧ q → [¯ ∧ r] là h ng đúng. p b] Ph đ nh và tìm chân tr c a m nh đ P : “∀x ∈ R, ∃y ∈ R, x2 − 3y + 2 ≤ 0”. Bài 1.8. a] Ch ng minh [[p → q ] ∧ q ] → p là h ng đúng. b] Ph đ nh và tìm chân tr c a m nh đ P : “∀x ∈ R, ∀y ∈ R, [x2 > y 2 ] → [x > y ]”. Bài 1.9. h a] Cho p, q, r là các bi n m nh đ , đ t E = [p ∧ r] ∨ [[p ∧ [p ∨ q ]] → r]. H i E là ¯ h ng đúng hay h ng sai? T i sao? b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ N, ∀y ∈ R, x + 2y < 2 ho c x2 + y = 3”. 2
3. Bài 1.10. a] Cho p, q, r là các bi n m nh đ . Ch ng minh [p ∧ q ] ∨ r ⇔ [p → q ] ∧ r ¯¯ b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ R, ∃y ∈ R, [x + y = 3] ∧ [x − y < 1]”. Bài 1.11. a] Cho p, q, r là các bi n m nh đ , đ t E = p ∧ r ∧ [¯ → p] ∧ [q ∨ r]. H i E là ¯r ¯ h ng đúng hay h ng sai? T i sao? b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ R, ∀y ∈ Z, x + 2y = 3 ho c 3x − 4y = 4”. Bài 1.12. a] Cho d ng m nh đ E = [[r → p] ∧ q ] → [¯ ∨ r]. Tìm chân tr c a q và r bi t p r ng E đúng, p sai. b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ Z, ∀y ∈ R, x + y = 2 ho c 2x − y = 1”. Bài 1.13. a] Cho p, q, r là các bi n m nh đ . Ch ng minh [¯ ∨ q ] ∧ [p → r] ⇔ p → [q ∧ r]. p b] Ph đ nh và tìm chân tr c a m nh đ P = “∀x ∈ N, ∀y ∈ R, [|x| = |y |] → [x = y ]”. Bài t p chương 2 Bài 2.1. a] Cho X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. H i có bao nhiêu t p h p con X c a A ch a 4 ph n t và nh n 2 ho c 3 làm ph n t nh nh t. b] Gi i h th c đ quy  xn − 5xn−1 + 6xn−2 = n − 3 v i n ≥ 2; x = 1; 0 x1 = 3. Bài 2.2. a] Tìm s cách chia 15 viên bi gi ng nhau cho 4 đ a tr sao cho m i đ a tr đ u có bi và đ a l n nh t đư c ít nh t 5 viên bi. b] Cho dãy an xác đ nh b i: an = 4an−1 − 4an−2 + 4 v i n ≥ 2, a0 = 1, a1 = 2. Tìm bi u th c c a an theo n. 3
4. Bài 2.3. a] Cho A = {n ∈ N | 10 ≤ n ≤ 89}. H i có bao nhiêu t p con c a A g m 5 ph n t , trong đó có đúng 2 ph n t có ch s t n cùng gi ng nhau. b] Cho dãy an xác đ nh b i: an = 5an−1 − 6an−2 + 2 v i n ≥ 3, a1 = 1, a2 = 2. Tìm bi u th c c a an theo n. Bài 2.4. a] Tìm s nghi m nguyên c a phương trình x + y + z + t = 20, bi t x ≥ 1, y ≥ 2, z ≥ 3, t ≥ 4. b] Cho dãy an xác đ nh b i: an = 5an−1 − 6an−2 + 2 v i n ≥ 2, a0 = 4, a1 = 9. Tìm bi u th c c a an theo n. Bài 2.5. a] Cho A = {1, 2, 3, 4, 5, 6, 7, 8}. H i có bao nhiêu t p con c a A ch a ph n t 2 và 3. b] Cho dãy an xác đ nh b i: an = 4an−1 − 4an−2 + 2 v i n ≥ 2, a0 = 1, a1 = 2. Tìm bi u th c c a an theo n. Bài 2.6. a] Có bao nhiêu chia 18 viên bi gi ng nhau cho 4 đ a tr sao cho m i đ a tr đ u có bi và đ a l n nh t đư c ít nh t 6 viên bi. b] Cho dãy an xác đ nh b i: an = 6an−1 − 9an−2 + 4 v i n ≥ 2, a0 = 1, a1 = 2. Tìm bi u th c c a an theo n. Bài 2.7. a] Tìm s nghi m nguyên c a phương trình x + y + z + t = 16 th a đi u ki n 2 ≤ x ≤ 5, y ≥ 1, z ≥ 2, t ≥ 3.  xn − 4xn−1 + 4xn−2 = 6 v i n ≥ 2; b] Gi i h th c đ quy x0 = 1; x1 = 4.  Bài 2.8. a] Tìm s nghi m nguyên c a phương trình x + y + z + t = 12 th a đi u ki n x ≥ 0, y ≥ 1, z ≥ 2, t ≥ 3.  4xn − 4xn−1 + xn−2 = 0 v i n ≥ 2; b] Gi i h th c đ quy x0 = 2; x1 = 4.  Bài 2.9. 4
5. a] Tìm s nghi m nguyên không âm c a phương trình x1 + x2 + x3 + x4 = 8 bi t x1 ≥ 1 hay x2 ≥ 2.  xn − 8xn−1 + 15xn−2 = 0 v i n ≥ 2; b] Gi i h th c đ quy: x0 = 1; x1 = 9.  Bài 2.10. a] Tìm s nghi m nguyên c a phương trình x + y + z + t = 15 th a đi u ki n x ≥ 1, y ≥ 2, z ≥ 2, t ≥ 3.  xn − 5xn−1 + 6xn−2 = 2n + 1 v i n ≥ 2; b] Gi i h th c đ quy x0 = 1; x1 = 2.  Bài t p chương 3 Bài 3.1. Cho t p A = {1, 2, 3, 4} và quan h trong A xác đ nh dư i đây. Hãy xác đ nh xem trong t ng trư ng h p có các tính ch t ph n x , đ i x ng, ph n x ng, b c c u không? = {[2, 2], [2, 3], [2, 4], [3, 2], [3, 3], [3, 4]} a] = {[1, 1], [2, 2], [3, 3], [3, 4]} b] = {[a, b] | |a − b| ≤ 2} c] = {[a, b] | hi u a − b chia h t cho 2} d] = {[a, b] | |a − b| > 3} e] = {[a, b] | |a − b| = 1} f] Bài 3.2. Trên t p h p A = {−2, −1, 1, 2, 3, 4, 5}. Ta xét quan h hai ngôi như sau: x y ⇔ x − 3y ch n. a] Ch ng minh là quan h tương đương. b] Tìm các l p tương đương c a [1], [2]. Bài 3.3. Trên t p h p A = {−2, −1, 0, 2, 3}, ta xét quan h hai ngôi như sau: x y ⇔ x2 − 2x = y 2 − 2y. a] Li t kê các ph n t c a t p quan h trên A. b] Tìm t p h p X có vô h n ph n t đ là m t quan h th t trên X . Gi i thích? 5
6. Bài 3.4. Trên t p h p A = {−1, 0, 2, 3, 4}, ta xét quan h hai ngôi như sau: x y ⇔ x2 − 3x = y 2 − 3y. a] Li t kê các ph n t c a t p quan h trên A. b] Tìm t p h p X có vô h n ph n t đ là m t quan h th t trên X . Gi i thích? Bài 3.5. Trên t p h p X , ta xét quan h hai ngôi sau: x y ⇔ x2 + 3 x ≤ y 2 + 3 y a] N u X = R thì có nh ng tính ch t nào? Gi i thích. b] N u X = N thì có ph i là quan h th t không? Gi i thích. Bài 3.6. Trên t p h p s t nhiên N, ta xét quan h hai ngôi như sau: x y ⇔ x2 − y 2 ch n. a] Ch ng minh là quan h tương đương trên N. b] Tìm phân ho ch c a N thành các l p tương đương. Bài 3.7. Trên t p h p A = {−2, −1, 0, 2, 3, 4, 5, 7, 9}, ta xét quan h hai ngôi như sau: x y ⇔ x − y chia h t cho 3. a] Ch ng minh là quan h tương đương trên A. b] Tìm l p tương đương c a [3]? Trong các l p [−2], [−1], [2], [5], [7] có bao nhiêu l p đôi m t phân bi t? Bài 3.8. Xét quan h trên Z đ nh b i: x, y ∈ Z, x y ⇔ ∃n ∈ Z, x = y 2n a] Ch ng minh là m t quan h tương đương. b] Trong s các l p tương đương [1], [2], [3], [4] có bao nhiêu l p đôi m t phân bi t? c] Câu h i tương t như câu b] cho các l p [6], [7], [21], [25], [35], [42]v [48]. Bài 3.9. Cho X = {2, 4, 6, 8, 10, 14, 16, 15, 20, 30, 36, 40, 60} v i v i quan h ư c s |. a] V sơ đ Hass. b] Tìm các ph n t t i đ i và t i ti u trong X 6
7. Bài 3.10. Trong các trư ng h p sau, hãy tìm các ph n t l n nh t, nh nh t, t i đ i, t i ti u [n u có] c a các t p h p đã cho v i th t tương ng. V các bi u đ Hasse. a] U30 = {n ∈ N | n|30} v i quan h ư c s |. b] X = {2, 3, 4, 6, 8, 10, 80} v i quan h ư c s |. c] X = {1, 2, 3, 4, 6, 8, 10, 11} v i quan h xác đ nh như sau: x y ⇔ x = y hay x < y − 1. Bài t p chương 4 Bài 4.1. V bi u đ Karnaugh và tìm các công th c đa th c t i ti u, d ng n i r i chính t c c a các hàm Bool theo 4 bi n x, y, z, t sau đây: ¯¯ ¯ ¯ ¯ ¯¯ ¯ a] f = z t ∨ xy t ∨ xy z ∨ xy z t ∨ xy z t ∨ y zt. ¯¯ ¯ ¯ ¯¯ ¯ y b] f = x[zt ∨ t] ∨ x[¯z ∨ y z t] ∨ z t[¯ ∨ xy ]. ¯ y ¯¯ ¯¯ c] f = xz t ∨ xy z ∨ xyt ∨ xyz t ∨ xzt ∨ xy t. ¯¯ ¯¯ ¯¯ ¯¯ d] f = xz t ∨ xy z t ∨ xyt ∨ xyz. ¯ ¯¯ ¯ e] f = z t ∨ xy t ∨ xy z ∨ xyzt ∨ xy z t ∨ yz t. ¯ ¯ ¯ ¯¯ ¯ Bài 4.2. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯ ¯¯ f [x, y, z, t] = z t ∨ xy z ∨ xyt ∨ xy z ∨ yz t ∨ y t. ¯¯ ¯ ¯ ¯¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.3. Cho hàm Bool 4 bi n xác đ nh b i ¯¯ f [x, y, z, t] = xy ∨ xt ∨ yt ∨ xt ∨ xy z . ¯ ¯¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.4. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯¯¯ ¯ f [x, y, z, t] = xz ∨ y z t ∨ xy t ∨ y z t ∨ xyz ∨ xy . ¯ ¯¯ ¯¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. 7
8. Bài 4.5. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯¯ f [x, y, z, t] = xy t ∨ y z t ∨ xyz ∨ yzt ∨ xy t ∨ xy z ¯ ¯¯ ¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.6. Cho hàm Bool 4 bi n xác đ nh b i ¯¯ ¯ ¯ ¯¯ ¯¯ f [x, y, z, t] = x y z t ∨ x z t ∨ y zt ∨ y z t ∨ y z t a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.7. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯ ¯ ¯¯ f [x, y, z, t] = x y z ∨ x y z ∨ x y t ∨ x z t ∨ x y zt ¯¯ ¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.8. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯¯ ¯¯ f [x, y, z, t] = x y z t ∨ y z t ∨ x zt ∨ x z t ∨ xz t ¯¯ ¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.9. Cho hàm Bool 4 bi n xác đ nh b i ¯¯ ¯¯ f [x, y, z, t] = xyz ∨ xz t ∨ xy t ∨ xzt ∨ xy z ∨ xy t ¯ ¯ ¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. Bài 4.10. Cho hàm Bool 4 bi n xác đ nh b i ¯¯ ¯ ¯ ¯ ¯¯ f [x, y, z, t] = xt ∨ yt ∨ xy ∨ xt ∨ xy z ∨ y z t ¯ a] V bi u đ Karnaugh c a f và xác đ nh các t bào l n. b] Tìm công th c đa th c t i ti u c a f. 8
9. Bài t p chương 5 Bài 5.1. a] Cho đ th G có 13 c nh, trong đó có 3 đ nh b c 1, 4 đ nh b c 2, 1 đ nh b c 5, các đ nh còn l i có b c là 3 ho c 4. H i G có bao nhiêu đ nh b c 3 và đ nh b c 4?   0 2 0 1 1 2 0 1 2 0     0 1 0 1 1 b] Cho ma tr n k c a đ th G là  . Gi i thích G có đư ng đi   1 2 1 0 0   1 0 1 0 0 Euler và tìm đư ng đi Euler c a G. Bài 5.2. Cho đ th G có 14 c nh, trong đó có 3 đ nh b c 1, 2 đ nh b c 3, 2 đ nh b c 4, 1 đ nh b c 5, các đ nh còn l i có b c là 2. H i G có bao nhiêu đ nh? Bài 5.3. Cho đ th G có 16 c nh, trong đó có 4 đ nh b c 1, 3 đ nh b c 2, 2 đ nh b c 5, các đ nh còn l i có b c là 3. H i G có bao nhiêu đ nh b c 3? Bài 5.4. Cho đ th L p ma tr n k và xác đ nh đư ng đi Euler c a đ th . Bài 5.5. a] Cho đ th G có 12 c nh, trong đó có 4 đ nh b c 1, 2 đ nh b c 4, 1 đ nh b c 5, các đ nh còn l i có b c là 2 ho c 3. H i G có bao nhiêu đ nh b c 2 và đ nh b c 3 ? b] Cho đ th 9
10. L p ma tr n k và xác đ nh chu trình Euler c a đ th . Bài 5.6. a] T n t i hay không đ th đơn g m 5 đ nh, trong đó có 3 đ nh b c 3, 1 đ nh b c 2 và 1 đ nh b c 4?. Gi i thích.   0 1 2 1 1 1 0 1 0 0     2 1 0 1 0 b] Cho ma tr n k c a đ th G là  . Gi i thích G có đư ng đi   1 0 1 0 1   1 0 0 1 0 Euler và tìm đư ng Euler c a đ th . Bài 5.7. a] Trong m t gi i thi đ u có n đ i tham d và đã có n + 1 tr n đ u đư c ti n hành. Ch ng minh có 1 đ i đã thi đ u ít nh t 3 tr n.   0 1 0 1 2 1 0 1 1 0     0 1 0 1 1 b] Cho ma tr n k c a đ th G là  . Gi i thích G có đư ng đi   1 1 1 0 1   2 0 1 1 0 Euler và tìm đư ng Euler c a đ th . Bài 5.8. a] Cho đ th G có 12 c nh, trong đó có 4 đ nh b c 1, 2 đ nh b c 3, 2 đ nh b c 4, các đ nh còn l i có b c là 2. H i G có bao nhiêu đ nh b c 2 ? b] Cho đ th 10
11. Gi i thích đ th có đư ng đi Euler và tìm đư ng Euler c a đ th . Bài 5.9. a] Cho G là đ th vô hư ng liên thông mà m i đ nh đ u có b c 6. Ch ng minh r ng n u xoá đi m t c nh b t kỳ thì đ th thu đư c v n còn liên thông.   0 0 0 1 1 0 0 2 1 0     0 2 0 1 1 b] Cho ma tr n k c a đ th G là  . Gi i thích G có đư ng đi   1 1 1 0 2   1 0 1 2 0 Euler và tìm đư ng Euler c a đ th . Bài 5.10. a] V nh ng đ th đơn vô hư ng g m 6 đ nh v i b c tương ng là 2, 2, 3, 3, 3, 5.   0 2 1 0 1 2 0 1 1 0     1 1 0 1 1 b] Cho ma tr n k c a đ th G là  . Gi i thích G là đ th   0 1 1 0 0   1 0 1 0 0 Euler và tìm chu trình Euler c a đ th . 11