Bài tập Cấu trúc rời rạc

Chia sẻ: Võ Minh Sơn | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

465
lượt xem 46
download

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

Tài liệu tham khảo dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Giáo trình, bài tập toán rời rạc. Bài 1.1: Gọi P,Q,R là cá mệnh đề: P:= "Bình đang học Toán" Q:= "Bình đang học Tin học"

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 Cấu trúc rời rạ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→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
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? = {(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
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
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
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
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
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
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