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"
AMBIENT/
Chủ đề:
Nội dung Text: Bài tập Cấu trúc 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→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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
