Môn Toán rời rạc và lý thuyết đồ thị

MÔN TÓAN RỜI RẠC & LÝ THUYẾT ĐỒ THỊ NỘI DUNG HỌC 45 TIẾT LÝ THUYẾT Chương 1: Cơ sở logic (6T) Chương 2: Phép đếm (8T) Chương 3: Hàm Boole và mạch tổ hợp (8T) Chương 4: Đại cương về đồ thị (8T) Chương 5: Bài tóan đường đi (8T) Chương 6: Cây (7T) Tài liệu tham khảo. 1. Đỗ Văn Nhơn – Giáo trình Tóan rời rạc – ĐHQG TpHCM. 2. Kenneth HH. Rosen – Tóan học rời rạc ứng dụng trong tin học (bản dịch tiếng Việt) – NXB Khoa học và Kỹ thuật. 1997. 3. Nguyễn Đức Nghĩa – Lý thuyết đồ thị - NXB Giáo dục. 1998. Chương 1. Cơ sở Logic I. LOGIC MỆNH ĐỀ. 1.KHÁI NIỆM MỆNH ĐỀ VÀ CHÂN TRỊ.  Mệnh đề tóan học là một phát biểu xác định rõ được tính đúng hay sai của phát biểu đó.  Tính đúng hay sai gọi là chân trị của mệnh đề: o Đúng ký hiệu là 1 o Sai ký hiệu là 0 Ví dụ: Các phát biểu sau đây là các mệnh đề (toán học). a= “6 là một số nguyên tố.” (0) b= “5 là một số nguyên tố.” (1) c= “1 < 2” (1) Ví dụ: Các phát biểu sau đây không phải là các mệnh đề (toán học) vì tính đúng sai của chúng không xác định. a= “Ai đang đọc sách?” (một câu hỏi) b= “Cho x là một số nguyên dương.” c= “x + y >z”. 2. CÁC PHÉP TOÁN MỆNH ĐỀ . A. PHÉP PHỦ ĐỊNH. Cho p là một mệnh đề, "Phép phủ định của p" được định nghĩa như sau đây:  Kí hiệu trong tóan học là:  p (hoặc ~p hoặc )  Kí hiệu trong ngôn ngữ lập trình C là: !p  Trong tiếng Việt là: không p  Trong tiếng Anh là: not p  Bảng chân trị. p  p 1 0 0 1 Ví dụ: Cho các mệnh đề a= 6 là một số nguyên tố. (0) b= 5 là một số nguyên tố. (1) c= 1 < 2 (1) thì phủ định của chúng là a= 6 không là một số nguyên tố. (1) b= 5 không là một số nguyên tố. (0) c= 1 ≥ 2 (0) B. PHÉP HỘI. Cho p và q là hai mệnh đề. “Phép hội của p với q” được định nghĩa như sau đây:  Kí hiệu trong tóan học là: p  q  Kí hiệu trong ngôn ngữ lập trình C là: p && q  Trong tiếng Việt là: p và q  Trong tiếng Anh là: p and q  Bảng chân trị. p q p  q 0 0 0 0 1 0 1 0 0 1 1 1 Ví dụ: Cho mệnh đề p = An học giỏi và Tuấn học giỏi. Thì p sai trong 3 trường hợp  Cả An, Tuấn cùng không học giỏi.  Chỉ An học giỏi, còn Tuấn không học giỏi.  Chỉ Tuấn học giỏi, còn An không học giỏi. p đúng trong 1 trường hợp  Cả An, Tuấn cùng học giỏi. Ví dụ: Cho 3 số thực a,b,c điều kiện để chúng là độ dài 3 cạnh của một tam giác như sau Viết theo tiếng Việt (a<b+c) và (b<a+c) và (c<a+b) Viết theo kí hiệu tóan học (a<b+c)  (b<a+c)  (c<a+b) Viết theo câu lệnh của ngôn ngữ lập trình C if (a<b+c)  (b<a+c)  (c<a+b)) printf(“3 số a,b,c tạo ra tam giác”); C. PHÉP TUYỂN. Cho p và q là hai mệnh đề. “Phép tuyển của p với q” được định nghĩa như sau đây:  Kí hiệu trong tóan học là: p  q  Kí hiệu trong ngôn ngữ lập trình C là: p || q  Trong tiếng Việt là: p hay q  Trong tiếng Anh là: p or q  Bảng chân trị. p q p  q 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ: Cho mệnh đề p = An học giỏi hay Tuấn học giỏi. Thì p đúng trong 3 trường hợp  Cả An, Tuấn cùng học giỏi.  Chỉ An học giỏi, còn Tuấn không học giỏi.  Chỉ Tuấn học giỏi, còn An không học giỏi. p sai trong 1 trường hợp  Cả An, Tuấn cùng không học giỏi. Ví dụ: Cho 3 số thực a,b,c điều kiện để chúng không là độ dài 3 cạnh của một tam giác như sau Viết theo tiếng Việt (a>=b+c) hay (b>=a+c) hay (c>=a+b) Viết theo kí hiệu tóan học (a>=b+c)  (b>=a+c) (c>=a+b) Viết theo câu lệnh của ngôn ngữ lập trình C if (a>=b+c)  (b>=a+c)  (c>=a+b)) printf(“3 số a,b,c không tạo ra tam giác”); D. PHÉP KÉO THEO. Cho p và q là hai mệnh đề. “Phép p kéo theo q” được định nghĩa như sau đây:  Kí hiệu trong tóan học là: p  q  Trong tiếng Việt là: p kéo theo q (nếu p thì q)  Trong tiếng Anh là: if p then q  Bảng chân trị. p q p  q 0 0 1 0 1 1 1 0 0 1 1 1 Ví dụ: Cho mệnh đề p = Nếu An chăm học thì An thi đậu. Thì p đúng trong 3 trường hợp  An chăm học, An thi đậu. (Cả giả thiết và kết luận cùng xẩy ra)  An không chăm học, An thi đậu. (Giả thiết không xẩy ra, kết luận xẩy ra)  An không chăm học, An thi không đậu. (Giả thiết không xẩy ra, kết luận không xẩy ra) p sai trong 1 trường hợp  An chăm học, An thi không đậu. (Giả thiết xẩy ra, kết luận không xẩy ra) E. PHÉP KÉO THEO 2 CHIỀU. Cho p và q là hai mệnh đề. Phép kéo theo 2 chiều hay phép tương đương, được đưa ra để mô hình cho loại phát biểu điều kiện hai chiều có dạng : "p nếu và chỉ nếu q". được định nghĩa như sau đây:  Kí hiệu trong tóan học là: p q  Trong tiếng Việt là: p nếu và chỉ nếu q  Trong tiếng Anh là: if p then q and else  Bảng chân trị. p q p q 0 0 1 0 1 0 1 0 0 1 1 1 Mệnh đề p q, được đọc là "p nếu và chỉ nếu q", còn được phát biểu dưới các dạng khác sau đây:  "p khi và chỉ khi q".  "p là điều kiện cần và đủ cho q". Mệnh đề p q có chân trị đúng (1) trong các trường hợp p và q có cùng chân trị. Ðộ ưu tiên của các phép tóan logic. Tương tự như đối với các phép toán số học, để tránh phải dùng nhiều dấu ngoặc trong các biểu thức logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. Ở trên ta có 5 toán tử logic:(không) , (và), (hay), (kéo theo), ( tương đương) có độ ưu tiên như sau:  Ưu tiên 1:   Ưu tiên 2:   Ưu tiên 3:  Trong đó, các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Trường hợp trong biểu thức có dấu ngoặc thì làm trong ngoặc trước, nếu có nhiều dấu ngoặc lồng nhau thì làm từ trong ra ngòai. Trường hợp các phép tóan cùng độ ưu tiên thì làm từ trái sang phải. Ví dụ: 1.  p q có nghĩa là (( p)  q). 2.  p q r  p có nghĩa là ((( p)  q) (r  p)). 3.  p q r có nghĩa là ((( p) q) r). 3. BIỂU THỨC LOGIC. A.ÐỊNH NGHĨA.  Có hai hằng logic là: 0 , 1.  Các biến logic (hay biến mệnh đề) là các biến chỉ nhận trị 0, 1.  Một biểu thức logic là tập hợp các hằng logic, các biến logic, các phép toán logic, và cả các dấu ngoặc "( )" để chỉ rõ thứ tự thực hiện của các phép toán.  Giả sử E, F là 2 biểu thức logic, khi ấy  E, E  F, E  F ,E  F, E  F cũng là các biểu thức logic. Ví dụ: E(p,q,r) = ((( p)  q) (r  p)). là một biểu thức logic trong đó p, q, r là các biến logic (biến mệnh đề). B.BẢNG CHÂN TRỊ. Bảng chân trị của một biểu thức logic: là bảng tính tóan chân trị của biểu thức logic đó, theo các bộ giá trị của những biến tham gia trong biểu thức. Mỗi bộ giá trị của các biến được viết trên một dòng của bảng chân trị. Với một biến mệnh đề, ta có 2 trường hợp là 0 (sai) hoặc 1 (đúng). Với 2 biến mệnh đề p, q ta có 4 bộ giá trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1), (1,0), và (1,1). Trong trường hợp tổng quát, với n biến mệnh đề thì ta có 2n bộ giá trị cho n biến đó. Cách lập bảng chân trị  Các cột bên trái, mỗi cột ứng với một biến trong biểu thức. Các cột bên phải, mỗi cột ứng với một phép tóan trong biểu thức (thứ tự cột theo đúng thứ tự thực hiện các phép tóan trong biểu thức).  Các dòng: mỗi dòng là một bộ giá trị của các biến (ứng với các cột bên trái chứa biến) và kết quả tính tóan của từng phép tóan (ứng với các cột bên phải chứa phép tóan). Để viết các bộ giá trị của các biến trên từng dòng chính xác, ta làm như sau: dòng đầu tiên viết bộ (0,0,,0), mỗi dòng tiếp sau bằng dòng trên nó cộng 1 (cộng nhị phân), dòng cuối cùng là bộ (1,1,,1). Cách cộng nhị phân: 0+0=0 0+1=1 1+0=1 1+1=0 (nhớ 1 qua bên trái) Ví dụ: Bảng chân trị của biểu thức logic p  ( q r) theo các biến mệnh đề p, q, r như sau: p q r qr p  ( q r) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 C.SỰ TƯƠNG ĐƯƠNG LOGIC.  Hai biểu thức logic E và F theo các biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn luôn có cùng chân trị trong mọi trường hợp chân trị của bộ biến mệnh đề.  Khi đó ta viết: E  F và đọc là "E tương đương với F". Như vậy, theo định nghĩa ta có thể kiểm tra xem 2 biểu thức logic có tương đương hay không bằng cách lập bảng chân trị của các biểu thức logic. Ví dụ: CMR p  q   p q Ta CM bằng cách lập bảng chân trị của các biểu thức logic p q và p  q như sau: p q pq p p  q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 D.BIỂU THỨC HẰNG ĐÚNG, BIỂU THỨC HẰNG SAI.  Biểu thức logic E được gọi là hằng đúng nếu chân trị của E luôn luôn bằng 1 (đúng) trong mọi trường hợp về chân trị của các biến mệnh đề trong biểu thức E. Nói một cách khác, E là một hằng đúng khi ta có: E 1.  Biểu thức logic E được gọi là hằng sai nếu chân trị của E luôn luôn bằng 0 (sai) trong mọi trường hợp về chân trị của các biến mệnh đề trong biểu thức E. Nói một cách khác, E là một hằng sai khi ta có: E0. Như vậy, ta có thể kiểm tra xem một biểu thức logic có phải là hằng đúng (hằng sai) hay không bằng cách lập bảng chân trị của biểu thức logic đó Ví dụ: CMR biểu thức p p là hằng đúng p  p p p 0 1 1 1 0 1 Ví dụ: CMR biểu thức p p là hằng sai p  p p p 0 1 0 1 0 0 Lưu ý:  Giả sử E và F là 2 biểu thức logic. Khi đó, E tương đương logic với F (tức là ta có EF) khi và chỉ khi biểu thức logic EF là hằng đúng (tức là EF1).  Nếu EF và FG thì EG. 4.CAC LUẬT LOGIC. Các luật về phép phủ định   p p (luật phủ định của phủ định)  1  0  0  1 Luật giao hoán p  q  q  p p  q  q  p Luật kết hợp p  (q  r)  (p  q)  r p  (q  r)  (p  q)  r Luật phân bố p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) Luật De Morgan  (p  q)   p   q  (p  q)   p   q Luật về phần tử bù p   p  1 p   p  0 Luật kéo theo p  q   p  q Luật tương đương p  q  (p  q)  (q  p) Các luật đơn giản của phép tuyển p  p  p (tính lũy đẳng của phép tuyển) p  1  1 (luật này còn được gọi là luật thống trị) p  0  p (luật này còn được gọi là luật trung hòa) p  (p  q)  p (luật này còn được gọi là luật hấp thụ) Các luật đơn giản của phép hội p  p  p (tính lũy đẳng của phép hội) p  1  p (luật này còn được gọi là luật trung hòa) p  0  0 (luật này còn được gọi là luật thống trị) p  (p  q)  p (luật này còn được gọi là luật hấp thụ) Ví dụ 1: Chứng minh rằng (p  q)  ( q   p). Ta có (p  q)   p  q (luật kéo theo)  q   p (luật giao hoán)  q)   p (luật phủ định)   q   p (luật kéo theo) Ví dụ 2: Chứng minh rằng biểu thức ((p  q)  p)  q là một hằng đúng. Ta có ((p  q)  p)  q   ((p  q)  p)  q (luật kéo theo)  ( (p  q)   p)  q (luật De Morgan)   (p  q)  ( p  q) (luật kết hợp)   (p  q)  (p  q) (luật kéo theo)  1 (luật về phần tử bù) Vậy biểu thức ((p  q)  p)  q là hằng đúng. Ví dụ 3: Chứng minh rằng biểu thức p  q  p là một hằng đúng. Ta có p  q  p   ( p  q)  p (luật kéo theo)  ( p   q)  p (luật De Morgan)  ( q   p)  p (luật giao hoán)   q  ( p  p) (luật kết hợp)   q  1 (luật về phần tử bù)  1 (luật đơn giản) Vậy mệnh đề p  q  p là hằng đúng. Ví dụ 4: Chứng minh rằng biểu thức p  pq là một mệnh đề hằng đúng. Ta có p  pq   p  (p q) (luật kéo theo)  ( p  p)  q (luật kết hợp)  1  q (luật về phần tử bù)  1 (luật đơn giản) Vậy mệnh đề p  pq là hằng đúng. Luật logic cũng có nhiều áp dụng trong ngôn ngữ hàng ngày. Chẳng hạn xem một số áp dụng sau: Áp dụng luật De morgan  (p  q)   p   q Để lấy phủ định của mệnh đề hội. Ví dụ: a= An học giỏi và Tuấn học giỏi. thì a= An không học giỏi hay Tuấn không học giỏi. Áp dụng luật De morgan  (p  q)   p   q Để lấy phủ định của mệnh đề tuyển. Ví dụ: b= An học giỏi hay Tuấn học giỏi. thì b= An không học giỏi và Tuấn không học giỏi. Ta có công thức phủ định mệnh đề điều kiện như sau: p  q)   p  q) (Luật kéo theo)  p  q (Luật De Morgan) Như vậy phủ định của câu điều kiện không phải một câu điều kiện, mà là câu hội với giả thiết đã xẩy ra và kết luận không xẩy ra Ví dụ: c= Nếu An chăm học thì An thi đậu. thì c= An chăm học và An thi không đậu. Cũng có thể dùng các từ đồng nghĩa với từ “và” như “mà”, “nhưng”, để câu phủ định hay hơn c= An chăm học mà An thi không đậu. c= An chăm học nhưng An thi không đậu. II. LOGIC VỊ TỪ VÀ LƯỢNG TỪ. 1. VỊ TỪ. Ðịnh nghĩa: Một vị từ là một phát biểu p(x, y, ) phụ thuộc theo các biến x, y, lấy giá trị trên các miền xác định X, Y, nào đó. Bản thân vị từ chưa có chân trị đúng hoặc sai. Tuy nhiên khi thay thế các biến trong vị từ bởi các giá trị cụ thể, thuộc các miền xác định của nó, thì nó có chân trị đúng hoặc sai, tức là nó trở thành một mệnh đề. Số biến có trong vị từ gọi là bậc của vị từ. (mệnh đề không chứa biến nên có thể xem là vị từ bậc 0) Ví dụ: Vị từ bậc 1 p(n)  "n là một số nguyên tố", với n là biến số tự nhiên. (chưa biết đúng hay sai) Nó có thể tạo ra các mệnh đề như: p(1) = "1 là một số nguyên tố" (0). p(2) = "2 là một số nguyên tố" (1). p(12) = "12 là một số nguyên tố" (0). p(17) = "17 là một số nguyên tố" (1). Ví dụ: Vị từ bậc 2 p(m,n)  "m là một ước số của n", với m và n là các biến số tự nhiên. (chưa biết đúng hay sai) Nó có thể tạo ra các mệnh đề như: p(2,4) = "2 là một ước số của 4" (1) p(3,4) = "3 là một ước số của 4" (0) 2. CÁC LƯỢNG TỪ VÀ CÁC MỆNH ĐỀ CÓ LƯỢNG TỪ. Ngoài việc thay thế giá trị cụ thể cho các biến trong vị từ để được một mệnh đề ta còn có một cách quan trọng khác để chuyển từ vị từ sang mệnh đề. Ðó là cách sử dụng các lượng từ "với mọi" và "tồn tại" (hay "có ít nhất một"). Lượng từ được sử dụng để nói lên rằng vị từ đúng đối với mọi giá trị thuộc miền xác định hay chỉ đúng với một phần các giá trị thuộc miền xác định. Giả sử P(x) là một vị từ theo biến x (biến x lấy giá trị thuộc một miền xác định đã biết nào đó và miền xác định nầy có thể được hiểu ngầm, không cần ghi rõ ra). Các phát biểu sau đây:  x : P(x) (1)  x : P(x) (2) Có chân trị hoàn toàn xác định. Nói cách khác chúng là những mệnh đề. Chân trị của các mệnh đề nầy được xác định một cách tự nhiên theo ngữ nghĩa thông thường của các lượng từ. Mệnh đề (1) là đúng khi và chỉ khi ứng với mỗi giá trị tùy ý x thuộc miền xác định ta đều có mệnh đề P(x) có chân trị đúng. Mệnh đề (2) là đúng khi và chỉ khi có một giá trị x nào đó thuộc miền xác định, ta có P(x) có chân trị đúng. Ghi chú: Phát biểu " x : P(x)" và phát biểu " x : P(x)" không phải là vị từ theo biến x nữa mà là các mệnh đề có chân trị xác định là đúng hoặc sai. Trong các phát biểu trên biến x đã được lượng từ hóa và chân trị của phát biểu không phụ thuộc theo biến x nữa. Ta cũng nói rằng biến x bị buộc bởi lượng từ. Ðối với một vị từ theo nhiều biến thì ta có thể lượng từ hóa một số biến nào đó trong vị từ để có một vị từ mới theo các biến còn lại. Chẳng hạn, nếu p(x, y, ) là một vị từ theo các biến x, y, thì ta có biểu thức q(y, )   x : p(x, y, ) sẽ là một vị từ theo các biến y, . Nếu tất cả các biến của vị từ đều được lượng từ hóa thì ta sẽ có một mệnh đề.Chẳng hạn, nếu p(x, y) làmột vị từ theo 2 biến x, y thì biểu thức  x,  y : p(x, y) sẽ là một mệnh đề, tức là có chân trị xác định và không phụ thuộc vào các biến x, y nữa. Trong nhiều phát biểu người ta cò dùng cụm từ "tồn tại duy nhất", ký hiệu bởi  !, như là một sự lượng từ hóa đặc biệt. Ví dụ: 1. Mệnh đề "Với mọi số nguyên n ta có 2n-1 là một số lẻ" có thể được viết dưới dạng ký hiệu như sau:  n Z : 2n-1 lẻ. Mệnh đề nầy có chân trị là 1 (đúng). 2. Mệnh đề "Ta có x2 > 0, với mọi số thực x khác 0" có thể được viết là  x R -  0 : x2 > 0. Mệnh đề nầy có chân trị là 1 (đúng). 3.QUI TẮC PHỦ ĐỊNH MỆNH ĐỀ CÓ LƯỢNG TỪ. Dựa vào cách xác định chân trị của các mệnh đề có lượng từ theo ngữ nghĩa tự nhiên của các phát biểu, ta có các qui tắc phủ định mệnh đề có lượng từ sau đây:  ( x : P(x))   x :  P(x) (1)  ( x : P(x))   x :  P(x) (2) Ví dụ: Tìm phủ định của các mệnh đề sau a=Tồn tại một số thực x, thỏa x2 < 0. b=Mọi sinh viên đều chăm học. c=Có sinh viên chăm học. Giải a=Với mọi số thực x, thỏa x2  0.  b=Có sinh viên không chăm học.  c=Mọi sinh viên không chăm học. Ghi chú: Từ các qui tắc trên ta có thể nói chung về qui tắc phủ định mệnh đề có lượng từ như sau: Nếu trong một mệnh đề có lượng từ ta thay thế lượng từ  bởi lượng từ  , lượng từ  bởi lượng từ  , và biểu thức vị từ được thay thế bởi phủ định của nó thì ta sẽ được mệnh đề phủ định của mệnh đề có lượng từ ban đầu. Qui tắc nầy cũng áp dụng được cho các mệnh đề với nhiều lượng từ. Ví dụ: p=  x,  y: x = y Thì p= x,  y: x # y BÀI TẬP Bài 1. Chứng minh các biểu thức logic sau đây là hằng đúng, bằng hai cách: bảng chân trị và dùng luật. a/ (p  q)  ( p  q)  q b/ (p  q)  (p  q) c/ (p q  r)  ((p q)  (p r)) d/  (p  q)  p   q e/ ((p  q) p)  (p  q) Bài 2. Hãy cho biết chân trị của mỗi mệnh đề dưới đây và viết mệnh đề phủ định của mệnh đề đó. a/  x : x+3 = 5 b/  x : x+3 = 5 c/  x,  y : x+y = 3 d/  x,  y : x+y = 3 e/  x,  y : x+y = 3 f/  x,  y : x+y = 3 Trong các mệnh đề trên các biến x và y là các biến số thực. Bài 3. Hãy sử dụng các ký hiệu toán học và logic để viết lại mệnh đề sau đây: Với mọi số thực dương x, có một số tự nhiên n sao cho x bằng 2n hoặc x nằm giữa 2n và 2n+1. Viết ra mệnh đề phủ định của nó. Bài 4. Trong bài tập nầy ký hiệu n chỉ một biến nguyên. Cho các vị từ : P(n)  "0 < n2  4" R(n)  "0 < n3  8" S(n)  "0 < n  2" a/ Ứng với mỗi vị từ trên hãy cho biết tập hợp các giá trị n làm cho vị từ có chân trị đúng. b/ Trong các vị từ trên, những vị từ nào tương đương với nhau. c/ Mệnh đề " n : R(n)  P(n)" là đúng hay sai? Bài 5. Viết mệnh đề phủ định của các mệnh đề sau: a/ Nếu mọi sinh viên trong lớp chăm học thì cả lớp thi đậu. b/ Kết quả tốt đẹp khi có sư cố gắng. c/ Nếu có sinh viên nói chuyện trong lớp thì mọi người khó tập trung. d/ Nếu được tăng lương thí An sẽ mua xe và máy tính. e/ Mọi người đều mệt mỏi và buồn ngủ. f/ Có người vui hay có người buồn. Bài 6. Cho vị từ P(x,y) = “x yêu y”, với x,y thuộc tập nhân lọai: NHANLOAI. Hãy dùng các lượng từ diễn đạt các câu nói sau: a/ Mọi người đều yêu An. b/ Mọi người đều yêu một ai đó. c/ Có một người mà tất cả mọi người đều yêu. d/ Có một người mà An không yêu. e/ Có một người mà không ai yêu. f/ Mọi người đều yêu chính mình.