Bài giảng Toán rời rạc - Chương 1: Cơ sở logic - Nguyễn Anh Thi

Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
2017
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Chương 1
Cơ sở logic
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Nội dung
1 Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Mệnh đề
Định nghĩa
Mệnh đề toán học (gọi tắt là mệnh đề) là một khẳng định có
giá trị chân lý xác định (đúng hoặc sai, nhưng không thể vừa
đúng vừa sai).
Ví dụ
• "Số 25 chia hết cho 5" là một mệnh đề đúng.
• "Mặt trời xoay quanh trái đất" là một mệnh đề sai.
• "Bạn bao nhiêu tuổi?" không phải là một mệnh đề toán
học vì nó là một câu hỏi không có giá trị chân lý xác định
(đúng hay sai).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Mệnh đề
Ta thường ký hiệu các mệnh đề bằng các chữ cái: P, Q, R . . .
Định nghĩa
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 chúng lại bằng các liên từ (và, hay,
nếu...thì...) hoặc trạng từ không.
Ví dụ
Nếu tôi rảnh rỗi, thì tôi sẽ đi chơi.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Chân trị của mệnh đề
Một mệnh đề chỉ có thể đúng hoặc sai, không thể vừa đúng
vừa 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 Đ, hay T (True), và 0, hay S, hay
F (False).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Mục đích của phép tính mệnh đề là nghiên cứu chân trị của
một mệnh đề phức hợp từ chân trị của các mệnh đề đơn giản
hơn và các phép nối những mệnh đề này thể hiện qua liên từ
hoặc trạng từ "không".
Các phép nối
• Phép phủ định: phủ định của mệnh đề P được ký hiệu
bởi ¬P (đọc là không P). Chân trị của ¬P là 0 nếu chân trị
của P là 1 và ngược lại. Ta có bảng sau, gọi là bảng chân
trị của phép phủ định.
P ¬P
0 1
1 0
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• 10 là số chẵn.
Phủ định: 10 không là số chẵn.
• 4 > 10
Phủ định: 4 ≤ 10
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
• Phép nối liền: mệnh đề nối liền của hai mệnh đề P,Q
được ký hiệu bởi P ∧ Q (đọc là P và Q). Chân trị của P ∧ Q
là 1 nếu cả P lẫn Q đều có chân trị 1. Trong các trường
hợp khác P ∧ Qcó chân trị 0. Nói cách khác phép nối liền
được xác định bởi bảng chân trị sau:
P Q P ∧ Q
0 0 0
0 1 0
1 0 0
1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• Hôm nay trời đẹp và trận bóng đá sẽ hấp dẫn.
• 15 chia hết cho 3 và 14 chia hết cho 5.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
• Phép nối rời: mệnh đề nối rời của hai mệnh đề P,Q là
mệnh đề ký hiệu bởi P ∨ Q (đọc là P hay Q). Chân trị của
P ∨ Q là 0 nếu cả hai P,Q cùng chân trị 0. Trong các
trường hợp khác, P ∨ Q có chân trị 1. Nói cách khác phép
nối rời được xác định bởi bảng chân trị sau
P Q P ∨ Q
0 0 0
0 1 1
1 0 1
1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• Ba đang đọc báo hay mẹ đang xem tivi.
• 2 là số nguyên tố hay là số chẵn.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
• Phép loại trừ: mệnh đề loại trừ của hai mệnh đề P,Q là
mệnh đề ký hiệu bởi P YQ (đọc là P hoặc Q). Chân trị của
P Y Q là 0 nếu cả hai P,Q có cùng chân trị 0 hay 1. Ta có
bảng chân trị,
P Q P Y Q
0 0 0
0 1 1
1 0 1
1 1 0
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• 15 là số chẵn hoặc là số lẻ.
• 7 là số nguyên tố hoặc không phải là số nguyên tố.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
• Phép kéo theo: mệnh đề nếu P thì Q được ký hiệu là
P → Q (cũng đọc là P kéo theo Q, hay P là điều kiện đủ
của Q, hay Q là điều kiện cần của P. Ta có bảng chân trị
của phép kéo theo:
P Q P → Q
0 0 1
0 1 1
1 0 0
1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• Nếu trời mưa thì tôi sẽ ở nhà xem tivi.
• Nếu 2 > 3 thì 3 > 4.
• Nếu 2 4.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
• Phép kéo theo hai chiều: mệnh đề nếu P thì Q và ngược
lại được ký hiệu bởi P ↔ Q (cũng đọc là P khi và chỉ khi
Q, P nếu và chỉ nếu Q, P là điều kiện cần và đủ để có Q).
Ta có bảng chân trị của phép kéo theo hai chiều:
P Q P ↔ Q
0 0 1
0 1 0
1 0 0
1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Phép tính mệnh đề
Ví dụ
• 2 = 4 khi và chỉ khi 2 + 1 = 0.
• 6 chia hết cho 3 khi và chỉ khi 5 là số nguyên tố.
• Paris là thủ đô của nước Pháp khi và chỉ khi Quy Nhơn là
thủ đô của Việt Nam.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Dạng mệnh đề
Định nghĩa
Dạng mệnh đề là một biểu thức được xây dựng từ:
• Các mệnh đề (các hằng mệnh đề).
• Các biến mệnh đề p, q, . . . tức là các biến lấy giá trị là
các mệnh đề nào đó.
• Các phép toán ¬,∧,∨,Y,→,↔ và dấu đóng mở ngoặc
"()".
Ví dụ
E(p, q, r) = (p ∧ q) ∨ ((¬r → P)) là một dạng mệnh đề trong
đó p, q, r là các biến mệnh đề còn P là một hằng mệnh đề.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Dạng mệnh đề
Định nghĩa
Bảng chân trị của dạng mệnh đề E(p, q, r) là bảng ghi tất cả
các trường hợp chân trị có thể xảy ra đối với dạng mệnh đề E
theo chân trị của các biến mệnh đề p, q, r. Nếu có n biến,
bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề.
Ví dụ
Lập bảng chân trị của những dạng mệnh đề sau:
E(p, q) = ¬(p ∧ q) ∧ p
E(p, q, r) = (p ∨ q) ∧ r
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Dạng mệnh đề
Ví dụ
Ta xây dựng bảng chân trị của dạng mệnh đề
E(p, q, r) = p ∨ (q ∧ r) theo các biến mệnh đề p, q, r.
p q r q ∧ r p ∨ (q ∧ r)
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Dạng mệnh đề
Định nghĩa
Hai dạng mệnh đề E và F được nói là tương đương logic nếu
chúng có cùng bảng chân trị. Khi ấy ta viết E ⇔ F.
Ví dụ
Xây dựng bảng chân trị của hai dạng mệnh đề p → q và
¬p ∨ q. Hai dạng mệnh đề p → q và ¬p ∨ q có cùng bảng
chân trị. Ta nói chúng tương đương logic.
p q ¬p p → q ¬p ∨ q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán ... hát từ một số khẳng
định đúng p1, p2, . . . , pn gọi là tiền đề, ta áp dụng các quy tắc
suy diễn để suy ra chân lý của một khẳng định q mà ta gọi là
kết luận. Nói cách khác, các quy tắc suy diễn được áp dụng để
suy ra q là hệ quả logic của p1 ∨ p2 ∨ · · · ∨ pn, hay nói cách
khác dạng mệnh đề
(p1 ∨ p2 ∨ · · · ∨ pn)→ q
là một hằng đúng, trong đó p1, p2, . . . , pn, q là các dạng mệnh
đề theo một số biến logic nào đó.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Các quy tắc suy diễn
Quy tắc khẳng định (Modus Ponens)
Quy tắc này được thể hiện bằng hằng đúng:
[(p → q) ∧ p]→ q
hoặc dưới dạng sơ đồ
p → q
p
∴ q
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Ví dụ
Nếu Minh học chăm thì Minh đậu môn Toán rời rạc.
mà Minh học chăm.
Suy ra Minh đậu môn Toán rời rạc.
Ví dụ
Nếu trời mưa thì đường trơn.
Mà hôm nay trời mưa.
Suy ra, hôm nay đường trơn.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc phủ định (Modus Tollens)
Phương pháp này thể hiện bởi hằng đúng
[(p → q) ∧ ¬q]→ ¬p
hay dưới dạng sơ đồ
p → q
¬q
∴ ¬p
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Ví dụ
Nếu Minh học chăm chỉ thì Minh đậu môn Toán rời rạc.
Minh rớt môn Toán rời rạc.
Suy ra, Minh không học chăm chỉ.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc tam đoạn luận
Quy tắc này được thể hiện bởi hằng đúng:
[(p → q) ∧ (q → r)]→ (p → r)
hay dưới dạng sơ đồ
p → q
q → r
∴ p → r
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Ví dụ
Minh đi chơi thì Minh không học Toán rời rạc.
Minh không học Toán rời rạc thì Minh trượt Toán rời rạc.
Suy ra, nếu Minh đi chơi thì Minh trượt Toán rời rạc.
Ví dụ
Nếu trời mưa thì đường ướt.
Nếu đường ướt thì đường trơn.
Nếu trời mưa thì đường trơn.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc tam đoạn luận rời
Quy tắc này được thể hiện bằng hằng đúng:
[(p ∨ q) ∧ ¬q]→ p
hoặc dưới dạng sơ đồ
p ∨ q
¬q
∴ p
Ý nghĩa của quy tắc: nếu một trong hai trường hợp có thể xảy
ra, chúng ta biết có một trường hợp không xảy ra thì chắc chắn
trường hợp còn lại sẽ xảy ra.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Ví dụ
Chủ nhật, Minh thường đá bóng hoặc đi về quê.
Chủ nhật này, Minh không về quê.
Suy ra, chủ nhật này, Minh đi đá bóng.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc nối liền:
Quy tắc này được thể hiện bằng hằng đúng:
(p ∧ q)→ (p ∧ q)
hoặc dưới dạng sơ đồ
p
q
∴ p ∧ q
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc đơn giản
Quy tắc này thể hiện bằng hằng đúng:
(p ∧ q)→ p
hoặc dưới dạng sơ đồ
p ∧ q
∴ p
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc mâu thuẫn (Chứng minh bằng phản chứng)
Ta có tương đương logic
[(p1 ∧ p2 ∧ . . . pn)→ q]⇔ [(p1 ∧ p2 ∧ · · · ∧ pn ∧ ¬q)→ 0]
Để chứng minh vế trái là một hằng đúng, ta chứng minh nếu
thêm phủ định của q vào các tiền đề thì được một mâu thuẫn.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Quy tắc chứng minh theo trường hợp Dựa trên hằng đúng
[(p → r) ∧ (q → r)]→ [(p ∨ q)→ r]
Ý nghĩa: Nếu p suy ra r và q suy ra r thì p hay q cũng có thể
suy ra r.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy tắc suy diễn
Để chứng minh một phép suy luận là sai hay
p1 ∧ p2 ∧ · · · ∧ pn → q
không là một hằng đúng. Ta chỉ cần chỉ ra một phản ví dụ.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy nạp yếu
Phương pháp:
Khi chứng minh một khẳng định nào đó đúng với mọi số
nguyên dương m bằng phương pháp quy nạp yếu, ta sẽ chứng
minh theo các bước sau:
• Chứng minh khẳng định đúng cho trường hợp m nhận các
giá trị nhỏ nhất, (thường là 0, 1, 2 . . . ).
• Giả sử khẳng định đúng với m = n. Ta chứng minh khẳng
định đúng với m = n + 1.
Ví dụ
Với mọi số nguyên dương m, chứng minh rằng
12 + 22 + · · ·+ m2 = m(m+1)(2m+1)6 .
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Ví dụ
Cho A =
 1 1 00 1 1
0 0 1
. Tính An, với n là một số nguyên
dương nào đó.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Ví dụ
Cho a0 = 0, và an+1 = 3an + 1 với mọi số nguyên dương n.
Tìm một công thức cho am.
HD: Ta thử tính những giá trị đầu tiên của dãy số trên:
1, 4, 13, 40, 121, . . . . Có thể đoán được dạng của dãy số trên là
am = (3m − 1)/2.
Ta sẽ chứng minh khẳng định này bằng quy nạp. Dễ dàng thấy
rằng kết luận đúng với trường hợp m = 0, 1. Giả sử khẳng định
đúng với m = n. Ta chứng minh khẳng định đúng với
m = n + 1.
Theo giả thiết quy nạp ta có
an+1 = 3an + 1 =
3.(3n − 1)
2 + 1 =
3n+1 − 1
2 .
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Ví dụ
Với mọi số nguyên dương n, chứng minh rằng số các tập con
của tập [n] là 2n.
HD: Với n = 1, ta thấy tập [1] có hai (21) tập con là {1}, ∅. Giả
sử khẳng định đúng với n = k, ta chứng minh khẳng định
đúng với n = k + 1. Ta chia các tập con của [n + 1] ra thành
hai nhóm. Nhóm một chứa phần tử n + 1 và nhóm hai không
chứa phần tử n + 1. Ta dễ dàng thấy số phần tử của nhóm hai
là 2n, chính là số tập con của [n]. Nhóm chứa n + 1 gồm tập
con của [n] và n + 1. Do đó số phần tử của nhóm này cũng là
2n. Suy ra số tập con của [n + 1] là 2n + 2n = 2n+1.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Quy nạp mạnh
Phương pháp
Khi chứng minh một khẳng định nào đó đúng với mọi số
nguyên dương m bằng phương pháp quy nạp mạnh, ta sẽ
chứng minh theo các bước sau:
• Chứng minh khẳng định đúng cho trường hợp m nhận các
giá trị nhỏ nhất, (thường là 0, 1, 2 . . . ).
• Giả sử khẳng định đúng với mọi số nguyên m nhỏ hơn hay
bằng n. Ta chứng minh khẳng định đúng với m = n + 1.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Ví dụ
Cho dãy số {an} được định nghĩa như sau a0 = 0, và
an+1 = a0 + a1 + a2 + · · ·+ an + n + 1 với n ≥ 1. Chứng minh
rằng với mọi số nguyên n, ta có an = 2n − 1.
HD: Với n = 0, ta thấy khẳng định đúng. Giả sử khẳng định
đúng với mọi số nguyên m nhỏ hơn hay bằng n, ta chứng
minh khẳng định đúng với m = n + 1. Bởi quan hệ đệ quy ta
có an+1 = a0 + a1 + · · ·+ an + n + 1 = (20 − 1) + (21 − 1) +
· · ·+ (2n − 1) + n + 1 = 1 + 2 + 4 + · · ·+ 2n = 2n+1 − 1.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Chương 1: Cơ
sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp
toán học
Nội dung
Chương 1: Cơ sở logic
Mệnh đề
Phép tính mệnh đề
Dạng mệnh đề
Vị từ và lượng từ
Quy tắc suy diễn
Phương pháp quy nạp toán học
Ví dụ
Cho hàm f : N→ N thỏa mãn điều kiện
f(m + n) = f(m) + f(n) với mọi m và n. Chứng minh rằng tồn
tại một hằng số c sao cho f(n) = cn.
HD: Với m = 0, ta có f(n + 0) = f(n) + f(0), suy ra f(0) = 0.
Giả sử khẳng định đúng với mọi số nguyên dương nhỏ hơn hay
bằng n. Nghĩa là tồn tại một hằng số c sao cho f(k) = ck với
k ≤ n. Ta có
f(n + 1) = f(n) + f(1) = cn + c = c(n + 1).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc