Bài giảng Toán rời rạc Phần 1

TOÁN HỌC RỜI RẠC
PHẦN 1
DISCRETE MATHEMATICS
PART ONE
NỘI DUNG ÔN TẬP
PHẦN 1
CƠ SỞ LOGIC
Phép tính mệnh đề & vị từ
Quy tắc suy luận. Quy nạp
ĐẠI SỐ BOOL
Quan hệ thứ tự & tập hợp được sắp
Dàn và đại số bool
Hàm bool
Phương trình bool & hệ phủ tối tiểu
Công thức tối tiểu của hàm bool
PHẦN 2
PHÉP ĐẾM
Nguyên lý cộng, nhân & bù trừ
Giải tích tổ hợp
Nguyên lý Dirichlet
Công thức đệ quy
2
NỘI DUNG ÔN TẬP (cont.)
LÝ THUYẾT ĐỒ THỊ
Đại cương
Đồ thị liên thông
Đường đi ngắn nhất
Cây khung trọng lượng tối tiểu
Luồng cực đại
SỐ HỌC
Lý thuyết chia hết
Lý thuyết đồng dư
3
CƠ SỞ LOGIC (1)
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Mệnh đề
Chân trị của mệnh đề: đúng, sai (true, false)
Các phép toán mệnh đề
Phép phủ định (NOT, ¬, …)
Phép hội (AND, )
Phép tuyển: (OR, )
Phép tuyển loại trừ (XOR, )
Phép toán trên bit
Phép kéo theo: 
Phép tương đương: 
Biểu thức mệnh đề
Mệnh đề hệ quả & mệnh đề tương đương
Hằng đúng (tautology), hằng sai
Tiếp liên
Mệnh đề hệ quả: P  Q hằng đúng
Tương đương logic: P  Q hằng đúng
4
CƠ SỞ LOGIC (2)
Các tương đương thường dùng (T=hằng đúng, F=hằng sai)





5
CƠ SỞ LOGIC (3)
Vị từ
Vị từ P: E  {0, 1}
Không gian của một vị từ: E = E1xE2x…xEn
Trọng lượng của một vị từ: n
Các phép toán vị từ: , , , …
Các lượng tử
¬ ( X: P(X)) =  X: ¬P(X)
¬ ( X: P(X)) =  X: ¬P(X)
6
CƠ SỞ LOGIC (4)
QUY TẮC SUY LUẬN
Các quy tắc suy luận:
7
CƠ SỞ LOGIC (5)
Các phương pháp chứng minh: P  Q
Chứng minh rỗng (P = false)
Chứng minh tầm thường (Q = true)
Chứng minh trực tiếp (P = true kéo theo Q = true)
Chứng minh gián tiếp (Chứng minh ¬Q  ¬P đúng)
Chứng minh phản chứng (Chứng minh ¬Q  P  False)
Chứng minh quy nạp
8
ĐẠI SỐ BOOL (1)
QUAN HỆ
Quan hệ tương đương
Def: (phản xạ, đối xứng, bắc cầu)
Lớp tương đương
Tập thương
Quan hệ thứ tự
Def: (phản xạ, phản xứng, bắc cầu) (E, )
Trội, trội trực tiếp, sơ đồ Hasse
Quan hệ thứ tự toàn phần, bộ phận
Phần tử
tối đại: MA  E, x A: M  x  x=M
tối tiểu: m A  E, x A: x  m  x=M
phần tử lớn nhất: MA  E, x A: x  M
phần tử nhỏ nhất: mA  E, x A: m  x
9
ĐẠI SỐ BOOL (2)
DÀN (LATTICE)
Cận trên: (E, ), x, y  E, A={z| x  z, y  z}, nếu A có phần tử nhỏ nhất thì phần tử nhỏ nhất đó được gọi là cận trên (đúng), ký hiệu sup(x, y) / xy
cận dưới: (E, ), x, y  E, A={z| z  x, z  y}, nếu A có phần tử lớn nhất thì phần tử lớn nhất đó được gọi là cận dưới (đúng), ký hiệu inf(x, y) / xy / xy
Dàn: (E, ), x, y  E,  sup(x, y) = xy, inf(x, y)=xy
Các tính chất (giao hoán, kết hợp, phân phối)
Phần tử bù: (E, )-dàn có phần tử lớn nhất ký hiệu 1, phần tử nhỏ nhất ký hiệu 0,
x  E phần tử bù của x (trong E) là phần tử, ký hiệu sao cho



Dàn mà mọi phần tử đều có phần tử bù được gọi là dàn bị bù
10
ĐẠI SỐ BOOL (3)
ĐẠI SỐ BOOL
Def1: dàn (E, ) có nhiều hơn một phần tử , là dàn phân phối và bị bù
Def2: (E, , ) kết hợp, giao hoán, phân phối, có phần tử trung hòa và phần tử bù
Định lý Stone
Atom: phần tử trội trực tiếp của phần tử nhỏ nhất
(E, ) là một đại số bool hữu hạn với phần tử nhỏ nhất ký hiệu là 0, x  0 E, a1, a2, …, ak là tất cả các atom bị trội bởi x khi đó:
x=a1  a2  …  ak
cách viết này là duy nhất nếu không kể đến thự tự của các atom
Số phần tử của một đại số bool là lũy thừa của 2
Đại số bool gồm 2n phần tử có n atom
11
HÀM BOOL (1)
HÀM BOOL
B=({0, 1}, , ) là một đại số bool
f : Bn  B

f tương ứng với một dãy nhị phân độ dài 2n (dãy các giá trị của f trên các bộ biến 0…00, 0…01, 0…10, …)
đánh chỉ số cho f bởi dãy nhị phân các giá trị của hàm f
Fn = tập tất cả các hàm bool n biến
f, g Fn , f ≤ g khi và chi khi X  Bn : f(X) ≤ g(X)
(Fn, ≤) là một đại số bool

12
HÀM BOOL (2)
DẠNG CHUẨN TẮC TUYỂN
Fn tập các hàm bool n biến
Từ tối tiểu (nguyên tử-Atom): 00..010..0
f là hàm bool, m1, m2, …, mk là tất cả các từ tối tiểu bị trội hơn bởi f, ta có: f=m1m2…mk
Literal:


Dạng chuẩn tắc tuyển của hàm bool f (n biến):
Lập bảng giá trị hàm f
Phân tích f thành tổng của các từ tối tiểu: f=m1  m2  …  mk
mi(b1, b2, …, bn) = 1,
13
HÀM BOOL (3)
DẠNG CHUẨN TẮC HỘI
Từ tối đại: 11…101…1
M là từ tối đại, M(b1, b2, …, bn)=0


Dạng chuẩn tắc hội của hàm f (n biến):
Lập bảng giá trị của f
Phân tích f thành tích các từ tối đại: f=M1M2…Mk
Mi(b1, b2, …, bn)=0

14
HÀM BOOL (4)
HỆ PHƯƠNG TRÌNH BOOL & PHỦ TỐI TIỂU
HỆ PHƯƠNG TRÌNH BOOL:
G1, G2, …, Gk, D1, D2, …, Dk là 2n hàm bool n biến x1, x2, …, xn
Hệ phương trình bool



Phương pháp giải
Biến đổi mỗi phương trình về dạng tổng của các tích
Áp dụng biến đổi tương đương G=D  1=GD¬G¬D, biến đổi hệ về dạng




Hệ tương đương với: 1=(G1D1¬G1¬D1)…(GkDk¬Gk¬Dk)
15
HÀM BOOL (5)
Biến đổi phương trình về dạng tổng của các tích: 1=h1  h2  …  hm (hi là tích của các biến hoặc phủ định của biến
Phương trình tương đương với tuyển




Do mỗi hi là tích các biến hoặc phủ định của biến, ta suy ra các nghiệm của hệ phương trình
PHỦ TỐI TIỂU
Cho tập hợp E, e1, e2, …, en là các phần tử của E, A1, A2, …, Ap là các tập con của E, { Ai | i=1,…, p}  {e1, e2, …, en}. Tìm họ con của họ {Ai} (phủ tối tiểu) sao cho:
Hợp các tập của họ con này chứa {e1, e2, …, en}
Bỏ đi một tập bất kỳ của họ con thì hợp của các tập còn lại không còn chứa {e1, e2, …, en}
Phương pháp giải:
Đặt xi là biến sao cho nếu Ai được chọn  xi = 1
ej / Aj1, Aj2, …, Ajq là tất cả các tập của họ chứa ej, ta xây dựng được phương trình: xj1  xj2 …  xjq = 1
Giải hệ phương trình ta tìm được phủ tối tiểu
16
ĐƠN GIẢN CÔNG THỨC (1)
CÔNG THỨC TỐI TIỂU
Đơn thức:
tích của các literals khác 0 (nhân tử nguyên tố)
Đơn thức = 0  tồn tại x bù của x trong đơn thức
Tồn tại duy nhất một cách viết đơn thức (sai khác thứ tự của các literals)
Tập Fn có 3n đơn thức
Ước
Đơn thức m là ước của đơn thức M (M chia hết cho m) nếu mỗi nhân tử nguyên tố của m đều là nhân tử nguyên tố của M
Đơn thức m là ước của M  M ≤ m
m là ước của M  m  M = m
Công thức dạng đa thức:
f  Fn , cách viết f dưới dạng tổng (  ) của các đơn thức được gọi là dạng đa thức của f: , mk là các đơn thức
Công thức dạng đa thức tối giản:
& i  j, mi không là ước của mj
17
ĐƠN GIẢN CÔNG THỨC (2)
Quan hệ đơn giản hơn:
hai công thức tối giản của f:
f=m1  m2  …  mp (1)
f=M1  M2  … Mq (2)
được gọi là đơn giản hơn (2) khi và chỉ khi:
p < q
i: mi là ước của ít nhất một Mj
Mỗi hàm bool f có một tập hợp hữu hạn công thức tối giản dạng đa thức và
quan hệ đơn giản hơn là một quan hệ thứ tự bộ phận trên tập đó
Công thức dạng tối tiểu dạng đa thức:
Công thức tối tiểu dạng đa thức của một hàm bool f là phần tử tối tiểu của tập
các công thức tối giản dạng đa thức của f
18
ĐƠN GIẢN CÔNG THỨC (3)
19
Sắp xếp các phần tử của B3 vào bảng karnaugh
Sắp xếp các phần tử của B4 vào bảng karnaugh
PHƯƠNG PHÁP KARNAUGH
Bảng Karnaugh





ĐƠN GIẢN CÔNG THỨC (4)
Sơ đồ karnaugh của hàm 3 hoặc 4 biến

20
hàm bool 3 biến f = 00110110
Hàm bool 4 biến f =0100110100000011
ĐƠN GIẢN CÔNG THỨC (5)
Định lý:
Sơ đồ karnaugh của
hàm đồng nhất 0 là bảng rỗng
hàm đồng nhất 1 là bảng có tất cả các ô dược « tô »
f ≤ g tương đương với sơ đồ karnaugh của g phủ sơ đồ karnaugh của f
Sơ đồ karnaugh của tích fg là giao của sơ đồ karnaugh của f và sơ đồ karnaugh của g
Sơ đồ karnaugh của tổng fg là hợp của sơ đồ karnaugh của f và sơ đồ karnaugh của g
Sơ đồ karnaugh của là sơ đồ « bù » của sơ đồ karnaugh của f (trong sơ đồ karnaugh của f: xoá các ô được tô, tô các ô không được tô)
Sơ đồ karnaugh của mỗi từ tối tiểu chỉ có một ô được tô
Sơ đồ karnaugh và dạng chuẩn tắc của hàm tương ứng


21
Dạng chuẩn tắc của hàm tương ứng là:
ĐƠN GIẢN CÔNG THỨC (6)
Sơ đồ karnaugh và đơn thức
Định lý: trong Fn, một đơn thức do p nhân tử nguyên tố tạo thành, sơ đồ karnaugh của nó có 2n-p ô được tô. Sơ đồ karnaugh có hình chữ nhật gồm 2n-p ô được tô là sơ đồ karnaugh của một đơn thức là tích của p literals (được gọi là cell)
Cell của một đơn thức được chứa trọn vẹn trong các dòng và các cột thì công thức của đơn thức là tích của các dòng, cột đó
Tìm công thức tối tiểu bằng phương pháp karnaugh
Lập bảng giá trị và sơ đồ karnaugh của f
Xác định các cell lớn (các cell không bị chứa trong cell khác)
Chọn các cell lớn chứa ít nhất một ô chỉ thuộc riêng cell đó, « chồng » các cell được chọn (nhận được sơ đồ phụ).
Nếu nhận được sơ đồ trùng sơ đồ karnaugh của f thực hiện 6. Nếu không thực hiện 5.
Chọn trong các cell lớn còn lại cell lớn chứa nhiều ô chưa được tô nhất (trong sơ đồ « chồng »). Nếu có nhiều cell lớn như vậy, chọn cell lớn nhất. Nếu tồn tại nhiều cell cùng thoả mãn, chọn một trong số đó. Chồng lên sơ đồ phụ. Thực hiện 4.
Xây dựng công thức tối tiểu của f : là tổng của các công thức của các cell lớn được chọn
So sánh các công thức xây dựng được để xác định công thức tôt nhất (ít phép toán nhất)
22
ĐƠN GIẢN CÔNG THỨC (7)
23
Các cell lớn
ĐƠN GIẢN CÔNG THỨC (7)
24
Chồng các cell có ô chỉ thuộc mình nó, ta được sơ đồ phụ:
Sơ đồ phụ còn khác sơ đồ Karnaugh gốc, chọn một trong hai cell lớn 2. hoặc 3, chồng lên sơ đồ phụ, ta được:
ĐƠN GIẢN CÔNG THỨC (7)
25
Sơ đồ phụ bây giờ trùng với sơ đồ Karnaugh gốc. Công thức tối tiểu dạng đa thức của hàm tương ứng là:
Cả hai công thức « tốt » như nhau
ĐƠN GIẢN CÔNG THỨC (8)
PHƯƠNG PHÁP CONSENSUS
Cơ sở phương pháp:
Nếu f = m1  m2  …  mp là công thức dạng đa thức của f, thì i: mi ≤ f
Nếu m là đơn thúc, m ≤ f thì tồn tại các đơn thức m1, …, mk sao cho f = m  m1  …  mk
Nguyên nhân: đơn thức m ≤ f được gọi là một nguyên nhân của f
Nguyên nhân nguyên tố: đơn thức m bị trội trực tiếp bởi f
Tổng các nguyên nhân nguyên tố của f là một công thức tối giản dạng đa thức của f
Trong công thức tối tiểu dạng đa thức của f, mỗi đơn thức là một nguyên nhân nguyên tố của f
 phương pháp tìm công thức tối tiểu dạng đa thức của f:
Tìm tập các nguyên nhân nguyên tố của f
Xác định tập nhỏ nhất các nguyên nhân nguyên tố tìm được có tổng là f (phủ tối tiểu)
Consensus: hai đơn thức , trong đó m1, m2 là các đơn thức không chứa x và , khi đó m1m2 đươc gọi là consensus của hai đơn thức
26
ĐƠN GIẢN CÔNG THỨC (9)
Consensus(m1, m2) ≤ m1  m2
Tìm nguyên nhân nguyên tố:
Xác định một công thức tối giản dạng đa thức của f. Lập danh sách L các đơn thức nguyên nhân
For each variable x
Chia L thành ba danh sách con: A gồm các đơn thức chứa x, B gồm các đơn thức chứa , C gồm các đơn thức còn lại
Nếu A hoặc B rỗng chuyển sang bước tiếp theo, nếu không ,tính các consensus của mỗi đơn thức của A với mỗi đơn thức của B thêm chúng vào L
Xoá bỏ khỏi L các đơn thức là bội của các đơn thức khác
Kết quả thu được: L là danh sách các nguyên nhân nguyên tố của f
Tìm phủ tối tiểu các nguyên nhân nguyên tố:
Lập và giải hệ phương trình bool cho phủ tối tiểu
Đơn thức C phủ đơn thức m  C là ước của m
27
ĐƠN GIẢN CÔNG THỨC (10)
PHƯƠNG PHÁP QUINE-MC CLUSKEY
Giai đoạn 1: Tìm công thức tối giản dạng đa thức
Lập bảng giá trị của f
Lập bảng gồm nhiều cột để ghi kết quả của các bước sau:
Viết vào cột thứ nhất các dãy bit làm f = 1, gom thành từng nhóm theo số bit 1 (sắp các nhóm theo thứ tự tăng của số bit 1)
Với mỗi dãy bit của nhóm i viết dưới dạng AxB tổng với dãy bit viết dưới dạng của nhóm i+1. kết quả (A_B) được ghi vào cột kế bên, đánh dấu dãy bit tham gia vào tổng (A hoặc B có thể là rỗng)
Lặp lại với cột kế tiếp đến khi không tạo ra cột mới , khi đó dãy bít không bị đánh dấu cho các đơn thức trong công thức tối giản dạng đa thức của f
28
ĐƠN GIẢN CÔNG THỨC (11)
Giai Đoạn 2: tìm công thức tối tiểu dạng đa thức
Lập bảng phủ: các cột tương ứng với các đơn thức mi trong dạng tuyển chuẩn tắc của f, dòng tương ứng với các đơn thức trong công thức tối giản dạng đa thức, tô ô giao của dòng và cột nếu đơn thức dòng tương ứng là ước của đơn thức cột tương ứng
Phát hiện các đơn thức cốt yếu: tìm các cột chỉ một ô được tô, ô được tô nằm trên dòng nào, đơn thức dòng đó là đơn thức cốt yếu
Xóa các cột được phủ bởi các đơn thức cốt yếu
Xóa các dòng không chứa ô được tô, xóa bớt các cột giống nhau (nếu có)
Trong các dòng còn lại, tìm tập ít nhất các đơn thức phủ các cột còn lại


29
30
END OF PART ONE’S THEORY