Bài giảng Toán rời rạc - Chương 1: Đại số logic - Nguyễn Quỳnh Diệp

ề phức hợp mà luôn luôn đúng với bất kì giá trị
 chân lí của mệnh đề thành phần gọi là hằng đúng
 • Mệnh đề mà luôn luôn sai gọi là mâu thuẫn
 • Mệnh đề không phải hằng đúng, không phải mâu thuẫn
 gọi là tiếp liên
 • Ví dụ:
 1. ( p  T ) 3. ( p  F )
 2. ( 풑  풑 ) 4. (풑 풑 )
 Toán rời rạc Nguyễn Quỳnh Diệp 27
SỰ TƯƠNG ĐƯƠNG CỦA CÁC MỆNH ĐỀ
 • Định nghĩa:
 Mệnh đề 풑 và 풒 được gọi là tương đương logic nếu
 mệnh đề 풑  풒 là hằng đúng. 
 Kí hiệu 풑  풒
 • Ví dụ: Chứng minh rằng các mệnh đề sau là tương đương logic
 1. (풑  풒 ) và (풑  풒 ) 
 2. (풑 풒) và (풑  풒)
 Toán rời rạc Nguyễn Quỳnh Diệp 28
CÁC TƯƠNG ĐƯƠNG LOGIC
 Các tương đương logic
 Tương đương Tên gọi
 Luật đồng nhất
 Luật trội
 Luật lũy đẳng
 Luật phủ định kép
 Luật giao hoán
 Luật kết hợp
 Toán rời rạc Nguyễn Quỳnh Diệp 29
CÁC TƯƠNG ĐƯƠNG LOGIC
 Các tương đương logic
 Tương đương Tên gọi
 Luật phân phối
 Luật De Morgan
 Luật hút thu
 Luật phủ định
 Toán rời rạc Nguyễn Quỳnh Diệp 30
CÁC TƯƠNG ĐƯƠNG LOGIC
 Tương đương logic của mệnh đề 
 Tương đương logic của mệnh 
 kéo theo
 đề hai điều kiện
 Toán rời rạc Nguyễn Quỳnh Diệp 31
BÀI TẬP
. Bài 5: Chứng minh mệnh đề sau là tương đương:
 a. (풑  풒) và (풑  풒)  ( 풑 풒 )
 b. (풑 풒)  (풑 풓) và 풑 (풒  풓 )
 c. (풑 풓)  (풒 풓) và (풑 풒) 풓
 32
 Toán rời rạc Nguyễn Quỳnh Diệp
 1.3. VỊ TỪ VÀ LƯỢNG TỪ
Toán rời rạc Nguyễn Quỳnh Diệp 33
LOGIC VỊ TỪ
• Cho câu sau: x lớn hơn 3
 biến vị từ
 - Ký hiệu 푷(풙) cho câu “x lớn hơn 3”
 - 푷 là kí hiệu vị từ “ lớn hơn 3” (Tính chất của biến x)
 - 푷(풙) là giá trị của hàm mệnh đề 푷 tại x. Khi biến x được
 gán cho một giá trị thì câu P(x) trở thành mệnh đề.
• Ví dụ: Cho một logic vị từ P(x) biểu diễn câu sau:
 x là số nguyên tố
 Xác định giá trị chân lí của các mệnh đề: P(2), P(4), P(7)
 Toán rời rạc Nguyễn Quỳnh Diệp 34
LƯỢNG TỪ
 - Lượng từ hóa: để biến các hàm mệnh đề thành mệnh đề
 - 2 lượng từ hóa:
 • Lượng từ hóa phổ quát (với mọi)
 • Lượng từ hóa tồn tại
 Toán rời rạc Nguyễn Quỳnh Diệp 35
LƯỢNG TỪ HÓA PHỔ QUÁT
• Định nghĩa:
 Lượng từ hóa phổ quát (với mọi) của P(x) là mệnh đề:
 “P(x) đúng với mọi giá trị của x trong không gian”
 - Kí hiệu: ∀풙푷(풙)
• Ví dụ:
 * Giả sử 푃( ) là câu “x > x-1”. Xác định giá trị chân lí của
 lượng từ hóa ∀ 푃( ) ?
 * Giả sử Q( ) là câu “x <2”. Xác định giá trị chân lí của lượng
 từ hóa ∀ 푄( ) ?
 Toán rời rạc Nguyễn Quỳnh Diệp 36
LƯỢNG TỪ HÓA TỒN TẠI
 • Định nghĩa:
 Lượng từ hóa tồn tại của P(x) là mệnh đề: “tồn tại một
 phần tử x trong không gian sao cho P(x) là đúng”
 - Kí hiệu: ∃풙푷(풙)
 • Ví dụ:
 Giả sử 푃( ) là câu “x > 5 và x là số thực”. Xác định giá trị 
 chân lí của lượng từ hóa ∃ 푃( ) ?
 Toán rời rạc Nguyễn Quỳnh Diệp 37
CÁC LƯỢNG TỪ
 Mệnh đề Khi nào đúng? Khi nào sai?
 ∀ 푃( ) P(x) đúng với mọi x Có một giá trị x để
 P(x) là sai
 ∃ 푃( ) Có một giá trị x để P(x) P(x) sai với mọi x
 là đúng
• Ví dụ: Xác định phủ định chân lý của mệnh đề ∃ 2 ≥ 10
 trong không gian các số nguyên dương không lớn hơn 4
 Tồn tạ𝑖 = 4 để ệ푛ℎ đề 2 ≥ 10 đúng. Do đó, mệnh đề
 ∃ 2 ≥ 10 có giá trị chân lý là 1
 Toán rời rạc Nguyễn Quỳnh Diệp 38
PHỦ ĐỊNH CÁC LƯỢNG TỪ
Phủ định Mệnh đề tương Khi nào phủ Khi nào sai?
 đương định đúng?
 ¬∃ 푃( ) ∀ ¬푃( ) P(x) sai với mọi x Có một x để 
 P(x) là đúng
 ¬∀ 푃( ) ∃ ¬푃( ) Có một x để P(x) P(x) đúng với
 là sai mọi x
• Ví dụ:
 Xác định phủ định của mệnh đề ∀ 2 ≥ 0 ?
 Toán rời rạc Nguyễn Quỳnh Diệp 39
TRẬT TỰ CỦA CÁC LƯỢNG TỪ
 Mệnh đề Khi nào đúng? Khi nào sai?
 ∀ ∀ 푃 , P(x,y) đúng với mọi Có một cặp (x,y) để
 ∀ ∀ 푃( , ) cặp (x,y) P(x,y) là sai
∀ ∃ 푃( , ) Với mọi x, có một y để Có một x, để P(x,y) sai
 P(x,y) đúng với mọi y
∃ ∀ 푃( , ) Có một x, để P(x,y) Với mọi x, có một y để
 đúng với mọi y P(x,y) sai
∃ ∃ 푃( , ) Có một cặp (x,y) để P(x,y) với sai với mọi
∃ ∃ 푃( , P(x,y) đúng cặp (x,y)
 Toán rời rạc Nguyễn Quỳnh Diệp 40
 BÀI TẬP
. Bài 1: Xác định chân lí các mệnh đề sau, nếu không gian bao gồm
 các số nguyên:
 a)n (n2 0); b) n (n2 = 2)
 c) n (n2 n); d) n (n2 < 0);
. Bài 2: Giả sử không gian của hàm mệnh đề P(x) gồm các số
 nguyên 0, 1, 2, 3 và 4. Hãy viết các mệnh đề sau bằng cách dùng
 các phép hội, tuyển, phủ định:
 a)xP(x); b) xP(x)
 c) xP(x); d)  (xP(x));
 41
 Toán rời rạc Nguyễn Quỳnh Diệp
 BÀI TẬP
. Bài 3: Dịch mệnh đề sau ra ngôn ngữ thông thường, với
 C(x) là câu “x là diễn viên hài”, F(x) là “x là người vui
 nhộn” và không gian là tất cả mọi người trên thế giới.
 a. (∀풙(푪 풙 → 푭 풙 )
 b. (∃풙(푪 풙 ∧ 푭 풙 )
 42
 Toán rời rạc Nguyễn Quỳnh Diệp
BÀI TẬP
. Bài 4: Dịch những câu sau đây thành các biểu thức logic nhờ sử
 dụng vị từ, lượng từ và liên từ logic:
 a) Không có ai là hoàn hảo
 b) Không phải mọi người đều hoàn hảo
 c) Tất cả các bạn của bạn đều hoàn hảo
 d) Một trong số các bạn của bạn là hoàn hảo
 e) Mọi người đều là bạn của bạn và hoàn hảo
 f) Không phải mọi người đều là bạn của bạn hoặc có ai đó là
không hoàn hảo.
 43
 Toán rời rạc Nguyễn Quỳnh Diệp
CÁC LƯỢNG TỪ LỒNG NHAU
 Các lượng từ xuất hiện bên trong các lượng từ khác
 • Ví dụ 1:
 Giả sử rằng không gian của các biến x và y là các số thực. Ta 
 có mệnh đề:
 ∀풙∀풚 풙 + 풚 = 풚 + 풙
 ∀풙∃풚(풙 + 풚 = )
 Toán rời rạc Nguyễn Quỳnh Diệp 44
CÁC LƯỢNG TỪ LỒNG NHAU
 • Ví dụ 2:
 Dịch mệnh đề sau sang ngôn ngữ thông thường:
 ∀풙(푪 풙 ∨ ∃풚 푪 풚 ∧ 푭 풙, 풚 )
 Trong đó:
 - C(x) : x có máy vi tính
 - F(x,y): x và y là bạn
 Với không gian của cả x và y là toàn thể sinh viên trong trường
 Toán rời rạc Nguyễn Quỳnh Diệp 45
CÁC LƯỢNG TỪ LỒNG NHAU
 • Ví dụ 3:
 Biểu diễn phủ định của mệnh đề:
 ∀풙∃풚(풙풚 = )
 Sao cho không có dấu phủ định đứng trước các lượng từ.
 Toán rời rạc Nguyễn Quỳnh Diệp 46
BÀI TẬP
. Bài 5: Cho L(x,y) là câu “x yêu y”, với không gian của x và y là
 tập hợp mọi người trên thế giới. Hãy dùng các lượng từ để diễn
 đạt các câu sau:
a. Mọi người đều yêu Jerry
b. Mọi người đều yêu một ai đó
c. Có một người mà tất cả mọi người đều yêu
d. Không có ai yêu tất cả mọi người
e. Có một người mà không ai yêu cả
 47
 Toán rời rạc Nguyễn Quỳnh Diệp
1.4. CÁC DẠNG CHUẨN TẮC HỘI, TUYỂN
 Toán rời rạc Nguyễn Quỳnh Diệp 48
DẠNG CHUẨN TẮC
 Dạng chuẩn tắc (chính tắc) của một biểu thức logic là biểu diễn biểu 
 thức về dạng đơn giản, chỉ bao gồm các phép toán phủ định, hội, 
 tuyển của các mệnh đề. 
 • Ví dụ:
 풑 ∧ 풒 ∧ 풓 
 Toán rời rạc Nguyễn Quỳnh Diệp 49
DẠNG CHUẨN TẮC
• Định nghĩa:
 - Hội các mệnh đề và phủ định của nó gọi là hội sơ cấp (HSC)
 - Tuyển các mệnh đề và phủ định của nó gọi là tuyển sơ cấp 
 (TSC)
 • Ví dụ:
 풑 ∧ 풒 ∧ 풓 ∧ 풑 (HSC)
 풑 ∨ 풒 ∨ 풓 ∨ 풑 (TSC)
 Toán rời rạc Nguyễn Quỳnh Diệp 50
DẠNG CHUẨN HỘI
• Định nghĩa:
 - Giả sử A là một biểu thức. Nếu ′ ≡ mà ′ là hội của các
 TSC thì ′ được gọi là dạng chuẩn tắc hội (DCTH) của A.
 ′
 - Tức là = 푻푺푪 ∧ 푻푺푪 ∧ ⋯ ∧ (푻푺푪)풏
 • Ví dụ:
 = ((풑 ∧ 풒) → 풒) ∧ ((풑 ∧ 풒 ) → 풑)
 ′ = (풑 ∨ 풒 ∨ 풒) ∧ (풑 ∨ 풒 ∨ 풑)
 Toán rời rạc Nguyễn Quỳnh Diệp 51
DẠNG CHUẨN TUYỂN
• Định nghĩa:
 - Giả sử A là một biểu thức. Nếu ′′ ≡ mà ′′ là tuyển của các
 HSC thì ′′ được gọi là dạng chuẩn tắc tuyển (DCTT) của A.
 ′′
 - Tức là = (푯푺푪) ∨ (푯푺푪) ∨ ⋯ ∨ (푯푺푪)풏
 • Ví dụ:
 ′′ = 풑 ∧ 풒 ∧ 풓 ∧ 풑 ∨ 풑 ∧ 풒 ∧ 풓 ∧ 풑
 Toán rời rạc Nguyễn Quỳnh Diệp 52
DẠNG CHUẨN HỘI, TUYỂN
• Định lý 1:
 Mọi biểu thức trong logic mệnh đề đều có DCTT và DCTH
 • Ví dụ:
 = 푿 ∧ (푿 → 풀)
 ′ = 푿 ∧ (푿 ∨ 풀) (DCTH)
 ′′ = 푿 ∧ 푿 ∨ ( 푿 ∧ 풀) (DCTT)
 Toán rời rạc Nguyễn Quỳnh Diệp 53
DẠNG CHUẨN HỘI, TUYỂN
• Định lý 2:
 Điều kiện cần và đủ để biểu thức A là hằng đúng là: 
 trong DCTH của A mỗi TSC chứa một mệnh đề đồng thời
 với phủ định của nó
 Điều kiện cần và đủ để biểu thức A là hằng sai (mâu
 thuẫn) thì trong DCTT của A mỗi HSC chứa một mệnh
 đề đồng thời với phủ định của nó
 Toán rời rạc Nguyễn Quỳnh Diệp 54
BÀI TẬP
 . Bài 6: Chứng minh mệnh đề sau là hằng đúng bằng cách
 xây dựng các dạng chuẩn tắc:
 a. 풑 → 풒 → (풒 → 풑 )
 b.¬ ( 풑 → 풒) → (풑 → 풓 ) → ¬(풑 → 풒 → 풓 )
 55
 Toán rời rạc Nguyễn Quỳnh Diệp
1.5. CÁC QUY TẮC SUY DIỄN
 Toán rời rạc Nguyễn Quỳnh Diệp 56
MỘT SỐ ĐỊNH NGHĨA
 • Định lí:
 - Định lí là một phát biểu có thể chứng tỏ được là đúng.
 - Định lí thường có dạng như sau:
 (풑 ∧ 풑 ∧ 풑  ∧ 풑풏) → 풒
 Giả thuyết Kết luận
 Toán rời rạc Nguyễn Quỳnh Diệp 57
MỘT SỐ ĐỊNH NGHĨA
 • Chứng minh: là những suy luận ra mệnh đề mới từ những 
 mệnh đề cũ.
 Các giả thuyết Kết luận
 +
 Các tiên đề
 +
 Các định lí đã 
 chứng minh
 ĐÚNG ĐÚNG?
 Toán rời rạc Nguyễn Quỳnh Diệp 58
MỘT SỐ ĐỊNH NGHĨA
 • Logic là công cụ cho phép phân tích tính đúng đắn của
 các chứng minh
 • Các quy tắc suy diễn là cách rút ra các kết luận từ
 những điều khẳng định khác
 Toán rời rạc Nguyễn Quỳnh Diệp 59
MÔ HÌNH SUY DIỄN
 • Ví dụ:
 Tam giác cân có một góc bằng 60 độ thì tam giác đó là tam 
 giác đều
 (풑 ∧ 풑 ∧  ∧ 풑풏) → 풒 ≡ 푻
 Mô hình suy diễn của biểu thức trên là;
 풑 
 풑 
 풑풏 Ký hiệu dấu  có nghĩa
 ∴ 풒 là “vậy thì”
 Toán rời rạc Nguyễn Quỳnh Diệp 60
MÔ HÌNH SUY DIỄN
• Ví dụ:
 Quy tắc suy luận nào là cơ sở của suy diễn sau: “Bây giờ trời quá 
 băng giá. Vậy thì bây giờ hoặc là trời quá băng giá hoặc trời đang 
 mưa”
 - p : Bây giờ trời quá băng giá
 - q: Bây giờ trời đang mưa
 - Khi đó suy diễn có dạng:
 풑
 ∴ 풑 ∨ 풒
 Toán rời rạc Nguyễn Quỳnh Diệp 61
CÁC QUY TẮC SUY DIỄN
 • Quy tắc suy diễn cộng:
 Cơ sở của quy tắc suy diễn là hằng đúng: 풑 → (풑 ∨ 풒)
 Mô hình suy diễn 풑
 ∴ 풑 ∨ 풒
• Quy tắc suy diễn rút gọn:
 Cơ sở của quy tắc suy diễn rút gọn là hằng đúng: 풑 ∧ 풒 → 풑
 Mô hình suy diễn 풑
 풒
 ∴ 풑
 Toán rời rạc Nguyễn Quỳnh Diệp 62
MÔ HÌNH SUY DIỄN
• Ví dụ:
 Dùng quy tắc suy diễn, chỉ ra công thức sau là hằng đúng:
 퐩 ∧ 풒 → ( 풑 ∨ 풒)
 Toán rời rạc Nguyễn Quỳnh Diệp 63
CÁC QUY TẮC SUY DIỄN
• Quy tắc suy diễn khẳng định:
 Cơ sở của quy tắc suy diễn là hằng đúng: 풑 ∧ ( 풑 → 풒) → 풒
 Mô hình suy diễn 풑
 풑 → 풒
 ∴ 풒
 • Quy tắc suy diễn phủ định:
 Cơ sở của quy tắc suy diễn là hằng đúng: ( 풑 → 풒 ∧ 풒 ) → 풑 
 Mô hình suy diễn 풑 → 풒
 풒 
 ∴ 풑 
 Toán rời rạc Nguyễn Quỳnh Diệp 64
MÔ HÌNH SUY DIỄN
• Ví dụ:
 “Nếu được thưởng cuối năm An sẽ đi Đà Lạt. Nếu đi Đà Lạt thì An sẽ
 thăm Thiền Viện. Mà An không thăm Thiền Viện. Vậy An không
 được thưởng cuối năm.”
 Suy luận của đoạn văn trên có đúng không?
 Toán rời rạc Nguyễn Quỳnh Diệp 65
CÁC QUY TẮC SUY DIỄN
 • Quy tắc suy diễn tam đoạn luận:
 Cơ sở của quy tắc suy diễn là hằng đúng:
 (풑 → 풒) ∧ ( 풒 → 풓) → (풑 → 풓)
 Mô hình suy diễn
 풑 → 풒
 풒 → 풓
 ∴ 풑 → 풓
 Toán rời rạc Nguyễn Quỳnh Diệp 66
CÁC QUY TẮC SUY DIỄN
 • Quy tắc suy diễn tam đoạn luận tuyển:
 Cơ sở của quy tắc suy diễn là hằng đúng:
 풑 ∨ 풒 ∧ 풑 → 풒
 Mô hình suy diễn
 풑 ∨ 풒
 풑 
 ∴ 풒
 Toán rời rạc Nguyễn Quỳnh Diệp 67
CÁC QUY TẮC SUY DIỄN
• Ví dụ:
 “Bình đi chơi thì Bình không học toán rời rạc. Bình không học toán
 rời rạc thì Bình thi trượt toán rời rạc. Mà Bình thích đi chơi. Vậy
 Bình thi trượt toán rời rạc.”
 Suy luận của đoạn văn trên có đúng không?
 Toán rời rạc Nguyễn Quỳnh Diệp 68
CÁC QUY TẮC SUY DIỄN
 • Quy tắc suy diễn mâu thuẫn:
 Cơ sở của quy tắc suy diễn là hằng đúng:
 풑 ∧ 풑 ∧ ⋯ ∧ 풑풏 → 풒 ≡ 푻
 풑 ∧ 풑 ∧ ⋯ ∧ 풑풏 ∧ ¬풒 ≡ 푭
 풑 
 Mô hình suy diễn 풑 풑 
 풑 ⋮
 ⋮ 풑풏
 풑 풒 
 풏 ≡
 ∴ 풒 ∴ 푭
 Toán rời rạc Nguyễn Quỳnh Diệp 69
CÁC QUY TẮC SUY DIỄN
 • Quy tắc suy diễn theo trường hợp:
 Cơ sở của quy tắc suy diễn là hằng đúng:
 풑 → 풓 ∧ 풒 → 풓 → ( 풑 ∨ 풒 → 풓)
 Mô hình suy diễn
 풑 → 풓
 풒 → 풓
 ∴ 풑 ∨ 풒 → 풓
 Toán rời rạc Nguyễn Quỳnh Diệp 70
CÁC QUY TẮC SUY DIỄN
• Ví dụ 1:
 Chỉ ra suy luận dưới đây là đúng:
 풑 → 풒
 풑 → 풓
 풓 → 풔
 ∴ 풒 → 풔
 Toán rời rạc Nguyễn Quỳnh Diệp 71
CÁC QUY TẮC SUY DIỄN
• Ví dụ:
 Suy luận dưới đây có đúng không:
 “Nếu muốn đi họp sáng thứ ba thì An phải dậy sớm. Nếu An đi nghe
 nhạc tối thứ hai thì An sẽ về muộn. Nếu An về muộn và thức dậy sớm
 thì An phải đi họp sáng thứ ba và chỉ được ngủ dưới 7 giờ trong ngày. 
 Nhưng An không thể đi họp nếu chỉ ngủ dưới 7 giờ. Vậy hoặc An 
 không đi nghe nhạc tối thứ hai hoặc An phải bỏ họp sáng thứ ba.”
 Toán rời rạc Nguyễn Quỳnh Diệp 72
BÀI TẬP
 . Bài 7: Chỉ ra công thức dưới đây là hằng đúng áp dụng
 các quy tắc suy diễn
 a. 푿 ∧ ( 푿 → 푿 ∧ 푿 ∨ 푿ퟒ ∧ (푿ퟒ → 푿 )) → (푿 ∨ 푿 )
 b. 푿 ∨ 푿 → 푿 
 푿 → (푿ퟒ ∨ 푿 )
 푿ퟒ ∧ 푿 
 푿 → 푿 
 ∴ 푿 
 73
 Toán rời rạc Nguyễn Quỳnh Diệp
BÀI TẬP
. Bài 8: Nếu nghệ sĩ nhân dân (NSND) X không trình diễn hay số
 vé bán ra ít hơn 50 vé thì đêm biểu diễn ở Công viên Hồ Tây bị
 hủy và ông bầu rất buồn. Nếu đêm biểu diễn hủy bỏ thì phải trả
 tiền vé lại cho người xem. Tiền vé đã không trả lại cho người xem. 
 Vậy NSND X đã trình diễn.
. Suy luận trên có đúng không?
 74
 Toán rời rạc Nguyễn Quỳnh Diệp
1.6. CÁC PHƯƠNG PHÁP CHỨNG MINH
 Toán rời rạc Nguyễn Quỳnh Diệp 75
ĐẶT VẤN ĐỀ
 • Làm sao để biết được giá trị đúng/sai của mệnh đề?
 • Có những phương pháp nào?
 Toán rời rạc Nguyễn Quỳnh Diệp 76
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Các phương pháp chứng minh định lí:
 • Chứng minh trực tiếp
 • Chứng minh gián tiếp
 • Chứng minh bằng phản chứng
 • Chứng minh từng trường hợp
 • Chứng minh tính tương đương
 Toán rời rạc Nguyễn Quỳnh Diệp 77
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Định nghĩa 1:
 Số nguyên n là chẵn nếu tồn tại một số nguyên k sao
 cho n = 2k và là lẻ nếu tồn tại một số nguyên k sao cho n 
 = 2k+1.
 Định nghĩa 2:
 Số thực r được gọi là hữu tỉ nếu tồn tại hai số nguyên
 p và q với q 0 sao cho r = p/q. Một số thực không
 phải là hữu tỉ được gọi là vô tỉ.
 Toán rời rạc Nguyễn Quỳnh Diệp 78
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Chứng minh trực tiếp:
 Chứng minh mệnh đề kéo theo 풑 → 풒 bằng cách xuất phát
 từ 풑 đúng, chỉ ra là 풒 cũng đúng.
 • Ví dụ:
 Chứng minh trực tiếp: “Nếu 풏 là một số nguyên lẻ thì 풏 cũng là một
 số nguyên lẻ”
 Toán rời rạc Nguyễn Quỳnh Diệp 79
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Chứng minh gián tiếp:
 Chứng minh mệnh đề kéo theo (풑 → 풒) bằng cách
 chứng minh mệnh đề (풒 → 풑 ) là đúng.
 • Ví dụ:
 Chứng minh gián tiếp: “Nếu 3풏 + là một số lẻ thì 풏 cũng lẻ”
 Toán rời rạc Nguyễn Quỳnh Diệp 80
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Chứng minh bằng phản chứng:
 Chỉ ra mệnh đề 풑 sai, do đó 풑 là đúng
 • Ví dụ:
 Chứng minh bằng phản chứng: “ là vô tỉ”
 Toán rời rạc Nguyễn Quỳnh Diệp 81
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Chứng minh tính tương đương:
 Để chứng minh một mệnh đề kéo theo có dạng 풑 ↔ 풒, ta 
 sử dụng hằng đúng
 풑 ↔ 풒 ≡ 풑 → 풒 ∧ (풒 → 풑)
 • Ví dụ:
 Chứng minh định lí: “n là số lẻ nếu và chỉ nếu n2 là lẻ”
 Toán rời rạc Nguyễn Quỳnh Diệp 82
1.5 CÁC PHƯƠNG PHÁP CHỨNG MINH
 Chứng minh từng trường hợp:
 Để chứng minh một mệnh đề kéo theo có dạng:
 풑 ∨ 풑 ∨ ⋯ ∨ 풑풏 → 풒
 có thể dùng hằng đúng
 풑 ∨ ⋯ ∨ 풑풏 → 풒 ↔ [ 풑 → 풒 ∧ ⋯ ∧ 풑풏 → 풒 ]
 Toán rời rạc Nguyễn Quỳnh Diệp 83
BÀI TẬP
 . Bài 1: Chứng minh nếu x là số vô tỉ thì 1/x cũng là số vô
 tỉ
 . Bài 2: Chứng minh trong số 64 ngày được chọn , ít nhất
 có 10 ngày cùng rơi vào một thứ trong tuần.
 . Bài 3: Chứng minh rằng x, y là 2 số thực, khi đó:
 max(x, y) + min(x,y) = x + y
 84
 Toán rời rạc Nguyễn Quỳnh Diệp
 85
Nguyễn Quỳnh Diệp