Ngân hàng bài tập môn Toán rời rạc | Đại học Kinh tế Quốc Dân
Ngân hàng bài tập môn Toán rời rạc có đáp án của trường Đại học kinh tế quốc dân giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!
Preview text:
BÀI TẬP TOÁN RỜI RẠC CHƯƠNG 1: CƠ SỞ LOGIC
1/ Xét chân trị của các vị từ p(x) , p(x)q(x), p(x)q(x), p(x) q(x) và p(x) q(x) tùy theo biến thực x :
a) p(x) = “ x2 2x 8 0 “ và q(x) = “ (x + 1)(x 2) 1 > 0 “
b) p(x) = “(3 2x)(x + 4) 1 0 “ và q(x) = “ (x2 + x 2)(x 3x + 10) > 0 “
2/ Cho a R. Viết mệnh đề phủ định A nếu A có nội dung như sau :
a) 2a3 +5a = 10 b) (2a 5)(3a + 1) 1 7 c) 8 5a 2 d) ln(a2 a 2) < 3
e) Khoảng 2/3 số học sinh có thể chất tốt f) Không đến 3/4 số tài xế có bằng lái hợp lệ
g) Không quá 2/5 dân số tốt nghiệp đại học h) Hơn một nửa số Bộ trưởng thực sự có năng lực
i) Không ít hơn 1/6 số trẻ em bị thất học j) Nhiều nhất là 30 ứng viên thi đạt ngoại ngữ
k) Có ít nhất 5 sinh viên đạt giải thưởng l) Đúng 12 thí sinh dự vòng chung kết của cuộc thi
m) Hơn 7 vận động viên phá kỷ lục quốc gia n) Ít hơn 16 quốc gia thi đấu môn bóng rổ
o) Nếu Sơn thắng trận thì anh ấy được đi Paris p) Không ai muốn làm việc vào ngày chủ nhật
q) Cả lớp nói chuyện ồn ào r) Có ai đó gọi điện thoại cho Tuấn s) Các cầu thủ không thích bơi lội
t) Hắn thông minh nhưng thiếu thận trọng u) Ngọc học Toán mà không học Lịch sử
v) Dũng cùng An đi thi ngoại ngữ w) Vũ vừa giỏi Vật Lý vừa giỏi Hóa học
x) Hải đạt kết quả thấp ở cả môn Tin học lẫn môn Toán y) Họ đến trường hay họ đi xem phim
z) Chúng tôi đi Vinh nhưng các anh ấy không đi Huế ) Nhóm bác sĩ hay nhóm kỹ sư đi làm từ thiện
Từ bài 3 đến bài 5, các ký hiệu p, q, r và s là các biến mệnh đề .
3/ Rút gọn các dạng mệnh đề sau :
a) [(p q) (p q )] q b) p q [( p q ) q ] c) p q ( p q r)
d) p (q r) ( p q r) e) (p q) [ q ( q r)] f) p (p q ) (p q r ) (p q r s ) 4/ Chứng minh
a) [(p q) p q p q ] (p q) b) [{(p r) (q r)} (p q)] ( p q r )
c) {(p q) [p (q r)]} (p q) d) {[( p q r ) q ] (p r)} (p q r)
e) {[q (p r)] ( p r) q } [(p r) q ] f) [p (q r)] [ r ( q p )]
g) [(p q) (q r) (r p)] [(p q) (q r) (r p)] h) [p ( q r)] [(q r ) p ]
i) [(p q) (q r) (r p)] [(p q) (q r) (r p)] j) [ ( q p ) p) ] p q
5/ Chứng minh các dạng mệnh đề sau là hằng đúng hoặc hằng sai :
a) (p q) (p q r) b) (p q) [(q r) (p r)] c) [p (q r)] (p q)
d) [(p q) (q r)] [p (q r)] e) {[(p q) (r p )] (q r )} p
f) [ p (q r)] [ (p q) r] g) (r q) ( p q) h) [(p q ) q] p q
i) [p (q r)] (p r ) p q j) (p q ) ( q p ) (q r)
6/ Cho các lượng từ và ( , {,} ). Xét chân trị của A và viết A tùy theo dạng cụ thể của và :
a) A = “ x R, | x | = x3 “ b) A = “ x Q, x2 2x > 2 “ c) A = “ x R, n N, 2n x < 2n + 1 “
d) A = “ x R, y R, (x2 = y2) (x = y) “ e) A = “ x Q, y R, (x2 + 2x 15)y = 0 “
f) A = “ x R, y Q, x2 + 4x y2+ 7 “ g) A = “ x R, k Z, (x y)2 2 2 “
7/ Viết dạng phủ định của A và xét chân trị A( xét trực tiếp A hay xét gián tiếp A ):
a) A = “n N, 4|n2 4|n“ b) A = “x R, sinx + 2x =1“ c) A = “x R,y R, 2x + 3siny > 0“
d) A = “ x R, y N, (x2 y2) (x y) “ e) A = “ x R, y Q, 2y + 2 y sinx + 3 “
f) A = “ x R, y Q, t Z, x y2 + 2t “ g) A = “ x Q, y R, t N, x3 3y 5t “
8/ Chứng minh qui nạp theo số nguyên n :
a) 13 + 23 + … + n3 = 4 1n2(n + 1)2 n 1 b) 1.1! + 2.2! + … + n.n! = (n + 1)! 1 n 1
c) 1.2.3 + 2.3.4 + … + n(n + 1)(n + 2) = 4 1n(n + 1)(n + 2)(n + 3) n 1 d) 2n < n! n 4
e) n2 < 2n n 5 ( để ý (n + 1)2 < 2n2 n 3 ) f) n3 < 2n n 10 ( để ý (n + 1)3 < 2n3 n 4 )
g) 2 1n + 1 1 1 + 2 1 + 3 1 + … + ( 2n ) 1 (n + 1) n 0 n
h) 8 | ( 3n + 7n 2 ) n 0 i) 4 | ( 6.7n 2.3n ) n 0 j) 3n + 1 | ( 3 2 1 ) n 0
k) Cho a R \ { 0 } và ( a + a 1 ) là số nguyên. Chứng minh ( an + a n ) là số nguyên n 1.
l) Cho dãy số Fibonacci a0 = 0,a1 = 1 và an + 2 = an + 1 + an n 0. Chứng minh rằng a 1 n = (
5 ) (n n) n 0 với và là 2 nghiệm thực của phương trình x2 x 1 = 0 thỏa > .
9/ Giải thích sự đúng đắn của các sự suy luận dưới đây (p, q, r, s, t và u là các biến mệnh đề) :
a) [p (p q) (s r) (r q )] (s t) b) [( p q) ( p r) ( r s)] ( q s)
c) { s [ ( p q) r] u [ r (s t)] (u t )] } p d) [(p q) r q ] p r
e) {[p (q r)] (t q) s (p s)} ( r t ) f) (p r q ) [(p r) q]
g) {[p (q r)] ( q p ) p} r h) {[(p q) r] (r s) s } (p q )
i) {(p q) (r s) [(s q) (p t)] (t p )} ( p r ) j) [p (p q) (r q )] r
k) {(p q) (r s) [(s q) t] t } ( p r ) l) [(p q) ( r q ) r ] p
m) {[p (r q)] p q [r (s t)] s } t n) [(p q) (p r) r ] q
10/ Chỉ ra sự sai lầm của các sự suy luận dưới đây (p, q, r và s là các biến mệnh đề):
a) [(p q) r] [p (q r)] b) [(p q) r] [p (q r)] c) {[p ( r q )] p q } 1
d) {[(p q) (q r)] [(p (q r)]} O e) {[ p {(q r) s}] [s ( r p)]} 1
f) [( r q) (s p )] q g) [(p (q r)] (p r) h) [(p q) r] [(p r) (q r)]
i) [( p q) q] p j) [(p q) p ] q k) [(p q) (q r) ( s q) (r s )] s
l) {(p r) p [p (q r )] ( s q )} s m) {[(p r) q] (q p) } (p q)
n) [(p q r) p (q r) ] {[p (q r)] p q r }
11/ Cho các vị từ p(x) và q(x) theo biến x A. Chứng minh
a) [ x A, p(x) q(x) ] [ ( x A, p(x)) ( x A, q(x)) ]
b) [ x A, p(x) q(x) ] [ ( x A, p(x)) ( x A, q(x)) ]
c) [ x A, p(x) q(x) ] [ ( x A, p(x)) ( x A: q(x)) ]
d) [ ( x A, p(x)) ( x A, q(x)) ] [ x A, p(x) q(x) ]
Cho ví dụ để thấy chiều đảo của c) và d) không đúng.
12/ Cho các vị từ p(x) và q(x) theo biến x A. Giải thích sự đúng đắn của các sự suy luận dưới đây :
a) {[ x A, p(x) (q(x) r(x))] [ x A, p(x) s(x) ]} [ x A, r(x) s(x) ]
b) {[ x A, p(x) q(x) ] [ x A, p(x) ] [ x A, q(x) r(x) ] [ x A, s(x) r(x) ]}
[ x A, s(x) ]
CHƯƠNG 2 : TẬP HỢP VÀ ÁNH XẠ
1/ Liệt kê các tập hợp sau đây :
A = {1 + (1)n / n N} B = {n + n 1 / n N} C = {x = (m/n) / m, n Z, n 0, m2 < 2 và 6n > n2 7}
D = { 2sin(n/6) + 5 / n Z } E = { x = (m/n) / m, n Z, 17 < n 80 và 2 1 < x < 1 }
F = { x Z / (x2 + 3x 10)(x + 4) 1 0 } G = { x Q / x4 256 và x = 3 cosx 2 sin3x }
2/ Cho A,B R. Viết A , B , A B, A B, A \ B, B \ A thành phần hội của các khoảng rời nhau trong R
a) A = (9, 3) [1,2] [4,5) (7,11] (13,+ ] B = ( ,7] [4,2) (0,3) (6,8] [10,15]
b) A = ( , 4) [4, 7] { 1, 2, 8, 10 } B = (5, 1] [6, 9) { 6, 3, 5, 10 }
3/ Cho A, B, C, D E. Hãy rút gọn các biểu thức sau đây :
a) ( A \ B ) ( B \ A ) ( A B ) b) ( A B ) \ [ ( A \ B ) ( A B ) ] c) A B ( A B C )
d) ( A B ) ( A B C D ) ( A B ) e) A ( A B ) ( A B C ) ( A B C D )
4/ Cho A,B,D E. Chứng minh
a) D \ ( A B ) = ( D \ A ) ( D \ B ) b) D \ ( A B ) = ( D \ A ) ( D \ B )
c) ( A B ) \ D = ( A \ D ) ( B \ D ) d) ( A B ) \ D = ( A \ D ) ( B \ D )
e) ( A \ B ) \ D = A \ ( B D ) = ( A \ D ) \ ( B \ D )
5/ Cho A, B, H, K E. Chứng minh
a) [ ( A H ) ( B K ) ] [ ( A B ) ( H K ) ]
b) [ (A B ) \ ( H K ) ] [ ( A \ H ) ( B \ K ) ] [ ( A B ) \ ( H K ) ]
c) [ ( A B ) \ H ] [ A ( B \ H )] d) [ (A B ) \ ( A H ) ] ( B \ H )
Cho các ví dụ để thấy trường hợp không có dấu đẳng thức xảy ra trong a), b), c) và d) .
6/ Cho A = { 0, 1, a }, B = { a, 2 } và C = { 2, b }.
a) Liệt kê các tập hợp A2, A x B, C x A, B x C và C x B.
b) Liệt kê các tập hợp B3, A x B2, C x A x C, A x B x C và C2 x B.
7/ Cho A, B E và H, K F. Chứng minh
a) A x ( H \ K ) = ( A x H ) \ ( A x K ) b) [ ( A x H ) \ ( B x K ) ] = [ ( A \ B ) x H ] [ A x ( H \ K ) ]
c) ( A x H ) ( B x K ) = ( A B ) x ( H K ) d) [ ( A x H ) ( B x K ) ] [ ( A B ) x ( H K ) ]
e) [ ( A \ B ) x ( H \ K )] [ ( A x H ) \ ( B x K ) ]
Cho các ví dụ để thấy trường hợp không có dấu đẳng thức xảy ra trong d) và e).
8/ Các qui tắc f : X Y sau có phải là ánh xạ không ? Tại sao ?
a) X = (2, 1], Y = R, f(x) = x(x2 + 2x 3) 1 x X b) X = R, Y = (6, + ), f(x) = ex + 9e x x X
c) X = Y = R, f(x) = ln| sinx | x X d) X = [1, + ), Y = R, f(x) = y sao cho y2 2y = x x X
e) X = [1, 3],Y = R\{0}, f(x) = 3x2 9x + 5 x X f) X = Q,Y = Z, f(m/n) = m2 + 3n mn (m/n) X
9/ Xét tính đơn ánh và toàn ánh của các ánh xạ f : X Y sau :
a) X = Y = R, f(x) = x(x2 + 1) 1 x X b) X = [2, + ), Y = (20, + ), f(x) = x2 + 6x 3 x X
c) X = Y = R, f(x) = (x 1)(x + 3) (x 4) x X d) X = R\{0}, Y = R, f(x) = (2x 3)x 1 x X
e) X = R, Y = [2, 2], f(x) = sinx + 3 cosx x X f) X = Y = R, f(x) = 3cos2x 7x + 8 x X
10/ Xác định u = gof, v = fog (nếu có) và w = hogof khi f : X Y, g : Z T và h : U V trong đó
a) X = Y = Z = T = U = V = R, f(x) = 2x + 1, g(x) = x2 + x 3 và h(x) = x3 + 4cosx
b) X = T = U = (0,+ ), Y = Z = R, V = [1, + ), f(x) = 3lnx 2, g(x) = esinx và h(x) = 5x4 x2 + 1
c) X = V = R,Y = Z = R\{1},T = U = R\{3}, f(x) = x2 4x + 6, g(x) = (3x + 2)(1 x) 1 và h(x) = ln| x + 3|
11/ Tìm f(A), f(B), f(C), f(D), f(E), f(R), f 1(G), f 1(H), f 1(K), f 1(L), f 1(M) và f 1(N) cho các ánh xạ sau
a) f : R R với f(x) = x 5 (nếu x 1) và f(x) = 2x + 1 (nếu x > 1) trong đó
A = { 1, 0, 1, 2, 3 }, B = [1,3], C = (1,2), D = ( ,0] và E = (3,+ ), G = { 7, 5, 3, 1, 2, 5, 7, 9 },
H = [7, 5], K = (5, 5), L = [7, + ), M = [1, 9) và N = (3, 2].
b) f : R R với f(x) = x + 7 (nếu x 0), f(x) = 5 2x (nếu 0 < x < 3) và f(x) = x 1 (nếu x 3)
trong đó A = { 2, 1, 0, 1, 2, 4, 5 }, B = [2, 1], C = (2, 4), D = (1, 5], E = [0, + ),
G = { 5, 2, 1, 0, 4, 5, 7, 10, 11 }, H = [5, 1], K = ( , 0], L = [2, 4), M = (5, 10] và N = (7, 11).
12/ Chứng minh các ánh xạ dưới đây là song ánh và viết ánh xạ ngược của chúng :
a) f : R (1, 1), f(x) = x(1 + | x |) 1 b) g : R R, g(x) = ex 3e x + 1
c) h : [1, 2) [5, 7), h(x) = 3x + 2x 1 d) p : R (2, 3), p(x) = (9 2ex) (ex + 3) 1
e) q : R\{1} R\{3}, q(x) = (5 3x) (x 1) 1 f) r : (0, 3] (2, 4 1.17], r(x) = (x + 1) + (x + 1) 1
g) Tìm các ánh xạ u,v,w thỏa p 1 1 ou = g, vof = g và f owop = g.
CHƯƠNG 3: PHƯƠNG PHÁP ĐẾM
1/ Cho các tập hợp hữu hạn A, B, C E.
Chứng minh | A B C | = | A | + | B | + | C | ( | A B | + | B C | + | C A | ) + | A B C |
2/ Cho E = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {2,4,5,7,9},B = {2,5,9}, C = {1, 3, 8} và D = {0, 2, 4, 5, 7, 8, 9}.
a) Có bao nhiêu tập hợp X E thỏa X = A ?
b) Có bao nhiêu tập hợp Y, Z, T, W E thỏa A Y = B, A Z = D, (A \ T) = B và (W \ A) = C ?
3/ Có bao nhiêu số nguyên tự nhiên chẵn ( hoặc dãy số với chữ số cuối cùng chẵn ) gồm 6 chữ số khác
nhau mà trong đó có chữ số 0 ?
4/ Cho S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Có bao nhiêu tập A S thỏa
a) | A | = 5 b) | A | = 5 và minA = 3 c) | A | = 5 và minA 3 d) | A | = 5 và min A 4
5/ Cho S = {1, 2,…, n}. Có bao nhiêu tập A S sao cho A có ít nhất một số nguyên chẵn? ( xét n chẵn, lẻ )
6/ Tìm n 7 biết rằng chỉ có một phần tư số tập con gồm 5 phần tử của S = { 1, 2, … , n } có chứa số 7.
7/ Cho S = {1, 2, 3, … , 14, 15}. Có bao nhiêu tập A S mà
a) A chỉ có toàn số lẻ b) A có 3 số lẻ c) | A | = 8 và A có 3 số lẻ d) A có 3 số lẻ và ít nhất 5 số chẵn
8/ Có bao nhiêu cách chia n sinh viên thành 2 đội ( n 2 ) mà trong đó
a) một đội học Anh Văn và một đội học Pháp văn ?
b) cả hai đội cùng đi làm công tác xã hội như nhau ? ( xét n chẵn, lẻ )
9/ Từ 10 nam và 10 nữ, có bao nhiêu cách chọn ra một đội gồm 12 người thỏa
a) chọn tùy ý b) đội có 6 nam c) đội có ít nhất 8 nam d) đội có nam ít hơn nữ e) đội có số nam chẵn
10/ Có bao nhiêu byte khác nhau chứa
a) 3 bit 1 b) ít nhất 4 bit 1 c) không quá 5 bit 1 d) ít nhất 3 bit 0 và 3 bit 1
11/ Có bao nhiêu cách chia 12 bút khác nhau cho 4 đứa trẻ nếu
a) mỗi đứa được 3 bút b) hai đứa lớn mỗi đứa 4 bút và hai đứa nhỏ mỗi đứa 2 bút
12/ Tìm hệ số của đơn thức
a) xy2z3t khi khai triển (x + 2y z + 4t 5u)7 b) x3y9z4t3 khi khai triển ( 2x y3 3z2 + 4t3 )9
13/ Xét tất cả các tam giác tạo từ 3 đỉnh khác nhau của một đa giác đều có n cạnh ( n 4 ) .
a) Có tất cả bao nhiêu tam giác như vậy ? b) Có bao nhiêu tam giác có chung 2 cạnh với đa giác trên?
c) Có bao nhiêu tam giác có chung đúng 1 cạnh với đa giác trên ?
d) Có bao nhiêu tam giác không có chung cạnh nào với đa giác trên ?
14/ Có bao nhiêu cách xếp a) 5 nam và 5 nữ xen kẽ nhau thành một hàng dọc?
b) 6 nam và 4 nữ thành một hàng dọc sao cho 6 nam đứng gần nhau?
c) 6 nam và 4 nữ thành một hàng dọc sao cho 4 nữ đứng gần nhau?
d) 6 nam và 4 nữ thành một hàng dọc sao cho 6 nam đứng gần nhau và 4 nữ đứng gần nhau?
e) 6 nam và 4 nữ thành một hàng dọc sao cho 6 nam đứng gần nhau hay 4 nữ đứng gần nhau?
f) 6 bác sĩ, 7 kỹ sư và 8 luật sư thành một hàng ngang sao cho các đồng nghiệp đứng gần nhau?
15/ Có bao nhiêu cách xếp 5 cặp vợ chồng vào một bàn tròn có 10 ghế được đánh số thứ tự nếu
a) xếp tùy ý ? b) những người nam ngồi gần nhau c) vợ chồng ngồi gần nhau
16/ Có bao nhiêu cách treo 3 áo đỏ,4 áo trắng và 5 áo xanh thành một hàng dọc (các áo khác nhau) nếu
a) treo tùy ý b) các áo cùng màu treo gần nhau c) các áo màu trắng treo gần nhau
17/ Làm lại bài 16 nhưng với giả thiết là các áo cùng màu được xem là giống nhau.
18/ Có bao nhiêu cách chọn 20 tờ giấy bạc từ các loại tiền 1 đồng, 2 đồng, 5 đồng, 10 đồng và 20 đồng ?
Nếu yêu cầu thêm có ít nhất 7 tờ 5 đồng và không quá 8 tờ 20 đồng thì có bao nhiêu cách chọn ?
19/ Tìm số nghiệm nguyên của phương trình x + y + z + t = 32 ( hay bất phương trình x + y + z + t 32 ) nếu
a) x, y, z, t 0 b) x 2, y 3, z 1, t > 5 c) x > 1, y 4, z > 4, t 3 d) x, y, z > 0 và 1 t < 25
20/ Có bao nhiêu cách chia 18 viên kẹo giống nhau cho 5 đứa trẻ nếu
a) chia tùy ý b) đứa nào cũng được kẹo c) đứa lớn nhất có 6 viên
d) đứa nhỏ nhất được ít nhất 4 viên e) đứa lớn nhất nhận không quá 7 viên
21/ Khi khai triển (x + y + z + t)10, ta được bao nhiêu đơn thức khác nhau ?
Trong số đó có bao nhiêu đơn thức xmynzu tv (không kể hệ số phía trước) thỏa m 2, n 3 và v 1 ?
22/ Có bao nhiêu cách chia 15 viên kẹo chanh (giống nhau) và 10 viên kẹo dừa (giống nhau) cho 6 đứa
trẻ sao cho đứa nào cũng có cả hai thứ kẹo ?
23/ Có bao nhiêu cách mua 20 hộp sơn với đúng 7 màu trong số 10 màu mà cửa hàng có ?
24/ Xét chuỗi ký tự bao gồm phần mẫu tự đứng trước và phần chữ số đứng sau. Phần mẫu tự có 8 mẫu tự
, , , , , , , , xếp tùy ý ( , , là 3 mẫu tự khác nhau lấy tùy ý từ A, E, H, P, Y ). Phần chữ số
là 6 chữ số xyzuvw( x, y, z, u, v, w được lấy tùy ý từ 0, 1, 2, … , 8, 9 ) thỏa 7 x + y + z + u + v + w 9
Hỏi có tất cả bao nhiêu chuỗi ký tự như vậy ?
25/ Cho A S = { 1, 2, … , 25 } thỏa | A | 14. Chứng minh rằng có a, b A thỏa a b và a + b = 26
26/ Cho A S = { 1, 2, … , 100 } thỏa | A | 11. Chứng minh rằng có x, y A thỏa 0 < | x y | < 1.
Tổng quát hóa kết quả trên theo 2 hướng khác nhau: theo | S | hoặc theo ( n x và n y ).
27/ Lấy 10 điểm khác nhau tùy ý trên một tam giác đều có cạnh bằng 3cm.
Chứng minh rằng trong số đó có ít nhất 2 điểm có khoảng cách không quá 1cm.
28/ Từ thứ hai đến thứ bảy của mỗi tuần có 12 buổi (sáng và chiều). Có 782 sinh viên đăng ký học đàn
theo các buổi nói trên trong tuần: mỗi sinh viên có thể chọn từ 2 đến 4 buổi.
Chứng minh rằng có ít nhất 2 sinh viên có lịch học trong tuần hoàn toàn giống nhau.
29/ Xếp các con số 1, 2, … , 25 một cách tùy ý trên một đường tròn. Chứng minh rằng có 3 số gần nhau
trên đường tròn có tổng 41 và có 3 số gần nhau trên đường tròn có tổng 37.
30/ Cho A S = { 1, 2, … , 14 } thỏa | A | 6.
Chứng minh có H,K A ( mà H K ) thỏa | H | 5, | K | 5 và h = k . h H k K
CHƯƠNG 4 : HỆ THỨC ĐỆ QUI
1/ Giải các hệ thức đệ qui tuyến tính thuần nhất sau đây :
a) a0 = 2 và an + 1 = 3an n 0 b) a1 = 5 và an = 8an 1 n 2 c) a2 = 28, a3 = 8 và an = 4an 2 n 4
d) a0 = 1, a1 = 0 và an + 1 = 5an 6an 1 n 1 e) a1 = 6, a2 = 8 và an + 2 = 4an + 1 4an n 1
2/ Giải các hệ thức đệ qui tuyến tính không thuần nhất sau đây :
a) a0 = 3 và an = an 1 + 9 n 1 b) a1 = 13 và an + 2 = 2an + 1 + 5.3n + 1 n 0
c) a2 = 61 và an + 1 = 3an + 4n 6 n 2 d) a0 = 7 và an + 1 = 4an 2(4)n + 1(n 2) n 0
e) a3 = 128 và an + 2 = 5an + 1 12 n 2
3/ Giải các hệ thức đệ qui tuyến tính không thuần nhất sau đây :
a) a0 = 1, a1 = 2 và an + 2 = 5an + 1 6an + 4 n 0 b) a1 = 4, a2 = 19 và an + 1 = 5an 4an 1 + 3 n 2
c) a2 = 5, a3 = 26 và an = 2an 1 an 2 10 n 4
d) a0 = 3, a1 = 5 và an = 2an 1 + 3an 2 + 8(1) n + 1 n 2
e) a1 = 13, a2 = 50 và an + 2 = 7an + 1 10an + (40n 1) 3n n 1
f) a2 = 28, a3 = 149 và an + 1 = 2an an 1 12n2 24n + 4 n 3
4/ Tính các tổng số sau theo n nguyên :
a) Sn = 13 + 23 + … + n3 (n 1) b) Sn = 14 + 24 + … + n4 (n 1) c) Sn = 14 + 24 + … + (1)nn4 (n 1) n n n d) S k k k n = (k 1)(k 2)2 (n 0) e) Sn =
(2k 1)( 3) (n 0) f) Sn = 3 2 (k 2k 4k)( 1) (n 1) k 0 k 0 k 1
5/ Vẽ n đường thẳng trong mặt phẳng cắt nhau từng đôi một nhưng trong đó không có 3 đường thẳng nào
đồng qui (n 1). Các đường thẳng này chia mặt phẳng thành bao nhiêu miền rời nhau từng đôi một ?
6/ Giả sử dân số thế giới năm 2000 là 7 tỉ người và tốc độ tăng dân số thế giới là 3% mỗi năm.
Tính dân số thế giới vào năm n (n 2000).
7/ Có bao nhiêu chuỗi ký tự gồm n ký tự (n ký tự này được lấy tùy ý từ các ký tự a,b,c) sao cho trong chuỗi
ký tự không có 2 ký tự a đứng gần nhau (n 1) ?
8/ Có bao nhiêu chuỗi ký tự gồm n ký tự (n ký tự này được lấy tùy ý từ các ký tự 1, 2) sao cho trong chuỗi
ký tự ít nhất 2 ký tự 1 đứng gần nhau (n 1) ?
9/ Cho a0 = , a1 = và an + 2 = an + 1 + an n 0. Chứng minh rằng an = fn + fn 1 n 1 trong đó
fm là số hạng thứ m (m 0) của dãy số Fibonacci ( f0 = 0, f1 = 1 và fn + 2 = fn + 1 + fn n 0 ).
10/ Tính an và bn biết rằng a0 = 1, b0 = 2, an + 1 = 3an + 2bn và bn + 1 = an + 2bn n 0.
( Hướng dẫn: Tìm , thỏa an + 1 + bn + 1 = (an + bn) và tính un = an + bn n 0 )
CHƯƠNG 5 : QUAN HỆ HAI NGÔI
1/ Đặt Ik = {0, 1, … , k} k N. Hãy viết tập hợp và xét các tính chất của quan hệ hai ngôi trên S nếu
a) S = I2, x, y S : x y 0 y x 1 b) S = I2, x, y S : x y x2 + y2 2
c) S = I2, x, y S : x y 3x + y 5 d) S = I3, x, y S : x y x + y 4
e) S = I4, x, y S : x y ( x = y hay x + 2y = 4 ) f) S = I4, x, y S : x y (x + 2) | y
2/ Xét các tính chất của quan hệ hai ngôi trên S nếu
a) S = Z, x, y S : x y x | y2 b) S = Z, x, y S : x y y | x2
c) S = Q, x, y S : x y x = | y | d) S = Q x Q, (x,u), (y,v) S : (x,u) (y,v) x y
e) S = R, x, y S : x y x y f) S = R, x, y S : x y x = 2y ( để ý 2t > t t R )
3/ Kiểm chứng là một quan hệ tương đương trên S rồi viết các lớp tương đương và tập thương tương ứng:
a) S = { Huế, Paris, Moscou, Rome, Tokyo, Kyoto, Milan, Vinh, Lyon, ĐàLạt, Kobe, Sàigòn, Cairo,
Nice, Bonn, Turin, Berlin }, x, y S : x y x và y là 2 thành phố thuộc cùng một quốc gia
b) S = { 5, 4, 3, 2, 1, 0, 1, 2 }, x, y S : x y x2 + 5x = y2 + 5y
c) S = { 4, 2, 3 , 1, 0, 1, 3 , 2, 3 }, x, y S : x y x3 + 3y = y3 + 3x
d) S = {1, 2, 3, 4, 6, 7, 21, 24, 25, 35, 42, 48}, x,y S : x y k Z : x = 2ky (k phụ thuộc x và y)
e) S = { 11/6, , 4/5, /4, /5, /7, 0, /6, /3, 5/6, , 5/4, 3 }
x, y S : x y sinx = cos(y + 2 1.7)
f) S = (E) với E ={ 1, 2, 3 }, X, Y S : X Y X A = Y A trong đó A = {1, 2}
4/ Kiểm chứng là một quan hệ tương đương trên S = R và xác định lớp tương đương [ a ] của a R
tương ứng ( biện luận theo tham số thực a )
a) x, y S : x y x2 + 3x = y2 + 3y
b) x, y S : x y x2 y2 = 2(x y)
c) x, y S : x y x3 12y = y3 12x ( xét riêng hai trường hợp + và )
d) x, y S : x y x2y + 7x = xy2 + 7y
e) x, y S : x y 4x + xy2 = x2y + 4y
f) x, y S : x y 2cos2x sin(xy)cos2y = 2cos2y sin(xy)cos2x
5/ Cho S = { a, b, c, d, e, f }.
a) Viết tập hợp nếu là quan hệ tương đương trên S có 3 lớp tương đương là {a, d, f},{c, e} và {b}.
b) Trên S có bao nhiêu quan hệ tương đương chia S thành 3 lớp tương đương có số phần tử của các lớp
lần lượt là 3, 2, 1 (tương tự như quan hệ tương đương ) ?
c) Trên S có bao nhiêu quan hệ tương đương chia S thành 3 lớp tương đương ?
6/ Kiểm chứng là một quan hệ thứ tự trên S. là thứ tự toàn phần hay bán phần? Tại sao ?
Vẽ sơ đồ Hasse cho (S,) và tìm min,max và các phần tử tối tiểu và tối đại (nếu có):
a) S = { 2, 3, … , 11, 12 }, x, y S : x y [ (x lẻ và y chẵn) hay (x y chẵn và x y) ]
b) S = { 2, 4, 6, 8, 10, 12, 16, 20 }, x, y S : x y x | y (quan hệ ước số)
c) S = { 2, 3, 4, 6, 8, 16, 24, 32, 48, 96 }, x, y S : x y x | y
d) S = { 0, 5, 10, 15, 20, 25, 30,40, 50 }, x, y S : x y x y (quan hệ bội số)
e) S = { 2, 3, 4, 5, 7, 8, 24, 48, 96 }, x, y S : x y x y
f) S = { 96, 768, 6, 48, 384, 3, 24 }, x, y S : x y k N: y = 2kx ( k phụ thuộc x và y )
7/ Cho S = { a = 2m3n/ m, n N , m 3 và n 2 } với các quan hệ thứ tự | và .
a) Vẽ sơ đồ Hasse và tìm min,max cho (S, | ) và (S, ) .
b) Đặt T = S \ { 1, 2, 72 }. Vẽ sơ đồ Hasse rồi tìm các phần tử tối tiểu và tối đại của (T, | ) và (T, ).
8/ Cho S = { a, b, c } với quan hệ thứ tự .
Giả sử a là một phần tử tối tiểu và c là một phần tử tối đại của (S, ).
a) Vẽ tất cả các trường hợp khác nhau có thể xảy ra cho sơ đồ Hasse của (S, ).
b) Yêu cầu như a) nhưng có thêm điều kiện “ b cũng là một phần tử tối đại của (S, ) “ .
9/ a) Giải thích thứ tự sắp xếp của các từ sau trong từ điển tiếng Anh :
individual, indistinct, real, indite, confirmation, individualism và red .
b) Giải thích thứ tự sắp xếp của các dãy số sau theo thứ tự từ điển :
852604, 74596, 935, 7489, 85297440, 85297311 và 7489231.
10/ Vẽ sơ đồ Hasse cho (S, ) rồi toàn phần hóa (sắp xếp topo) các thứ tự bán phần sau:
a) S = { a, b, c, d, e, f, g, h, i } với d a, b e, g e, h f, i e và h d.
b) S = { 1, 2, 4, 5, 12, 15, 20 } với là quan hệ | (ước số) .
c) S = { 2, 3, 6, 7, 8, 9, 12, 16 } với là quan hệ (bội số) .
d) S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } với là quan hệ | (ước số) . CHƯƠNG 6 : HÀM BOOL
1/ Tìm dạng nối rời chính tắc cho các hàm Bool sau đây :
a) f(x, y, z) = x y x(y z) b) f(x, y, z, t) = (xy zt)(x z) )(xz yt)(xt yz)
c) f(x, y, z) = ( x yz)( y xz)( z xy) d) f(x, y, z, t) = yz zt xt (xy y z x t )xyt
e) f(x, y, z, t) = xyz y zt [x t (x y) (z t)] [(x z) (y t)] [(x t)(y z)]
2/ Tìm các công thức đa thức tối tiểu cho các hàm Bool f có 4 biến rồi viết dạng nối rời chính tắc cho f
và f biết rằng S = Kar(f) hay S = ( Phần bù của S trong bảng mã của B4 ) như sau :
a) S = { (1,1), (1,3), (2,2), ( 2,4), (3,1), (3,3), (4,2), (4,4) } b) S = { (1,2), (1,3), (2,1), (2,3), (3,4), (4,3) }
c) S = { (1,2), (1,3), (2,1), (3,1), (4,2), (4,3) } d) S = { (1,1), (1,4), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1) }
e) S = { (2,3), (2,4), (3,1), (3,2), (3,3), (4,1), (4,4) } f) S = { (1,1), (2,2), (2,3), (3,1), (4,1) }
g) S = { (2,2), (2,3), (2,4), (3,4), ( 4,1), (4,2) } h) S = { (1,3), (2,1), (2,2), (3,4) }
3/ Ký hiệu x’ = x , y’ = y , z’ = z và t’ = t .
Tìm các công thức đa thức tối tiểu cho các hàm Bool f có 4 biến rồi viết dạng nối rời chính tắc cho f
và f biết rằng f có dạng đa thức như sau :
a) f(x, y, z, t) = yt’ xyz’ x’yz xy’z t’ x’y’z’t’
b) f(x, y, z, t) = xzt’ y’z’t’ xyt x’yz x’y’z’t’ x’yz’t
c) f(x, y, z, t) = x’y’z’t’ yzt xy’z xyz’t yzt’ x’y’t
d) f(x, y, z, t) = x’yz xy’ xz’t’ x’yt’ xyzt’ y’zt
e) f(x, y, z, t) = xy’zt’ yz’t x’y’zt’ yz’t’ x’yz xy’z’t’
f) f(x, y, z, t) = x’z’t’ xyzt xy’z’t’ xy’t x’zt’ x’yz’t
g) f(x, y, z, t) = xyzt x’y’ xz’t yz’t’
h) f(x, y, z, t) = z’t’ xyt’ x’yz’ x’y’zt’ xy’z’t y’zt
4/ Vẽ mạng các cổng tổng hợp hàm Bool f trong bài 2 và 3 (dùng một công thức đa thức tối tiểu của nó)
5/ a) Có bao nhiêu hàm Bool 6 biến lấy giá trị 1 tại các vector Bool có đúng 2 biến là 1 ( và lấy giá trị
tùy ý tại các vector Bool khác ) ?
b) Có bao nhiêu hàm Bool 6 biến lấy giá trị 1 tại các vector Bool có ít nhất 2 biến là 1( và lấy giá trị
tùy ý tại các vector Bool khác ) ?
c) Có bao nhiêu hàm Bool 6 biến không phụ thuộc biến thứ nhất ?
d) Có bao nhiêu hàm Bool 6 biến không phụ thuộc 3 biến đầu tiên ?
CHƯƠNG 7: ĐẠI CƯƠNG VỀ ĐỒ THỊ
1/ Vẽ phác họa các đồ thị vô hướng liên thông (đơn đồ thị, đa đồ thị không có cạnh song song, đa đồ thị
không có vòng, đa đồ thị có cả vòng và cạnh song song) có bậc của các đỉnh lần lượt là
a) 1, 2, 2, 3 (chỉ có 3 trường hợp đầu) b) 1, 1, 1, 3, 3, 3 (chỉ có 3 trường hợp đầu) c) 1, 2, 3, 3, 4, 5 d) 2, 2, 2, 4, 4, 4
2/ Cho đồ thị vô hướng G = (V, E). Tìm | V | nếu
a) | E | = 12 và mọi đỉnh có bậc 2 b) | E | = 21, G có 3 đỉnh bậc 4 và các đỉnh khác bậc 5
c) | E | = 6 và mọi đỉnh có cùng bậc d) | E | = 16, G có 3 đỉnh bậc 5 và các đỉnh khác có bậc 3 và 4
3/ Cho đồ thị vô hướng G = (V, E).
a) | V | = 9 và mọi đỉnh có bậc 5 được không? b) | V | = 6 và các bậc là 6 số nguyên liên tiếp được không?
c) Giả sử mọi đỉnh có bậc r lẻ. Chứng minh r | | E | d) Tìm max| V | nếu | E | =19 và mọi đỉnh có bậc 3
4/ Cho G = (V, E). Viết ma trận kề MG và vẽ phác họa G. Giải thích tại sao G liên thông? G là đơn hay
đa đồ thị? G có chu trình hay đường Euler không? Tại sao? Nếu có thì xác định chúng theo thuật toán :
a) E = { AB(3), AF, AJ(3), BC(2), BK, CD(2), CH(2), CI, DF, DJ, FI(2), FK(2), HH(4), HJ,II(2), JK(3) }
V = { A, B, C, D, F, H, I, J, K }
b) E = { AB,AH,BC,BH,BJ,CD,CJ,CK,DF,DK,DL,FH,HI,IJ,JK,KL } và V = { A,B,C,D,F,H,I,J,K,L }
c) E = { AB, AC, AF, AH, BC, BH, CD, CH, DF(2), DI, FH } và V = { A, B, C, D, F, H, I }
d) E = { AA(2),AB,AF,BC,BD,BF,CF,CH(2),DH,DI,DJ,FI,HI,IJ,JJ(2) } và V = { A, B, C, D, F, H, I, J }
e) E = { AB(2), AD(3), BB(4), BF,BH, CC(2) ,CD,CH, DD(2 ), FF(2) ,FH } và V = { A, B, C, D, F, H }
f) E = { AB, AC, AD, AF, BD, CD, CH, CI, DF, DH, DI, FH, FI, HI } và V = { A, B, C, D, F, H, I }
g) E = { AB, AC(2), AF(2), AH(2), BF, BH(2), CD, CH, DF, FH } và V = { A, B, C, D, F, H }
Lưu ý: AB(3) có nghĩa là có 3 cạnh nối A với B .
5/ Các đồ thị vô hướng G. H và L dưới đây có chu trình Euler hay đường Euler không ? Tại sao?
Nếu có thì xác định chúng theo thuật toán :
6/ Cho 8 cặp đồ thị vô hướng từ (G và G’) cho đến ( T và T’) như dưới đây. Hãy cho biết cặp đồ thị nào
bao gồm hai đồ thị đẳng cấu với nhau ( hoặc không đẳng cấu với nhau) và giải thích tại sao ?
HƯỚNG DẪN BÀI TẬP TOÁN RỜI RẠC CHƯƠNG 1: CƠ SỞ LOGIC
1/ a) p(x) đúng x [2,4] ; p(x) sai x (,2) (4,+) ; q(x) đúng x (,1) (2,+) ;
q(x) sai x [1,2] . Từ đó suy ra chân trị của các vị từ tùy theo giá trị của biến x.
b) Tương tự a). Để ý (x2 3x + 10) > 0 x R.
2/ b) Ta có thể viết A = “ (3a + 1) 0 và (2a 5) (3a + 1) 1 > 0 “ rồi suy ra A .
c) và d) Để ý miền xác định của biểu thức rồi thể hiện A tương tự như trong b). Từ đó suy ra A .
e), f), g), h) và i) A nêu ra các tỉ lệ và dùng một trong các dấu <, >, =, , . Từ đó suy ra A .
j), k), l), m) và n) A nêu ra các số lượng và dùng một trong các dấu <, >, =, , . Từ đó suy ra A .
o) Mệnh đề kéo theo p) Không ai muốn = mọi người không muốn q) Cả lớp = mọi người trong lớp
s) Các cầu thủ = mọi cầu thủ t) x) Các từ nối đều có nghĩa là “ và” y) Họ = mọi người trong số họ
z),) Chúng tôi = mọi người trong chúng tôi ; các anh ấy, nhóm bác sĩ, nhóm kỹ sư được hiểu tương tự
3/ a) p q b) p q c) p q r d) p q e) p q r s
4/ a) h) và j) Dùng các luật logic biến đổi tương đương vế trái thành vế phải.
i) Chiều () : dùng qui tắc suy diễn tam đoạn luận ; Chiều () : hiển nhiên
5/ a) g) Dùng các luật logic biến đổi thành 1 h), i) và j) Dùng các luật logic biến đổi thành O
a), c), f) và g) Có thể dùng các qui tắc suy diễn để chứng minh hằng đúng.
6/ a) và b) Lần lượt gán = và = ( mỗi câu xét 2 mệnh đề A1 và A2 )
c), d), e), f) và g) Lần lượt gán ( = , =), ( = , = ), ( = , = ), ( = , = )
( mỗi câu xét 4 mệnh đề A1, A2 ,A3 và A4 ).
g) Để ý a R, ! a’ Z thỏa a’ a < a’ + 1. Ký hiệu a’ = [ a ] và gọi a’ là phần nguyên của a.
7/ a) x | y nghĩa là “x là ước số của y” e) Để ý y Q, 2y + 2 y 2 (Cauchy) f) A sai g) A đúng
8/ a) j) Dùng giả thiết qui nạp yếu k) và l) Dùng giả thiết qui nạp mạnh
e) và f) Giải thích bất đẳng thức phụ (dễ dàng) trước khi chứng minh bất đẳng thức chính.
g) Tự giải thích n 0, 2 1 (2n + 1) 1 + (2n + 2) 1 + (2n + 3) 1 + … + (2n + 2n ) 1 < 1 (*) và dùng
bất đẳng thức phụ (*) để chứng minh bất đẳng thức chính.
h) Để ý (3k + 1 + 7 k + 1 2) = [ 7(3k + 7 k 2 ) 4(3k + 3) ] k 0
i) Để ý n 0, 2 | (3.7 n 3) và có thể chứng minh trực tiếp (không cần qui nạp). k k 1 k 1 j) Đặt a = 3 2 và b = 1 thì ( 3 2
+ 1) = a3 + b3 = (a + b)[ (a + b)2 3ab ] và giải thích 3k + 2 | ( 3 2 + 1)
k) Ta có (a0 + a 0 ) = 2 Z và (a1 + a 1 ) Z (*) . Xét k 1 và giả sử (an + a n ) Z n = 1,…, k (**).
Để ý (ak + 1 + a k 1 ) = (ak + a k ) (a1 + a 1 ) (ak 1 + a1 k ) rồi dùng (*) và (**).
l) Thử n = 0 và n = 1. Xét k 1 và giả sử an = 1
( 5) (n n) n = 0,1,…, k (*). Để ý a 1 k + 1 = ak + ak 1 = (
5) (k + k 1 k 1 k ) để suy ra ak + 1 = 1
( 5) (k + 1 k + 1) .
9/ Dùng các qui tắc suy diễn phối hợp với các luật logic.
10/ Chọn các phản ví dụ ( bằng cách gán cho mỗi biến mệnh đề chân trị 1 hoặc 0 tùy ý ) sao cho
a), b) và f) Một vế đúng và một vế sai c) và e) Vế trái sai d) Vế trái đúng
g) n) Vế trái đúng và vế phải sai
11/ và 12/ Dùng định nghĩa của lượng từ, các qui tắc suy diễn phối hợp với các luật logic.
CHƯƠNG 2 : TẬP HỢP VÀ ÁNH XẠ
1/ C : m {0, 1} và n {1,2,3,4,5,6} D : chỉ cần chọn n {0,1,2,…,11} và tính trực tiếp các phần tử
E : n {5,6,7,8}, tìm m thỏa 2 1 < (m/n) < 1 F : xét nghiệm nguyên của (x + 5)(x 2)(x + 4) 1 0
G : | x | 4 và | x | 3 + 2 < 4
2/ Biểu diễn A và B trên trục x’Ox để xác định kết quả các phép toán tập hợp bù, giao, hội và hiệu.
3/ Rút gọn bằng các phép toán tập hợp a) A B b) B \ A c) A B C d) B e) A B C D
4/ Dùng các phép toán tập hợp biến đổi vế này thành vế kia.
5/ Dùng các phép toán tập hợp rút gọn các vế trước khi chứng minh các bao hàm thức.
7/ a),b) và c) Chứng minh “ (x,y) vế trái (x,y) vế phải “
e) và f) Chứng minh “ (x,y) vế trái (x,y) vế phải “
8/ a) Xét f(1) b) Xét f(ln3) c) Xét f(0) d) Xét f(0) e) Có a [1,3] mà f(a) = 0 f) (1/1) = (2/2) Q
9/ a) f(2) = f(1/2) và f(x) (1/2) x X b) f’(x) > 0 và f(x) = (x + 3)2 12 12 x X
c) f(1) = f(3) và f(X) = Y d) x,t X, (f(x) = f(t) x = t) và f(X) = Y \ {2}
e) f(0) = f(2) và f(x) = 2sin(x + /3) x X thỏa f(X) = Y f) f’(x) < 0 x X và f(X) = Y
12/ a) y ( 1,0 ), phương trình f(x) = y có nghiệm duy nhất trên X là x = y / (1 + y) = y / ( 1 | y | ).
y [ 0,1 ), phương trình f(x) = y có nghiệm duy nhất trên X là x = y / (1 y) = y / ( 1 | y | ).
b) y R, phương trình g(x) = y e2x + (1 y) ex 3 = 0 t2 + (1 y) t 3 = 0 với t = ex > 0
Như vậy y R, phương trình g(x) = y có nghiệm duy nhất trên R là x = ln { 2 1 [ y 1 + 2 ( y 1) 12 ] }
c) y [ 5,7) , phương trình h(x) = y 3x2 yx + 2 = 0 có nghiệm duy nhất trên [ 1,2 ) là x = x 1 1 1 = 6 ( y + 2 y 24 ) vì 2 y 24
[ 1,5 ) ( loại nghiệm x2 = 6 ( y 2 y 24 ) (0,1)).
f) Xét : ( 0,3 ] ( 1,4 ] với (x) = x + 1 x ( 0,3 ]. là song ánh và 1(x) = x 1 x ( 1,4 ].
Xét : ( 1,4 ] ( 2, 4 1.17 ] với (x) = x + x 1 x ( 1,4 ]. Ta có r = 1 1
o . Ta kiểm tra là song ánh để có r là song ánh và r = 1o .
y ( 2, 4 1.17 ], phương trình (x) = y x2 yx + 1 = 0 có nghiệm duy nhất trên ( 1,4 ] là x = x 1 1 = 2 ( y + 2 y 4 ) vì 2 y 4
( 0,15/4 ] ( loại nghiệm x2 = (1/ x1) [ 1/4,1)).
g) Giải các phương trình ánh xạ, ta có u = p 1 1 og, v = gof , w = fogop .
CHƯƠNG 3 : PHƯƠNG PHÁP ĐẾM
1/ Dùng | X Y | = | X | + | Y | | X Y | lần lượt cho
( X = A, Y = B C ), ( X = B, Y = C ) và ( X = A B, Y = A C ) .
2/ b) Để ý Y = B H với H tùy ý ( E \ A ), Z = ( D \ A ) K với K tùy ý A,
T = ( A \ B ) L với L tùy ý ( E \ A ) và W = P C với P tùy ý A .
3/ N = abcdef với b, c, d, e { 0, 1,…, 9}, f { 0, 2, 4, 6, 8 }, a, b, c, d, e, f khác nhau đôi một.
a) Trường hợp 1 (N là số nguyên dương) thì a {1, 2, …,9}: dùng nguyên lý nhân và nguyên lý cộng.
* Khi f = 0 : 9 cách chọn a, 8 cách chọn b, 7 cách chọn c, 6 cách chọn d và 5 cách chọn e.
* Khi f {2,4,6,8}: 0 {b,c,d,e} nên ta có thể giả sử b = 0 (3 trường hợp còn lại cho cùng kết quả) :
4 cách chọn f, 8 cách chọn a, 7 cách chọn c, 6 cách chọn d và 5 cách chọn e.
b) Trường hợp 2 (N là dãy số nguyên ) thì a {0,1,2, …,9}: làm tương tự như trường hợp 1.
4/ b) A = {3} A’ với | A’ | = 4 và A’ {4,5,…,10}: để ý số tập hợp A = số tập hợp A’
c) Xét minA = 3, minA = 2 hay minA = 1 : mỗi trường hợp tương tự như b) rồi dùng nguyên lý cộng
d) Cách 1 : phối hợp kết quả a) và c) ; Cách 2 : xét minA = 4, minA = 5 hay minA = 6 : tương tự như c)
5/ a) Trường hợp n = 2k chẵn (A1 = {1,3,…,(2k 1)}, A2 = {2,4,…,2k} có | A1 | = k) :
kết quả là |(A) \ (A1) | = |(A) | \ |(A1) | .
b) Trường hợp n = (2k + 1) lẻ (A1 = {1,3,…,(2k 1), (2k + 1)} có | A1 | = k + 1) : tương tự như a) .
6/ = {A S / | A | = 5} và = {A S / | A | = 5 và 7 A}. Ta có | | = 4 | | là một phương trình
theo ẩn số n 7 mà ta cần giải. Việc tính | | làm tương tự như b) của bài 4 .
7/ S1 = { 1, 3,…, 15 }, S2 = { 2, 4,…, 14} có | S1 | = 8 và | S2 | = 7 .
a) Đếm số tập A thỏa A S 1 b) A = A1 A2 với A1
S1, | A1 | = 3 và A2 S2 : nguyên lý nhân
c) Như b) thêm | A2 | = 5 : nguyên lý nhân d) Như b) thêm | A2 | = 5,6 hay 7 : nguyên lý nhân và cộng
8/ a) Chỉ cần xác định đội học Anh văn : số cách chia 1 C + 2 C + … + n 1 C = 2n 2 . n n n
b) Chỉ cần xác định đội nhỏ (có không quá 2 1n sinh viên) :
* Khi n = 2k chẵn : số cách chia 1 C + 2 C + … + k
C = 2n 1 1 + 2 1 k C . n n n n
* Khi n = (2k + 1) lẻ : số cách chia 1 C + 2 C + … + k C = 2n 1 1 n n n
9/ Dùng tổ hợp, nguyên lý nhân và nguyên lý cộng : a) 6 nam và 6 nữ b) (8 + 4) hay (9 + 3) hay (10 + 2)
c) (5 + 7) hay (4 +8) hay (3 + 9) hay (2 +10) d) (2 +10) hay (4 +8) hay (6 + 6) hay (8 +4) hay (10 + 2)
10/ Chỉ quan tâm sự xuất hiện các bit 1 : dùng tổ hợp và nguyên lý cộng
a) chọn 3 trong 8 b) có từ 4 đến 8 bit 1 c) có từ 0 đến 5 bit 1 d) có từ 3 đến 5 bit 1
11/ Xem việc chia bút lần lượt cho 4 người chính là 4 việc liên tiếp : dùng tổ hợp và nguyên lý nhân.
12/ b) Đặt x = u, y3 = v, z2 = w và t3 = h. Ta tìm hệ số của u3v3w2h trong khai triển (2u v 3w + 4h)9
13/ b) n c) n(n 4) [ mỗi cạnh của đa giác liên kết với (n 4) đỉnh không liền kề ] d) Dùng a), b) và c)
14/ Nhóm người xếp gần nhau (nhóm nam, nhóm nữ, nhóm đồng nghiệp) xem như là “một người” xếp
hàng với các người khác. Dùng phép hoán vị (đối nội và đối ngoại), nguyên lý cộng và nguyên lý nhân
a) 2.5!5! b) 6!5! c) 4!7! d) 2.4!6! e) dùng nguyên lý bù trừ phối hợp b),c) và d) f) 3!6!7!8!
15/ Ghi số thứ tự cho các ghế từ 1 đến 10 (theo chiều kim đồng hồ).
Dùng phép hoán vị (đối nội và đối ngoại), nguyên lý cộng và nguyên lý nhân.
a) Có 10 cách chia thành 2 khu : một khu cho 5 nam ngồi gần nhau, một khu cho 5 nữ ngồi gần nhau.
b) Có 2 cách chia thành 5 khu :mỗi khu gồm 2 ghế liên tiếp dành cho một cặp vợ chồng ngồi gần nhau.
16/ Tương tự bài 14. Tính chất “cùng màu” tương đồng vói tính chất “đồng nghiệp” hay “ cùng giới tính”.
17/ Dùng phép hoán vị lặp. Ý tưởng như bài 16 nhưng không có hoán vị đối nội.
18/ 21/ Dùng tổ hợp lặp, phép đổi biến và phép lấy bù để đưa về trường hợp các biến nguyên 0.
Nếu là bất phương trình thì tạo thêm một ẩn giả nguyên 0 để chuyển về dạng phương trình.
22/ Đây là 2 việc đồng thời. Dùng nguyên lý nhân, tổ hợp lặp và phép đổi biến để đưa về trường hợp các biến nguyên 0.
23/ Đây là 2 việc liên tiếp. Dùng nguyên lý nhân, tổ hợp, tổ hợp lặp và phép đổi biến để đưa về trường
hợp các biến nguyên 0.
24/ Đây là 2 việc đồng thời. Dùng nguyên lý nhân, hoán vị lặp, chỉnh hợp, tổ hợp lặp và nguyên lý cộng.
25/ Dùng nguyên lý Dirichlet. Tạo 13 ô. Đưa các số hạng của A vào các ô và mỗi ô nhận không quá 2 số
(ô 1 chỉ nhận 1 hay 25 ; ô 2 chỉ nhận 2 hay 24 ; … ; ô 12 chỉ nhận 12 hay 14 ; ô 13 chỉ nhận 13)
26/ Dùng nguyên lý Dirichlet. Tạo 10 ô. Đưa các số hạng của A vào các ô (ô 1 chỉ nhận từ 12 đến 22 1 ;
ô 2 chỉ nhận từ 22 đến 32 1 ; … ; ô 9 chỉ nhận từ 92 đến 102 1 ; ô 10 chỉ nhận 102 )
27/ Dùng nguyên lý Dirichlet. Chia tam giác đều cạnh 3 thành 9 tam giác đều nhỏ cạnh 1. Để ý rằng
hai điểm bất kỳ trong một tam giác nhỏ có khoảng cách không quá 1.
28/ Dùng nguyên lý Dirichlet. Có 3 dạng lịch học (2 buổi, 3 buổi, 4 buổi). Số lịch học có thể có < 782 .
29/ a) Xóa số 1. Khi đó 24 số còn lại trên đường tròn chia thành 8 nhóm rời nhau (mỗi nhóm gồm 3 số gần
nhau). Tổng của 8 nhóm này = (2 + 3 + … + 25) > (40 x 8).
b) Xóa số 25. Khi đó 24 số còn lại trên đường tròn chia thành 8 nhóm rời nhau (mỗi nhóm gồm 3 số
gần nhau). Tổng của 8 nhóm này = (1 + 2 + … + 24) < (38 x 8).
30/ Dùng nguyên lý Dirichlet. A có ít nhất là ( 1 C + 2 C + … + 5
C ) tập hợp con khác có 5 phần tử. 6 6 6
Tổng các số hạng trong mỗi tập con đó có giá trị nằm trong khoảng từ 0 đến (10 + 11 + … + 14) .
CHƯƠNG 4 : HỆ THỨC ĐỆ QUI
1/ a) an = 2(3)n n 0 b) an = 5(8n1) n 1 c) an = 3(2n) + 4(2)n n 2
d) an = 3(2n) 2(3n) n 0 e) an = (4 n)2n n 1
2/ a) an = 9n 3 n 0 b) an = 3n 5(2)n n 1 c) an = 7(3n) + 2(1 n) n 2
d) an = (5n n2 7)(4)n n 0 e) an = 5n + 3 n 3
3/ a) an = 2(3n) 3(2n) + 2 n 0 b) an = 2(4n) n 11 n 1 c) an = 4n + 7 5n2 n 2
d) an = (4 2n)(1)n 3n n 0 e) an = 4(2)n + (5)n + (n 1)3n n 1
f) an = 3n2 + 5n n4 4n3 2 n 2 4/ a) S 1
1 = 1, Sn + 1 = Sn + (n + 1)3 n 1 và Sn = 4 n2(n + 1)2 n 1 b) S 1
1 = 1, Sn + 1 = Sn + (n + 1)4 n 1 và Sn = 30
n(n + 1)(6n3 + 9n2 + n 1) n 1 c) S 1
1 = –1, Sn + 1 = Sn + (1)n + 1(n + 1)4 n 1 và Sn = 2
(1)n n(n3 + 2n2 1) n 1
d) S0 = 2, Sn + 1 = Sn + (n + 2)(n + 3) 2n + 1 n 0 và Sn = 2[ 2n (n2 + n + 2) 1 ] n 0 e) S 1
0 = – 1, Sn + 1 = Sn + (2n + 1)(3)n + 1 n 0 và Sn = 8
[ 3(3)n (4n 1) 5 ] n 0
f) S1 = – 3, Sn + 1 = Sn + (1)n + 1(n + 1)(n2 + 3) n 1 và S 1 n = 8
[(1)n (4n3 2n2 + 8n + 7) 7 ] n 1 5/ a 1
1 = 2, an + 1 = an + (n + 1) n 1 và an = 2 (n2 + n + 2) n 1
( để ý đường thẳng thứ (n + 1) bị n đường thẳng trước đó chia thành (n + 1) đoạn thẳng ) 6/ a 2 2
2000 = 7.109, an + 1 = (1 + 3.10
)an n 2000 và an = 7.109(1 + 3.10 ) n 2000 n 2000 (5 3 2) 1 3 n (5 3 2) 1 3 7/ a n
1 = 3, a2 = 8, an + 2 = 2an + 1 + 2an n 1 và an = ( ) ( ) 3 2 3 2
n 1 ( Xét An + 2 = u1u2...un un + 1un + 2 trong 2 trường hợp un + 2 = a hay un + 2 a ) (3 5) 1 5 (3 5) n 1 5 8/ a n
2 = 1, a3 = 3, an + 2 = an + 1 + an + 2 n 2 và an = ( ) ( ) 2 5 2 2 5 2
n 2 ( Xét An + 2 = u1u2...un un + 1un + 2 trong 3 trường hợp
[un + 2 = 2] hay [ un + 2 = 1 = un + 1] hay [un + 2 = 1 và un + 1 = 2] ).
9/ Chứng minh bằng cách qui nạp (dùng giả thiết qui nạp mạnh) theo n 2.
10/ Tìm c, d R thỏa an + 1 + cbn + 1 = d(an + cbn) n 0 (*)
Mặt khác, từ giả thiết ta có an + 1 + cbn + 1 = (c + 3)an + (2c + 2)bn n 0 (**)
Từ (*) và (**), ta có c(c + 3) = 2c + 2 và d = (c + 3). Do đó (c = 1, d = 4) hoặc (c = 2, d = 1). Đặt u
n = (an + bn) và vn = (an 2bn) n 0. Hãy chỉ ra hệ thức đệ qui cho mỗi dãy un (n 0)
và vn (n 0) để tính được un và vn theo n 0. Suy ra an = 2.4n 1 và bn = 4n + 1 n 0.
CHƯƠNG 5 : QUAN HỆ TRÊN CÁC TẬP HỢP
1/ Liệt kê tập hợp = { (x,y) S2 / x y } rồi xét các tính chất phản xạ, đối xứng, phản xứng và truyền.
a) + + b) + + c) + d) + e) + + f) ( + : có ; : không có )
2/ Xét các tính chất phản xạ, đối xứng, phản xứng và truyền của :
a) + b) c) + + d) + + e) + f) + ( + : có ; : không có )
3/ e) x y sinx = siny ( x = y + k2 hay x = y + k2 với k Z )
4/ a) [ a ] = { x R / (x a)(x + a + 3) = 0 }. Biện luận số phần tử của [ a ] ( là 1 hay 2 ) tùy theo a R . b) Tương tự a)
c) Trường hợp () : [ a ] = { x R / (x a)(x2 + ax + a2 + 12) = 0 } = { a } a R.
Trường hợp (+) : [ a ] = { x R / (x a)(x2 + ax + a2 12) = 0 }.
Biện luận số phần tử của [ a] ( là 1, 2 hay 3 ) tùy theo a R.
d) [ a ] = { x R / (x a)(ax + 7) = 0 }. Biện luận số phần tử của [ a ] ( là 1 hay 2 ) tùy theo a R.
e) [ a ] = { x R / (x a)(ax 4) = 0 }. Biện luận số phần tử của [ a ] ( là 1 hay 2 ) tùy theo a R.
f) [ a ] = { x R / (cos2x cos2a)(sinax + 2) = 0 } = { x R / cos2x = cos2a } có những phần tử nào?
5/ a) có 14 cặp b) 1 2 3 C C C c) 1 2 3 C C C + 2 2 2 C C C + 1 1 4 C C C 6 5 3 6 5 3 6 4 2 6 5 4
6/ a) toàn phần, có min và max b) bán phần, có min và các phần tử tối đại
c) bán phần, có max và các phần tử tối tiểu d) bán phần, có min và max
e) bán phần, có các phần tử tối tiểu và các phần tử tối đại f) toàn phần, có min và max
7/ Liệt kê 12 phần tử của S .
8/ a) Có 7 trường hợp khác nhau b) Có 4 trường hợp khác nhau
10/ b) và d) Chọn thứ tự toàn phần mới không trùng với thứ tự thông thường trên S.
c) Chọn thứ tự toàn phần mới không trùng với thứ tự thông thường trên S. CHƯƠNG 6 : HÀM BOOL
1/ Dùng các luật của hàm Bool để nhân ra dạng đa thức, rút gọn và nâng bậc các đơn thức.
2/ a) 8 tế bào lớn loại 1 ô, 1 phép phủ, 1 công thức đa thức tối tiểu.
b) 5 tế bào lớn (2 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 1 phép phủ, 1 công thức đa thức tối tiểu.
c) 4 tế bào lớn loại 4 ô, 2 phép phủ tối tiểu, 2 công thức đa thức tối tiểu ngang nhau.
d) 5 tế bào lớn (1 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 1 công thức đa thức tối tiểu
e) 6 tế bào lớn loại 2 ô, 3 phép phủ tối tiểu, 3 công thức đa thức tối tiểu ngang nhau.
f) 6 tế bào lớn (5 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 1 công thức đa thức tối tiểu.
g) 7 tế bào lớn (2 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 4 phép phủ tối tiểu,2 công thức đa thức tối tiểu ngang nhau.
h) 8 tế bào lớn (5 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 5 phép phủ tối tiểu,1 công thức đa thức tối tiểu.
Dựa vào mỗi ô của S = Kar(f) hay S , ta viết được dạng nối rời chính tắc của f và f .
3/ a) 5 tế bào lớn (1 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 1 phép phủ, 1 công thức đa thức tối tiểu.
b) 5 tế bào lớn (2 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 2 công thức đa thức tối tiểu ngang nhau.
c) 6 tế bào lớn (3 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 1 công thức đa thức tối tiểu
d) 6 tế bào lớn (3 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 1 công thức đa thức tối tiểu
e) 6 tế bào lớn (2 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 3 phép phủ tối tiểu, 3 công thức đa thức tối tiểu ngang nhau.
f) 6 tế bào lớn (1 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 2 phép phủ tối tiểu, 1 công thức đa thức tối tiểu.
g) 7 tế bào lớn (1 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 4 phép phủ tối tiểu, 2 công thức đa thức tối tiểu ngang nhau.
h) 8 tế bào lớn (1 tế bào lớn loại 4 ô, còn lại là loại 2 ô), 5 phép phủ tối tiểu, 1 công thức đa thức tối tiểu
Dựa vào mỗi ô của S = Kar(f), ta viết được dạng nối rời chính tắc của f và f .
4/ Chọn một công thức đa thức tối tiểu của f để vẽ mạng các cổng tổng hợp f .
5/ a) Có tất cả 26 = 64 vector Bool. Có 2
C = 15 vector Bool có đúng 2 biến nhận giá trị 1. 6
Số hàm Bool cần tính là 264 15 = 249 b) Có 2 C + 3 C + … + 6 C = 26 ( 0 C + 1
C ) = 57 vector Bool có ít nhất 2 biến nhận giá trị 1. 6 6 6 6 6
Số hàm Bool cần tính là 264 57 = 27 = 128 5
c) Số hàm Bool cần tính = số hàm Bool của F 2 5 = 2 = 232 3
d) Số hàm Bool cần tính = số hàm Bool của F 2 3 = 2 = 28 = 256
CHƯƠNG 7 : ĐẠI CƯƠNG VỀ ĐỒ THỊ :
2/ Đặt | V | = k. Dùng công thức bậc = 2| E | để lập phương trình rồi tính toán và suy luận.
a) 2k = 2 x 12 b) (3 x 4) + 5(k 3) = 2 x 21 c) kr = 2 x 6 với r 1 và k 2 ( r = bậc của mỗi đỉnh )
d) p đỉnh bậc 3, q đỉnh bậc 4 thì k = p + q + 3 và (3 x 5) + 3p + 4q = 2 x 16 . Từ đó tính được p và q .
3/ Đặt | V | = k. Dùng công thức bậc = 2| E | để lập phương trình rồi tính toán và suy luận.
a) 9 x 5 = 2| E | : vô lý b) 6 đỉnh bậc a, a + 1,…, a + 5 a + (a + 1) + … + (a + 5) = 2| E | : vô lý
c) kr = 2| E | k = 2m chẵn mr = | E | d) 2 x 19 = 2| E | = bậc 3k 3k 38 và k nguyên
4/ a) Không có chu trình Euler và đường Euler b), d), f) Có chu trình Euler c), e), g) Có đường Euler
6/ ( G và G’ ) : tính số đỉnh bậc 2 của mỗi đồ thị.
( H và H’ ) : lập ma trận của mỗi đồ thị theo các tập hợp đỉnh có thứ tự V = {a, b, c, p, q, r} ( của H ) và
V’ = {x, m, j, n, s, t} ( của H’ ).
( K và K’ ) : xét tính liên thông của mỗi đồ thị.
( L và L’ ) : tính số chu trình tứ giác của mỗi đồ thị.
( P và P’ ) : lập ma trận của mỗi đồ thị theo các tập hợp đỉnh có thứ tự V = {a, b, c, u, v, w, x} ( của P )
và V’ = {m, q, s, n, p, t, r} ( của P’ ).
( Q và Q’ ) : lập ma trận của mỗi đồ thị theo các tập hợp đỉnh có thứ tự V = {a, b, c, u, v, w, p, q, h, k}
( của Q ) và V’ = {m, s, z, i, j, x, t, y, r, n} ( của Q’ )
( S và S’ ) : tính số chu trình tam giác của mỗi đồ thị.
( T và T’ ) : mỗi đồ thị có đúng 4 chu trình tam giác. T’ có 1 chu trình tứ giác mà mỗi cạnh của nó lấy
từ 1 chu trình tam giác. Tuy nhiên T không có tính chất này.