Chứng minh vacuous & Chứng minh trivial

C h ứ n g m i n h va c u ous

Giả sử giả thiết p trong phép kéo theo p→q là sai. Khi đó ta có thể suy ra ngay phép kéo theo p→q luôn đúng, bởi vì câu lệnh có dạng F→T hay F→F, nên nó luôn đúng. Chính vì vậy, nếu chúng ta chỉ ra p là sai, khi đó phép chứng minh của chúng ta gọi là chứng minh vacuous.

Chứng minh vacuous thường dùng cho các trường hợp đặc biệt khi phép kéo theo là

đúng cho tất cả các số nguyên dương.

Vídụ10: Chứng minh rằng mệnh đề P(0) là đúng trong đó P(n) là mệnh đề “nếu

n>1 thì n2>n”.

Giải: Mệnh đề P(0) chỉ ra rằng “nếu 0>1 thì 02>0”. Bởi vì giả thiết 0>1 là sai, do đó

P(0) là đúng.

Ví d ụ 11:

Với mọi n, nếu n vừa lẻ vừa chẵn, thì n2 = n + n.

Giải: Khẳng định “n vừa lẻ vừa chẵn” là sai, bởi vì không có số nào vừa lẻ vừa

chẵn. Do vậy mọi kết luận là đúng.

C h ứ n g m i n h tr i vial

Giả sử rằng kết luận q trong phép duy dẫn p→q là đúng. Khi đó p→q là đúng, bởi vì câu lệnh dạng T→T hay F→T đều là đúng. Vì vậy, nếu để chứng minh q là đúng, thì khi đó chứng minh được gọi là chứng minh trivial. Chứng minh trivial thường quan trọng trong khi chứng minh một số trường hợp đặc biệt.

Ví d ụ 12:

Coi P(n) là mệnh đề: “nếu a và b là hai số nguyên dương và a>=b thì an>=bn”. Chứng minh rằng P(0) là đúng.

Giải: Mệnh đề P(0) là “nếu a>=b, thì a0>=b0 ” bởi vì a0=b0 =1, vậy P(0) là đúng. Vì vậy, P(0) là đúng. Đây là một ví dụ của chứng minh trivial. Như vậy là khẳng định a>=b không cần thiết trong chứng minh.

Vídụ13:

Với mọi số tự nhiên n, nếu n là tổng của hai số nguyên tố, thì hoặc n là chẵn

hoặc n là lẻ.

Giải: Bất kỳ một số tự nhiên n nào cũng hoặc là chẵn hoặc là lẻ. Do vậy kết luận của phép duy dẫn là đúng bất chấp điều kiện là đúng hay sai. Phép duy dẫn được gọi là phép duy dẫn trivial□