Chứng minh gián tiếp là gì

* Phát triển cần tài ngun dồi dào

- Trước quan niệm: PT kinh tế quốc gia phụ thuộc tài ngun

- Nước phát triển, nghèo tài ngun (Japan, Singapore)

- Nước giàu tài ngun, nước nghèo chậm PT (Châu Phi)

* Muốn tăng năng suất cây lúa cần áp dụng ‘’3 giảm 3 tăng’’

- KQ nc năng suất giảm 200 kg/ha đối với chân ruộng sạ dày,

bón nhiều phân và phun nhiều thuốc trừ sâu.

- Tại Philippin nơng dân sử dụng PP truyền thống, khơng biết 3

giảm 3 tăng năng suất chỉ đạt 3 T/ha

- NC của Viện lúa Ơ mơn khi sạ thưa, bón ít N và phun ít thuốc

trừ sâu đã nâng NS lên 30%.

• Chứng minh gián tiếp là phép chứng minh tính

đúng của luận đề được chứng minh bằng tính khơng

đúng của phản luận đề

Phương pháp bác bỏ giả thuyết

• Là CM chỉ rõ tính khơng đúng của một phán đốn

• Chứng minh bác bỏ một trong 3 yếu tố: hoặc luận

đề sai hoặc luận cứ sai hoặc luận chứng sai

EX:

Say rượu khơng xảy ra tai nạn

Áp dụng 3 giảm 3 tăng khơng làm tăng năng suất

Chương 4

CƠ SỞ LÝ LUẬN CỦA ĐỀ TÀI

4.1. Khái niệm “cơ sở lý luận của đề tài”

4.2. Nội dung cơ sở lý luận của đề tài

4.1 Khái niệm cơ sở khoa học

Cơ sở lý luận là luận cứ lý thuyết được chứng minh bởi

các nghiên cứu trước (trích dẫn tài liệu).

Lý thuyết là một hệ thống tri thức khoa học, cung cấp

một quan niệm hoàn chỉnh về bản chất sự vật và

mối liên hệ cơ bản giữa sự vật với thế giới hiện

thực. Lý thuyết gồm: khái niệm, phạm trù, qui luật

về sự vật.

Ý nghóa của CSLL mượn để chứng minh giả thuyết

•

- tiết kiệm vật chất, thời gian, tài chính

•

- làm nền tảng kiến giải cho những luận cứ thực

tiễn (thực nghiệm)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây  (1.03 MB, 21 trang )

. Chứng minh tầm thường

. Chứng minh trực tiếp

. Chứng minh gián tiếp

. Chứng minh phản chứng

. Chứng minh qui nạp

Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 29
2.2.
Suy luận toán học
2.2.1. Khái niệm
Suy luận được xem là một trong những nền tảng xây dựng nên các ngành khoa
học tự nhiên. Từ xưa đến nay, nhờ suy luận mà người ta có thể nhận thức được cái
chưa biết từ những cái đã biết. Suy luận còn là cơ sở của sự sáng tạo. Từ các phán
đoán, đưa đến các chứng minh để chấp nhận hay bác bỏ một vấn đề nào đó.
Suy luận toán học dựa trên nền tả
ng của các phép toán mệnh đề, chủ yếu là
phép kéo theo. Để chứng minh một vấn đề nào đó, thông thường người ta phải xác
định điểm ban đầu (có thể gọi là giả thiết) và điểm kết thúc (gọi là kết luận). Quá trình
đi từ giả thiết đến kết luận gọi là quá trình chứng minh và quá trình này đươc thực thi
bằng cách nào thì gọi đó là phương pháp chứng minh.
Các phương pháp chứng minh là rất quan trọng vì không nhữ
ng chúng thường
được sử dụng trong toán học mà còn được áp dụng nhiều trong tin học. Ví dụ, sự kiểm

tra tính đúng đắn của một chương trình, của một hệ điều hành, xây dựng các luật suy
diễn trong lĩnh vực trí tuệ nhận tạo... Do đó, chúng ta cần phải nắm vững các phương
pháp chứng minh.
Tuy nhên, có những phương pháp chứng minh đúng vì nó được dựa trên cơ sở
của một mệnh đề đúng (hằng đúng) và có những phương pháp chứng minh sai. Các
phương pháp chứng minh sai này là cố ý hoặc vô ý. Khi phương pháp chứng minh
dựa trên một hằng sai thì sẽ mang lại kết quả sai nhưng người ta vẫn cho là đúng thì
được gọi là cố ý. Đôi khi có những phương pháp chứng minh dựa trên một tiếp liên
(có khi mệnh đề là đúng nhưng cũng có lúc sai) mà người ta tưởng lầm là hằng đúng
nên cho là kết quả bao giờ cũng đúng thì trường hợp này gọi là vô ý (hay ngộ nhận).
Sau đây, chúng ta sẽ đi tìm hiểu các qui tắc suy luận.
2.2.2. Các qui tắc suy luận
Như đã giới thiệu ở trên, những suy luận có dùng các qui tắc suy diễn gọi là suy
luận có cơ sở. Khi tất cả các suy luận có cơ sở là đúng thì sẽ dẫn đến một kết luận
đúng. Một suy luận có cơ sở có thể dẫn đến một kết luận sai nếu một trong các mệnh
đề đã dùng trong suy diễn là sai. Sau đây là bảng các qui tắc suy luận đúng.

Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 30
Quy Tắc Hằng đúng Tên Luật
QP
P

P(PQ)
Cộng
P
QP

(PQ)P
Rút gọn
Q
QP
P

(P(PQ))Q
Modus Ponens
P
QP
Q
¬

¬

(¬Q(PQ))  ¬P
Modus Tollens
RP
RQ
QP

((PQ)(QR))

(PR)
Tam đoạn luận giả
định
Q
QP

(PQ)  Q
Tam đoạn luận tuyển

Trong các phân số của qui tắc thì các giả thiết được viết trên tử số, kết luận
được viết dưới mẫu số. Kí hiệu

có nghĩa là "vậy thì", "do đó",...
Ví dụ : Qui tắc suy luận nào là cơ sở của suy diễn sau :

" Nếu hôm nay trời mưa thì cô ta không đến,
Nếu cô ta không đến thì ngày mai cô ta đến,
Vậy thì, nếu hôm nay trời mưa thì ngày mai cô ta đến."
Đây là suy diễn dựa trên qui tắc tam đoạn luận giả định.

"Nếu hôm nay tuyết rơi thì trường đại học đóng cửa.
Hôm nay trường đại học không đóng cửa.
Do đó, hôm nay đã không có tuyết rơi "
Đây là suy diễn dựa trên qui tắc Modus Tollens

" Alice giỏi toán. Do đó, Alice giỏi toán hoặc tin"
Đây là suy diễn dựa trên qui tắc cộng.

Ngụy biện
Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 31
Các phương pháp chứng minh sai còn được gọi là ngụy biện. Ngụy biện
giống như qui tắc suy luận nhưng không dựa trên một hằng đúng mà chỉ là
một tiếp liên. Đây chính là sự khác nhau cơ bản giữa suy luận đúng và suy
luận sai. Loại suy luận sai này được gọi là ngộ nhận kết luận.
Ví dụ : Xét xem suy diễn sau là có cơ sở đúng không ?
" Nếu bạn đã giải hết bài tập trong sách toán r
ời rạc 2 này thì bạn nắm
vững logic. Bạn nắm vững logic vậy thì bạn đã giải hết bài tập trong sách
toán rời rạc 2 này".
Nhận thấy suy diễn này là dựa trên mệnh đề sau :
((PQ)  Q)  P
Trong đó:
P = "Bạn đã giải hết bài tập trong sách toán rời rạc 2"
Q = "Bạn nắm vững logic"
Mệnh đề ((PQ)  Q)  P không phải là hằng đúng vì nó sẽ sai khi P
là F và Q là T. Do đó, suy diễn này không hoàn toàn có cơ sở đúng. Bởi vì,
khi Q là T nghĩa là bạn đã nắm vững logic nhưng không chắc là bạn đã giải
hết bài tập trong sách toán rời rạc 2 này mà có thể giải sách khác (P là F).
2.3.
Các phương pháp chứng minh
Như đã giới thiệu trong phần trên, mỗi bài toán cần chứng minh thông thường
đều có hai phần chính là giả thiết và kết luận. Việc chỉ ra được cái nào là giả thiết, cái
nào là kết luận sẽ giúp cho việc chứng minh dễ dàng hơn thông qua việc sử dụng
phương pháp chứng minh thích hợp. Do đó, các phương pháp chứng minh trong dạng

bài toán này là có liên quan đến mệnh đề kéo theo.
Vậy, trước khi tìm hiểu các phương pháp chứng minh, chúng ta hãy xem lại
bảng chân trị
của mệnh đề P kéo theo Q ( với P là giả thiết và Q là kết luận). Các
trường hợp để cho mệnh đề P kéo theo Q là đúng cũng chính là các phương pháp để
chứng minh bài toán đúng.

p

q

p

q
Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 32

T

T

T

T

F

F

F

T

T

F

F

T

Nhận thấy rằng, PQ là đúng có 3 trường hợp. Các trường hợp này chính là
các phương pháp chứng minh sẽ được trình bày dưới đây.
Trước khi đi vào các phương pháp chứng minh, có một khái niệm mà chúng ta
cần tìm hiểu, đó là khái niệm về "hàm mệnh đề".

Hàm mệnh đề :
¾ Cho A là một tập họp không rỗng sao cho ứng với mỗi xA ta có một mệnh
đề, ký hiệu là P(x). Bấy giờ ta nói P (hay P(x)) là một hàm mệnh đề theo biến xA.
Như vậy, khi nói ứng với mỗi xA, ta có một mệnh đề P(x), nghĩa là khi đó tính đúng
sai của P(x) được hoàn toàn xác định phụ thuộc vào từng giá trị của xA.
Ví dụ : Cho hàm mệnh đề

P(x) = { x là số lẻ } ; xN
Ta có : P(1) là mệnh đề đúng
P(2) là mệnh đề sai.
¾ Tổng quát, với các tập họp không rỗng A
1
, A
2
, ..., A
n
, sao cho ứng với mỗi
x
1
A
1
, x
2
A
2
, ..., x
n
A
n
, ta có một mệnh đề, ký hiệu P(x
1
, x
2
, ...,x
n
). Ta nói P(x
1

,
x
2
, ...,x
n
) là một hàm mệnh đề theo n biến x.
Ví dụ : Cho hàm mệnh đề
P(x,y,z) = { 2x + y - z = 0 } x,y,zZ
Ta có : P(x,y,z) là mệnh đề đúng khi x = 1, y = -1, z = 1.
P(x,y,z) là mệnh đề sai khi x = 1, y = 1, z = 1.
2.3.1. Chứng minh rỗng ( P là sai)
Dựa vào 2 dòng cuối của bảng chân trị, nhận thấy rằng khi P sai, bất
chấp kết luận Q thế nào thì mệnh đề PQ là luôn đúng. Vậy, để chứng minh mệnh đề
Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 33
PQ là đúng, người ta chỉ cần chứng minh rằng P là sai. Phương pháp chứng minh
này được gọi là chứng minh rỗng.
Phương pháp chứng minh rỗng thường được sử dụng để chứng minh các trường
hợp đặc biệt của định lý. Trường hợp tổng quát thì định lý này luôn đúng với mọi số n
nguyên dương.
Ví dụ : Cho hàm mệnh đề P(n) = " Nếu n>1 thì n
2
>n "
Chứng minh rằng P(1) là đúng.
Giải : Ta có P(1) = { Nếu 1 >1 thì 1
2
>1 }
Nhận thấy rằng giả thiết 1>1 là sai, bất chấp kết luận 1

2
>1 là đúng hay
sai thì P(1) là đúng.
2.3.2. Chứng minh tầm thường (Q là đúng)
Dựa vào dòng 1 và dòng 3 của bảng chân trị, nhận thấy rằng khi Q đúng,
bất chấp giả thiết P là đúng hay sai thì mệnh đề PQ là luôn đúng. Vậy, để chứng
minh mệnh đề PQ là đúng, người ta chỉ cần chứng minh rằng Q là đúng. Phương
pháp chứng minh này được gọi là chứng minh tầm thường.
Phương pháp chứng minh tầm thường cũng được sử dụng để chứng minh các
trường hợp đặc biệt của định lý. Trường hợp tổng quát thì định lý này luôn đúng với
mọi số n nguyên dương.
Ví dụ : Cho hàm mệnh đề
P(n) = { Nếu a và b là 2 số nguyên dương và a  b thì a
n
 b
n
}
Chứng minh rằng P(0) là đúng.
Giải : Ta có a
0
= b
0
=1. Do đó a
0
 b
0
là đúng.
Vậy P(0) là đúng bất chấp giả thiết ab là đúng hay sai.
2.3.3. Chứng minh trực tiếp
Trong dòng 1 của bảng chân trị, mệnh đề P kéo theo Q có thể được chứng minh

bằng cách chỉ ra rằng nếu P đúng thì Q cũng phải đúng. Nghĩa là tổ hợp P đúng Q sai
không bao giờ xảy ra. Phương pháp này được gọi là chứng minh trực tiếp.
Vậy để thực hiện phương pháp chứng minh trực tiếp, người ta giả sử rằng P là
đúng, sau đó sử dụng các qui tắc suy luận hay các định lý để chỉ ra rằ
ng Q là đúng và
kết luận PQ là đúng.
Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 34
Ví dụ 1: Chứng minh rằng { Nếu n là số lẻ thì n
2
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,...)
 n
2
= (2k + 1)
2
= 4k
2
+ 4k + 1
= 2(2k + 2k) + 1 là lẻ.
Vậy nếu n là số lẻ thì n
2
là số lẻ.
Ví dụ 2 : Cho hàm mệnh đề P(n) = " Nếu n>1 thì n
2
>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)
 n
2
= ( 1 + k )
2
= 1 + 2k + k
2
= (1 + k) + k + k
2
> n
Vậy Nếu n>1 thì n
2
>n .
2.3.4. Chứng minh gián tiếp
Vì mệnh đề PQ  ¬Q  ¬P. Do đó, để chứng minh mệnh đề PQ
là đúng, người ta có thể chỉ ra rằng mệnh đề ¬Q  ¬P là đúng.
Ví dụ : 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 ( kN )
 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ụ 1 :
Sử dụng chứng minh gián tiếp để chứng minh rằng " Nếu n>1 thì n
2
>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à n
2
< n.
Chương 2: Suy luận toán học & Các phương pháp chứng minh

Trang 35
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ì n
2
>n.
Ví dụ 2 : 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ẻ.
Ở đây chúng ta phải chứng minh thêm định lý là tích của 2 số
lẻ là một số lẻ thì bài
giải chặt chẽ hơn. Do đó, trong bài toán này việc sử dụng chứng minh gián tiếp là hay
hơn dùng trực tiếp.
Để chứng minh mệnh đề có dạng :
(P
1

P
2
...P
n
)  Q
Chúng ta có thể sử dụng hằng đúng sau :
((P
1
P
2
...P
n
) Q)  ((P
1
Q)(P
2
Q)....(P
n
Q))
Cách chứng minh này gọi là chứng minh từng trường hợp.
Ví dụ 3: Chứng minh rằng:
" Nếu n không chia hết cho 3 thì n
2
không chia hết cho 3".
Giải : Gọi P là mệnh đề "n không chia hết cho 3" và Q là mệnh đề "n
2

không chia hết cho 3". Khi đó, P tương đương với P
1
 P

2
. Trong đó:
P
1
= " n mod 3 =1"
P
2
= " n mod 3 =2"
Vậy, để chứng minh P  Q là đúng, có thể chứng minh rằng:
(P
1
 P
2
)  Q hay là (P
1
 Q )  ( P
2
Q)
Giả sử P
1
là đúng. Ta có, n mod 3 = 1. Đặt n = 3k + 1
( k là số nguyên nào đó).
Suy ra
n
2
= ( 3k+1)
2
= 9k
2
+ 6k + 1 = 3(3k

2
+ 2k) + 1 không chia chẳn cho 3.
Do đó, P
1
 Q là đúng.