Bài tập chương 1: Toán rời rạc

Chia sẻ: Nguyen Thanh Tung | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

143
lượt xem 30
download

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

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

Chủ đề:

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

Lưu

Nội dung Text: Bài tập chương 1: Toán rời rạc

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
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 → (r ∧ q) p→q ¯ q ¯ q→p ¯ ¯ q∨r ¯ r → (s ∨ t) (q ∧ r) → s r ¯ p r ¯ s ¯ t→r ∴p∨r ∴ r ∴q ∴ t ¯ ¯ ∴s→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
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
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
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? a) = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} b) = {(1, 1), (2, 2), (3, 3), (3, 4)} c) = {(a, b) | |a − b| ≤ 2} d) = {(a, b) | hi u a − b chia h t cho 2} e) = {(a, b) | |a − b| > 3} f) = {(a, b) | |a − b| = 1} 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
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 + 3x ≤ y 2 + 3y 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 = y2n 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
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: ¯¯ ¯ ¯ z ¯¯ ¯ a) f = z t ∨ xy t ∨ xy¯ ∨ xy z t ∨ x¯z t ∨ y zt. y¯ ¯ ¯ z¯ ¯ y b) f = x(zt ∨ t) ∨ x(¯z ∨ y¯t) ∨ z t(¯ ∨ xy). ¯ y z¯ ¯ ¯ c) f = x¯t ∨ x¯z ∨ xyt ∨ xyz t ∨ xzt ∨ xy t. y¯ ¯¯ z¯ y ¯ d) f = x¯t ∨ x¯z t ∨ xyt ∨ xyz. ¯ ¯ y ¯ ¯¯ ¯ z¯ ¯ e) f = z t ∨ x¯t ∨ xy z ∨ xyzt ∨ xy¯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 ∨ x¯z ∨ xyt ∨ xy z ∨ yz t ∨ y t. y¯ ¯ ¯ ¯¯ 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 ∨ x¯ z . y¯ 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
Bài 4.5. Cho hàm Bool 4 bi n xác đ nh b i y ¯¯ ¯ ¯ ¯ z f (x, y, z, t) = x¯t ∨ y z t ∨ xyz ∨ yzt ∨ xy t ∨ 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. Bài 4.6. Cho hàm Bool 4 bi n xác đ nh b i ¯ ¯ ¯ ¯ ¯¯ z ¯ f (x, y, z, t) = x y z t ∨ x z t ∨ y zt ∨ y z 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.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 ¯ ¯¯ z¯ f (x, y, z, t) = x y z t ∨ y z t ∨ x zt ∨ x z t ∨ x¯ 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 ¯ ¯ ¯ y z y¯ f (x, y, z, t) = xyz ∨ xz t ∨ x¯t ∨ xzt ∨ xy¯ ∨ x¯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 ¯¯ y ¯ ¯ ¯¯ f (x, y, z, t) = xt ∨ yt ∨ xy ∨ xt ∨ x¯ 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
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   b) Cho ma tr n k c a đ th G là   0 1 0 1 1 . 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
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   b) Cho ma tr n k c a đ th G là   2 1 0 1 0 . 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   b) Cho ma tr n k c a đ th G là   0 1 0 1 1 . 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
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   b) Cho ma tr n k c a đ th G là   0 2 0 1 1 . 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   b) Cho ma tr n k c a đ th G là   1 1 0 1 1 . 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