Ktl-icon-tai-lieu

Lý thuyết thông tin phần 1

Được đăng lên bởi Duy Khanh
Số trang: 5 trang   |   Lượt xem: 193 lần   |   Lượt tải: 0 lần
• Tập hợp

•

1, 2, 3

•

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

• Quan hệ
• Phép chứng minh quy nạp
• ðồ thị và cây
1

3

Phần tử

•
•
•

• Ký hiệu: ∅ hoặc

Mon, Tue, Wed, Thu, Fri, Sat, Sun
Tập các ñối tượng rời rạc
Không trùng lắp

• Ký hiệu:

⊂

(Ngược lại:

⊄

)

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

• Tập hợp là tập các ñối tượng không
có sự lặp lại
Printed with FinePrint - purchase at 

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

4

:
• Ký hiệu:

(Ngược lại:

≠

• A \ B = { x | x ∈ A nhưng x ∉ B }

)

• { 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 } ≠ { 2, 1 }
• A x B = { (a,b) | a ∈ A và b ∈ B }

• Ký hiệu:

A

:

A

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

:

7

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

• A’ = { x | x ∉ A }

• A∩B={2}

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

• A\B={1}
• A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) }
• 2A = { ∅, {1}, {2}, {1, 2} }

• A ∩ B = { x | x ∈A và x ∈ B }
6

Printed with FinePrint - purchase at 

8

S

∀a∈
∈S

( A × B ) = aRb

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

nếu aRb và bRc thì

)

(

e

g

r

a
n

i

✟
r

g

t

á

✂
i

n

i
a

n

m

×

m

)

(
d

o

✟

h

ñ

n

c
x

n

m

i

á

✂

nếu aRb thì bRa
aRc
:
• L không là quan hệ phản xạ hay ñối xứng
9

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

11

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) }
• Quan hệ ‘chẵn lẻ’
= { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)}
10

Printed with FinePrint - purchase at 

12

∪

2

1

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

• 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
• Nếu a ∈ Si và b ∈ Sj thì a b sai
P có 2 lớp tương ñương {0, 2} và {1, 3}

13

15

chứng minh
+

giả sử
⇒
• Nếu (a,b) ∈ R thì (a,b) ∈R

∀

≥

+

n

2
i
=
∑
chứng minh

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

+

i =0

• Không còn gì thêm trong R+
• R* = R+ ∪ { (a, a)  a ∈ S }
Printed with FinePrint - purchase at 

14

n (n + 1)(2n + 1)
6

16

là ñồ thị có hướng
• V : tập các ñỉnh (nút)

• 1 nút gốc

• E : tập các cạnh nối giữa 2 nút

• Nút trung gian (nút trong)
• Nút lá: không dẫn ra nút con

ñồ thị G = (V, E)
• V = { 1, 2, 3, 4, 5 }

→

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

• ...
1
Tập hợp
Quan hệ
Phép chứng minh quy nạp
ðồ thị và cây
2
Mon, Tue, Wed, Thu, Fri, Sat, Sun
Tập hợp tập các ñối tượng không
có sự lặp lại
Tập các ñối tượng rời rạc
Không trùng lắp
Phần tử
3
1, 2, 3
x x một ngày trong tuần
4
Ký hiệu:
hoặc
hiệu:
(Ngược lại:
)
{ 1, 2, 4 }
{ 1, 2, 3, 4, 5 }
{ 2, 4, 6 }
{ 1, 2, 3, 4, 5 }
Printed with FinePrint - purchase at www.fineprint.com
Lý thuyết thông tin phần 1 - Trang 2
Lý thuyết thông tin phần 1 - Người đăng: Duy Khanh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
5 Vietnamese
Lý thuyết thông tin phần 1 9 10 329