Giáo trình Toán học rời rạc

Nội dung text: Giáo trình Toán học rời rạc

1. Mệnh đề có hai loại: (1)Mệnh đề sơ cấp (elementary): mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là nó không thể phân tích được thành một hay nhiều (từ 2 trở lên) mệnh đề thành phần đơn giản hơn. (2) Mệnh đề phức hợp (compound): mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không” dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, vv Ví dụ : xét các mệnh đề sau: p: “15 chia hết cho 3” ; q: “2 là một số nguyên tố và là một số lẻ” Ta có: p là mệnh đề sơ cấp, q là mệnh đề phức hợp, vì q được tạo thành từ 2 mệnh đề: p1 : “2 là một số nguyên tố” ; P2: “2 là một số lẻ” nhờ vào liên kết logic “và”. 1.3.2.Các phép toán mệnh đề Khi có các mệnh đề phức hợp theo các mệnh đề sơ cấp thì việc tính toán giá trị chân lý sẽ được thực hiện như thế nào? Để trả lời được cần có các phép toán logic, các phép toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như từ “không”, “và”, “hay”, “hoặc”, “suy ra”, “nếu thì ”, “nếu và chỉ nếu ” Các phép toán logic được định nghĩa bằng bảng giá trị chân lý (truth table). a.Phép phủ định Ký hiệu là:  Giả sử p là một mệnh đề, phủ định của p được ký hiệu là  p hay p . Bảng giá trị chân lý của phép phủ định được cho bởi bảng: p p 0 1 1 0 Ví dụ 1: Cho mệnh đề p: 5<3 : 5 3 Giá trị chân lý của p là 0 Giá trị chân lý của là 1 Ví dụ 2: Chỉ ra rằng p và p luôn có cùng giá trị chân lý: Giải: lập bảng giá trị chân lý của mệnh đề (p) p 0 1 0 1 0 1 Qua bảng giá trị chân lý của mệnh đề ta nhận thấy rằng p và luôn có cùng giá trị chân lý nên ta có thể nói rằng là tương đương logic với b.Phép hội Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề “p và q” là pq. Phép hội được định nghĩa bởi bảng giá trị chân lý sau đây. p q pq 0 0 0 0 1 0 1 0 0 1 1 1 8
2. Ví dụ 1: Cho các mệnh đề p: “5>2” ; q: “6 là số nguyên tố” r: “Một tam giác đều cũng là tam giác cân” Giá trị chân lý của p, q, r là 1, 0, 1. Khi đó ta có: pq = 0; pr = 1 qr = 0; Ví dụ 2: Bằng cách lập bảng giá trị chân lý ta có: 1.Các mệnh đề p và pp luôn có cùng giá trị chân lý. 2.Mệnh đề p  p luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai) c.Phép tuyển Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề p hoặc q (p hay q) là pq. Phép tuyển hay phép hoặc được định nghĩa bởi bảng chân lý sau: p q pq 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có: pq = 1; pr = 1 Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề p  p là luôn đúng. Nhận xét: Một mệnh đề phức hợp mà luôn đúng bất kể các giá trị chân lý của các mệnh dề thành phần của nó được gọi là hằng đúng. Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn. Một mệnh đề không phải hằng đúng, cũng không phải mâu thuẫn được gọi là tiếp liên Ví dụ 3 : là luôn đúng nó là hằng đúng.  là luôn luôn sai nó là mâu thuẫn. Phép loại trừ ký hiệu là XOR. p XOR q được định nghĩa bởi bảng chân lý sau: p q p XOR q 0 0 0 0 1 1 1 0 1 1 1 0 p XOR q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai. d.Phép kéo theo, ký hiệu là Cho p và q là 2 mệnh đề. Mệnh đề p kéo theo q ký hiệu là p q dùng để diễn đạt phát biểu: nếu p thì q và được định nghĩa bởi bảng chân lý sau: p q p q 0 0 1 0 1 1 1 0 0 1 1 1 9
3. Ví dụ : với n N, ta xét mệnhđề: p: n chia hết cho 5 q: n chia hết cho 9 Lúc đó mệnh đề p q có giá trị xác định cụ thể: n = 45 p: 1 q: 1 p q: 1 n = 15 p: 1 q: 0 p q: 0 n = 16 p: 0 q: 0 p q: 1 Xét mệnh đề p q (1). Khi đó các mệnh đề sau đây gọi là các mệnh đề liên kết với (1) q p (2) p q (3) q p (4) Mệnh đề (1) được gọi là mệnh đề thuận Mệnh đề (2) được gọi là mệnh đề đảo Mệnh đề (3) được gọi là mệnh đề phản Mệnh đề (4) được gọi là mệnh đề phản đảo Các mệnh đề liên kết chia thành 2 cặp tương đương: i/ p q q p ii/ q p p q với mệnh đề (1): Nếu có p thì có q do đó còn nói: p là điều kiện đủ để có q. Mệnh đề (1) tương đương mệnh đề (4) nghĩa là không q thì không p, do đó có thể nói: q là điều kiện cần để có p. e.Phép kéo theo hai chiều (phép tương đương). Ký hiệu là  Cho p, q là 2 mệnhđề. Mệnh đề p tương đương q dùng để diễn đạt phát biểu: p nếu và chỉ nếu q và được định nghĩa bởi bảng giá trị chân lý sau: 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 hay còn được phát biểu dưới các dạng khác:  p khi và chỉ khi q  p là điều kiện cần và đủ cho q Độ ưu tiên của các toán tử logic 1.  2. ,  3. ,  Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Ví dụ : 1. x  y có nghĩa là x  y 2. x  y p  q có nghĩa x  y p  q 1.3.3.Biểu thức logic (công thức logic) Trong đại số ta có các biểu thức số học được xây dựng từ các hằng số, các biến số và các phép toán số học. Khi thay thế các biến trong một biểu thức số học bởi các hằng số 10
4. thì kết quả thực hiện các phép toán trong biểu thức là một hằng số. Trong đại số mệnh đề ta có biểu thức logic cũng được xây dựng như sau: a.Định nghĩa: Các mệnh đề chưa xác định p, q, r gọi là các biến mệnh đề. 1.Các biến mệnh đề là các biểu thức 2.Nếu P, Q là các (công thức) biểu thức logic thì P , P  Q, P  Q, P Q , P  Q là các (công thức) biểu thức. 3.Mọi ký hiệu khác không được xác định theo 2 qui tắc 1, 2 đều không là các biểu thức. Ví dụ: p(x, y, z) = x  p q  r là một biểu thức logic với các biến mệnh đề x, p, q, r. b.Sự tương đương logic Hai biểu thức logic E và F theo bộ biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn có cùng giá trị chân lý trong mọi trường hợp giá trị chân lý của bộ biến mệnh đề. Khi đó ta viết E F hay E  F và đọc là “E tương đương với F”. Như vậy, để chứng minh 2 biểu thức logic là tương đương logic thì có thể lập bảng giá trị chân lý. Ví dụ: Chứng minh p  q r p r  q r Giải: ta lập bảng giá trị chân lý như sau: p q r p  q p r q r p  q r p r  q r 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy: c.Phép biến đổi công thức (biểu thức): Để biến đổi biểu thức một cách thuận tiện, ta qui ước các điều sau: 1.Không viết dấu ngoặc ngoài cùng đối với mỗi công thức (biểu thức). 2.Thay ký hiện  bởi dấu . hoặc bỏ đi. 3.Các phép toán được thực hiện theo thứ tự: , , ,  4.Nếu có dấu phủ định trên một biểu thức thì bỏ dấu ngoặc hai đầu biểu thức đó. Ví dụ :  ( p  q r ) được viết là p q r  p q  r được viết là p q  r d.Các luật của logic mệnh đề Biểu thức logic A gọi là hằng đúng nếu A nhận giá trị 1 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Biểu thức logic A gọi là hằng sai nếu A nhận giá trị 0 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Khi A là hằng đúng thì ta gọi A là một luật, ký hiện là = A. Khi A là hằng sai thì ta gọi A là một mâu thuẫn. Ví dụ : p  p 1 nên ta có một luật = p  p . Luật = p  p gọi là luật bài trung: Trong hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng. 11
5. Các luật logic cơ bản 1. Luật phủ định kép: p p 2. Luật giao hoán: p q q  p , p q q  p 3. Luật kết hợp: p  (q  r) p  q  r , p  (q  r) p  q  r 4. Luật phân phối: p  (q  r) p  q  q  r , p  (q  r) p  q  q  r 5. Luật Demorgan: p q p  q , p q p  q 6. Luật về mối liên hệ giữa p với chính nó, với p , với 0 và 1: p  p p p  p p p 0 0 p  0 p p 1 p p 1 1 p  p 0 p  p 1 7. Luật kéo theo: p q p  q 8. Luật tương đương: p q p q  q p Nhận xét: Có thể dùng các luật logic để biến đổi tương đương các biểu thức logic, hay nói cách khác, để chứng minh 2 biểu thức logic tương đương ta có thể dùng phương pháp biến đổi logic. Ví dụ: Chứng minh p  q r p r  q r Ta biến đổi vế trái về vế phải như sau: Vế trái p  q  r (p  q)  r (p  r)  (q  r) (p r)  (q r)  Vế phải 1.3.4.Các dạng chính tắc a.Dạng chính tắc tuyển Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức hội cơ bản nếu nó có dạng sau: F = q1 q2   qn với qi = pi hoặc qi pi (i = 1 n). Ví dụ: Biểu thức xyz hoặc x  y  z hoặc x  y  z là các biểu thức hội cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được gọi là có dạng chính tắc tuyển khi E có dạng: E = E1 E2   Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức hội cơ bản theo các biến mệnh đề p1, p2, , pn. Ví dụ : Các biểu thức sau đây có dạnh chính tắc tuyển. E x, y, z x  y  z  x  y  z  x  y  z F p1 , p2 , p3 , p4 p1  p2  p3  p4  p1  p2  p3  p4  p1  p2  p3  p4 Định lý: Mọi biểu thức logic F(p1, p2, , pn) đều có thể viết dưới dạng chính tắc tuyển duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong phép tuyển). Nói cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản {E1, E2, , Em} sao cho biểu thức E (p1, p2, , pm) E1  E2   Em. Ví dụ : Tìm dạng chính tắc tuyển của biểu thức: E x,, y z x  z  x y E x, y, z x  z  x  y x  z  x  x  z  y x  z  x  y  z 12
6. x  y  y  z  x  y  z x  y  z  x  y  z  x  y  z x  y  z  x  y  z b. Dạng chính tắc hội Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau: F = q1 q2   qn với qi = pi hoặc qi pi (i = 1 n). Ví dụ: Biểu thức x y z hoặc x  y  z hoặc x  y  z là các biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được gọi là có dạng chính tắc hội khi E có dạng: E = E1 E2   Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức tuyển cơ bản theo các biến mệnh đề p1, p2, , pn. Ví dụ : Các biểu thức sau đây có dạng chính tắc hội. E x, y, z x  y  z  x  y  z  x  y  z F p1 , p2 , p3 , p4 p1  p2  p3  p4  p1  p2  p3  p4  p1  p2  p3  p4 Định lý: Mọi biểu thức logic F(p1, p2, , pn) đều có thể viết dưới dạng chính tắc hội duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội). Nói cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, , Em} sao cho biểu thức E (p1, p2, , pm) E1  E2   Em. Ví dụ 1: Tìm chính tắc hội của biểu thức sau: E x, y, z,t x  y y  z z  t E x, y, z,t x  y  zz  tt xx  y  z  tt xx  yy  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t Ví dụ 2: Tìm chính tắc tuyển của biểu thức: x y  z y x  y  z  y x  y  z  x  y  y xz  yz  xy  yy xz  yz  xy x y  y z  x  x yz  xy z  z xyz  xyz  xyz  xyz  xyz  xyz xyz  xyz  xyz  xyz 1.3.5.Vị từ, lượng từ a.Vị từ (Hàm mệnh đề) P(x) là một hàm mệnh đề (một biến) xác định trên tập X nếu với mỗi x X thì P(x) là một mệnh đề. Hàm mệnh đề một biến còn được gọi là vị từ 1-ngôi. 13
7. Nếu P(x) là một hàm mệnh đề xác định trên X thì x được gọi là biến tử, một phần tử cụ thể a X gọi là hằng tử, P(a) là một hàm mệnh đề hoàn toàn xác định. Tương tự ta có hàm mệnh đề m biến, hay vị từ m-ngôi với m N* b.Miền đúng của hàm mệnh đề Giả sử P(x) là một hàm mệnh đề trên X, khi đó miền đúng của P(x) là tập EP(x)={ a X P(a) là mệnh đề đúng} Ví dụ: 2 1. P(x): x -6x+5=0 với x R có EP(x)={ 1,5} 2 2. P(x): x -6x+5 0 với x R có EP(x)= ( ,1)  (5, ) Hàm mệnh đề P(x) xác định trên X gọi là hằng đúng nếu EP(x)=X, gọi là hằng sai nếu EP(x)=, gọi là thực hiện được nếu EP(x)  Ví dụ: 1. P(x): x2+1>0 là hằng đúng trên R 2. P(x): x2+1=0 là hằng sai trên R 3. P(x): 3x-4=0 là thực hiện được trên R nhưng không thực hiện được trên N Hai hàm mệnh đề P(x) và Q(x) cùng xác định trên tập X được gọi là tương đương logic, kí hiệu là P(x) Q(x) hoặc P(x)  Q(x) khi và chỉ khi EP(x)= EQ(x) c.Phép toán trên các hàm mệnh đề Phép phủ định Cho P(x) là một hàm mệnh đề xác định trên X, ta gọi phủ định của P(x) là hàm mệnh đề Px() xác định trên X, nhận giá trị 1 trên tập các phần tử a X , P(a)  0, nhận giá trị 0 trên miền đúng của P(x) E X \ E Ta có: P(x) P(x) E P(x) EP(x) Phép hội Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, hội của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử a X sao cho P(a) 1 Q(a) 1, nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP(x)Q(x) EP(x)  EQ(x) 14
8. Phép tuyển Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, tuyển của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử a X sao cho P(a)  0  Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP(x)Q(x) EP(x)  EQ(x) Phép kéo theo Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) kéo theo Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử a X sao cho P(a) 1 Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP(x) Q(x) (X \ EP(x) )  EQ(x) Phép tương đương Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) tương đương Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử a X sao cho P(a)  Q(a) , nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP(x)Q(x) (X \ (EP(x)  EQ(x) )) (EP(x)  EQ(x) ) d. Lượng từ Cho P(x) là hàm mệnh đề xác định trên X. Ta gọi x X P(x) hiểu là Với mọi x X, P(x) là mệnh đề đúng nếu EP(x)=X, sai trong các trường hợp khác. Ta gọi x X P(x) hiểu là tồn tại x X, P(x) là mệnh đề đúng nếu EP(x) , sai trong các trường hợp khác. Ký hiệu  gọi là lượng từ phổ dụng (với mọi), ký hiệu  gọi là lượng từ tồn tại Như vậy: x X P(x) đúng P(x) hằng đúng trên X x X P(x) đúng P(x) thực hiện được trên X Ví dụ: 1. x R (x 2 1 0) là mệnh đề đúng 2. x R (3x 1 0) là mệnh đề sai 3. x R (3x 1 0) là mệnh đề đúng 4. x N (3x 1 0) là mệnh đề sai e. Lượng từ trên các hàm mệnh đề nhiều biến Cho hàm mệnh đề 2 biến Px,y) xác định trên X x Y. Khi đó với mỗi y cố định x X P(x,y), x X P(x,y) là các mệnh đề, do đó ta được các hàm mệnh đề x X P(x,y), x X P(x,y) xác định theo y Y. Ta có thể áp dụng các lượng từ với mọi và tồn tại lên các hàm mệnh đề này để được các mệnh đề xác định: x X y Y P(x,y), x X y Y P(x,y) , x X y Y P(x,y) , x X y Y P(x,y) f. Mối liên hệ giữa 2 mệnh đề phổ dụng và tồn tại Cho P(x) là hàm mệnh đề xác định trên X, khi đó ta có: 1. x XP(x)  x X P ( x ) ; 2. x XP(x)  x X P ( x ) 1.4 Suy luận toán học & các phương pháp chứng minh 1.4.1 Qui tắc suy luận Giả sử A1, A2, , An, B là các biểu thức logic. Ta nói B là hệ quả logic của A1, A2, , An nếu với mọi bộ giá trị chân lý có thể nhận của bộ biến mệnh đề có mặt trong trong các biểu thức đó mà A1, A2, , An đồng thời nhận giá trị 1 đều có B nhận giá trị 1. 15
9. Khi B là hệ quả logic của A1, A2, , An thì nói rằng có một qui tắc suy luận từ các tiên đề A1, A2, , An tới hệ quả logic B. A1 , A2 , , An Qui tắc suy luận trên được kí hiệu là: hay A1, A2, , An = B B Ta có A1, A2, , An đồng thời nhận giá trị 1 khi và chỉ khi A1  A2   An nhận giá trị 1 Khi đó A1  A2   An B đúng A1  A2   An nhận giá 1 thì B cũng nhận giá trị 1 Hay có qui tắc suy luận có luật Như vậy để chứng minh qui tắc suy luận ta có thể dùng một trong 2 phương pháp sau: 1. Lập bảng giá trị chân lý, xét theo đúng định nghĩa 2. Chỉ ra mệnh đề là hằng đúng. p, p q Ví dụ 1: Chứng minh qui tắc suy luận q Cách 1: Lập bảng giá trị chân lý p q p q 0 0 1 0 1 1 1 0 0 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có một bộ giá trị của p,q làm cho p,q nhận giá trị 1 thì cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy luận Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh ( p  ( p q)) q 1( hằng đúng) Thực vậy: ( p  ( p q)) q p  (p  q) q (p  p)  (p  q) q p  q q p  q  q 1 (ĐPCM) p q, q r Ví dụ 2: Chứng minh qui tắc suy luận p r Cách 1: Lập bảng giá trị chân lý p q r p q q r p r 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 16
10. 1 1 0 1 0 0 1 1 1 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có 4 bộ giá trị của p,q, r làm cho p q và q r đồng thời nhận giá trị 1 thì p r cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy p q, q r luận p r Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh (( p q)  (q r)) ( p r) 1( hằng đúng) Thực vậy: (( p q)  (q r)) (p r) (p  q)  (q  r)  p  r (p  q)  p  (q  r)  r q  q  p  r 1 p  r 1 (ĐPCM) 1.4.2 Các qui tắc suy luận cơ bản Trong suy luận toán học người ta thường dùng 28 qui tắc suy luận cơ bản sau, các qui tắc này đã được chứng minh theo 2 phương pháp trên. 2 ví dụ vừa xét là qui tắc suy luận số1 và qui tắc số 3. p q, p p q,q 1. 2. q p p q, q r p  q,q  r 3. 4. p r p  r p q,q p p  q, p 5. 6. p  q q p r,q r p q, p r 7. 8. p  q r p q  r p q,r s p  q,r  s 9. 10. p  r q  s p  r  q  s p q,r s p  q,r  s 11. 12. p  r q  s p  r  q  s p, q p  q 13. 14. p  q p p p p 15. 16. ; p  q p p p q q p p  q 17. ; 18. q p p q p q p  q r p q r p  q r 19. 20. p q r p  q r p r 17
11. p q r p q, p q 21. 22. q p r q p q  q p q, q 23. 24. p p p p p  q r  r p  q p 25. 26. ; p p q p q x   x x  x Q x , P a 27. 28.  a Q a 1.4.3 Hai kiểu suy luận a.Suy luận diễn dịch (Suy diễn): Là suy luận theo các quy tắc suy luận, xác định rằng nếu các tiên đề là đúng thì kết luận rút ra cũng phải đúng. Ví dụ: Từ 2 tiền đề >3 và <4 suy ra 3< <4, trong suy luận này ta đã sử dụng qui tắc suy luận số 13. b.Suy luận có lý: Là suy luận không theo qui tắc suy luận nào để từ tiên đề đã có rút ra được kết luận xác định. Nếu các tiền đề đều đúng thì kết luận chưa chắc đã đúng mà chỉ mang tính chất dự đoán, giả thuyết. Trong toán học thường dùng 2 kiểu suy luận có lý, đó là phép qui nạp không hoàn và phép tương tự. Hai kiểu suy luận này có vai trò đặc biệt quan trọng trong phát minh sáng tạo, nó giúp con người đưa ra những phán đoán về các kết quả mới. 1.4.4 Các phương pháp chứng minh a. Khái niệm về chứng minh A1 , A2 , , An Khi có quy tắc suy luận nếu tất cả các tiền đề A1, A2, , An đều B đúng thì kết luận logic B gọi là kết luận chứng minh và mệnh đề B gọi là đã được chứng minh. Như vậy một kết luận chứng minh là một kết luận logic của các tiền đề đúng. Ví dụ: Có qui tắc suy luận: Với a,b R, nếu a=b thì a2=b2 Đặt A: a=b; B: a2=b2 1/ A:2=2 ; B:22=22 ; có A B nên B:22=22 là một kết luận logic và B cũng là một kết luận chứng minh vì tiền đề A là đúng. 2/ A: -2=2 ; B:(-2)2=22 ; có A B nên B:22=22 là một kết luận logic nhưng B không phải là một kết luận chứng minh vì tiền đề A là sai. b. Kết cấu của chứng minh Một chứng minh có 3 bộ phận cấu thành: 1. Luận đề: Là mệnh đề cần phải chứng minh 2. Luận cứ: Là các mệnh đề được thừa nhận được lấy ra làm tiên đề trong mỗi suy luận. 3. Luận chứng: Là các quy tắc suy luận được vận dụng trong mỗi bước suy luận của chứng minh. c. Các phương pháp chứng minh trong toán học i.Chứng minh theo phương pháp trực tiếp Mệnh đề B gọi là được chứng minh trực tiếp nếu ta chỉ ra được B là kí hiệu logic của các tiền đề đúng A1, A2, , An Ví dụ: Chứng minh trực tiếp định lý: Nếu n là số lẻ thì n2 cũng là số lẻ Chứng minh: Theo giả thiết n là số lẻ n=2k+1, k Z 18
12. n2=4k2+4k+1, k Z hay n2= 2(2k2+2k)+1=2k’+1, k’ Z n2 là số lẻ (ĐPCM) ii.Chứng minh theo phương pháp phản chứng: Là phương pháp sử dụng qui tắc suy luận số 26. p  q r  r p  q p 26. ; p q p q Ví dụ: Chứng minh rằng: Nếu 3n+2 là số lẻ thì n cũng lẻ Đặt p: 3n+2 là số lẻ q: n là số lẻ Ta phải chứng minh p q Giả thiết có q tức là n là số chẵn n=2k, k Z Khi đó ta có 3n+2=3.2k+2=2(3k+1)=2k’ , k’ Z 3n+2 là số chẵn, điều này mâu thuẫn với giả thiết p đã cho 3n+2 là số lẻ. Vậy theo quy tắc suy luận số 26 ta có ĐPCM hay p q iii. Chứng minh theo phương pháp phân chia trường hợp Cho P(x) là một hàm mệnh đề xác định trên X. Giả sử X= X1  X 2   X n với x X P(x),x X P(x), ,x X P(x) X  X  Khi đó ta có quy tắc suy luận 1 2 n i j x XP(x) Ví dụ: Cho n Z, hãy chứng minh n3+2n chia hết cho 3 Ta có n3+2n=n(n2+2) sẽ chia hết cho 3 khi n là bội của 3 Với mỗi n Z, gọi r = n mod 3 khi đó ta có: 1/ r=0 ; 2/ r=1; 3/ r=2 Có 3 trường hợp (r=0)(r=1)(r=2) Xét trường hợp1: với r=0, n có dạng n=3k, k Z n3+2n =3k(9k2+2) chia hết cho 3 Xét trường hợp 2: với r=1, n có dạng n=3k+1, k Z n3+2n =3(k+1)(9k2+6k+3)=(3k+1)3(3k2+2k+1) chia hết cho 3 Xét trường hợp 3: với r=2, n có dạng n=3k+2, k Z n3+2n =3(k+2)(9k2+12k+6)=(3k+2)3(3k2+4k+2) chia hết cho 3 Như vậy trong mọi trường hợp (r=0), (r=1), (r=2) có thể có ta đều chứng minh được n3+2n chia hết cho 3. Vậy có ĐPCM iv. Chứng minh theo qui nạp toán học: Giả sử P(n) là một khẳng định phụ thuộc vào số tự nhiên n, cần phải chứng minh P(n) đúng với n. Ta không thể dùng phép qui nạp hoàn toàn vì tập N là vô hạn, không thể tiến hành kiểm tra tất cả các trường hợp riêng. Nếu dùng phép quy nạp không hoàn toàn để kết luận thì có thể dẫn đến sai lầm. Để khắc phục khó khăn này ta dùng một phương pháp suy luận đặc biệt gọi là phương pháp qui nạp toán học. Giả sử cần chứng minh tính chất đúng đắn của khẳng định P(n) với mọi số tự nhiên n 0 (n Z+), ta thực hiện: 1. Trước tiên kiểm tra P(1) đúng 2. Sau đó chứng minh rằng, với mọi số tự nhiên k 1, từ tính đúng đắn của khẳng định n=k cũng suy ra được khẳng định đúng khi n=k+1. Khi khẳng định đúng với n=k+1 thì khẳng định P(n) được coi là đúng với mọi số tự nhiên n. Một hình thức khác của phương pháp qui nạp toán học: Chứng minh n n0 P(n) là đúng 1. Chỉ ra khẳng định P(n0) là đúng 2. Nếu khẳng định P(k) là đúng thì khẳng định P(k+1) cũng đúng với mọi số tự nhiên k n0 ( hay nếu P(1), P(2), ,P(k) đúng thì P(k+1) cũng đúng) 19