Quan hệ hai ngôi và một số bài toán liên quan

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

---------------------------

BÙI THỊ THU THỦY

QUAN HỆ HAI NGÔI

VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

---------------------------

BÙI THỊ THU THỦY

QUAN HỆ HAI NGÔI

VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 8 46 01 13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Trần Nguyên An

THÁI NGUYÊN - 2019

Möc löc

Mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Ch÷ìng 1. Ki¸n thùc chu©n bà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Quan h» hai ngæi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. ¤i sè tê hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Ch÷ìng 2. Quan h» hai ngæi v  mët sè b i to¡n . . . . . . . . . . . . . 15

2.1. ¸m mët sè quan h» hai ngæi °c bi»t . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. nh x¤ v  mët sè b i to¡n li¶n quan. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3. Ph¥n ho¤ch, sè Stirling lo¤i hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4. ¸m sè quan h» t÷ìng ÷ìng v  quan h» hai ngæi b­c c¦u . . . . . . 32

K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

i

Mð ¦u

Cho A, B l  c¡c tªp hñp. Mët quan h» hai ngæi tø tªp A ¸n tªp B

l  mët tªp con cõa tªp t½ch · c¡c A × B. °c bi»t, mët quan h» hai ngæi

tø A ¸n A ÷ñc gåi l  mët quan h» hai ngæi tr¶n A. N¸u R l  mët quan

h» hai ngæi tr¶n tªp A v  (a, b) ∈ R th¼ ta k½ hi»u aRb (åc l  a câ quan

h» R vîi b). Quan h» hai ngæi xu§t hi»n trong nhi·u ng nh kh¡c nhau cõa

to¡n håc: ¤i sè, Sè håc, H¼nh håc, Lþ thuy¸t ç thà, Khoa håc m¡y t½nh,

.... Mët tr÷íng hñp °c bi»t cõa quan h» hai ngæi. C¡c quan h» hai ngæi iºn

h¼nh trong ch÷ìng tr¼nh phê thæng l  "quan h» chia h¸t", "quan h» çng

d÷", "quan h» lîn hìn", "quan h» song song", h m sè, .... Ta th÷íng quan

t¥m ¸n c¡c t½nh ch§t sau cõa quan h» hai ngæi ph£n x¤ (reflexive), èi xùng

(symmetric), b­c c¦u (transitive), b§t èi xùng (asymmetric), ph£n èi xùng

(antisymmetric), b§t ph£n x¤ (irreflexive). Möc ½ch ch½nh cõa luªn v«n l 

t¼m hiºu mët sè b i to¡n tê hñp v· quan h» hai ngæi. T i li»u ch½nh cõa luªn

v«n l  gi£i mët sè b i tªp trong [7], [2] v  b i b¡o [6].

Luªn v«n ÷ñc chia l m hai ch÷ìng. Ch÷ìng 1 tr¼nh b y mët sè ki¸n

thùc chu©n bà v· lþ thuy¸t quan h» hai ngæi, quan h» t÷ìng ÷ìng, quan h»

thù tü, ¡nh x¤ v  mð ¦u v· lþ thuy¸t tê hñp. Tuy l  ki¸n thùc chu©n bà cho

Ch÷ìng 2 nh÷ng èi vîi t¡c gi£ nhi·u ki¸n thùc cõa ch÷ìng l  ki¸n thùc mîi

v  câ nhi·u ùng döng trong gi£i to¡n phê thæng. Ch÷ìng n y chõ y¸u tham

kh£o theo c¡c t i li»u [1, 2].

Ch÷ìng 2 theo t i li»u [6, 7] l  ch÷ìng ch½nh cõa luªn v«n tr¼nh b y

v· mët sè b i to¡n li¶n quan ¸n quan h» hai ngæi. B­t ¦u l  b i to¡n ¸m

mët sè quan h» hai ngæi °c bi»t. Công c¦n ph£i nâi th¶m r¬ng quan h» hai

ngæi xu§t ph¡t tø nhúng v§n · trong to¡n sì c§p nh÷ "lþ thuy¸t chia h¸t",

"lþ thuy¸t çng d÷" nh÷ng v¼ khuæn khê cõa luªn v«n t¡c gi£ ch¿ khai th¡c

mët sè b i to¡n sì c§p li¶n quan ¸n b i to¡n tê hñp. Mët l÷u þ cõa luªn

1