08/14/14 (c)2001-2003, Michae
l P. Frank
1
Module #2 - Proofs
University of Florida
Dept. of Computer & Information Science & Engineering
COT 3100
Applications of Discrete Structures
Dr. Michael P. Frank
Slides for a Course Based on the Text
Slides for a Course Based on the Text
Discrete Mathematics & Its Applications
Discrete Mathematics & Its Applications


(5
(5
th
th
Edition)
Edition)
by Kenneth H. Rosen
by Kenneth H. Rosen
08/14/14 (c)2001-2003, Michae
l P. Frank
2
Module #2 - Proofs
Bài 2:
Các phương pháp chứng minh cơ bản
Rosen 5
Rosen 5

th
th
ed., §1.5
ed., §1.5
48 slides, ~3 lectures
48 slides, ~3 lectures
08/14/14 (c)2001-2003, Michae
l P. Frank
3
Module #2 - Proofs
Bản chất và tầm quan trọng của
chứng minh
•
Trong toán học, chứng minh là:
Trong toán học, chứng minh là:
–
Diễn giải đúng đắn (suy luận được, đúng về logic) và
Diễn giải đúng đắn (suy luận được, đúng về logic) và
hoàn chỉnh (rõ ràng, chi tiết) để xác định chân lý của
hoàn chỉnh (rõ ràng, chi tiết) để xác định chân lý của
khẳng định toán học một cách không từ chối được và
khẳng định toán học một cách không từ chối được và
chặt chẽ.
chặt chẽ.
•
Tại sao diễn giải cần đúng đắn và hoàn chỉnh?
Tại sao diễn giải cần đúng đắn và hoàn chỉnh?
–
Đúng đắn ngăn chúng ta khỏi bị lừa chính mình
Đúng đắn ngăn chúng ta khỏi bị lừa chính mình

.
.
–
Hoàn chỉnh cho phép bất kỳ ai có thể kiểm chứng kết
Hoàn chỉnh cho phép bất kỳ ai có thể kiểm chứng kết
quả
quả
.
.
•
Trong môn này (& cũng như các môn toán) đòi hỏi
Trong môn này (& cũng như các môn toán) đòi hỏi
chuân rất cao về chứng minh tính đúng đắn và hoàn
chuân rất cao về chứng minh tính đúng đắn và hoàn
chỉnh!!
chỉnh!!
08/14/14 (c)2001-2003, Michae
l P. Frank
4
Module #2 - Proofs
Tổng quan về §1.5
•
Các phương pháp chứng minh có thể được
Các phương pháp chứng minh có thể được
hình thức hoá trong thuật ngữ các luật suy
hình thức hoá trong thuật ngữ các luật suy
diễn logic (
diễn logic (
rules of logical inference)
rules of logical inference)

.
.
•
Chứng minh toán học có thể tự biểu diễn
Chứng minh toán học có thể tự biểu diễn
hình thức như cấu trúc rời rạc.
hình thức như cấu trúc rời rạc.
•
Chúng ta có thể xem lại các suy diễn đúng
Chúng ta có thể xem lại các suy diễn đúng
đắn và sai lầm và một số phương pháp
đắn và sai lầm và một số phương pháp
chứng minh.
chứng minh.
08/14/14 (c)2001-2003, Michae
l P. Frank
5
Module #2 - Proofs
Các ứng dụng chứng minh
•
Như bài tập trong trao đổi rõ ràng về các suy luận
Như bài tập trong trao đổi rõ ràng về các suy luận
logic trong bất cứ lĩnh vực học tập nào.
logic trong bất cứ lĩnh vực học tập nào.
•
Hoạt động cơ bản của toán học là khám phá và
Hoạt động cơ bản của toán học là khám phá và
làm sáng tỏ thông qua chứng minh các định lý
làm sáng tỏ thông qua chứng minh các định lý
mới lý thú.

mới lý thú.
•
Chứng minh định lý có ứng dụng trong kiểm
Chứng minh định lý có ứng dụng trong kiểm
chứng chương trình, an toàn máy tính và các hệ
chứng chương trình, an toàn máy tính và các hệ
suy luận tự động, v.v
suy luận tự động, v.v
•
Chứng minh định lý cho phép ta tin cậy vào tính
Chứng minh định lý cho phép ta tin cậy vào tính
đúng đắn của nó ngay cả trong tình huống căng
đúng đắn của nó ngay cả trong tình huống căng
thẳng nhất.
thẳng nhất.
08/14/14 (c)2001-2003, Michae
l P. Frank
6
Module #2 - Proofs
Thuật ngữ chứng minh
Proof Terminology
•
Định lý
Định lý
–
Khẳng định cần được chứng minh đúng đắn.
Khẳng định cần được chứng minh đúng đắn.
•
Tiên đề
Tiên đề

, nguyên lý, giả thuyết,
, nguyên lý, giả thuyết,
giả thiết
giả thiết
–
Các đề xuất (thường không được chứng minh)
Các đề xuất (thường không được chứng minh)
xác định cấu trúc mà ta đang suy luận về chúng.
xác định cấu trúc mà ta đang suy luận về chúng.
•
Các luật suy diễn
Các luật suy diễn
–
Mẫu suy luận đúng từ giả thiết đến kết luận.
Mẫu suy luận đúng từ giả thiết đến kết luận.
08/14/14 (c)2001-2003, Michae
l P. Frank
7
Module #2 - Proofs
Nói thêm về thuật ngữ
•
Bổ đề - định lý nhỏ sử dụng như bước đệm để
Bổ đề - định lý nhỏ sử dụng như bước đệm để
chứng minh định lý chính
chứng minh định lý chính
.
.
•
Hệ quả - định lý nhỏ được chứng minh bằng cách
Hệ quả - định lý nhỏ được chứng minh bằng cách

suy luận dễ dàng từ định lý chính.
suy luận dễ dàng từ định lý chính.
•
Giả thuyết - khẳng định mà giá trị chân lý đúng
Giả thuyết - khẳng định mà giá trị chân lý đúng
của nó chưa được chứng minh
của nó chưa được chứng minh
.
.


(Tuy nhi
(Tuy nhi
ên, giả
ên, giả
thuyết có thể được tin tưởng rộng rãi vào tính
thuyết có thể được tin tưởng rộng rãi vào tính
đúng đắn
đúng đắn
)
)
•
Lý thuyết – tập tất cả các định lý mà được chứng
Lý thuyết – tập tất cả các định lý mà được chứng
minh từ tập các tiên đề
minh từ tập các tiên đề
.
.
08/14/14 (c)2001-2003, Michae
l P. Frank

8
Module #2 - Proofs


Trực quan bằng đồ thị
…
Various Theorems
Various Theorems
The Axioms
The Axioms
of the Theory
of the Theory
A Particular Theory
A Particular Theory
A proof
A proof
08/14/14 (c)2001-2003, Michae
l P. Frank
9
Module #2 - Proofs
Luật suy diễn - Dạng tổng quát
•
Luật suy diễn là
Luật suy diễn là
–
Mẫu xác lập rằng nếu chúng ta biết tập các tiền
Mẫu xác lập rằng nếu chúng ta biết tập các tiền
đề (
đề (
antecedent)

antecedent)
ở một dạng nào đó là đúng, thì
ở một dạng nào đó là đúng, thì
chúng ta có thể suy luận một cách đúng đắn
chúng ta có thể suy luận một cách đúng đắn
rằng các mệnh đề kết quả (
rằng các mệnh đề kết quả (
consequent)
consequent)
là đúng.
là đúng.
•


antecedent 1
antecedent 1
antecedent 2 …
antecedent 2 …
∴
∴


consequent
consequent
“
“
∴
∴
” nghĩa là “khi đó”
” nghĩa là “khi đó”

08/14/14 (c)2001-2003, Michae
l P. Frank
10
Module #2 - Proofs
Luật suy diễn và phép kéo theo
•
Mỗi luật suy diễn đúng tương ứng với phép
Mỗi luật suy diễn đúng tương ứng với phép
kéo theo là hằng đúng.
kéo theo là hằng đúng.
•


antecedent 1 Luật suy diễn
antecedent 1 Luật suy diễn
antecedent 2 …
antecedent 2 …
∴
∴


consequent
consequent
•
Hằng đúng tương ứng:
Hằng đúng tương ứng:
((
((
ante. 1
ante. 1

)
)
∧
∧
(
(
ante. 2
ante. 2
)
)
∧
∧
…)
…)
→
→


consequent
consequent
08/14/14 (c)2001-2003, Michae
l P. Frank
11
Module #2 - Proofs
Một số luật suy diễn
•


p
p

Luật cộng
Luật cộng
∴
∴


p
p
∨
∨
q
q
•


p
p
∧
∧
q
q
Luật đơn giản
Luật đơn giản


∴
∴


p

p
•


p
p
Luật hội
Luật hội


q
q


∴
∴


p
p
∧
∧
q
q
08/14/14 (c)2001-2003, Michae
l P. Frank
12
Module #2 - Proofs
Modus Ponens & Tollens
•



p
p
Luật suy xét độc lập
Luật suy xét độc lập


p
p
→
→
q
q




(Rule of
(Rule of
modus ponens
modus ponens
)
)
∴
∴
q
q
•



¬
¬
q
q
p
p
→
→
q
q
Luật cách từ chối
Luật cách từ chối
∴¬
∴¬
p (
p (
Rule of
Rule of
modus tollens)
modus tollens)


“the mode of
affirming”
“the mode of denying”
08/14/14 (c)2001-2003, Michae
l P. Frank
13
Module #2 - Proofs

Luật tam đoạn luận
•


p
p
→
→
q
q
Luật tam đoạn luận kéo theo
Luật tam đoạn luận kéo theo


q
q
→
→
r
r
Rule of hypothetical syllogism
Rule of hypothetical syllogism
∴
∴
p
p
→
→
r
r

•
p
p
∨
∨


q Luật tam đoạn luận tuyển
q Luật tam đoạn luận tuyển


¬
¬
p
p
Rule of disjunctive syllogism
Rule of disjunctive syllogism
∴
∴


q
q
Aristotle
(ca. 384-322 B.C.)
08/14/14 (c)2001-2003, Michae
l P. Frank
14
Module #2 - Proofs
Chứng minh hình thức

•
Chứng minh hình thức của kết luận
Chứng minh hình thức của kết luận
C
C
, cho
, cho
trước tiền đề
trước tiền đề
p
p
1
1
,
,
p
p
2
2
,…
,…
,
,
p
p
n
n
bao gồm dãy các
bao gồm dãy các
bước

bước
, mỗi bước áp dụng một luật suy diễn
, mỗi bước áp dụng một luật suy diễn
cho một tiền đề hoặc các mệnh đề đã được
cho một tiền đề hoặc các mệnh đề đã được
chứng minh trước (
chứng minh trước (
antecedents
antecedents
) để tạo ra
) để tạo ra
mệnh đề đúng tiếp theo (the
mệnh đề đúng tiếp theo (the
consequent
consequent
).
).
•
Chứng minh chứng tỏ rằng nếu tiền đề đúng
Chứng minh chứng tỏ rằng nếu tiền đề đúng
thì kết luận sẽ đúng.
thì kết luận sẽ đúng.
08/14/14 (c)2001-2003, Michae
l P. Frank
15
Module #2 - Proofs
Ví dụ chứng minh hình thức
•
Giả sử ta có các tiền đề sau:
“Trời không nắng và trời lạnh.”

“Để chúng ta bơi được thì trời cần phải nắng.”
“Nếu chúng ta không bơi, thì chúng ta sẽ đi
cano.”
“Nếu chúng ta đi cano, thì chúng ta sẽ về nhà
sớm.”
•
Cho trước các tiền đề, chứng minh định lý
“Chúng ta sẽ về nhà sớm” sử dụng các luật suy
diễn.
08/14/14 (c)2001-2003, Michae
l P. Frank
16
Module #2 - Proofs
Chứng minh tiếp theo.
•
G/s ta viết tắt:
G/s ta viết tắt:
–
sunny
sunny
=
=
“It is sunny”
“It is sunny”
;
;
cold
cold
=
=

“It is cold”
“It is cold”
;
;
swim
swim
=
=
“We will swim”
“We will swim”
;
;
canoe
canoe
=
=
“We will
“We will
canoe”
canoe”
;
;
early
early
=
=
“We will be home early”
“We will be home early”
.
.

•
Khi đó các tiền đề được viết như sau:
Khi đó các tiền đề được viết như sau:
(1)
(1)
¬
¬
sunny
sunny


∧
∧


cold
cold
(2)
(2)
swim
swim
→
→


sunny
sunny
(3)
(3)
¬

¬
swim
swim
→
→


canoe
canoe
(4)
(4)
canoe
canoe
→
→


early
early
08/14/14 (c)2001-2003, Michae
l P. Frank
17
Module #2 - Proofs
Proof Example cont.
Step
Step
Proved by
Proved by
1.
1.

¬
¬
sunny
sunny


∧
∧


cold
cold


Premise #1.
Premise #1.
2.
2.
¬
¬
sunny
sunny
Simplification of 1.
Simplification of 1.
3.
3.
swim
swim
→
→

sunny
sunny
Premise #2.
Premise #2.
4.
4.
¬
¬
swim
swim
Modus tollens on 2,3.
Modus tollens on 2,3.
5.
5.
¬
¬
swim
swim
→
→
canoe
canoe


Premise #3.
Premise #3.
6.
6.
canoe
canoe

Modus ponens on 4,5.
Modus ponens on 4,5.
7.
7.
canoe
canoe
→
→
early
early
Premise #4.
Premise #4.
8.
8.
early
early
Modus ponens on 6,7.
Modus ponens on 6,7.
08/14/14 (c)2001-2003, Michae
l P. Frank
18
Module #2 - Proofs
Các luật suy diễn lượng tử
∀
∀
∀
x
x



P
P
(
(
x
x
)
)
∴
∴
P
P
(
(
o
o
)
)
(thế đối tượng cụ thể bất kỳ
(thế đối tượng cụ thể bất kỳ
o
o
)
)
•
P
P
(
(
g

g
)
)
(cho p/tử tổng quan
(cho p/tử tổng quan
g
g
từ u.d.)
từ u.d.)
∴∀
∴∀
x
x


P
P
(
(
x
x
)
)
∀
∃
∃
x
x



P
P
(
(
x
x
)
)
∴
∴
P
P
(
(
c
c
)
)
(thế hằng mới
(thế hằng mới
c
c
)
)
•
P
P
(
(
o

o
)
)
(thế đối tượng hiện có bất kỳ
(thế đối tượng hiện có bất kỳ
o
o
)
)
∴∃
∴∃
x
x


P
P
(
(
x
x
)
)
08/14/14 (c)2001-2003, Michae
l P. Frank
19
Module #2 - Proofs
Nguỵ biện chung
•
Nguỵ biện là luật suy diễn hoặc chứng minh

Nguỵ biện là luật suy diễn hoặc chứng minh
khác mà không đúng về logic.
khác mà không đúng về logic.
–
Nguỵ biện có thể dẫn đến kết luận sai!
Nguỵ biện có thể dẫn đến kết luận sai!
•
Nguỵ biện về ngộ nhận kết luận:
Nguỵ biện về ngộ nhận kết luận:
–
“
“
p
p
→
→
q
q
là đúng, và
là đúng, và
q
q
là đúng, vậy
là đúng, vậy
p
p
cần phải
cần phải
đúng.”
đúng.”

•
Nguỵ biện phủ nhận giả thiết:
Nguỵ biện phủ nhận giả thiết:
–
“
“
p
p
→
→
q
q
là đúng, và
là đúng, và
p
p
là sai, vậy
là sai, vậy
q
q
cần phải là
cần phải là
sai.”
sai.”
08/14/14 (c)2001-2003, Michae
l P. Frank
20
Module #2 - Proofs
Suy luận vòng quanh
•

Ngụy biện giả thiết tường minh hay ẩn ngay chính
Ngụy biện giả thiết tường minh hay ẩn ngay chính
mệnh đề đang cần phải chứng minh tính đúng đắn.
mệnh đề đang cần phải chứng minh tính đúng đắn.
Ví dụ:
Ví dụ:
•
Ch
Ch
ứng minh số nguyên
ứng minh số nguyên


n
n
l
l
à chẵn, nếu
à chẵn, nếu


n
n
2
2
l
l
à chẵn
à chẵn
.

.
•
Th
Th
ử chứng minh
ử chứng minh
:
:
“G/s
“G/s
n
n
2
2
l
l
à chẵn
à chẵn
. Khi
. Khi
đó
đó


n
n
2
2
=2
=2

k
k


v
v
ới số nguyên
ới số nguyên
k n
k n
ào đó
ào đó
. Chia c
. Chia c
ả hai vế cho
ả hai vế cho
n
n
được
được


n
n
= (2
= (2
k
k
)/
)/

n
n
= 2(
= 2(
k
k
/
/
n
n
)
)
. V
. V
ậy có số nguyên
ậy có số nguyên
j
j
(k
(k
ý hiệu
ý hiệu
thay
thay
k
k
/
/
n
n

) sao cho
) sao cho
n
n
=2
=2
j
j
. V
. V
ì vậy
ì vậy


n
n
l
l
à chẵn
à chẵn
”
”
–
Đã có suy luận vòng quanh trong chứng minh trên
Đã có suy luận vòng quanh trong chứng minh trên
.
.
Ở
Ở
đâu

đâu
?
?
Begs the question: How do
you show that j=k/n=n/2 is an integer,
without first assuming that n is even?
08/14/14 (c)2001-2003, Michae
l P. Frank
21
Module #2 - Proofs
Chứng minh đúng
Ta biết
Ta biết
n
n
cần phải là lẻ hoặc chẵn. Nếu
cần phải là lẻ hoặc chẵn. Nếu
n là
n là
lẻ
lẻ
, thì
, thì
n
n
2
2
cần phải là lẻ, (vì số lẻ nhân với số lẻ
cần phải là lẻ, (vì số lẻ nhân với số lẻ
luôn được số lẻ). Vì

luôn được số lẻ). Vì
n
n
2
2
là chẵn, nó không lẻ,
là chẵn, nó không lẻ,
(vì không có số nào vừa là chẵn vừa là lẻ).
(vì không có số nào vừa là chẵn vừa là lẻ).
Nên, theo modus tollens,
Nên, theo modus tollens,
n
n
không là số lẻ
không là số lẻ
được. Vậy, theo tam đoạn luận tuyển
được. Vậy, theo tam đoạn luận tuyển
(disjunctive syllogism),
(disjunctive syllogism),
n
n
cần phải là chẵn.
cần phải là chẵn.
■
■
This proof is correct, but not quite complete,
since we used several lemmas without proving
them. Can you identify what they are?
08/14/14 (c)2001-2003, Michae
l P. Frank

22
Module #2 - Proofs
Một phương án c/m dài dòng nữa
G/s
G/s
n
n
2
2
l
l
à ch
à ch
ẵn
ẵn
∴
∴
2|
2|
n
n
2
2


∴
∴


n

n
2
2
mod 2 = 0. Tất nhiên
mod 2 = 0. Tất nhiên
n
n


mod 2 bằng 0 hoặc 1. Nếu bằng 1, thì
mod 2 bằng 0 hoặc 1. Nếu bằng 1, thì
n
n
≡
≡
1 (mod 2),
1 (mod 2),
khi đó
khi đó
n
n
2
2
≡
≡
1 (mod 2), sử dụng định lý nếu
1 (mod 2), sử dụng định lý nếu
a
a
≡

≡
b
b
(mod
(mod
m
m
) v
) v
à
à
c
c
≡
≡
d
d
(mod
(mod
m
m
) th
) th
ì
ì
ac
ac
≡
≡
bd

bd
(mod m), v
(mod m), v
ới
ới


a
a
=
=
c
c
=
=
n v
n v
à
à
b
b
=
=
d
d
=1.
=1.
Bây giờ
Bây giờ
n

n
2
2
≡
≡
1 (mod 2) suy ra
1 (mod 2) suy ra
n
n
2
2


mod 2 = 1. Vậy theo Luật tam đoạn luận kéo theo,
mod 2 = 1. Vậy theo Luật tam đoạn luận kéo theo,
(
(
n
n
mod 2 = 1) suy ra (
mod 2 = 1) suy ra (
n
n
2
2
mod 2 = 1). Vì ta biết
mod 2 = 1). Vì ta biết
n
n
2

2


mod 2 = 0
mod 2 = 0
≠
≠
1, bằng Luật
1, bằng Luật
modus tollens
modus tollens
ta biết rằng
ta biết rằng
n
n
mod 2
mod 2
≠
≠
1. Vậy theo tam đoạn luận tuyển ta có
1. Vậy theo tam đoạn luận tuyển ta có
n
n


mod 2 = 0
mod 2 = 0
∴
∴
2|

2|
n
n
∴
∴


n
n
là chẵn.
là chẵn.
Uses some number theory we haven’t defined yet.
08/14/14 (c)2001-2003, Michae
l P. Frank
23
Module #2 - Proofs
Các phương pháp chứng minh kéo theo
Để chứng minh kéo theo
Để chứng minh kéo theo
p
p
→
→
q
q
, ta có:
, ta có:
•
Ch
Ch

ứng minh trực tiếp
ứng minh trực tiếp
:
:
G/s
G/s
p
p


đúng
đúng
, v
, v
à c/m
à c/m


q
q
.
.
•
C/m ph
C/m ph
ản chứng
ản chứng
:
:
G/s

G/s
¬
¬
q
q
, v
, v
à c/m
à c/m


¬
¬
p
p
.
.
•
Ch
Ch
ứng minh trống rỗng
ứng minh trống rỗng
:
:
c/m
c/m
t
t
ự có
ự có

¬
¬
p
p
.
.
•
Ch
Ch
ứng minh hiển nhiên
ứng minh hiển nhiên
:
:
C/m
C/m
t
t
ự có
ự có
q
q
.
.
•
Ch
Ch
ứng minh phân trường hợp
ứng minh phân trường hợp
:
:



Chỉ ra
Chỉ ra


p
p
→
→
(
(
a
a


∨
∨


b
b
), v
), v
à
à
(
(
a
a

→
→
q
q
) v
) v
à
à
(
(
b
b
→
→
q
q
).
).
08/14/14 (c)2001-2003, Michae
l P. Frank
24
Module #2 - Proofs
Ví dụ chứng minh trực tiếp
•
Định nghĩa:
Định nghĩa:
Số
Số
n
n

gọi là lẻ iff
gọi là lẻ iff
n
n
=2
=2
k
k
+1
+1
với k
với k
nguyên;
nguyên;
n
n
là chẵn iff
là chẵn iff
n
n
=2
=2
k
k
với
với
k nguy
k nguy
ên
ên

.
.


•
Định lý:
Định lý:
Mọi số nguyên hoặc là chẵn hoặc là lẻ
Mọi số nguyên hoặc là chẵn hoặc là lẻ
–
Có thể chứng minh từ các tiên đề đơn giản hơn
Có thể chứng minh từ các tiên đề đơn giản hơn
•
Định lý:
Định lý:
(Với mọi số
(Với mọi số
n
n
) Nếu
) Nếu
n
n
là lẻ, thì
là lẻ, thì
n
n
2
2
là số

là số
nguyên lẻ.
nguyên lẻ.
•
C/m:
C/m:
nếu
nếu
n
n
lẻ, thì
lẻ, thì
n
n
= 2
= 2
k
k
+1
+1
với
với
k nguy
k nguy
ên nào đó
ên nào đó
.
.
Vậy,
Vậy,

n
n
2
2
= (2
= (2
k
k
+1)
+1)
2
2
= 4
= 4
k
k
2
2
+ 4
+ 4
k
k
+ 1 = 2(2
+ 1 = 2(2
k
k
2
2
+ 2
+ 2

k
k
) + 1
) + 1
.
.
Nên
Nên
n
n
2
2
có dạng
có dạng
2
2
j
j
+ 1
+ 1
(với
(với
j
j
bằng
bằng
2
2
k
k

2
2
+ 2
+ 2
k
k
), vậy
), vậy
n
n
2
2


là lẻ.
là lẻ.
□
□
08/14/14 (c)2001-2003, Michae
l P. Frank
25
Module #2 - Proofs
Ví dụ chứng minh phản chứng
•
Đ
Đ
ịnh lý:
ịnh lý:
(Với mọi số nguyên
(Với mọi số nguyên

n
n
)
)
Nếu
Nếu
3
3
n
n
+2
+2
là lẻ, thì
là lẻ, thì
n
n
là lẻ.
là lẻ.
•
C/m:
C/m:
Giả sử kết luận là sai, tức là,
Giả sử kết luận là sai, tức là,
n
n
là chẵn. Khi
là chẵn. Khi
đó
đó
n

n
=2
=2
k
k
với
với
k nguy
k nguy
ên nào đó
ên nào đó
. Vậy
. Vậy
3
3
n
n
+2 = 3(2
+2 = 3(2
k
k
)
)
+2 = 6
+2 = 6
k
k
+2 = 2(3
+2 = 2(3
k

k
+1)
+1)
. Do đó
. Do đó
3
3
n
n
+2
+2
là chẵn, vì nó
là chẵn, vì nó
bằng
bằng
2
2
j
j
với
với
j
j
= 3
= 3
k
k
+1
+1
. Vậy

. Vậy
3
3
n
n
+2
+2
không là lẻ. Ta
không là lẻ. Ta
vừa chỉ ra rằng
vừa chỉ ra rằng
¬(
¬(
n
n
is odd)→¬(3
is odd)→¬(3
n
n
+2 is odd)
+2 is odd)
, v
, v
ậy
ậy
mệnh đề phản đảo của nó là
mệnh đề phản đảo của nó là


(3

(3
n
n
+2 is odd)
+2 is odd)
→ (
→ (
n
n
is odd)
is odd)
c
c
ũng là đúng
ũng là đúng
. □
. □