Bài giảng Toán rời rạc - Chương 1: Cơ sở logic - Vũ Đình Long

Chương 1
CƠ SỞ LOGIC
Mệnh đề

 Mệnh đề là một khẳng định có giá trị chân lý đúng hoặc sai. 
Các mệnh đề đúng được gọi là có giá trị chân lý đúng (chân 
trị đúng), ngược lại các mệnh đề sai được gọi là có chân trị
sai.

 Mệnh đề được xây dựng từ các mệnh đề khác nhờ các liên 
từ hoặc trạng từ không gọi là mệnh đề phức hợp.

 Các mệnh đề không xây dựng từ các mệnh đề khác nhờ các 
liên từ hoặc trạng từ không gọi là các mệnh đề nguyên thủy 
hay sơ cấp.
Mệnh đề (tt)
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, sơ cấp.
Phép tính mệnh đề (tt)
Phép tính mệnh đề (tt)
Phép tính mệnh đề (tt)
Phép tính mệnh đề (tt)
Phép tính mệnh đề (tt)
Biểu thức mệnh đề (tt)
Biểu thức mệnh đề (tt)
Biểu thức mệnh đề (tt)
Biểu thức mệnh đề (tt)
Biểu thức mệnh đề (tt)
Biểu thức mệnh đề (tt)

 Qui tắc thay thế:

 Trong biểu thức (dạng) mệnh đề E nếu thay thế biểu thức 
logic con F bởi một dạng mệnh đề tương đương logic thì
dạng mệnh đề thu được cũng tương đương logic với E.

 Ví dụ: p -> (q -> r) tương đương logic với p -> (┐p v r).

 Giả sử dạng mệnh đề E(p,q,r, ...) là một hằng đúng. Nếu 
ta thay thế những chỗ xuất hiện p trong E bởi một dạng 
mệnh đề tùy ý E’(p’, q’, r’, ...) thì dạng mệnh đề E(q, r, p’, 
q’, r’, ...) cũng là một hằng đúng.

 Ví dụ: (p -> q) (┐p v q) khi đó nếu thay p bằng r -> s 
ta được

 ((r -> s) -> q) (┐(r -> s) v q) cũng là một hằng đúng.
Các luật logic
Các luật logic (tt)
Các luật logic (tt)
Các quy tắc suy diễn
Các quy tắc suy diễn (tt)
Các quy tắc suy diễn (tt)

 Các qui tắc khác:
• Phương pháp phủ định
• Tam đoạn luận
• Tam đoạn luận rời
• Chứng minh từng trường hợp
• Phương pháp phản chứng
Vị từ và lượng từ
Vị từ và lượng từ (tt)
Vị từ và lượng từ (tt)
Vị từ và lượng từ (tt)
Nguyên lý quy nạp
Nguyên lý quy nạp

 Ví d
: chứng minh rằng

 1 + 3 + 5 + ... + (2k-1) = k2 (*)

 Bước cơ sở: với k = 1 ta có 1 = 1 (*) đúng.

 Bước quy nạp: Giả sử

 1 + 3 + ... + (2n-1) = n2

 ta sẽ chứng tỏ:

 1 + 3 + ... + (2n-1) + (2n+1) = (n+1)2

 Thật vậy, ta có

 VT = n2 + (2n+1) = (n+1)2 = VP