Một sốkiếnthức cơbản
Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 1
Nội dung
Lý thuyết tập hợp
Logic mệnh đề
Logic vị từ
Thuật toán và độ phức tạp
Bài tập
http://www.ptit.edu.vn2
Một sốký hiệu tập hợp
http://www.ptit.edu.vn3
Tập hợp: 𝐴,𝐵,…,𝑋,𝑌,…
Phần tử của tập hợp: 𝑎,𝑏,…,𝑥,𝑦,…
Phần tử 𝑥thuộc (không thuộc) 𝐴: 𝑥 ∈ 𝐴, 𝑥 ∉ 𝐴
Số phần tử của tập hợp 𝐴: |𝐴|
oMột tập hợp có 𝑛phần tử được gọi là một 𝑛-tập
Tập hợp con: 𝐴 ⊆ 𝐵
o𝑥 ∈ 𝐴 ⇒ 𝑥 ∈ 𝐵
Tập hợp bằng nhau: nếu 𝐴 ⊆ 𝐵 và 𝐵 ⊆ 𝐴 thì 𝐴 = 𝐵
Tập rỗng: ∅
oKhông có phần tử nào
oLà con của mọi tập hợp
Các phép toán trên tập hợp
http://www.ptit.edu.vn4
Phần bù của 𝐴trong 𝑋: ҧ
𝐴 = 𝑥 ∈ 𝑋|𝑥 ∉ 𝐴
Hợp của hai tập hợp: 𝐴∪𝐵 = 𝑥|𝑥 ∈ 𝐴ℎ𝑜ặ𝑐 𝑥 ∈ 𝐵
Giao của hai tập hợp: 𝐴∩𝐵 = {𝑥|𝑥 ∈ 𝐴𝑣à𝑥 ∈ 𝐵}
Hiệu của hai tập hợp:𝐴 ∖B = {𝑥|𝑥 ∈ 𝐴𝑣à𝑥 ∉ 𝐵}
Luật kết hợp:
Luật giao hoán: 𝐴∪𝐵 = 𝐵 ∪𝐴,𝐴 ∩𝐵 = 𝐵 ∩𝐴
Luật phân bố:
Luật đối ngẫu:𝐴∪𝐵 = ҧ
𝐴∩ ത
𝐵,𝐴 ∩𝐵 = ҧ
𝐴∪ ത
𝐵
Tích Đề các: 𝐴 ×𝐵 = {(𝑎,𝑏)|𝑎 ∈ 𝐴,𝑏 ∈ 𝐵}
𝐴∪𝐵 ∪𝐶 = 𝐴∪ 𝐵 ∪𝐶
𝐴∩𝐵 ∩𝐶 = 𝐴∩ 𝐵 ∩𝐶
𝐴∪ 𝐵 ∩𝐶 = (𝐴∪𝐵)∩ 𝐴∪𝐶
𝐴∩(𝐵 ∪𝐶) = (𝐴∩𝐵)∪(𝐴∩𝐶)
Quan hệ
http://www.ptit.edu.vn5
Quan hệ: một quan hệ hai ngôi 𝑅trên tập 𝑋, 𝑅(𝑋), là
một tập con của tích Đề các 𝑋 ×𝑋
Tính chất của quan hệ:
oPhản xạ: mọi phần tử có quan hệ với chính nó
oĐối xứng: 𝑎có quan hệ với 𝑏kéo theo 𝑏có quan hệ với 𝑎
oKéo theo: 𝑎có quan hệ với 𝑏và 𝑏có quan hệ với 𝑐kéo theo 𝑎
có quan hệ với 𝑐
Ví dụ
o𝑋 = 1,2,3,4
o𝑎,𝑏 ∈ 𝑋,𝑎 có quan hệ 𝑅đối với 𝑏nếu 𝑎chia hết cho 𝑏
o𝑅 𝑋 = { 1,1 , 2,1 , 2,2 , 3,1 , 3,3 , 4,1 , 4,2 ,(4,4)}
Phản xạ, kéo theo, nhưng không đối xứng