TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM MÃ LƯU TRỮ
ĐỀ THI KẾT THÚC HỌC PHẦN CK2425-1
Học kỳ I – Năm học 2024 - 2025 MTH00045
Tên học phần: TOÁN RỜI RẠC (HỆ CQ KHÓA 2024)
Mã HP: MTH 00045
Thời gian làm bài: 90 phút
Ngày thi: 08 / 01 / 2025
Ghi chú: Sinh viên không được phép sử dụng tài liệu khi làm bài.
Câu 1 (1,5 điểm).
Cho a0= 4,a1= 24 và an+2 = 6an+1 −9an−(4n−17)2n,∀n≥0. Tính antheo n(n≥0).
Câu 2 (3,25 điểm = 1,25đ + 1,25đ + 0,75đ).
Cho m= 43615880,n =−22198176,a = 36567 và b= 6886.
a) Phân tích nguyên tố mvà nđể tìm d= (m,n),e = [m,n]và một dạng tối giản của m
n.
b) Dùng thuật chia Euclid để tìm r,s,u,v ∈Zthỏa 1 = ra +sb và 1
ab =u
a+v
b.
c) Mô tả các ước số nguyên của mvà cho biết mcó bao nhiêu ước số nguyên?
Câu 3 (3,25 điểm = 1,25đ + 1đ + 1đ).
a) Cho quan hệ hai ngôi ℜtrên S={1,2,3}được xác định bởi ∀x,y ∈S,xℜy⇔(x−y)2≤1.
Liệt kê tập hợp H={(x,y)∈S2|xℜy}.
Xét các tính chất phản xạ, đối xứng, phản xứng và truyền của quan hệ ℜ.
b) Trên T={1,2,4,5,6,7,10,12,24,30}, cho quan hệ thứ tự Ωđược xác định bởi
∀x,y ∈T, xΩy⇔y=xhoặc có số nguyên chẵn ksao cho y=kx (kphụ thuộc vào x
và y).
Vẽ sơ đồ Hasse của (T,Ω) và tìm các phần tử min, max, tối tiểu và tối đại (nếu có) của
(T,Ω).
c) Áp dụng phần b) Câu 2 để giải phương trình 6886 ·¯y=¯
238 trong Z36567.
Suy ra nghiệm của phương trình 6886 ×6·¯x= 238 ×6trong Znvới n= 36567 ×6.
Câu 4 (2 điểm = 1đ + 1đ).
Cho hàm Boole ftheo các biến Boole x,y,z,t được xác định bởi
f(x,y,z,t) = x¯yzt ∨¯x¯zt ∨xyz¯
t∨¯xy¯
t∨x¯yz¯
t∨¯xzt
a) Vẽ biểu đồ Karnaugh cho fvà xác định các tế bào lớn của nó.
b) Tìm các công thức đa thức tối tiểu cho f.
HẾT
1
lOMoARcPSD|42620215
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM MÃ LƯU TRỮ
ĐỀ THI KẾT THÚC HỌC PHẦN CK2324-3
Học kỳ III – Năm học 2023 - 2024 MTH00041
Tên học phần: TOÁN RỜI RẠC (23HE1)
Mã HP: MTH 00041
Thời gian làm bài: 90 phút
Ngày thi: 26 / 8 / 2024
Ghi chú: Sinh viên không được phép sử dụng tài liệu khi làm bài.
Câu 1 (1 điểm).
Cho các biến mệnh đề p,q và r. Chứng minh dạng mệnh đề (p∧q∧r)→(p∨r)là hằng đúng.
Câu 2 (1 điểm).
Cho ánh xạ f:R\ {1} → R\ {1}thỏa mãn f(x) = x+1
x−1,∀x∈R\ {1}. Chứng minh flà một
song ánh và tìm ánh xạ ngược của f.
Câu 3 (1 điểm = 0,5đ + 0,5đ).
a) Với klà số nguyên dương lẻ, có bao nhiêu số tự nhiên có kchữ số được lấy từ tập hợp
{1,2}mà mỗi số chứa một số chẵn chữ số 1?
b) Có bao nhiêu số tự nhiên có 2024 chữ số được lấy từ tập hợp {1,2,3,4}mà mỗi số đó
chứa một số chẵn chữ số 1 và một số lẻ chữ số 2?
Câu 4 (2 điểm).
Cho a0= 7,a1= 2 và an+2 = 7an+1 −12an+ (2n2−10n−4)2n. Tính antheo n(n≥0).
Câu 5 (2 điểm = 1đ + 1đ).
Cho m= 702408,n = 181704.
a) Dùng thuật chia Euclid để tìm d= (m,n)và tìm r,s ∈Zthỏa d=rm +sn. Từ đó chỉ
ra dạng tối giản của m
n.
b) Tính e= [m,n]và tìm u,v ∈Zthỏa 1
e=u
m+v
n.
Câu 6 (3 điểm = 1đ + 1đ + 1đ).
a) Cho quan hệ hai ngôi R trên Zđược xác định bởi: ∀x,y ∈Z,xRy⇔3x−ylà số chẵn.
Chứng minh R là quan hệ tương đương.
b) Cho quan hệ hai ngôi ∆trên R×Rđược xác định bởi:
∀x,y,z,t ∈R,(x,y)∆(z,t)⇔ ∃k∈N∗:z=kx,t =ky. Chứng minh ∆là quan hệ thứ
tự.
c) Trong Z17, tính 11.31. Áp dụng để giải phương trình 300.¯x= 225 trong Z85.
HẾT
2
lOMoARcPSD|42620215
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM MÃ LƯU TRỮ
ĐỀ THI CUỐI KỲ CK2324-1
Học kỳ I – Năm học: 2023-2024 MTH00043
Tên học phần: TOÁN RỜI RẠC 1A
Mã HP: MTH00043
Thời gian làm bài: 90 phút
Ngày thi: 09/01/2024
Ghi chú: Sinh viên không được phép sử dụng tài liệu khi làm bài.
Câu 1 (2 điểm).
a) Tìm số nghiệm nguyên không âm của phương trình x+y+z+t= 18 thỏa mãn điều
kiện 2≤x≤8và y≥5.
b) Cho m= 273654117139và n= 243211132. Gọi Slà tập hợp các phần tử vừa là ước số
dương của mvà vừa là bội số dương của n. Tìm số phần tử của S.
Câu 2 (2 điểm). Tìm nghiệm của hệ thức đệ quy
(xn+2 = 5xn+1 −6xn+ 2n(2 −4n)với n≥0;
x0= 7,x1= 24.
Câu 3 (2 điểm).
a) Hãy dùng thuật toán Euclid để tìm d=UCLN(870,384). Sau đó tìm a,b ∈Zsao cho
d= 870a+ 384b.
b) Giải phương trình 192¯x+ 139 = 316 trong Z435.
Câu 4 (2 điểm).
Cho tập hợp A={−2,1,3,5,6,9,10,12}và Rlà một quan hệ trên Ađược định bởi xRy⇔
x2−4y2chia hết cho 3.
a) Chứng minh rằng Rlà một quan hệ tương đương trên A.
b) Phân hoạch Athành các lớp tương đương.
Câu 5 (2 điểm).
Cho B={1,3,4,5,6,8,12,15,18,30}và .
.
. là quan hệ “chia hết cho” trên B.
a) Vẽ sơ đồ Hasse của (B,.
.
.).
b) Tìm phần tử tối đại, tối tiểu, nhỏ nhất, lớn nhất (nếu có).
HẾT
3
lOMoARcPSD|42620215
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM MÃ LƯU TRỮ
ĐỀ THI CUỐI KỲ CK2425-1
Học kỳ I – Năm học: 2024-2025 MTH00043
Tên học phần: TOÁN RỜI RẠC 1A
Mã HP: MTH00043
Thời gian làm bài: 90 phút
Ngày thi: 10/01/2025
Ghi chú: Sinh viên không được phép sử dụng tài liệu khi làm bài.
Câu 1 (2 điểm).
a) Có bao nhiêu dãy số có 8 chữ số được thành lập từ 1,4,4,7,7,8,8,8thỏa điều kiện chữ
số đầu tiên là chẵn.
b) Có bao nhiêu cách xếp 16 viên bi giống nhau vào 4 hộp khác nhau thỏa điều kiện tất cả
các hộp đều có bi và hộp cuối cùng có không quá 8 viên.
Câu 2 (1,5 điểm). Với n≥0ta đặt
sn=n
X
k=0(2k+ 1)3k= 1 ·30+ 3 ·31+· · · + (2n−1)3n−1+ (2n+ 1)3n.
Tìm công thức sntheo nbằng cách sử dụng hệ thức đệ quy.
Câu 3 (2 điểm).
a) Dùng thuật toán Euclide để tìm d=UCLN(656,212) và tìm a,b ∈Zsao cho d=
656a+ 212b.
b) Giải phương trình 106¯x−135 = 117 trong Z328.
Câu 4 (2 điểm). Cho tập hợp A={−4,0,1,5,7,10,12,19}và Rlà một quan hệ trên Ađược
định bởi xRy⇔2x+ 3ychia hết cho 5.
a) Chứng minh rằng Rlà một quan hệ tương đương trên A.
b) Tìm tất cả các lớp tương đương trong quan hệ trên.
Câu 5 (1,5 điểm). Trên tập hợp B={1,2,3,5,6,9,10,12,18,36}ta định nghĩa một quan hệ
thứ tự như sau xSy⇔tồn tại số nguyên lẻ ksao cho kx =y.
a) Vẽ sơ đồ Hasse của (B,S).
b) Tìm phần tử tối đại, tối tiểu, nhỏ nhất, lớn nhất (nếu có).
Câu 6 (1 điểm). Cho X={1,2,3,4,5}. Hỏi trên Xcó bao nhiêu quan hệ có tính chất phản
xạ và đối xứng?
4
lOMoARcPSD|42620215
HẾT
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM MÃ LƯU TRỮ
ĐỀ THI KẾT THÚC HỌC PHẦN CK2425-1
Học kỳ I – Năm học 2024 - 2025 MTH00041
Tên học phần: Toán rời rạc (23KDL1)
Mã HP: MTH00041
Thời gian làm bài: 90 phút
Ngày thi: 12/02/2025
Ghi chú: Sinh viên [ ] được phép / [x] không được phép sử dụng tài liệu khi làm bài.
Câu 1 (2 điểm).
Giải hệ thức đệ quy: an+2 −5an+1 + 6an= 3n+1(2n+ 7)∀n≥0,a0= 1,a1= 4.
Câu 2 (2 + 1 điểm).
a) Cho m= 315,n = 147. Tìm d= (m,n)và e= [m,n], tìm các số nguyên a,b,u,v sao cho
d=am +bn và 1
e=u
m+v
n.
b) Giải phương trình trong Z315:147¯x=84.
Câu 3 (1 + 1 điểm).
Cho tập hợp S={0,1,2,3,−1,−2,−3,−4}và quan hệ R:xRy ⇔(x=y)∨(y≥ |x|).
a) Chứng minh Rlà một quan hệ thứ tự trên tập S.
b) Vẽ sơ đồ Hasse cho quan hệ R. Liệt kê các phần tử tối tiểu, tối đại.
Câu 4 (2 điểm).
Cho hàm Bool 4 biến f=xy(z∨¯
t)∨xyz¯
t∨y¯
t∨x¯y¯
t. Tìm công thức đa thức tối tiểu cho f
bằng cách sử dụng sơ đồ Karnaugh.
Câu 5 (1 điểm).
Cho S={1,2,3,4}và Rlà quan hệ tương đương trên S. Biết rằng (1,2),(2,3) ∈Rvà
(2,4) /∈R, hãy chỉ ra các lớp tương đương của R, sau đó liệt kê R.
(Câu này chỉ cần ghi kết quả, không cần giải thích)
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG-HCM
ĐỀ THI KẾT THÚC HỌC PHẦN
Học kỳ I – Năm học 2023 - 2024
Tên học phần: TOÁN RỜI RẠC (HỆ CQ KHÓA 2023) Mã HP: MTH 00041
Thời gian làm bài: 90 phút Ngày thi: 24/01/2024
Ghi chú: Sinh viên không được phép sử dụng tài liệu khi làm bài.
Câu 1 (1,5 điểm).
5
lOMoARcPSD|42620215