3/5/2009
1
Phạm Phúc Thịnh
PHẦN MỞ ĐẦU
Các kiến thức sẽ học
1. Cơ Sở Logic
a) Mệnh đề & chân trị
b) Các phép toán mệnh đề
c) Dạng mệnh đề & Luật logic
d) Quy tắc suy diễn
e) Vị từ & lượng từ
f) Tập hợp – Các phép toán tập hợp
g) Quy nạp toán học – Định nghĩa đệ quy
Các kiến thức sẽ học
2. Phép đếm
a) Định nghĩa – tính chất cơ bản.
b) Nguyễn lý cộng - nguyên lý nhân
c) Nguyên lý Chuồng bồ câu
d) Chỉnh hợp – Tổ hợp. Công thức nhị thức
e) Tổ hợp có lặp
3. Quan hệ
a) Quan hệ & Các tính chất
b) Biễu diễn quan hệ
c) Quan hệ tương đương – Đồng dư.
d) Quan hệ thứ tự
Các kiến thức sẽ học
4. Đại số Bool
a) Hàm Bool. Dạng nối rời chính tắc
b) Công thức đa thức tối tiểu
c) Phương pháp biểu đồ Karnaugh
d) Mạng các cổng
Thời gian học tập
Tổng số tiết : 45 (Bao gồm lý thuyết + bài tập
a) Lý thuyết : 30 tiết
b) Bài tập : 14 tiết
c) Kiểm tra : 1 tiết
Mục tiêu của học phần:
Nhằm trang bịcho sinh viên những kiến thức cơbản về
Logic, Lý thuyết tập hợp, Các nguyên lý đếm, Quan hệ, và
Hàm Bool.
Tài liệu tham khảo:
-Các giáo trình toán rời rạc của bậc học Cao đẳng (Có
thể tìm thấy trong thư viện hoặc trên mạng Internet)
-- Bài giảng của giáo viên quan trang blog :
Chuottau.blogtiengviet.net
3/5/2009
2
CHƯƠNG 1 PHẦN 1
Khái niệm mệnh đề và chân trị
Các đối tượng cơbản mà chúng ta khảo sát ở
đây là các phát biểu hay các mệnh đề.Tuy
nhiên, ta chỉxét đến các mệnh đề toán học, và
chúng ta nói vắn tắt các mệnh đề toán học là
các mệnh đề.
Mệnh đề toán họclà những phát biểuđể diễn
đạt một ý tưởng trọn vẹn và ta có thểkhẳng
định một cách khách quan là nó đúng hoặc sai.
Khái niệm mệnh đề và chân trị
Tính chất cơbản của một mệnh đề là nó đúng
hoặc sai, và không thểvừađúng vừa sai. Giá trị
đúng hoặc sai của một mệnh đề được gọi là
chân trịcủa mệnh đề.
Vềmặt ký hiệu, ta dùng các mẫu tự(nhưp, q, r,
...) để ký hiệu cho các mệnh đề, và chúng cũng
được dùng để ký hiệu cho các biến logic, tức là
các biến lấy giá trị đúng hoặc sai.
Chân trị“đúng” thường được viết là 1, và chân
trị“sai” được viết là 0.
Các ví dụ về mệnh đề
1. 6 là một sốnguyên tố.
2. 5 là một sốnguyên tố.
3. -3 < 2
4. Tam giác cân có hai góc bằng nhau.
5. H2O là một axít.
Các mệnh đề 2, 3, và 4 trong ví dụtrên là những
mệnh đề đúng.
Các mệnh đề 1, 5 là những mệnh đề sai.
Các ví dụ về mệnh đề
Các phát biểu sau đây không phải là các mệnh
đề (toán học) vì tính đúng sai của chúng không
xác định.
1. Ai đang đọc sách? (một câu hỏi)
2. Hãy đóng cửa lạiđi!
3. Anh ta rất thông minh.
4. Cho x là một sốnguyên dương.
5. a là một sốchính phương.
6. x + y = z.
3/5/2009
3
Mệnh đề sơ cấp – Mệnh đề phức hợp
Phân loại mệnh đề : mệnh đề sơcấp
(elementary), mệnh đề phức hợp (compound).
Mệnh đề sơcấplà các mệnh đề không thểphân
tích được thành một hay nhiều (từhai trởlên)
mệnh đề thành phầnđơn giản hơn.
Mệnh đề phức hợplà mệnh đề được tạo thành
từmột hay nhiều mệnh đề khác bằng cách sử
dụng các liên kết logic nhưtừ“không” dùng
trong việc phủ định một mệnh đề, các từnối:
“và”, “hay”, “hoặc”, “suy ra”, v.v....
Ví dụ về phân loại mệnh đề
1. p = “15 chia hết cho 3”.
2. q = “2 là một sốnguyên tốvà là một sốlẻ”.
Ta có p là một mệnh đề sơcấp. Nhưng q là một
mệnh đề phức hợp, vì mệnh đề qđược tạo
thành từhai mệnh đề “2 là một sốnguyên tố” và
“2 là một sốlẻ” nhờvào liên kết logic “và”.
PHẦN 2
Bảng chân trị của một mệnh đề
Vnđ : làm thếnào để tính toán chân trịcủa
các mệnh đề phức hợp theo các mệnh đề sơ
cấp cấu thành mệnh đề phức hợpđó nhờvào
các phép toán logic.
Các phép toán logic là các ký hiệuđược dùng
thay cho các từliên kết logic như“không”, “và”,
“hay”, “hoặc”, “suy ra” hay “nếu ... thì ...”, “nếu
và chỉnếu”.
Bảng chân trị của một mệnh đề
Các phép toán logic đượcđịnh nghĩa bằng bảng
chân trị(truth table). Bảng chân trịcho ta chân
trịcủa mệnh đề phức hợp theo từng trường hợp
của các chân trịcủa các mệnh đề sơcấp tạo
thành mệnh đề phức hợp.
Bảng chân trị được dùng với mụcđích : liệt kê
sựliên hệchân trịgiữa các mệnh với các mệnh
đề đơn giản hơn cấu thành chúng.
Phép Phủ định
Cho p là một mệnh đề, ký hiệu “¬p” để chỉmệnh
đề phủ định của mệnh đề p. “Sựphủ định” được
định nghĩa bởi bảng chân trịsau đây:
p ¬p
1 0
0 1
Mệnh đề phủ định ¬p có
chân trịlà đúng (1) khi
mệnh đề p có chân trịsai
(0), ngược lại ¬p có chân trị
sai (0) khi p có chân trị
đúng (1).
3/5/2009
4
Phép Phủ định
Ví dụ1 :
Nếu ta ký hiệu p là mệnh đề “5 < 3” thì ¬p là ký
hiệu cho mệnh đề “5 ≥3”. Trong trường hợp nầy p
sai, ¬ p đúng. Ta có thểviết p = 0, ¬ p = 1.
Phép Phủ định
p¬p¬(¬p)
0 1 0
1 0 1
Ví dụ2 : Chỉra rằng ¬(¬p) và p luôn có
cùng chân trị.
Giải. Lập bảng chân trịcủa mệnh đề
¬(¬ p):
Trên mỗi dòng giá trịtrong bảng chân trị
ta có chân trịcủa p và ¬(¬p) đều bằng
nhau (so sánh cột 1 và cột 3 trong
bảng). Vậy ¬(¬p) và p có cùng chân trị.
Ta cũng nói rằng ¬(¬p) tương đương
logic với p.
Mệnh đề ¬(¬p) thường được viết là
¬¬p.
Phép Hội
Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p
hay q” là pΛq. Phép “và”, ký hiệu là Λđượcđịnh
nghĩa bởi bảng chân trịsau đây:
p q p Λq
0 0 0
0 1 0
1 0 0
1 1 1
Phép Hội
Qua định nghĩa trên ta nhận thấy rằng các mệnh đề pΛq
và q Λp luôn luôn có cùng chân trị, hay tương đương logic.
Tuy nhiên, trong ngôn ngữthông thường các mệnh đề “p và
q” và “q và p” đôi khi có ý nghĩa khác nhau theo ngữcảnh.
Ví d: Cho các mệnh đề
p = “5 > -7”,
q = “2721 là một số nguyên tố”,
r = “một tam giác đều cũng là một tam giác cân”.
Khi đó ta có :
p Λ q = 0 (p Λq sai, tức là có chân trị bằng 0, vì p = 1 và q = 0),
p Λr = 1 (p Λr đúng, tức là có chân trị bằng 1, vì p = 1 và r = 1).
Phép Hội
Nhận xét: Bằng cách lập bảng chân trị, ta có:
1. Các mệnh đề p và p Λp luôn có cùng chân trị.
2. Mệnh đề pΛ¬ p luôn có chân trịbằng 0 (tức là
một mệnh đề luôn sai).
3. Một mệnh đề phức hợp luôn luôn có chân trịlà sai
trong mọi trường hợp chân trịcủa các mệnh đề sơ
cấp tạo thành nó sẽ được gọi là một sựmâu
thuẩn.
Phép Tuyển
Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p
hay q” là p ∨q. Phép “hay”, ký hiệu là ∨,đượcđịnh
nghĩa bởi bảng chân trịsau đây:
p q p ∨q
0 0 0
0 1 1
1 0 1
1 1 1
3/5/2009
5
Phép Tuyển
Chân trịcủa mệnh đề p∨q phụthuộc vào các chân
trịcủa2mệnh đề p, q. Trong 4 trường hợp chỉcó
một trường hợp mệnh đề p∨q sai, đó là trường
hợp p sai và q sai.
Qua định nghĩa trên ta nhận thấy rằng các mệnh đề
p∨q và q ∨p luôn luôn có cùng chân trị, hay tương
đương logic.
Phép Tuyển
Ví dụ:Cho các mệnh đề
• p = “5 > 7”,
• q = “2721 là một số nguyên tố”,
• r = “một tam giác đều cũng là một tam giác cân”.
Khi đó ta có :
p V q = 0,
p V r = 1.
Phép Tuyển
Nhận xét :
1. Cho p là một
mệnh đề. Lập
bảng chân trị
của mệnh đề p
∨¬ p
ta có mệnh đề
p∨¬ p luôn luôn
đúng.
p¬p p∨¬ p
0 1 1
1 0 1
Phép Kéo theo
Phép kéo theo, ký hiệu bởi→,đượcđưa ra để mô
hình cho loại phát biểuđiều kiện có dạng : “nếu . . .
thì . . .”. Cho p và q là 2 mệnh đề, ta sẽviếtp→qđể
diễnđạt phát biểu “nếu p thì q”. Phép toán kéo theo
→đượcđịnh nghĩa bởi bảng chân trịsau đây:
p q p q
0 0 1
0 1 1
p q p q
1 0 0
1 1 1
Phép Kéo theo
Mệnh đề p →q, được đọc là “nếu p thì q”, còn được
phát biểu dưới các dạng khác sau đây:
”q nếu p”.
”p chỉ nếu q”.
”p là điều kiện đủ cho q”.
”q là điều kiện cần cho p”.
Phép Kéo theo 2 chiều
Phép kéo theo 2 chiều hay phép tương đương, ký hiệu
bởi ↔, được đưa ra để mô hình cho loại phát biểu điều
kiện hai chiều có dạng : “. . . nếu và chỉ nếu . . .”. Cho p
và q là 2 mệnh đề, ta viết p↔qđể diễn đạt phát biểu “p
nếu và chỉ nếu q”. Phép toán tương đương được định
nghĩa bởi bảng chân trị sau đây
p q p ↔q
0 0 1
0 1 0
p q p ↔q
1 0 0
1 1 1