Bài giảng Toán rời rạc - Chương 1: Phương pháp đếm - Phạm Thị Thuận
TOÁN RỜI RẠC
Giảng viên: Ths. Phạm Thị Thuận
LOGO
NỘI DUNG
PHẦN 1: ĐẠI SỐ LOGIC
CHƯƠNG 1: PHƯƠNG PHÁP ĐẾM
CHƯƠNG 2: LOGIC MỆNH ĐỀ
CHƯƠNG 3: ĐẠI SỐ BOOLE
CHƯƠNG 4: SUY DIỄN VÀ CHỨNG MINH
PHẦN 2: LÝ THUYẾT ĐỒ THỊ
CHƯƠNG 1: ĐỒ THỊ HỮU HẠN
CHƯƠNG 2: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
CHƯƠNG 3: CÂY
Thời lượng môn học
❖ Môn học 6 trình
❖ Số bài kiểm tra 6 bài
❖ được phép nghỉ 2 buổi
Tài liệu tham khảo
Giá o trì nh Toá n rời rạc, Trường đại học Kinh Doanh &
Cô ng Nghệ, tá c giả TS. Hoàng Xuâ n Thảo
KHÁI NIỆM TOÁN RỜI RẠC
❖ Các bạn đã học môn toán nào?
❖Toá n rời rạc nó i tổng quá t là nghiên cưú về mọi
châ n lý đúng tuyệt đối, về mọi khá i niệm (như
hì nh ảnh, â m thanh…) được định nghĩa một
cá ch đúng đắn.
Khái niệm: TRR là nghiên cứu các đối tượng
không liên tục (rời rạc), toán học dành cho tin học
Toán học nghiên cứu lĩnh vực gì?
Lý thuyết tổ hợp
Lý thuyết đồ thị
Tập hợp
Ứng dụng trong toán rời rac
Hàm: biểu diễn các
Logic và suy luận
toá n học sẽ nghiên
cứu về cá c luật, cá c
phé p biến đổi, cá c
suy luận, logic, logic
mờ, ứng dụng nhiều
trong mô n trí tuệ nhâ n
tạo.
Đồ thị nghiên cứu về
mô hì nh đồ thị, biểu
diễn đồ thị. Ứng dụng
trong thiết lập sơ đồ
mạng
phép biến đổi ánh xạ
phần tử này sang
phần tử kia. ứng dụng
trong phân tích độ
phức tạp thuật toán
Toán rời rạc
học về
Quan hệ: nghiên cứu
mô hình quan hệ,
biểu diễn các quan hệ
của phần tử trong tập
hợp, ứng dụng trong
mô n csdl
Số nguyên: nghiên
cứu tí nh chia hết,
UCLN, BCNN, số học
đồng dư. Ứng dụng
trong mật mã , như
cá c hàm băm
Đại số Boole nghiên
cứu cá c phé p toá n và
quy tắc trên tập (0,1).
Ứng dụng trong mạch
logic, mạch cộng
trong CPU
CHƯƠNG 1: PHƯƠNG PHÁP ĐẾM:
A. TẬP
I. Khá i niệm
Tập hợp là một khá i niệm khô ng định nghĩa mà chỉ có
thể mô tả, một tập hợp được xá c định khi đưa ra
một qui tắc, qui luật để phâ n biệt đối tượng hoặc
phần tử thuộc nó hay khô ng
Ví dụ: cá c số nguyên dương tạo thành tập số tự nhiên
2
N, thì số 2 là một phần tử của tập N, cò n khô ng
phải phần tử của tập hợp
- Dùng cá c chữ cá i nhỏ a, b, x, y.... Để chỉ phần tử
- Dùng cá c chữ cá i lớn A, B, X, Y,.. Để chỉ cá c Tập
II. Quan hệ giữa phần tử với tập và giữa các tập
với nhau
1. Nhận biết các phần tử của tập hợp
- x gọi là phần tử thuộc A thì ta viết x A hoặc A →
x và đọc “ A chứa x”
- x là phần tử khô ng thuộc A thì ta viết x A hoặc
A x và đọc A khô ng chứa x
2. Tập con
Tập A được gọi là tập con của tập hợp X, nếu mọi
phần tử của A đều là phần tử của X. ký hiệu là
AX
(AX xA → x X)
Đọc “ X bao hàm A” hoặc A là tập con của X
→ số phần tử trong một tập, cò n gọi là bản số hay
bậc luống của tập đó
3. Tập hợp bằng nhau
Tập A được gọi là bằng tập B, nếu mọi phần tử của A là phần tử
của B và ngược lại mọi phần tử của B đều là phần tử của A
A=B xA xB
*) Chú ý : số phần tử trong một tập hợp còn gọi là bản số hoặc bậc
luống
4. Lực lượng
Lực lượng của tập A là số phần tử trong A. Kí hiệu |A| hoặc N(A)
Ví dụ: T={a, b, c}
cho tập S là tập tất cả các hoán vị của tập
suy ra N(T)=3
5. Tập các tập con
Cho A là một tập hợp, tập các tập con của A bao
gồm cả tập rỗng và A, ký hiệu p(A), trong tập
này mỗi phần tử là một tập con của A
Ví dụ: A={2,4,6}
P(A)={{2},{4},{6},{2,4},{4.6},{2,4,6},{}}
III. Cách xác định một tập hợp
1. Liệt kê ra tất cả các phần tử của tập
Nếu mọi phần tử x1, x2, .., xn đều thuộc A thì ta viết
A={x1, x2,...,xn}
2. Chỉ rõ tính chất đặc trưng của mọi phần tử thuộc
tập
Nếu tập A chứa các phần tử x có tính chất P thì ta viết
A={x/P}
3. Cá c tập vũ trụ thường dùng
R={tập số thực}
Z={tập số nguyên}
Z + ={tập cá c số nguyên khô ng â m}
N={ tập cá c số tự nhiên}
IV. Các phép toán về tập hợp
1. phép hợp (phép cộng)
Hợp của hai tập hợp A và B là một tập hợp bao gồm các
phần tử thuộc ít nhất một trong hai tập hợp đã cho. Ký
hiệu là A B
(x A B (xA ν x B)
Ký hiệu
A
B
- Tổng quát: hợp của n tập A1, A2, …, An
là tập các phần tử thuộc ít nhất một tập
IV. Các phép toán về tập hợp
2. phé p giao.
Giao của hai tập hợp A và B là một tập hợp bao gồm các
phần tử thuộc cả hai tập hợp đã cho. Ký hiệu A B
(x A B (xA
٨
x B) Kí hiệu:
B
A
- Tổng quát: Giao của n tập A1, A2, …, An
Là tập các phần tử chung thuộc tất cả n tập
3. Phép hiệu:
Cho A và B là 2 tập hợp hiệu của A và B kí hiệu
A\B là các phần tử thuộc A mà không thuộc B
A\B={x|x A x B}
Kí hiệu:
A
B
- Tượng tự viết trường hợp B\A
4. Hiệu đối xứng:
Hiệu đối xứng của 2 tập A và B là 1 tập hợp . kÍ
hiệu A B
A B={x|xA\B V x B\A}
A
B
5. Phần bù.
Cho A là tập con thực sự của X, phần bù của tập
A trong X, ký hiệu Ā =X\A. gồm các phần tử
thuộc X mà không thuộc A
Ā={x X và x A}
Kí hiệu
X
A
6. Tích đề các.
Tích đề các của hai tập hợp A và B là một tập hợp bao
gồm các phần tử có dạng (a, b) trong đó a thuộc A,
b thuộc B.
ký hiệu A x B ={(a,b) | aA b B}
7. Tập rỗng
Tập không có phần tử nào gọi là tập rỗng. Kí hiệu
- Tập rỗng có hai tính chất:
+ Tập rỗng là tập duy nhất
+ Tập rỗng được xem là tập con của bất kỳ tập nào,
kể cả nó.
Ví dụ: A={tập các nghiệm thực của phương trình x2 +1=0
A=
Tính chất tập rỗng
a.A = A
b.A =
c.A A =
V. Tính chất của các phép toán về tập
hợp
1. Tính chất giao hoán
a. A B= B A
b. A B = B A
2. Tính kết hợp
a. A (B C)=(A B) C
b. A (B C) = (A B) C
3. Tính chất phân phối
a. A (B C) = (A B) (A C)
b. A (B C)= (A B) (A C)
4. Luật đối ngẫu De Uocgan
a. A\ (B C)=(A\B) (A\C)
b. A\ (B C)=(A\B)(A\C)
Tải về để xem bản đầy đủ
49 trang
19820
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 1: Phương pháp đếm - Phạm Thị Thuận", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_1_phuong_phap_dem_pham_thi_thu.ppt
