1.

Thông tin về học phần:
-

Tên học phần

CẤU TRÚC RỜI RẠC

-

Mã học phần

KC21206

-

Loại học phần

(Bắt buộc)

2.

Số tín chỉ: 2 lý thuyết

3.

Trình độ: Cho SV năm thứ 2

4.

Phân bổ thời gian

5.

-

Lên lớp: 80%

-

Bài tập: 20%

Mục tiêu của học phần
Trang bị cho sinh viên kiên thức cơ bản về Cấu trúc rời rạc và các ứng

dụng của nó mà một kỹ sư CNTT cần có trong việc thiết kế máy tính và xây
dụng các phần mềm để giải quyết các bài toán thực tế.
6.

Mô tả vắn tắt nội dung môn học
Cung cấp cho sinh viên những kiến thức cơ bản về Tập hợp, Đại số Boole,

Thuật toán, Đồ thị, Cây, Một số kiến thức cơ bản và bổ trợ khác
7.

8.

Nhiệm vụ của sinh viên
-


Dự lớp

-

Tự học

-

Bài tập

Tài liệu học tập
-

Sách, giáo trình chính

-

Sách tham khảo
[1] Đỗ Đức Giáo, Toán Rời rạc ứng dụng trong Tin học, NXB Giáo
dục, 2006
[2] Vũ Kim Thành, Toán Rời rạc, ĐH Nông nghiệp Hà Nội, 2008
[3] Nguyễn Đức Nghĩa , Toán rời rạc, Đại học Quốc Gia Hà Nội, 2003.
[4] Đỗ Đức Giáo, Toán học rời rạc, Đại học Quốc Gia Hà Nội, 1998.


[5] Đỗ Đức Giáo, Cơ sở toán trong lập trình, KH&KT Hà Nội, 1998.
[6] Nguyễn Xuân Quỳnh, Cơ sở toán rời rạc và ứng dụng, GDĐT,
1993
9.


Tiêu chuẩn đánh giá sinh viên
-

Điểm đánh giá nhận thức và thái độ tham gia thảo luận: 10%

-

Điểm kiểm tra giữa học phần: 20%

-

Điểm thi kết thúc học phần: 70%

10.

Thang điểm Thực hiện theo học chế tín chỉ

11.

Nội dung học phần Gồm 3 phần
-

Phần I Lý thuyết tập hợp (Từ chương I đến III)
Phần II Lý thuyết đồ thị (Chương IV, V)
Phần III Lôgic (Chương VI, VII)


MỤC LỤC

Trang



Chương 1 TẬP HỢP
Mục tiêu Cung cấp cho sinh viên những kiến thức cơ bản về tập hợp, hàm số,
các phương pháp đếm trên tập hợp. Từ đó, sinh viên có cái nhìn tổng quan về
một cấu trúc rời rạc cơ bản nhất để dựng lên tất cả cấu trúc khác.
1.1. BIỂU DIỄN TẬP HỢP TRÊN MÁY TÍNH
1. 1. 1.Khái niệm tập hợp
Các tập hợp dùng để nhóm các đối tượng với nhau. Thông thường các
đối tượng trong một tập hợp có tính chất tương tự nhau.
Định nghĩa
Một tụ tập các đối tượng có một tính chất chung nào đó gọi là một tập
hợp. Các đối tượng trong một tập hợp được gọi là các phần tử cửa tập hợp đó.
Tập hợp thường gọi tắt là tập.
Cách viết tập hợp: Tên tập hợp = {a1, a2, …, an}
Tên tập hợp có thể có hoặc không, ai là giá trị các phần tử của tập hợp
(i = 1 … n), n là số phần tử của tập hợp đó.
Ví dụ
Tập N các số tự nhiên, N = {0, 1, 2, … }
Tập N* các số tự nhiên khác 0, N* = {1, 2, … }
Tập Z các số nguyên, Z = { …, -1, 0, 1, 2, … }
Tập Z+ các số nguyên dương, Z+ = {1, 2, 3, … }
…
Ta viết a ∈ A ( đọc: a thuộc A) để chỉ a là phần tử của tập A; a ∉ A
(đọc: a không thuộc A) để chỉ a không phải là phần tử của tập hợp A.
Tập hợp không chứa phần tử nào được gọi là tập rỗng, ký hiệu ∅.
Ví dụ Tập hợp các số nguyên dương lớn hơn bình phương của nó là
một tập rỗng.
4



1. 1. 2. Biểu diễn các tập hợp trên máy tính
Có nhiều cách biểu diễn tập hợp trên máy tính. Ở đây, giới thiệu
phương pháp biểu diễn bằng cách lưu trữ các phần tử của tập hợp dưới dạng
sắp xếp tùy các phần tử của tập vũ trụ.
Giả sử X là một tập vũ trụ và A ⊆ X (với giả thiết dung lượng bộ nhớ
của máy tính không nhỏ hơn lực lượng của X).
Giả sử |X| = n, khi đó ta sắp các phần tử của X = {a1, a2, …, an}.
Biểu diễn tập con A bằng một xâu bit có chiều dài n, trong đó bit thứ i
là 1 nếu ai ∈ A, còn bit thứ i là 0 nếu ai ∉ A.
Ví dụ 1 Cho X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A = {1, 3, 5, 7, 9}
B = {2, 4, 6, 8, 10}
a. Tìm xâu bit của A ∪ B
b. Tìm xâu bit của A ∩ B
c. Tìm xâu bit của A và B
Hướng dẫn
Xâu bit biểu diễn tập con A = {1, 3, 5, 7, 9} là 1010101010.
Xâu bit biểu diễn tập con B = {2, 4, 6, 8, 10} là 0101010101.
Để nhận đuợc xâu bit cho các hợp và giao của hai tập hợp, ta thực hiện
phép toán Boole trên các xâu bit biểu diễn hai tập hợp đó.
Xâu bit đối với hợp là OR (phép tuyển ∨) bit của hai xâu tương ứng và
xâu bit đối với giao là AND (phép hội ∧) của hai xâu tuơng ứng.
Xâu bit của A ∪ B: 1010101010 ∨ 1010101010 = 1111111111
tương ứng với tập A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Xâu bit của A ∩ B: 1010101010 ⋀ 0101010101 = 0000000000
tương ứng với tập A ∩ B = ∅
Để nhận được xâu bit của phần bù tập hợp A, ta chỉ việc thay 0 bởi 1 và
thay 1 bởi 0 trong xâu bit của A.
5



Xâu bit của A: 0101010101; của B: 1010101010
Ví dụ 2
Cho tập vũ trụ U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Tìm các tập biểu diễn
bới các xâu
a) 11110 01111. A = {1, 2, 3, 4, 7, 8, 9, 10}
b) 01011 11000. B = {2, 4, 5, 6, 7}
c) 10000 00001. C = {1, 10}
1. 1. 3. Quan hệ giữa các tập hợp
Định nghĩa 1
Tập A được gọi là tập con của tập B nếu và chỉ nếu mỗi phần tử của A
đều là phần tử của B.
Ta dùng ký hiệu A ⊆ B để chỉ tập A là con của tập B.
Nhận xét A ⊆ B nếu và chỉ nếu lượng từ ∀x (x ∈ A → x ∈ B) là đúng.
Ví dụ
a) Tập các số nguyên dương lẻ nhỏ hơn 10 là một tập con của tập các số
nguyên dương nhỏ hơn 10.
b) Tập rỗng là con của mọi tập hợp.
c) Mọi tập hợp đều là tập con của chính nó.
Khi muốn nhấn mạnh tập A là tập con của tập B nhưng A ≠ B, ta viết A
⊂ B và nói rằng A là tập con thật sự của B
Định nghĩa 2
Hai tập hơp là bằng nhau nếu và chỉ nếu chúng có cùng các phần tử.
Ví dụ Các tập {1, 3, 5} và {3, 5, 1} là bằng nhau vì chúng có cùng các
phần tử.
Nhận xét Nếu A ⊆ B và B ⊆ A thì A = B
Ví dụ
6



Xác định xem các mệnh đề sau đúng hay sai
a) x ∈ {x} (đúng)

b) {x} ⊆ {x} (đúng)

c) {x} ∈ {x} (sai)

d) {x} ∈ {{x}} (đúng)

e) ∅ ⊆ {x} (đúng)

f) ∅ ∈ {x} (sai)

Định nghĩa 3
Nếu có chính xác n phần tử phân biệt trong tập hợp S, với n là số
nguyên không âm,thì ta nói rằng S là tập hữu hạn và n là bản số của S, ký
hiệu |S| = n.
Ví dụ S là tập các chữ cái tiếng Anh, |S| = 26; |∅| = 0;
Lưu ý
-

Các phần tử của một tập hợp có thể là các tập hợp khác.

-

Nếu S = {∅} thì |S| = 1.

Ví dụ Xác định bản số của các tập sau
a) {a} (|S| = 1)


b) {{a}} (|S| = 1)

c) {a,{a}} (|S| = 2)

d) {a,{a},{a,{a}}} (|S| = 3)

Định nghĩa 4
Một tập được gọi là vô hạn, nếu nó không phải là hữu hạn.
Ví dụ Các tập N, Z, Z+, Q và R đều là tập vô hạn
1. 1. 4. Các phép toán tập hợp
a)

Phép hợp

Cho A và B là hai tập hợp. Hợp của A và B, ký hiệu là A∪ B, là tập hợp
chứa các phần tử, hoặc thuộc A hoặc thuộc B.
7


A ∪ B = {x| x ∈ A ∨ x ∈ B}

b)

Phép giao

Cho hai tập hợp A và B. Giao của A và B, ký hiệu là A ∩ B, là tập hợp
chứa các phần tử thuộc cả A và B.
A ∩ B = {x| x ∈ A ∧ x ∈ B}


c)

Phép hiệu
Cho A và B là hai tập hợp, hiệu của A và B, ký hiệu là A – B (hay A\

B), là tập hợp chứa các phần tử thuộc A nhưng không thuộc B.

Hiệu của A và B còn đuợc gọi là phần bù của B đối với A.
A – B = {x| x ∈ A ∧ x ∉ B}
Đặc biệt Cho U là tập vũ trụ. Phần bù của tập A, kí hệu là A, là phần
bù của của A đối với U: A = {x| x ∉ A}
8


Ví dụ
a) Cho A = {1, 2, 3} và B = {1, 3, 5} thì A ∪ B = {1, 2, 3, 5}.
b) Cho A = {1, 2, 3} và B = {1, 3, 5} thì A ∩ B = {1, 3}.
c) Cho A = {1, 2, 3, 4, 5} và B = {4, 5} thì A – B = B = {1, 2, 3}
Ví dụ
Giả sử rằng A là tập sinh viên năm thứ hai ở trường bạn và B là tập các
sinh viên đang học môn toán rời rạc ở trường bạn. Hãy biểu diễn các tập sau
đây qua A và B
a) Tập hợp các sinh viên năm thứ hai học môn toán rời rạc ở trường bạn
(A ∩ B)
b) Tập hợp các sinh viên năm thứ hai ở trường bạn không học môn toán
rời rạc (A \ B)
c) Tập hợp các sinh viên ở trường bạn hoặc là năm thứ hai hoặc đang
học tóan rời rạc (A ∪ B)
1. 1. 5. Tập hợp lũy thừa
Cho tập S, tập lũy thừa của S là tập tất cả các tập con của S, ký hiệu là

P(S).
P(S) = {A| A ⊆ S}
Ví dụ Tìm tập lũy thừa của tập ∅ và tập luỹ thừa của tập {∅}.
P(∅) = {∅} , P({∅}) = {∅, {∅}}.
Nếu một tập có n phần tử thì tập lũy thừa của nó có 2n phần tử.
9


Ví dụ Tìm tập lũy thừa của tập các chữ số nhị phân B = {0,1}
P(B) = {∅, {0},{1},{0,1}}.
1. 1. 6. Các cách xác định tập hợp
a.

Liệt kê các phần tử

Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử
của nó.
Ví dụ
a) V = {a, e, I, o, u}.

b) O = {1, 3, 5, 7, 9}.

c) N = {0, 1, 2, 3, …}.

d) Z = { ..., 0, 1, 2, 3, …}.

b.

Chỉ ra các thuộc tính đặc trưng của phần tử


Một tập hợp cũng có thể được xác định bằng cách chỉ ra rõ các thuộc
tính đặc trưng của các phần tử của nó.
Ví dụ
a) V = {x| x là nguyên âm trong bảng chữ cái Tiếng Anh}.
b) O = {x| x là số nguyên dương, lẻ, nhỏ hơn 10}.
c) N = {x| x là số tự nhiên}.
d) R = {x| x là số thực}.
Ví dụ
1. Liệt kê các phần tử của tập hợp sau
a) {x| x là số thực sao cho x2 = 1}. A = {-1, 1}
b) {x| x là số nguyên sao cho x2 = 2}. B = ∅
2. Dùng cách chỉ rõ các thuộc tính đặc trưng mô tả các tập hợp sau
a) {0, 3, 6, 9, 12}. A = {x| x = 3k ∧ x ≤ 12, (k ≥ 0)}
b) {-3, -2, -1, 0, 1, 2, 3}. B = {x| x ∈ Z ∧ |x| ≤ 3}
1. 1. 7. Lực lượng của tập hợp
a.

Định nghĩa
10


Lực lượng của tập A, ký hiệu là |A|, là số phần tử của A.
b.
Các công thức tính lượng của tập hợp
| A ∪ B | = | A |+ | B | - | A ∩ B |
|A∪ B∪ C| = |A| + | B| + | C| - |A∩B |
-|A∩C | -| B ∩C | + |A∩ B∩ C|
|A∪ B∪ C∪ D| = |A| + | B | + | C| + | D|
- | A ∩ B | - | A ∩ C | - |A ∩ D|
- | B ∩ C | -| B ∩ D | - | C ∩ D |

+ | A ∩ B ∩ C | + | A ∩ B ∩ D | + |A ∩ C ∩ D|
+ | B∩ C∩ D| -|A∩B ∩C ∩D|
1. 1. 8. Tích Đề - các của các tập hợp và lực lượng của nó
Cho hai tập A và B. Tích Đề - các của A và B, ký hiệu là A × B, là tập
tất cả các cặp (a, b) với a ∈ A và b ∈ B.
A × B = {(a, b)| a ∈ A ∧ b ∈ B}.
Lực lượng

|A × B| = |A| . |B|

Ví dụ Cho A = {1, 2}, B = {a, b, c}
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A ={(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
A2 = A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}
Nhận xét A × B ≠ B × A.
Tích Đề các của các tập A 1, A2, …, An, đuợc ký hiệu bởi A1× A2× …
× An là tập hợp các dãy đuợc sắp thứ tự (a1, a2, …, an) trong đó ai ∈ Ai với i
= 1, 2, …, n.
A1× A2× … × An = {(a1, a2, … , an)| ai ∈ Ai với i = 1, 2, … n}
Lực lượng |A1× A2× … × An| = |A1| × |A2| × … × |An|
Ví dụ Cho A = {0, 1}, B = {1, 2}, C = {0, 1, 2} thì
A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1,
1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}.
11


1. 1. 9. Các hằng đẳng thức trên tập hợp
HẰNG ĐẲNG THỨC
A∪∅ =A,A∪U=A


TÊN GỌI
Luật đồng nhất

A ∪ U = U, A ∩ ∅ = ∅

Luật nuốt

A ∪ A = A, A ∩ A = A

Luật lũy đẳng

=A
A ∪ B = B ∪ A, A ∩ B = B ∪ A

Luật bù
Luật giao hoán

A ∪ (B ∪ C) = (A ∪ B) ∪ C

Luật kết hợp

(A)

A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∪ C)

Luật phân phối

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∪ B = A ∩ B,


A∩B =A∪ B

Luật De Morgan

Để chứng minh hai tập hợp bằng nhau ta thường dùng các kỹ thuật sau
- Chứng minh tập này là tập con của tập kia và ngược lại.
- Dùng cách chỉ rõ các thuộc tính đặc trưng và các tương đuơng logic.
Ví dụ Chứng minh A ∩ B = A ∪ B bằng cách chứng minh tập này là
con tập kia và ngược lại.
Hướng dẫn
∀ x, x ∈ A ∩ B ⇒ x ∉ A ∩ B ⇒ x ∉ A ∨ x ∉ B⇒ x ∈ A ∨ x ∈ B
⇒x ∈ A ∪ B⇒ A∩B ⊆A∪B
∀ x, x ∈ A ∪ B ⇒ x ∈ A ∨ x ∈ B ⇒ x ∉ A ∨ x ∉ B ⇒ x ∉ A ∩ B
⇒x∈A∩B⇒A∪B⊆A∩B
Vậy A ∩ B = A ∪ B
Ví dụ Dùng cách chỉ rõ các thuộc tính đặc trưng và các tương đuơng
logic chứng minh A ∩ B = A ∪ B
12


Hướng dẫn
A ∩ B = { x| x ∉ A ∩ B} = { x| ¬ ( x ∈ A ∩ B)}
= { x| ¬ (x ∈ A ∧ x ∈ B)}
= { x| x ∉ A ∨ x ∉ B}
= { x| x ∈ A ∨ x ∈ B}
= { x| x ∈ A ∪ B}
=A∪ B

13



1.2. HÀM SỐ
1.2.1 Định nghĩa hàm số
Cho A và B là hai tập khác rỗng. Một ánh xạ f từ A đến B là sự gán
chính xác một phần tử của B cho mỗi phần tử duy nhất của A.
Vậy để có một ánh xạ f phải có tập nguồn A, tập đích B đồng thời
không có phần tử nào của A không được gán với một phần tử của B và cũng
không có phần tử nào của A được gán với hai phần tử khác nhau của B.
Ký hiệu b = f(a) gọi là giá trị của f tại a.
Nếu f là một ánh xạ từ A đến B, ta viết f: A → B
Ta có thể nói “hàm f xác định trong A và lấy giá trị trong B” thay cho
cụm từ “f ánh xạ từ A đến B”. Tuy nhiên, hai từ ánh xạ và hàm không đồng
nhất. Ánh xạ xác định khắp nơi trên A còn hàm thì không nhất thiết nhưng
hàm luôn là một ánh xạ từ tập hợp xác định (miền xác định - nguồn) của nó
đến tập đích (miền giá trị).
Hàm số là ánh xạ từ tập số thực (tập con của tập số thực) vào tập số
thực

f ánh xạ từ A đến B
A được gọi là miền xác định của f.
B được gọi là miền giá trị của f.
Nếu ta nói b là ảnh của a và a là nghịch ảnh b.
14


Ảnh của A, ký hiệu f(A) là tập hợp tất cả các ảnh của các phần tử thuộc
A qua f. f(A) = { f(a)| a ∈ A}
Ví dụ
a) Giả sử f : Z → Z gán bình phương của một số nguyên cho số nguyên

đó. Khi đó f(x) = x2, f có miền xác định là Z, miền giá trị trong Z và miền ảnh
của Z là f(Z) = {1, 4, 9, ….}.
b) Cho f là hàm gán hai bit cuối cùng của một xâu bit chiều dài hai hoặc
lớn hơn tới xâu đó. Khi đó miền xác định của f là tập các xâu bit có chiều dài
hai hoặc lớn hơn còn miền giá trị của f là tập {00, 01, 10, 11}.
c) Trong Pascal cho khai báo Function floor (x: real): integer có nghĩa
hàm floor có miền xác định là R và miền giá trị là Z.
Định nghĩa
Cho f1 và f2 là hai hàm từ A đến R. Khi đó f1 + f2 và f1f2 cũng là các
hàm từ A đến R được định nghĩa bởi
(f1+ f2)(x) = f1(x) + f2(x)
(f1f2)(x) = f1(x)f2(x)
Ví dụ
Cho f1 và f2 là hai hàm từ R đến R sao cho f1(x) = x2 và f2(x) = x2 - x.
Xác định các hàm f1+ f2 và f1f2 ?
Hướng dẫn
(f1 + f2)(x) = f1(x) + f2(x) = x2 + (x2 - x) = 2x2 - x
(f1f2)(x) = f1(x)f2(x) = x2(x2 - x) = x4 - x3
1.2.2. Đơn ánh, toàn ánh, song ánh
Định nghĩa 1
15


Cho hàm f: A→ B, f đuợc gọi là đơn ánh nếu và chỉ nếu ∀ x, y ∈ A,
nếu x ≠ y thì f(x) ≠ f(y) (tương đương ∀x, y ∈ A , nếu f(x) = f(y) thì x = y).
Nói cách khác đơn ánh là ánh xạ mà không có hai phần tử nào của tập
nguồn được gán cho cùng một phần tử của tập đích.
Ví dụ
Các hàm f: Z → Z sau có phải là hàm đơn ánh không?
a) f(x) = x2

b) f(x) = x + 1
Hướng dẫn
Hàm f(x) = x2 không là đơn ánh vì f(-1) = f(1) mà 1 ≠ -1.
Hàm f(x) = x + 1 là đơn ánh vì x + 1 = y + 1 kéo theo x = y.
Định nghĩa 2
Cho hàm số f: A → B, f đuợc gọi là toàn ánh nếu và chỉ nếu ∀ b ∈ B
→ ∃ a ∈ A: f(a) = b (Một cách tương đương f(A) = B)
Ví dụ Các hàm f trong ví dụ trên có phải là toàn ánh không?
Hướng dẫn
F(x) = x2 không toàn ánh vì không có số nguyên nào cho x2 = -1.
F(x) = x + 1 toàn ánh vì với mọi số nguyên y tồn tại số nguyên x = y - 1
thỏa f(x) = x + 1 = (y - 1) + 1 = y.
Ví dụ
a
b
c

1
2

a

1

1

b

2


a
b

3

c

2

c

3

4

d

3

d

4

Đơn ánh, không toàn ánh

Toàn ánh, không đơn ánh
16

Đơn ánh và toàn ánh



Định nghĩa 3
Hàm f là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh.
Ví dụ Hàm f: Z → Z, f(x) = x + 1 là song ánh.
Ví dụ Xác định các hàm từ R đến R dưới đây có phải là song ánh?
a) f(x) = 2x +1
b) f(x) = x2 + 1
c) f(x) = x3
1.2.3. Hàm ngược
Cho f là song ánh từ tập A đến tập B. Hàm ngược của f là gán một phần
tử duy nhất a ∈ A cho mỗi phần tử b ∈ B sao cho f(a) = b, kí hiệu là f-1.
Vậy f-1(b) = a khi f(a) = b.

f là song ánh

Hàm ngược của f

Hàm song ánh còn gọi là hàm khả nghịch vì khi f song ánh thì mỗi
phần tử b = f(a) với b ∈ B đều là ảnh của một và chỉ một phần tử a ∈ A.
Như vậy có thể gán tương ứng mỗi phần tử b ∈ B với một phần tử a ∈
A. Phép gán đó xác định một ánh xạ từ B sang A, gọi là hàm ngược của hàm f
Ví dụ

17


Cho hàm f: Z → Z, f(x) = x + 1. Hàm f có khả nghịch không? Nếu có,
hãy tìm hàm ngược đó.
Hướng dẫn
Hàm f khả nghịch vì nó là song ánh.

f có hàm ngược là f-1(y) = y - 1 vì f(y - 1) = (y - 1) + 1 = y.

18


1.2.4. Hợp thành của các hàm
Cho hàm f từ tập A đến tập B và hàm g từ tập B đến tập C. Hợp thành
của các hàm f và g, đuợc ký hiệu là gof, đuợc định nghĩa bởi (gof)(a) = g(f(a))

Minh họa về hợp thành hai hàm
Ví dụ
Cho f và g là hai hàm từ Z đến Z với f(x) = 2x + 3 và g(x) = x – 1. Tìm
hợp thành fog và gof ?
Hướng dẫn
(fog)(x) = f(g(x)) = 2g(x) + 3 = 2(x - 1) + 3 = 2x + 1
(gof)(x) = g(f(x)) = f(x) – 1 = (2x + 3) – 1 = 2x + 2
1.2.5. Đồ thị của hàm
Cho f: X → Y. Đồ thị của hàm f là tập các cặp có thứ tự {(x, y)| x ∈ X,
y = f(x)}
1.2.6. Một số hàm quan trọng
Hàm sàn (hay hàm phần nguyên) gán giá trị x số nguyên lớn nhất có
giá trị nhỏ hơn hay bằng x. Giá trị hàm sàn ký hiệu là ⎣x⎦ (hay [x] )
Hàm trần (hàm sàn trên) gán giá trị x số nguyên nhỏ nhất có giá trị lớn
hơn hay bằng x. Giá trị hàm trần ký hiệu là x
Ví dụ [1,3] = 1, ⎣1,3⎦ = 1, -0.5 = 0.
19


1.2.7. Dãy và phép tính tổng
1.2.7.1. Dãy

Dãy là một cấu trúc rời rạc biểu diễn một bảng liệt kê sắp thứ tự
Định nghĩa 1
Một dãy là một ánh xạ từ một tập con của tập hợp các số nguyên tới tập
S. Ký hiệu {an}
Ký hiệu an để chỉ ảnh của số nguyên n; an đuợc gọi là số hạng của dãy.
Ví dụ
a) Xét dãy {an}, trong đó an =
Bảng liệt kê các số hạng của dãy từ a1, a2, a3, … là: 1, , , …
b) Xét dãy {bn}, trong đó bn = (-1)n
Bảng liệt kê các số hạng của dãy từ b1, b2, b3,… là: -1, 1, -1, …
Định nghĩa 2
Một cấp số nhân là dãy có dạng a, ar, ar 2, …, arn, trong đó số hạng đầu
a và công bội r là các số thực.
Cấp số nhân là các giá trị tương tự của hàm mũ f(x) = ar x với các giá trị
rời rạc của đối số
Định nghĩa 3
Một cấp số cộng là dãy có dạng a, a + d, a + 2d, …, a + nd, trong đó số
hạng đầu a và công sai d là các số thực
Cấp số cộng là các giá trị rời rạc của hàm tuyến tính f(x) = dx + a
Các dãy hữu hạn có dạng a1 , a2, …, an còn được gọi là xâu và ký hiệu
a1a2 … an ; độ dài của xâu S là số các số hạng trong xâu đó, xâu rỗng có độ dài
là 0.
1.2.7.2. Phép tính tổng
20


n

Ta dùng ký hiệu ∑ aj để biểu diễn tổng (am + am+1 + … +an)
J=m


j được gọi là chỉ số lấy tổng.
m là giới hạn dưới
n là giới hạn trên.
Ví dụ Biểu diễn của 100 số hạng đầu tiên của dãy {an} với an = và n =
1, 2, 3, … là
100

∑ ()

J=1
5

Ví dụ Xác định giá trị của dãy ∑ j2
J=1

Hướng dẫn

5

∑ j2 = 12 + 22 + 32 + 42 + 52 = 55
j=1

1.2.8. Khái niệm Big - O
Độ tăng của hàm thường được mô tả bằng cách dùng một khái niệm
đặc biệt được định nghĩa: Cho f và g là hai hàm từ Z (hay R) vào R. Ta nói
hàm f(n) có cấp thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số C > 0 và một
số tự nhiên n0 sao cho |f(n)| ≤ C|g(n)| ∀ n ≥ n0.
Ta viết f(n) = O(g(n)) và nói f(n) thoả mãn quan hệ big - O đối với g(n).
Nghĩa là nếu xét những giá trị n ≥ n 0 thì hàm f(n) sẽ bị chặn trên bởi

một hằng số nhân với g(n).
Ví dụ Chứng minh f(x) = x2 + 2x + 1 là O(x2)
Hướng dẫn
21


Vì 0 ≤ x2 + 2x + 1 ≤ x2 + 2x2 + x2 = 4x2
∀ x > 1 (lấy C = 4 và k = 1), từ đó suy ra f(x) là O(x2).
Ví dụ Chứng minh 7x2 là O(x3)
Hướng dẫn
Dễ thấy bất đẳng thức 7x2 < x3 đúng với mọi x > 7 (chọn C = 1, k = 7)
. Do đó 7x2 là O(x3).
Trong Tin học khái niệm Big - O được dùng để đánh giá độ phức tạp về
thời gian của một thuật toán.
Định lý Cho f (x) = an xn + an-1 xn-1 + … + a1 x + a0. Ở đây a0, a1, … , an
là các số thực. Khi đó f(x) là O(xn)
Chứng minh ∀x > 1, ta có
|f(x)| = |an xn + an-1 xn-1 + … + a1 x + a0|
≤ |an| xn + |an-1| xn-1 + … + |a1| x + |a0|

= xn ( |an| +

|an-1|
x

+…+

|a1|
xn-1


+

|a0|

)

xn

≤ xn (|an| + |an-1|+ … + |a1| + |a0|)
Điều này chứng tỏ rằng |f (x)| ≤ Cxn
Với C = |an| + |an-1|+ … + |a1| + |a0| với x > 1. Vậy f(x) là O(xn)
Ví dụ Dùng khái niệm big - O đánh giá tổng n số nguyên dương đầu
tiên

22


Hướng dẫn
Ta có 1 + 2 + 3 + … + n ≤ n + n + … + n = n2
Suy ra 1 + 2 + … + n là O(n2), khi lấy C = 1 và k = 1.
Ví dụ Chỉ ra hàm n! là O(nn ) và log n! là O(nlogn)
Hướng dẫn
Ta có n! = 1. 2 … n ≤ n. n … n = nn
Vậy n! là O(nn)
Log n! ≤ log (nn) = nlogn
Vậy log n! là O(nlogn)

23



1.3. CÁC PHƯƠNG PHÁP ĐẾM TRÊN TẬP HỢP
Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên
nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần
tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất
định nào đó. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp.
Liệt kê, đếm các đối tượng có những tính chất nào đó là một phần quan
trọng của lý thuyết tổ hợp. Chúng ta cần phải đếm các đối tượng để giải nhiều
bài toán khác nhau. Hơn nữa các kỹ thuật đếm được dùng rất nhiều khi tính
xác suất của các biến cố, xác định độ phức tạp tính toán của thuật toán.
1.3.1. Những nguyên lý đếm cơ bản
1.3.1.1. Quy tắc cộng
Giả sử có k công việc T1, T2, ..., Tk. Các việc này có thể làm tương
ứng bằng n1, n2, ..., nk cách và giả sử không có hai việc nào có thể làm đồng
thời. Khi đó số cách làm một trong k việc đó là n1+ n2+ ... + nk.
Cơ sở cuả quy tắc cộng là một trong các công thức sau
|A ∪ B| = |A|+ |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C|
- |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Trường hợp giữa k công việc có m cách làm đồng thời thì ta có n 1+
n2+ ... + nk – m cách để làm k công việc trên.
Ví dụ
1)

Một sinh viên có thể chọn bài thực hành máy tính từ một trong ba danh sách

2)

tương ứng có 23, 15 và 19 bài.
Theo quy tắc cộng có 23 + 15 + 19 = 57 cách chọn bài thực hành.
Trong lớp CNTT có 45 sinh viên biết tiếng Anh, 30 sinh viên biết tiếng Pháp,


a)

10 sinh viên biết cả Anh và Pháp.
Tính số sinh viên của lớp, biết trong lớp không có sinh viên nào không biết
một trong 2 thứ tiếng trên.
24


b)

Cho sỉ số lớp là 70, hỏi có bao nhiêu sinh viên không biết tiếng Anh,
Pháp

Hướng dẫn
Đặt A là số SV biết tiếng Anh |A| = 45;
B là số SV biết tiếng Pháp |B| = 30;
A ∩ B là số SV biết cả tiếng Anh và Pháp |A ∩ B| = 10;
Số sinh viên của lớp là số sinh viên biết tiếng Anh hoặc Pháp A ∪ B
Theo công thức cơ sở ta có |A ∪ B| = | A |+ |B| - |A ∩ B|
= 45 + 30 – 10 = 65
Số sinh viên không biết tiếng Anh, Pháp 70 – 65 = 5
3) Giá trị của biến m bằng bao nhiêu sau khi đoạn chương trình sau được thực
hiện?
m: = 0
for i1: = 1 to n1
m: = m + 1
for i2: =1 to n2
m: = m + 1
.......................

for ik: = 1 to nk
m: = m + 1
Giá trị khởi tạo của m bằng 0. Khối lệnh này gồm k vòng lặp khác
nhau. Sau mỗi bước lặp của từng vòng lặp giá trị của m được tăng lên một
đơn vị. Gọi Ti là việc thi hành vòng lặp thứ i. Có thể làm T i bằng ni cách vì
vòng lặp thứ i có ni bước lặp. Do các vòng lặp không thể thực hiện đồng thời
nên theo quy tắc cộng, giá trị cuối cùng của m bằng số cách thực hiện một
trong số các nhiệm vụ Ti, tức là m = n1+ n2+ ... + nk.
25