Bài giảng Cấu trúc rời rạc

CẤU TRÚC RỜI RẠC 
1 
CHƯƠNG I: CƠ SỞ LÔGIC 
Mệnh đề 
Biểu thức logic (Dạng mệnh đề) 
Qui tắc suy diễn 
Vị từ, lượng từ 
Quy nạp toán học 
2 
	“Toan tính của chiến lược gia 44 tuổi đã suýt thành công nếu ông không tính tới đột biến từ những ngôi sao đối phương”. 
Nguồn: 
3 
Mệnh đề 
 Định nghĩa: Mệnh đề là một khẳng định có giá trị chân lý xác định, đúng hoặc sai. 
	 Câu hỏi, câu cảm thán, mệnh lệnh không là mệnh đề. 
Ví dụ: 
- Đại học CNTT trực thuộc ĐHQG TP.HCM. 
- 1+ 7 = 8. 
- Hôm nay em đẹp quá! (k hông là mệnh đề) 
- Hôm nay ngày thứ mấy? (k hông là mệnh đề) 
4 
Mệnh đề 
Ký hiệu: người ta dùng các ký hiệu P, Q, R (p,q,r,) để chỉ mệnh đề. 
Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. 
Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T) và 0(hay S,F) 
5 
Mệnh đề 
Phân loại: gồm 2 loại 
 Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi,) hoặc trạng từ “không” 
 Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không” 
6 
Mệnh đề 
Ví dụ: 
- 2 là số nguyên tố . 
- 2 không l à số nguyên tố . 
- 2 là số nguyên tố và là số lẻ. 
- An đang xem ti vi hay đang học bài. 
7 
Các phép toán : có 5 phép toán 
Phép phủ định: phủ định của mệnh đề P là một mệnh đề, ký hiệu là  P hay (đọc là “không” P hay “phủ định c ủa” P ) . 
Bảng chân trị : 
Ví dụ: 
- 2 là số nguyên tố . 
Phủ định: 2 không là số nguyên tố 
- 15 > 5 	 Phủ định: 1 5 ≤ 5 
P 
0 
1 
1 
0 
Mệnh đề 
8 
 Phép hội (nối liền, giao): của hai mệnh đề P, Q là một mệnh đề, kí hiệu P  Q (đọc là “P và Q ) 
Bảng chân trị : 
NX : P  Q đúng khi và chỉ khi 
P và Q đồng thời đúng. 
Ví dụ: 
 P: “Hôm nay là chủ nhật” 
 Q: “Hôm nay trời mưa” 
 P  Q : “ Hôm nay là chủ nhật và trời mưa” 
P 
Q 
P  Q 
0 
0 
1 
1 
0 
1 
0 
1 
0 
0 
0 
1 
Mệnh đề 
9 
 Phép tuyển (nối rời, hợp): của hai mệnh đề P, Q là mộ t mệnh đề, kí hiệu P  Q (đọc là “P hay Q”) . 
Bảng chân trị : 
NX: P  Q sai khi và chỉ khi 
P và Q đồng thời sai. 
 Ví dụ: 
 - e > 4 hay e > 5 (S) 
 - 2 là số nguyên tố hay là số lẻ (Đ) 
P 
Q 
P  Q 
0 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
1 
Mệnh đề 
10 
 Phép kéo theo: Mệnh đề P kéo theo mệnh đề Q là một mệnh đề, kí hiệu P Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”) . 
Bảng chân trị : 
NX: P Q sai khi và chỉ 
khi P đúng mà Q sai. 
 Ví dụ: 
 e >4 kéo theo 5>6 
P 
Q 
P Q 
0 
0 
1 
1 
0 
1 
0 
1 
1 
1 
0 
1 
Mệnh đề 
11 
 Phép kéo theo hai chiều (phép tương đương) : Mệnh đề P kéo theo mệnh đề Q và ngược lại (mệnh đề P tương đương với mệnh đề Q) là một mệnh đề , ký hiệu P  Q (đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”) . 
Bảng chân trị : 
NX: P  Q đúng khi và chỉ 
 khi P và Q có cùng chân trị 
Ví dụ: 6 chia hết cho 3 khi 
v à chỉ khi 6 chia hết cho 2 
P 
Q 
P  Q 
0 
0 
1 
1 
0 
1 
0 
1 
1 
0 
0 
1 
Mệnh đề 
12 
 Định nghĩa: B iểu thức logic được cấu tạo từ: 
 - Các mệnh đề (các hằng mệnh đề) 
 - Các biến mệnh đề p, q, r, , tức là các biến lấy giá trị là các mệnh đề nào đó 
 - Các phép toán logic  ,  ,  , ,  và dấu đóng mở ngoặc () để chỉ rõ thứ tự thực hiện của các phép toán. 
Ví dụ: 
E(p,q) =  (  p  q) 
F(p,q,r) = (p  q)  (q  r) 
Biểu thức logic (Dạng mệnh đề) 
13 
 Độ ưu tiên của các toán tử logic: 
- Ưu tiên mức 1: () 
- Ưu tiên mức 2:  
- Ưu tiên mức 3:  ,  
- Ưu tiên mức 4: ,  
Bảng chân trị của một biểu thức logic: là bảng liệt kê chân trị c ủa biểu thức logic theo các trường hợp về chân trị của tất cả các biến mệnh đề trong biểu thức logic hay theo các bộ giá trị của bộ biến mệnh đề . 
Biểu thức logic 
14 
Bảng chân trị của một biểu thức logic. 
Ví dụ: 
Với một biến mệnh đề, ta có hai trường hợp là 0 hoặc 1. 
Với hai biến mệnh đề p,q ta có bốn trường hợp chân trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1), (1,0) và (1,1). 
NX: Trong trường hợp tổng quát, n ếu có n biến mệnh đề thì ta có trường hợp chân trị cho b ộ n biến. 
Biểu thức logic 
15 
 Ví dụ: Cho E(p,q,r) =(p  q) r . 
Ta có bảng chân trị sau: 
Biểu thức logic 
16 
p 
q 
r 
p  q 
(p  q) r 
0 
0 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
0 
1 
0 
0 
1 
1 
1 
1 
1 
0 
0 
1 
0 
1 
0 
1 
1 
1 
1 
1 
0 
1 
0 
1 
1 
1 
1 
1 
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 nếu chúng có cùng bảng chân trị. 
Ký hiệu : E F (E tương đương với F). 
Ví dụ :  (p  q)  p   q 
Biểu thức logic E được gọi là hằng đúng nếu chân trị của E 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 đề có trong E. Nói cách khác, E là hằng đúng khi ta có E 1. 
Biểu thức logic 
17 
Tương tự, E là một hằng sai khi ta có E 0. 
Ví dụ: E(p,q) = p   p là hằng sai. 
	 F(p,q) =(p q)  (  p  q ) là hằng đúng. 
Định lý: Hai biểu thức logic E và F tương đương với nhau khi và chỉ khi E  F là hằng đúng. 
Ví dụ: (p q) (  p  q ) 
Hệ quả logic: F được gọi là hệ quả logic của E nếu E F là hằng đúng. 
Ký hiệu : E F 
Ví dụ:  (p  q)  p 
Biểu thức logic 
18 
Phủ định của phủ định :  p p 
Qui tắc De Morgan: 	  (p  q)  p   q 
	  (p  q)  p   q 
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) 
Các luật logic 
19 
Luật phân phối : p  (q  r) (p  q)  (p  r) 
	 p  (q  r) (p  q)  (p  r) 
Luật lũy đẳng :	 	 p  p p 
	 	 p  p p 
Luật trung hòa:	 p  0 p 
	p  1 p 
Luật về phần tử bù:	 p   p 0 
	p   p 1 
Các luật logic 
20 
 Luật thống trị: 	 p  0 0 
	p  1 1 
 Luật hấp thu: 	 p  (p  q) p 
	p  (p  q) p 
 Luật về phép kéo theo:	 p q  p  q 
	 	  q  p 
Ví dụ: Cho p, q, r là các biến mệnh đề. Ch ứng minh rằng: (  p r)  (q r) (p q) r 
Các luật logic 
21 
Các luật logic 
22 
Qui tắc De Morgan: 	  (p  q)  p   q 
  (p  q)  p   q 
VD: Dùng bảng chân trị chứng minh qui tắc De Morgan 
Ví dụ: Cho p, q, r là các biến mệnh đề. Ch ứng minh rằng: (  p r)  (q r) (p q) r . 
Giải: 
Các luật logic 
23 
 (  p r)  (q r) 
 ( p  r )  (  q  r) 
 ( p   q )  r 
  (  p  q )  r 
  ( p q )  r 
 ( p q ) r 
Định nghĩa: 
Trong các chứng minh toán học, ta thường thấy những lý luận dẫn xuất có dạng: nếu và và thì q. 
Dạng lý luận này là đúng khi ta có biểu thức 
 là hằng đúng. 
Ta gọi dạng lý luận trên là một quy tắc suy diễn và thường được viết theo các cách sau đây: 
Cách 1 : Biểu thức hằng đúng 
Qui tắc suy diễn 
24 
Định nghĩa: 
Cách 2 : Dòng suy diễn 
Cách 3: Mô hình suy diễn 
Các biểu thức logic được gọi là giả thiết (hay tiên đề), biểu thức q được gọi là kết luận. 
Qui tắc suy diễn 
25 
 Qui tắc khẳng định (Modus Ponens) : 
	[(p q)  p] q 
Ví dụ: 
Học tốt thi đậu 	 
SV A học tốt 
Suy ra: SV A thi đậu 
 Nếu chuồn chuồn bay thấp thì mưa	 
 Thấy chuồn chuồn bay thấp 
Suy ra: trời mưa 
Qui tắc suy diễn 
26 
p q 
p 
 q 
2. Qui tắc phủ định (Modus Tollens): 
 [(p q)  q ]  p 
Ví dụ: 
• Nếu A đi học đầy đủ thì A đậu toán rời rạc. 
• A không đậu toán rời rạc. 
Suy ra: A không đi học đầy đủ. 
Qui tắc suy diễn 
27 
 p q 
q 
 p 
3. Qui tắc tam đoạn luận : 
 [(p q)  (q r)] (p r) 
Ví dụ: 
• Nếu trời mưa thì đường ướt 
• Nếu đường ướt thì đường trơn 
Suy ra : nếu trời mưa thì đường trơn. 
Qui tắc suy diễn 
28 
p q 
q r 
 p r 
29 
Qui tắc suy diễn 
 Qui tắc phản chứng: 
 * Tổng quát: 
Qui tắc suy diễn 
30 
Để chứng minh vế trái là một hằng đúng, ta chứng minh nếu thêm phủ định của q vào các tiên đề thì được một mâu thuẫn. 
 Qui tắc phản chứng: 
Ví dụ: 
Qui tắc suy diễn 
31 
Chứng minh suy luận: 
 p r 
p q 
 q s 
r s 
Giải: CM bằng phản chứng 
 p r 
p q 
 q s 
r 
s 
0 
 Qui tắc chứng minh theo trường hợp : 
 [(p r)  (q r)] [(p  q) r] 
* Tổng quát: 
Qui tắc suy diễn 
32 
6.Phản ví dụ: 
 Để chứng minh một phép suy luận là sai hay không là một hằng đúng , t a chỉ cần chỉ ra một phản ví dụ . 
Qui tắc suy diễn 
33 
Để tìm một phản ví dụ ta chỉ cần chỉ ra một trường hợp về chân trị của các biến mệnh đề sao cho các tiên đề trong phép suy luận là đúng còn kết luận là sai. 
6.Phản ví dụ: 
Ví dụ: Hãy kiểm tra suy luận: 
NX: Ta sẽ tìm p,q,r thỏa 
Dễ dàng tìm thấy một phản ví dụ: p=1,q=0,r=1. 
Vậy suy luận đã cho là không đúng 
Qui tắc suy diễn 
34 
6. Phản ví dụ 
Ví dụ: Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán xe.Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc và cuối cùng ông Minh đã được tăng lương. 
 Suy ra nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ . 
Qui tắc suy diễn 
35 
p : ông Minh được tăng lương. 
q : ông Minh nghỉ việc. 
r : vợ ông Minh mất việc. 
s : gia đình phải bán xe. 
t : vợ ông hay đi làm trể. 
p q 
 q  r s 
 t r 
 p 
s t 
 Ví dụ:Suy luận sau đúng hay sai 
Qui tắc suy diễn 
36 
37 
 Ví dụ:Suy luận sau đúng hay sai 
HD: Dùng phản ví dụ: Chọn 
Qui tắc suy diễn 
37 
p=1, q=0, r=1, s=0, t=1 
Suy luận (lập luận) sau đúng hay sai? 
38 
39 
Qui tắc suy diễn 
40 
Giải 
41 
Định nghĩa: 
Vị từ là một khẳng định p(x,y,..), trong đó x,y...là các biến thuộc tập hợp A, B,.. cho trước sao cho: 
- Bản thân p(x,y,..) không phải là mệnh đề 
- Nếu thay x,y,.. thành giá trị cụ thể thì p(x,y,..) là mệnh đề. 
Ví dụ: 
- p(n) = “n +1 là số nguyên tố” 
- q(x,y) = “x + y = 1” 
Vị từ - Lượng từ 
42 
Các phép toán trên vị từ 
Cho trước các vị từ p(x), q(x) theo một biến x A. Khi ấy, ta cũng c ó các phép toán tương ứng như trên mệnh đề: 
 Phủ định: p(x) 
 Phép nối liền (hội, giao): p(x)  q(x) 
 Phép nối rời (tuyển, hợp): p(x)  q(x) 
 Phép kéo theo: p(x) q(x) 
 Phép kéo theo hai chiều: p(x)  q(x) 
Vị từ - Lượng từ 
43 
Cho p(x) là một vị từ theo một biến xác định trên A. Các mệnh đề lượng từ hóa của p(x) được định nghĩa như sau: 
- Mệnh đề “Với mọi x thuộc A, p(x) ” , kí hiệu: “x A, p(x)” là mđ đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a A.  đgl lượng từ phổ dụng 
- Mệnh đề “Tồn tại (có ít nhất một) x thuộc A, p(x)” kí hiệu “x A, p(x)” là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x= a ’ A nào đó sao cho mệnh đề p(a ’ ) đúng.  đgl lượng từ tồn tại 
Vị từ - Lượng từ 
44 
45 
Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A B. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau: 
“x A,y B, p(x, y)”  “x A, (y B, p(x, y))” 
“x A, y B, p(x, y)”  “x A, (y B, p(x, y))” 
“x A, y B, p(x, y)”  “x A, (y B, p(x, y))” 
“x A, y B, p(x, y)”  “x A, (y B, p(x, y))” 
Vị từ - Lượng từ 
47 
Ví dụ : Các mệnh đề sau đúng hay sai? 
- “x R, ” 
- “x R, ” 
- “x R, y R, 2x + y < 1” 
- “x R, y R, 2x + y < 1” 
- “x R, y R, x + 2y < 1” 
- “x R, y R, x + 2y < 1” 
Vị từ - Lượng từ 
48 
49 
50 
51 
52 
Định lý 
Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A B. Khi đó: 
 “x A, y B, p(x, y)” “y B, x A, p(x, y)” 
 “x A, y B, p(x, y)” “y B, x A, p(x, y)” 
 “x A, y B, p(x, y)” “y B, x A, p(x, y)” 
Phủ định của mệnh đề lượng từ hóa vị từ p(x,y,..) có được bằng cách: thay  thành , thay  thành , và p(x,y,..) thành  p(x,y,..). 
Vị từ - Lượng từ 
53 
Với vị từ theo 1 biến ta có : 
Với vị từ theo 2 biến 
Vị từ - Lượng từ 
54 
Ví dụ phủ định các mệnh đề sau 
- “x A, 2x + 1 0” 
- “>0,  > 0 :( x R : x – a< f(x) – f(a)< ) ” 
Vị từ - Lượng từ 
55 
56 
Cho n 0 N và p(n) là một vị từ theo biến tự nhiên n n 0 . 
Để chứng minh tính đúng đắn của mệnh đề: 
	n n 0 , p(n) 
ta có thể dùng các dạng nguyên lý quy nạp như sau: 
*Nguyên lý quy nạp yếu (giả thiết đúng với k) 
Mô hình suy diễn:	 
Qui n ạp 
57 
(cơ sở) 
(GTQN) 
*Nguyên lý quy nạp mạnh (giả thiết đúng đến k) 
Mô hình suy diễn:	 
(cơ sở) 
(GTQN) 
Qui n ạp 
58 
Ví dụ : 
Chứng minh 
Ví dụ : 
Chứng minh 
Qui n ạp 
59 
60 
61 
62 
63