chứng minh các mệnh đề suy diễn
C HỨ N G M I N H C Á C M Ệ N H Đ Ề SUY D I ỄN ...
C HỨ N G M I N H C Á C M Ệ N H Đ Ề SUY D I ỄN
Bây giờ chúng ta sẽ làm rõ hơn về các phương pháp xây dựng chứng minh,
chúng ta sẽ mô tả các chứng minh cho các loại mệnh đề khác nhau.
Trong nhiều định lý, kỹ thuật chứng minh các mệnh đề kiểu kéo theo là quan trọng. Ta thấy p→q sẽ luôn đúng trừ khi p là đúng nhưng q sai. Chú ý rằng khi p→q được chứng minh, nếu chúng ta chỉ cần chỉ ra q là đúng nếu p đúng;
C h ứ n g m i n h tr ự c tiếp
Ta thấy p→q sẽ được chứng minh bằng cách chỉ ra p là đúng, sau đó q phải là đúng. Điều này cho thấy rằng không thể có p đúng và q sai cùng xảy ra. Một chứng minh như vậy được gọi là chứng minh trực tiếp. Để áp dụng chứng minh kiểu này, giả định p là đúng và dùng luật suy diễn cùng các định lý đã được chứng minh để chỉ ra rằng q phải là đúng.
Chứng minh trực tiếp là phương pháp chứng minh suy diễn trực tiếp dẫn từ giả thiết đến kết luận thông qua việc áp dụng các luật suy diễn (hay qui tắc suy diễn), các định lý, các nguyên lý và các kết quả đã biết. Ðây là một kiểu tư duy giải bài toán rất tự nhiên và người ta thường xuyên sử dụng. Trong khi suy nghĩ để tìm ra cách chứng minh theo phương pháp nầy người ta thường phải tự trả lời các câu hỏi sau
đây:
- Ta sẽ dùng luật suy diễn nào?
- Các định lý nào, các kết qua nào có thể sử dụng được đề ta suy ra được một điều gì đó từ những sự kiện, những yếu tố hiện đang có?
- Việc áp dụng định lý có khả năng sẽ dẫn đến kết luận hay kết quả mong
muốn hay không?
- Trong trường hợp ở một bước suy diễn nào đó có nhiều định lý hay nhiều luật nào đó có thể áp dụng được và cũng có kkhả năng sẽ dẫn đến kết luận hay kết quả mong muốn thì ta sẽ chọn cái nào?
- Ðến một giai đoạn nào đó, khi gặp phải sự bế tắc thì ta sẽ phải tự hỏi rằng phải chăng bài toán không có lời giải, hay vì kiến thức của ta chưa đủ, hay ta phải sử dụng một phương pháp chứng minh nào khác?
Quả thật là không thể trả lời được các câu hỏi một cách đầy đủ và chính xác. Nó phụ thuộc chủ yếu vào kiến thức, kinh nghiệm của người giải bài toán và cả sự nhạy bén, tính năng động sáng tạo của họ. Tuy nhiên Những câu hỏi trên cho ta một sự định hướng chung của quá trình suy nghĩ. Ngoài ra, cũng cần nói thêm rằng chúng
là cơ sở cho việc phát triển các hệ chương trình trợ giúp giải toán một cách "thông minh" trên máy tính được thiết kế theo phương pháp chứng minh nầy.
Dưới đây, chúng ta sẽ xem xét một vài ví dụ về phương pháp chứng minh trực tiếp.
Vídụ1:Chứng minh rằng { Nếu n là số lẻ thì n2 là số lẻ }
Giải : Giả sử rằng giả thiết của định lý này là đúng, tức là n là số lẻ. Ta có n
= 2k + 1 ( k=0,1,2,...)
n2 = (2k + 1)2 = 4k2 + 4k + 1
= 2(2k2 + 2k) + 1 là lẻ.
Vậy nếu n là số lẻ thì n2 là số lẻ.
Vídụ2:Cho hàm mệnh đề P(n) = " Nếu n>1 thì n2 >n " Chứng minh rằng P(n) là đúng với n là số nguyên dương.
Giải : Giả sử n > 1 là đúng, ta có :
n = 1 + k ( k ≥ 1)
n2 = ( 1 + k )2 = 1 + 2k + k2 = (1 + k) + k + k2 > n
Vậy Nếu n>1 thì n2 >n .
Vídụ3Giả sử p, r, s, t, u là các mệnh đề sau cho ta có các mệnh đề sau đây la`
đúng:
(1) p →r (2) r → s (3) t ∨ s (4) t ∨ u (5) u.
Hãy chứng minh mệnh đề p là sai, tức là chứng minh mệnh đề p la` đúng.
C h ứ n g m i nh :
Áp dụng luật suy diễn tam đoạn luận, từ (1) và (2) ta suy ra: (6) p → s
Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (3) dưới dạng:
(7) s → t
Áp dụng luật suy diễn tam đoạn luận, từ (6) và (7) ta suy ra:
(8) p → t
Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (4) dưới dạng:
(9) t → u
Áp dụng luật suy diễn tam đoạn luận, từ (8) và (9) ta suy ra: (10) p → u
Áp dụng luật suy diễn Modus Tollens, từ (10) và (5) ta suy ra: (11) p
Vậy mệnh đề p là đúng.
Vídụ4:Cho p(x), q(x) và r(x) là các vị từ theo biến x (x ∈ A), và a là một phần tử
cố định nhưng tùy ý của tập hợp A. Giả sử ta có các mệnh đề sau đây la` đúng:
Chứng minh rằng mệnh đề r(a) la` đúng.
C h ứ n g m i nh :
Áp dụng kết quả từ bảng 3 trong 3.2 ta suy ra: (4) x∈ A : p(x) → r(x)
Áp dụng kết quả bảng 3 trong 3.2 ta suy ra: (5) r(a)
Vậy mệnh đề r(a) la` đúng.
3 . 3 . 2 C h ứ n g m i n h gi á n tiếp
Vì mệnh đề P→Q ⇔ (¬Q → ¬P). Do đó, để chứng minh mệnh đề P→Q
là đúng, người ta có thể chỉ ra rằng mệnh đề ¬Q → ¬P là đúng.
Vídụ 5:Chứng minh định lý { Nếu 3n + 2 là số lẻ thì n là số lẻ }
Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức n là chẳn. Ta có
n = 2k( k∈ N )
3n + 2 = 3.2k + 2 = 2( 3k + 1 ) là số chẳn
Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ
Nh ậ n x ét
Có những bài toán có thể sử dụng phương pháp chứng minh trực tiếp hay gián tiếp đều được cả. Tuy nhiên, có những bài toán không thể sử dụng phương pháp chứng minh trực tiếp được hoặc sử dụng trực tiếp thì bài giải sẽ dài dòng phức tạp hơn là sử dụng chứng minh gián tiếp ( hoặc ngược lại). Đây chính là sự khác biệt
của chứng minh trực tiếp và chứng minh gián tiếp.
Ví d ụ 6 :
Sử dụng chứng minh gián tiếp để chứng minh rằng " Nếu n>1 thì n2
>n " Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức là n2 < n
Vì n là nguyên dương nên ta có thể chia 2 vế cho n mà bất đẳng thức không đổi chiều. Ta có : n < 1.
Vậy từ ¬Q đã dẫn đến ¬P. Do đó, Nếu n>1 thì n2 >n.
Vídụ7:Sử dụng chứng minh trực tiếp để chứng minh rằng " Nếu 3n + 2 là số lẻ thì n là số lẻ ".
Giải : Giả sử 3n + 2 là số lẻ là đúng.
Nhận thấy rằng vì 2 là số chẳn nên suy ra được 3n là số lẻ. Vì 3 là số lẻ do đó n là số lẻ.
Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ.
Ởđâychúngta phảichứngminhthêmđịnhlýlàtíchcủa2sốlẻlàmộtsốlẻthì bàigiảichặtchẽhơn.Dođó,trongbàitoánnàyviệcsửdụngchứngminhgiántiếp làhayhơndùngtrựctiếp.