Bài giảng Toán rời rạc - Chương 1: Cơ sở lôgic

Giới thiệu
TOÁN RỜI RẠC
lvluyen@hcmus.edu.vn
∼luyen/trr
FB: fb.com/trr2015
Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh
lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 1
Tài liệu
1 Giáo trình:
Nguyễn Hữu Anh, Toán Rời Rạc, Nhà Xuất Bản Lao
Động 2001
2 Tham khảo thêm:
Kenneth H. Rosen, Discrete mathematics and its
applications, Seventh Edition, 2011
Thang điểm đánh giá
- Giữa kỳ 30% (thi vào ngày 1 tháng 12)
- Thi cuối kỳ 70%
Lưu ý. Trong quá trình học, một số bạn sẽ được gọi lên bảng làm bài.
Tùy theo bài làm mà có được xem xét cộng thêm điểm vào điểm giữa
kỳ hay không.
lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 2
Nội quy
- Lớp không điểm danh nhưng đã đi học thì
không được đi trể
- Chuyển điện thoại sang chế độ im lặng và
không sử dụng điện thoại trong lớp
- Đi học phải có giấy và viết
lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 3
TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016
Nội dung môn học gồm 6 chương
1. Cơ sở logic
2. Tập hợp và ánh xạ
3. Phép đếm và hệ thức đệ quy
4. Tập hợp số nguyên
5. Quan hệ
6. Hàm Boole
lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 4
TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016
Chương 1
CƠ SỞ LOGIC
lvluyen@hcmus.edu.vn
∼luyen/trr
FB: fb.com/trr2015
Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 5
Nội dung
Chương 1. CƠ SỞ LOGIC
1. Mệnh đề
2. Dạng mệnh đề
3. Vị từ, lượng từ
4. Quy tắc suy luận
5. Nguyên lý quy nạp
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 6
1.1. Mệnh đề
1 Định nghĩa và chân trị của mệnh đề
2 Phân loại mệnh đề
3 Các phép toán trên mệnh đề
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 7
1.1.1. Định nghĩa và chân trị của mệnh đề
Định nghĩa. Mệnh đề là một phát biểu có giá trị chân lý xác định,
đúng hoặc sai.
Nhận xét. Câu hỏi, câu cảm thán, mệnh lệnh không là mệnh đề.
Ví dụ. Phát biểu nào sau đây là mệnh đề
a) Mặt trời quay quanh trái đất
b) 1 + 1 = 2
c) Hôm nay trời đẹp quá! (không là mệnh đề)
d) Học bài đi! (không là mệnh đề)
e) 3 là số lẻ phải không? (không là mệnh đề)
Chúng ta dùng các ký hiệu P,Q,R, . . . để chỉ mệnh đề.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 8
Chân trị của mệnh đề
Một mệnh đề chỉ có thể đúng hoặc sai. Khi mệnh đề P đúng ta nói P
có chân trị đúng, ngược lại ta nói P có chân trị sai.
Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1 (hay Đ, T )
và 0 (hay S, F )
Ví dụ. Kiểm tra các phát biểu sau có phải là mệnh đề không? Nếu có,
hãy xác định chân trị.
a) Paris là thành phố của Mỹ.
b) n là số tự nhiên.
c) Con nhà ai mà xinh thế!
d) 3 là số nguyên tố.
e) Toán rời rạc là môn bắt buộc của ngành Tin học.
f) Bạn có khỏe không?
g) x2 + 1 luôn dương.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 9
1.1.2. Phân loại mệnh đề
Mệnh đề gồm 2 loại:
1 Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề
khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi,...) hoặc
trạng từ “không”.
2 Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng
từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không”.
Ví dụ. Phân loại các mệnh đề sau:
a) 2 không là số nguyên tố
b) 2 là số nguyên tố
c) Nếu 3 > 4 thì trời mưa
d) An đang xem phim hay An đang học bài
e) Hôm nay trời đẹp và 1 + 1 = 3
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 10
1.1.3. Các phép toán trên mệnh đề
a. Phép phủ định
Phủ định của mệnh đề P được ký hiệu là ¬P hay P (đọc là “không”
P hay “phủ định của” P ), là mệnh đề được định bởi:
¬P đúng ⇔ P sai.
Bảng chân trị :
P ¬P
1 0
0 1
Ví dụ.
1 P=“2 là số nguyên tố”⇒ ¬P= “2 không là số nguyên tố”
2 Q =“1 > 2”⇒ ¬Q= “1 ≤ 2”
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 11
b. Phép nối liền (hội, giao)
Phép nối liền của hai mệnh đề P và Q được kí hiệu bởi P ∧Q (đọc
là “P và Q”), là mệnh đề được định bởi:
P ∧Q đúng ⇔ P và Q đồng thời đúng.
Bảng chân trị :
P Q P ∧Q
0 0 0
0 1 0
1 0 0
1 1 1
Ví dụ. Xác định chân trị của các mệnh đề sau:
a) 3 > 4 và Trần Hưng Đạo là vị tướng
b) 2 là số nguyên tố và là số chẵn
c) An đang hát và uống nước
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 12
c. Phép nối rời (tuyển, hợp)
Phép nối rời của hai mệnh đề P và Q được kí hiệu bởi P ∨Q (đọc
là “P hay Q”), là mệnh đề được định bởi:
P ∨Q sai ⇔ P và Q đồng thời sai.
Bảng chân trị :
P Q P ∨Q
0 0 0
0 1 1
1 0 1
1 1 1
Ví dụ. Xác định chân trị của các mệnh đề sau:
a) 3 > 4 hay Paris là thủ đô của Anh
b) Mặt trời mọc ở hướng Đông hay 1 + 3 = 5
c) pi > 4 hay trời không mưa
d) 2 là số nguyên tố hay là số chẵn
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 13
d. Phép kéo theo
Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu bởi P → Q
(đọc là
“P kéo theo Q” hay
“Nếu P thì Q” hay
“P là điều kiện đủ của Q” hay
“Q là điều kiện cần của P ”)
là mệnh đề được định bởi:
P → Q sai ⇔ P đúng và Q sai.
Bảng chân trị:
P Q P → Q
0 0 1
 ... định trên
A×B. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau:
(i) “∀x ∈ A,∀y ∈ B, p(x, y)” := “∀x ∈ A, (∀y ∈ B, p(x, y))”
(ii) “∀x ∈ A,∃y ∈ B, p(x, y)” := “∀x ∈ A, (∃y ∈ B, p(x, y))”
(iii) “∃x ∈ A,∀y ∈ B, p(x, y)” := “∃x ∈ A, (∀y ∈ B, p(x, y))”
(iv) “∃x ∈ A,∃y ∈ B, p(x, y)” := “∃x ∈ A, (∃y ∈ B, p(x, y))”
Ví dụ. Mệnh đề “∀x ∈ R, ∀y ∈ R, x+ 2y < 1” đúng hay sai?
Giải. Mệnh đề sai vì tồn tại x0 = 0, y0 = 1 ∈ R mà x0 + 2y0 = 1.
Ví dụ. Mệnh đề “∀x ∈ R,∃y ∈ R, x+ 2y < 1” đúng hay sai?
Giải. Mệnh đề đúng vì với mỗi x = a ∈ R, tồn tại ya ∈ R như
ya = −a/2, sao cho a+ 2ya < 1.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 39
Định lý. Cho p(x, y) là một vị từ theo hai biến x, y xác định trên
A×B. Khi đó:
i) “∀x ∈ A,∀y ∈ B, p(x, y)”⇔ “∀y ∈ B, ∀x ∈ A, p(x, y)”
ii) “∃x ∈ A,∃y ∈ B, p(x, y)”⇔ “∃y ∈ B, ∃x ∈ A, p(x, y)”
iii) “∃x ∈ A,∀y ∈ B, p(x, y)‘⇒ “∀y ∈ B, ∃x ∈ A, p(x, y)”
Chiều đảo của 3) nói chung không đúng.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 40
1.3.4. Phủ định của mệnh đề lượng từ hóa vị từ
Phủ định của mệnh đề lượng từ hóa vị từ p(x, y, ..) có được bằng các
thay ∀ thành ∃ , thay ∃ thành ∀ và vị từ p(x, y, ..) thành ¬p(x, y, ..).
Ví dụ. Phủ định các mệnh đề sau
a) ∀x ∈ A, 2x+ 1 > 0
b) ∃x ∈ N,∀y ∈ R, (x+ y > 1)→ (x2 < y)
c) ∀ε > 0,∃δ > 0, ∀x ∈ R, |x− a| < δ ∧ |f(x)− f(a)| < ε
Giải.
a) ∃x ∈ A, 2x+ 1 ≤ 0
b) ∀x ∈ N,∃y ∈ R, (x+ y > 1) ∧ (x2 ≥ y)
c) ∃ε > 0,∀δ > 0, ∃x ∈ R, |x− a| ≥ δ ∨ |f(x)− f(a)| ≥ ε
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 41
Ví dụ.(tự làm) Phủ định các mệnh đề sau
a) ∃x ∈ R,∀y ∈ R, (x > y) ∨ (x2 − 1 > y)→ (x2 ≥ y2)
b) ∃x ∈ Z,∃y ∈ Z, (2x+ y = 5) và (x− 3y = −1)
Ví dụ.(tự làm) Phủ định các mệnh đề sau
1 Có ít nhất một số nguyên chẵn
2 Ai cũng có ít nhất một người bạn thân
Ví dụ.(tự làm) Cho C = “∀x ∈ R, ∃y ∈ Z, y 6= x và |y − x| ≤ 1”. Viết
mệnh đề phủ định C.
Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∃y ∈ Z, 2x+ y > 5 và 5y − x = 1”.
C đúng hay sai ? Tại sao ? Viết mệnh đề phủ định C.
Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∀y ∈ Z, 8y − 2y2 ≤ 3−x”. Xét chân
trị của C và viết mệnh đề phủ định C của C.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 42
Ví dụ.(tự làm) Cho A = “∀x ∈ R,∃y ∈ Z, y2 + 6y > 3x”. Viết mệnh đề
phủ định A của A và xét chân trị của A.
Ví dụ.(tự làm) Cho mệnh đề
A = “∃x ∈ R,∀y ∈ R, (x2 ≥ y2)→ (x ≥ y và xy ≤ 0)”.
Viết mệnh đề phủ định của A.
Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∀y ∈ R, sin y − cos y ≤ 1− x2”. Xét
chân trị của C và viết mệnh đề phủ định của C.
Ví dụ.(tự làm) Cho A = “Nếu Tuấn thắng trận chung kết thì tất cả
các bạn trong lớp đến chúc mừng". Hãy viết mệnh đề phủ định của A.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 43
1.3.5. Các quy tắc phổ dụng
Đặc biệt hóa phổ dụng
∀x ∈ A, p(x)
a ∈ A
∴ p(a)
Ví dụ. “Mọi người đều chết“
“Socrate là người“
Vậy “Socrate cũng chết“
Tổng quát hóa phổ dụng
Nếu với mỗi a ∈ X ta có p(a) là mệnh đề đúng thì khẳng định
“∀x ∈ X, p(x)” là mệnh đề đúng.
Ví dụ. Mỗi số thực đều có bình phương không âm nên mọi số thực
đều có bình phương không âm.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 44
1.4. Quy tắc suy luận
1 Các quy tắc suy luận
2 Các phương pháp chứng minh
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 45
Giới thiệu
Ví dụ. Xem xét suy luận sau:
- Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 thì
đêm diễn sẽ bị hủy bỏ và ông bầu rất buồn.
- Nếu đêm biểu diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem.
- Nhưng tiền vé đã không được trả lại cho người xem.
Vậy nghệ sĩ Văn Ba có trình diễn.
Hỏi Suy luận trên đúng hay sai?
Ví dụ. Xem xét suy luận sau: Ông Minh nói rằng nếu không được
tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và
vợ ông ấy bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay
đi làm trễ thì trước sau gì cũng sẽ bị mất việc. Và cuối cùng ông Minh
đã được tăng lương.
Suy ra, nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ
Hỏi Suy luận trên đúng hay sai?
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 46
1.4.1. Các quy tắc suy luận
Trong các chứng minh toán học, xuất phát từ một số khẳng định đúng
p, q, r, . . . (tiền đề), ta áp dụng các qui tắc suy luận để suy ra chân lí
của một mệnh đề h mà ta gọi là kết luận.
Nói cách khác, dùng các qui tắc suy luận để chứng minh:
(p ∧ q ∧ r ∧ . . .) có hệ quả logic là h.
Ta thường mô hình hóa phép suy luận đó dưới dạng:
p
q
r
. . .
∴ h
Viết dưới dạng hằng đúng:
(p ∧ q ∧ r ∧ . . .)→ h
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 47
a. Qui tắc khẳng định (Modus Ponens)
Sơ đồ
p→ q
p
∴ q
Thể hiện bằng hằng đúng
((p→ q) ∧ p)→ q
Ví dụ.
- Trời mưa thì đường ướt.
- Mà chiều nay trời mưa.
Suy ra: Chiều nay đường ướt.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 48
b. Quy tắc phủ định
Sơ đồ
p→ q
¬q
∴ ¬p
Thể hiện bằng hằng đúng
[(p→ q) ∧ ¬q]→ ¬p
Ví dụ.
- Nếu An đi học đầy đủ thì sẽ đậu môn Toán Rời Rạc.
- An không đậu Toán Rời Rạc.
Suy ra: An không đi học đầy đủ.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 49
c. Quy tắc tam đoạn luận
Sơ đồ p→ q
q → r
∴ p→ r
Thể hiện bằng hằng đúng
[(p→ q) ∧ (q → r)]→ (p→ r)
Ví dụ.
- Nếu trời mưa thì đường ướt
- Nếu đường ướt thì đường trơn
Suy ra: Nếu trời mưa thì đường trơn
Ví dụ. Xem xét suy luận sau đúng hay sai?
- Một con ngựa rẻ là một con ngựa hiếm
- Cái gì hiếm thì đắt
Suy ra: Một con ngựa rẻ thì đắt
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 50
d. Quy tắc tam đoạn luận rời
Sơ đồ p ∨ q
¬p
∴ q
Thể hiện bằng hằng đúng
[(p ∨ q) ∧ ¬p]→ q
Ví dụ.
- Tối nay An sẽ đi uống cafe với bạn hoặc ở nhà học bài
- Tối nay An không học bài ở nhà
Suy ra: Tối nay, An đi uống cafe với bạn
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 51
e. Những quy tắc suy luận đơn giản
Quy tắc Sơ đồ Hằng đúng
Nối liền
p
q
∴ p ∧ q (p ∧ q)→ (p ∧ q)
Đơn giản
p ∧ q
∴ p (p ∧ q)→ p
Cộng
p
∴ p ∨ q p→ (p ∨ q)
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 52
Ví dụ. Xem xét suy luận sau:
- Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 thì
đêm diễn sẽ bị hủy bỏ và ông bầu rất buồn.
- Nếu đêm biểu diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem.
- Nhưng tiền vé đã không được trả lại cho người xem.
Vậy nghệ sĩ Văn Ba có trình diễn.
Hỏi Suy luận trên đúng hay sai?
Nếu ta đặt:
p: “nghệ sĩ Văn Ba đã trình diễn”
q: “số vé bán ra ít hơn 50”
r: “đêm diễn sẽ bị hủy bỏ”
t: “trả lại tiền vé cho người xem”
s: “ông bầu rất buồn”
Ta có sơ đồ suy luận sau:
(¬p ∨ q)→ (r ∧ s)
r → t
¬t
∴ p
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 53
Ví dụ. Chứng minh suy luận sau
p→ (q → r)
p ∨ s
t→ q
¬s
∴ ¬r → ¬t
Giải.
p ∨ s
¬s
∴ p
Tam đoạn luận rời
p→ (q → r)
p
∴ q → r
Khẳng định
t→ q
q → r
∴ t→ r
Tam đoạn luận
Cuối cùng ta có
t→ r ⇔ ¬r → ¬t (Luật phép kéo theo)
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 54
Ví dụ.(tự làm) Chứng minh các suy luận sau:
p→ q
¬q
¬r
∴ ¬(p ∨ r)
p→ (q → r)
¬q → ¬p
p
∴ r
p ∧ q
p→ (r ∧ q)
r → (s ∨ t)
¬s
∴ t
t→ u
r → (s ∨ t)
(¬p ∨ q)→ r
¬(s ∨ u)
∴ p
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 55
f. Quy tắc mâu thuẫn
Ta có tương đương logic
[(p1 ∧ p2 ∧ . . . ∧ pn)→ q]⇔ [(p1 ∧ p2 ∧ . . . ∧ pn ∧¬q)→ 0].
Do đó nếu chứng minh được dạng mệnh đề ở bên phải là một hằng
đúng thì dạng mệnh đề ở bên trái cũng là một hằng đúng.
Nói cách khác nếu thêm giả thiết phụ ¬p vào các tiền đề cho trước mà
dẫn đến một mâu thuẫn thì q là hệ quả logic của các tiền đề cho trước.
Ví dụ. Chứng minh suy luận sau
p→ r
¬p→ q
q → s
∴ ¬r → s
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 56
Giải. Phủ định kết luận
¬(¬r → s)⇔ ¬(r ∨ s)⇔ ¬r ∧ ¬s
Ta thêm điều này vào tiền đề. Khi đó ta sẽ chứng minh suy luận sau:
p→ r
¬p→ q
q → s
¬r ∧ ¬s
∴ 0
Ta lần lược thực hiện các quy tắc suy luận sau:
¬r ∧ ¬s
∴ ¬r
p→ r
¬r
∴ ¬p
¬r ∧ ¬s
∴ ¬s
q → s
¬s
∴ ¬q
¬p→ q
¬p
∴ q
¬q
q
∴ 0
Như vậy suy luận trên đã được chứng minh
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 57
Ví dụ. Xem suy luận sau đúng hay sai?
Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc.
Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán
xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ
bị mất việc. Và cuối cùng ông Minh đã được tăng lương.
Suy ra, nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ.
Nếu ta đặt:
p: “ông Minh được tăng lương”
q: “ông Minh nghỉ việc”
r: “vợ ông Minh mất việc”
s: “gia đình phải bán xe”
t: “vợ ông hay đi làm trể”
Ta có sơ đồ suy luận sau:
¬p→ q
(q ∧ r)→ s
t→ r
p
∴ ¬s→ ¬t
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 58
Phản ví dụ
B Để chứng minh suy luận đúng, chúng ta sẽ sử dụng các luật logic và
quy tắc suy luận.
B Để chỉ một suy luận sai (hay còn gọi là ngụy biện) ta sẽ đưa giá các
giá trị làm cho các tiền đề đúng nhưng kết luận thì sai.
Ví dụ. Kiểm tra suy luận sau đúng hay sai
¬p→ q
(q ∧ r)→ s
t→ r
p
∴ ¬s→ ¬t
Giải. Cho s = 0, t = 1, p = 1, q = 0, r = 1, ta thấy các tiền đề đều
đúng, nhưng kết luận sai. Suy ra suy luận trên là sai.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 59
1.4.2. Các phương pháp chứng minh
Mỗi bài toán chứng minh gồm 2 phần chính: giả thiết và kết luận. Quá
trình chứng minh bài toán là quá trình sử dụng các tiên đề, luật logic,
các quy tắc suy luận,... và áp dụng các phương pháp chứng minh để từ
giả thiết đã cho ta có được kết luận.
Trong phần này ta tìm hiểu các phương pháp chứng minh sau:
1 Chứng minh trực tiếp
2 Chứng minh gián tiếp
3 Chứng minh phản chứng
4 Chứng minh theo từng trường hợp
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 60
a. Chứng minh trực tiếp
Để chứng minh A suy ra B, chúng ta giả sử A đúng, sau đó áp dụng
các quy tắc suy luận, các luật logic, các tiên đề,... để chỉ ra B đúng.
Ví dụ. Chứng minh rằng, nếu n là một số lẻ thì n2 cũng là số lẻ.
Giải. Vì n là số lẻ nên n = 2k + 1 với k ∈ Z. Ta có
n2 = (2k + 1)2 = 4k2 + 4k + 1.
Do 4k2 + 4k chẵn nên n2 là số lẻ.
Ví dụ.(tự làm) Cho ABC là tam giác và M là trung điểm của BC.
Chứng minh rằng nếu AM =MB thì tam giác ABC vuông tại A.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 61
b. Chứng minh gián tiếp
Ta có A→ B ⇔ ¬B → ¬A.
Do đó để chứng minh A đúng suy ra B đúng, ta có thể giả sử B sai và
chứng minh A sai.
Ví dụ. Cho n là một số nguyên, nếu 5n là số lẻ thì n là số lẻ
Giải. Ta sẽ dùng phương pháp chứng minh gián tiếp. Nghĩa là, cho n
là số chẵn cần chứng minh 5n là số chẵn.
Vì n là số chẵn nên n = 2k (với k ∈ Z). Do đó 5n = 5.2k = 10k là một
số chẵn.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 62
c. Chứng minh phản chứng
Ta có A→ B ⇔ ¬A ∨B.
Suy ra ¬(A→ B)⇔ A ∧ ¬B.
Như vậy để chứng minh từ A đúng suy ra B đúng, ta có thể giả sử B
sai. Sau đó dùng các tiền đề, các luật logic, các quy tắc suy luận,...
chứng tỏ điều này mâu thuẫn.
Ví dụ. Chứng minh rằng
√
2 là số vô tỉ.
Giải. Giả sử
√
2 là số hữu tỉ, nghĩa là
√
2 có thể biểu diễn thành
√
2 =
m
n
(m,n ∈ Z).
Ta có thể giả sử m,n là hai số nguyên tố cùng nhau. Bình phương 2 vế
ta có
2 =
m2
n2
⇔ m2 = 2n2.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 63
2 =
m2
n2
⇔ m2 = 2n2.
Từ đây suy ra m là số chẵn (vì bình phương số lẻ là số lẻ). Do đó
m = 2k (với k ∈ Z). Ta có
(2k)2 = 2n2 ⇔ 4k2 = 2n2.
Suy ra n2 = 2k2. Như vậy n cũng là một số chẵn. Do m,n đều là số
chẵn nên chúng không là số nguyên tố cùng nhau (mâu thuẫn)
Ví dụ.(tự làm) Trong mặt phẳng, nếu hai đường thẳng cùng song song
với đường thẳng thứ ba thì chúng song song với nhau.
Gợi ý. Sử dụng tiên đề Euclide:
“Qua một điểm nằm ngoài một đường thẳng ta vẽ được một và chỉ một
đường thẳng song song với đường thẳng đã cho."
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 64
d. Chứng minh theo trường hợp
Ta có (A ∨B)→ C ⇔ (A→ C) ∧ (B → C)
Do đó, để chứng minh (A ∨B)→ C ta chỉ cần chứng minh A→ C và
B → C là được.
Ví dụ. Chứng minh rằng n3 + 2n luôn chia hết cho 3 với mọi số
nguyên n.
Giải. Chia hai trường hợp
Trường hợp 1. n chia hết cho 3, hiển nhiên n3 + 2n chia hết cho 3.
Trường hợp 2. n không chia hết cho 3, khi ấy ta có thể viết
n = 3k ± 1 với k ∈ Z nào đó. Ta có
n2 + 2 = (3k ± 1)2 + 2 = 9k2 ± 6k + 3 = 3(3k2 ± 2k + 1).
Suy ra n(n2 + 2) cũng chia hết cho 3.
Như vậy n3 + 2n chia hết cho 3 với mọi số nguyên n.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 65
1.5. Nguyên lý quy nạp
Với những bài toán chứng minh tính đúng đắn của một biểu thức
mệnh đề có chứa tham số n, như P (n). Quy nạp toán học là một kỹ
thuật chứng minh P (n) đúng với mọi số n ≥ N0.
Quy nạp yếu
Gồm 2 bước:
- Bước cơ sở: Chỉ ra P (N0) đúng.
- Bước quy nạp: Chứng minh nếu P (k) đúng thì P (k + 1) đúng.
Trong đó P (k) được gọi là giả thiết quy nạp.
Ví dụ. Chứng minh 1 + 3 + · · ·+ (2n− 1) = n2 với mọi số nguyên
dương n.
Giải. Gọi P (n) = “1 + 3 + · · ·+ (2n− 1) = n2”
- Bước cơ sở: Hiển nhiên P (1) đúng vì 1 = 12.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 66
- Bước quy nạp:
Giả sử P (k) đúng, tức là
1 + 3 + 5 + · · ·+ (2k − 1) = k2.
Ta cần chứng minh P (k + 1) đúng, tức là
1 + 3 + 5 + · · ·+ (2k + 1) = (k + 1)2.
Từ giả thiết quy nạp ta có
1 + 3 + 5 + · · ·+ (2k + 1) = 1 + 3 + 5 + · · ·+ (2k − 1) + (2k + 1)
= k2 + (2k + 1).
= (k + 1)2.
Suy ra, P (k + 1) đúng. Vậy theo nguyên lý quy nạp P (n) đúng với mọi
số nguyên dương n.
Ví dụ.(tự làm) Chứng minh 1 + 2 + · · ·+ n = n(n+ 1)
2
với mọi số
nguyên dương n.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 67
Quy nạp mạnh
Gồm 2 bước:
- Bước cơ sở: Chỉ ra P (N0) ∧ P (N0 + 1) ∧ . . . đúng.
- Bước quy nạp mạnh: Chứng minh nếu P (m) đúng với mọi m ≤ k
thì P (k + 1) đúng.
Ví dụ. Mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích
những thừa số nguyên tố.
Giải. Gọi P (n) = “n phân tích được thành tích những thừa số nguyên
tố"
- Bước cơ sở: Hiển nhiên P (2) đúng vì 2 = 2 là số nguyên tố.
- Bước quy nạp mạnh:
Giả sử P (m) đúng với mọi m ≤ k, tức là, với 1 < m ≤ k phân tích
được thành tích những thừa số nguyên tố.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 68
Ta cần chứng minh P (k + 1) đúng, tức là k + 1 phân tích được thành
tích những thừa số nguyên tố.
Nếu k + 1 là số nguyên tố thì P (k + 1) đúng, ngược lại, gọi p là một
ước nguyên tố của k + 1.
Nếu k + 1 là số nguyên tố. Khi đó k + 1 = p.t với 1 < p, t < k + 1. Vì p
và t nhỏ hơn k + 1 nên theo giả thiết quy nạp p và t phân tích được
thành tích những thừa số nguyên tố. Do đó k+ 1 phân tích được thành
tích những thừa số nguyên tố.
Ví dụ.(tự làm) Chứng minh tích của ba số tự nhiên liên tiếp thì chia
hết cho 6.
lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 69