Bài giảng toán rời rạc | Trường Đại học Kinh tế Thành phố Hồ Chí Minh

lOMoAR cPSD| 49519085 lOMoAR cPSD| 49519085
Bai giang TRR - Trang 1 1. Khái niệm thuật toán
Thuật toán là một dãy hữu hạn các bước cần thực
hiện nhằm xác ịnh kết quả của bài toán từ các giá trị ban
ầu (có thể có) 2. Đặc iểm của thuật toán Dữ liệu ầu vào (Input) Dữ liệu ầu ra (Output)
Tính hữu hạn (Finiteness)
Tính tổng quát (Generalliness) ThS N.Q.Thanh 2 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 2 1 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 3 2 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 4 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 5 3 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 6
BT1. Giải phương trình bậc nhất
BT2. Đếm số phần tử chẵn trong tập có n phần tử
BT3. Tìm bội số chung nhỏ nhất của 2 số
BT4. Tìm giá trị nhỏ nhất trong tập có n phần tử
BT5. Kiểm tra n có phải là số nguyên tố
BT6. Tìm x trong tập có n phần tử 12 4 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 7 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 8 1 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 9 2 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 10 VD1
Cho p = “An giỏi Toán” q = “An yếu Tin” Viết lại các mệnh
ề sau (dạng hình thức) a/
An giỏi Toán nhưng yếu Tin b/ An yếu cả Toán lẫn Tin
c/ An giỏi Toán hoặc An yếu Toán nhưng giỏi Tin d/
Nếu An giỏi Toán thì An cũng giỏi Tin e/ An chỉ giỏi
một môn hoặc An yếu cả hai ThS N.Q.Thanh 8 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 11 3
1. Định nghĩa 3 (biểu thức mệnh ề) E(p,q,r) = (p q) r F(p,q,r) = p (q r)
2. Định nghĩa 4 (BT mệnh ề tương ương) E F? 3. Định nghĩa 5 (Hằng
úng, hằng sai) E(p,q,r) = 1
với mọi trường hợp của p, q, r
E(p,q,r) = 0 với mọi trường hợp của p, q, r ThS N.Q.Thanh 10 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 12 4 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 13 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 14 5 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 15 6 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 16
VD3: Chỉ ra các khẳng ịnh úng a/ p q p q b/ p (p q) p q
VD4: Rút gọn các biểu thức sau a/ ((p q) (p q)) q b/ (p q) (( p q) q)
VD5: Hãy kiểm tra các suy luận sau: a/ ((p q) r) ( ((p r) q)) 0 b/ p (q (r s)) (p q) ( r s) ThS N.Q.Thanh 20 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 17 7 ThS N.Q.Thanh lOMoAR cPSD| 49519085
Bai giang TRR - Trang 18
2. Vị từ và lượng từ Cho P(x) là hàm mệnh ề theo biến x, với x A x A, P(x) x A, P(x) !x A, P(x)
VD: Xét A là tập hợp sinh viên D18, ta có a) x
A, x qua môn Toán rời rạc
b) x A, x chưa qua môn Cơ sở lập trình c) !x A, x ạt 10
iểm môn Cơ sở dữ liệu ThS N.Q.Thanh 23 2. Phủ ịnh của vị từ Nếu P(x) là hàm mệnh ề xác ịnh trên tập A, ta có ( x A, P(x)) x A, (P(x)) ( x A, P(x)) x A, (P(x))
VD: Cho A là tập hợp SV D18, phủ ịnh các vị từ a) x
A, x qua môn Toán rời rạc
b) x A, x chưa qua môn Cơ sở lập trình 24 8 ThS N.Q.Thanh