•

1, 2, 3

• Tập hợp

• Quan hệ

•

x x là một ngày trong tuần

• Phép chứng minh quy nạp

• ðồ thị và cây

1

3

Phần tử

•

• Ký hiệu: ⊂⊂⊂⊂ (Ngược lại: ⊄⊄⊄⊄ )

• Tập các ñối tượng rời rạc • Không trùng lắp

Mon, Tue, Wed, Thu, Fri, Sat, Sun • Ký hiệu: ∅∅∅∅ hoặc

• { 1, 2, 4 } ⊂⊂⊂⊂ { 1, 2, 3, 4, 5 }

• { 2, 4, 6 } ⊄⊄⊄⊄ { 1, 2, 3, 4, 5 }

• Tập hợp là tập các ñối tượng không

2

4

có sự lặp lại

Printed with FinePrint - purchase at www.fineprint.com

:

• A \ B = { x | x ∈ A nhưng x ∉∉∉∉ B } (Ngược lại: ≠≠≠≠ )

• Ký hiệu: • { 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 } ≠≠≠≠ { 2, 1 }

A

: • A x B = { (a,b) | a ∈ A và b ∈ B }

• Ký hiệu:

A = {∅∅∅∅, {1}, {2}, {3}, {1, 2},

• A = { 1, 2, 3 } thì

5

7

{2, 3}, {3, 1}, {1, 2, 3} }

:

cho A = {1, 2} và B = {2, 3}

• A ∪ B = { 1, 2, 3 } • A’ = { x | x ∉∉∉∉ A }

• A ∩ B = { 2 } :

• A \ B = { 1 } • A ∪∪∪∪ B = { x | x ∈∈∈∈ A hoặc x ∈∈∈∈ B }

6

8

Printed with FinePrint - purchase at www.fineprint.com

• A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) } • 2A = { ∅, {1}, {2}, {1, 2} } • A ∩ B = { x | x ∈A và x ∈ B }

nếu aRa là ñúng với

S

∀∀∀∀a∈∈∈∈S

( A × B ) = aRb

nếu aRb thì bRa

(cid:2)

(cid:2)

(

)

)

(

á

á

(cid:8)

i

i

i

i

(cid:8)

t

d

ñ

h

r

r

c

e

a

an

g

o

n

g

n

n

n

m

m

m

x

××××

nếu aRb và bRc thì

aRc

:

• L không là quan hệ phản xạ hay ñối xứng

9

11

• E và P mang tính phản xạ, ñối xứng và bắc cầu

cho S = {0, 1, 2, 3}

• Quan hệ ‘thứ tự nhỏ hơn’

= { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) }

• E và P là quan hệ tương ñương • Quan hệ ‘bằng’

• L không là quan hệ tương ñương = { (0, 0), (1, 1), (2, 2), (3, 3) }

= { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)}

10

12

Printed with FinePrint - purchase at www.fineprint.com

• Quan hệ ‘chẵn lẻ’

R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3}

1 ∪∪∪∪ 2 ∪∪∪∪

• R+ = { (1, 2), (2, 2), (2, 3), (1, 3) }

• R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) }

• Si ∩ Sj = ∅∅∅∅

• Nếu a, b cùng thuộc Si thì a b ñúng

13

15

• Nếu a ∈∈∈∈ Si và b ∈∈∈∈ Sj thì a b sai

P có 2 lớp tương ñương {0, 2} và {1, 3}

chứng minh

+

giả sử

⇒⇒⇒⇒ ∀∀∀∀ ≥≥≥≥

n

• Nếu (a,b) ∈ R thì (a,b) ∈R+

+

+

2

=∑ i

chứng minh

)1n2)(1n(n 6

= 0i

• Nếu (a,b) ∈∈∈∈ R+ và (b,c) ∈∈∈∈ R thì (a,c) ∈∈∈∈ R+ • Không còn gì thêm trong R+

14

16

Printed with FinePrint - purchase at www.fineprint.com

• R* = R+ ∪ { (a, a)  a ∈ S }

là ñồ thị có hướng

• 1 nút gốc • V : tập các ñỉnh (nút)

• Nút trung gian (nút trong) • E : tập các cạnh nối giữa 2 nút

(cid:4)(cid:4)(cid:4)(cid:4)

(cid:1)(cid:1)(cid:1)(cid:1)

• V = { 1, 2, 3, 4, 5 }

ñồ thị G = (V, E) • Nút lá: không dẫn ra nút con

• E = { (n, m) | n+m = 4 hoặc n+m = 7}

(cid:3)(cid:3)(cid:3)(cid:3)

(cid:2)(cid:2)(cid:2)(cid:2)

(cid:5)(cid:5)(cid:5)(cid:5)

17

19

• Thứ tự duyệt trên cây: →→→→

cây minh họa cấu trúc cú pháp câu ‘An là

â

C

ñ

u

n

ơ

sinh viên giỏi’

Chủ ngữ

Vị ngữ

• V : tập các ñỉnh (nút) • E : tập các cung có hướng →→→→

Danh từ

ðộng từ

Bổ ngữ

ñồ thị G = (V, E)

Danh từ

Tính từ

à

ê

(cid:15)

A

l

i

i

i

i

h

n

s

v

n

n

g

18

20

Printed with FinePrint - purchase at www.fineprint.com

• V = { 1, 2, 3, 4 } • E = { i → j  i < j }