Giáo trình Toán rời rạc - Trường Đại học Hàng Hải
BỘ GIAO THÔNG VẬN TẢI
TRƢỜNG ĐẠI HỌC HÀNG HẢI
BỘ MÔN: KHOA HỌC MÁY TÍNH
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
TOÁN RỜI RẠC
TÊN HỌC PHẦN
MÃ HỌC PHẦN
: TOÁN RỜI RẠC
: 17203
TRÌNH ĐỘ ĐÀO TẠO
: ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2010
MỤC LỤC
NỘI DUNG
Chƣơng 1. Đại cƣơng về logic
TRANG
1
1.1. Phép tính mệnh đề
1
1.1.1. Khái niệm về mệnh đề và chân trị
1.1.2. Các phép toán trên mệnh đề
1.2. Biểu thức logic
1
2
5
1.2.1. Định nghĩa và bảng chân trị của biểu thức logic
1.2.2. Sự tương đương logic
5
8
1.2.3. Giá trị của biểu thức logic
1.3. Các luật logic
8
8
1.3.1. Các luật logic
8
1.3.2. Các quy tắc thay thế
10
11
12
12
13
14
14
16
17
18
20
20
21
21
23
25
29
29
29
29
31
33
1.3.3. Ví dụ áp dụng
1.4. Các dạng chuẩn tắc
1.4.1. Chuẩn tắc tuyển
1.4.2. Chuẩn tắc hội
1.5. Quy tắc suy diễn
1.5.1. Đại cương về quy tắc suy diễn
1.5.2. Kiểm tra một quy tắc suy diễn
1.5.3. Các quy tắc suy diễn cơ bản
1.5.4. Các ví dụ áp dụng
1.6. Vị từ, lượng từ
1.6.1. Định nghĩa vị từ và ví dụ
1.6.2. Các phép toán trên vị từ
1.6.3. Lượng từ và mệnh đề có lượng từ
1.6.4. Quy tắc phủ định mệnh đề có lượng từ
1.6.5. Một số quy tắc dùng trong suy luận
Chƣơng 2. Các phƣơng pháp chứng minh
2.1. Các phương pháp chứng minh cơ bản
2.1.1. Khái niệm về chứng minh
2.1.2. Chứng minh trực tiếp
2.1.3. Chứng minh phản chứng
2.1.4. Chứng minh bằng cách phân chia trường hợp
NỘI DUNG
TRANG
34
35
35
36
38
41
41
41
42
43
45
45
45
46
48
52
53
56
56
56
57
58
59
59
59
60
60
62
63
63
65
71
71
2.1.5. Phản ví dụ
2.2. Nguyên lý quy nạp
2.2.1. Đại cương về quy nạp
2.2.2. Các nguyên lý quy nạp thường dùng
2.2.3. Các ví dụ
Chƣơng 3. Phƣơng pháp đếm
3.1. Tập hợp
3.1.1. Khái niệm tập hợp
3.1.2. Quan hệ “bao hàm trong” và tập hợp con
3.1.3. Các phép toán trên tập hợp
3.1.4. Tích Decartes của các tập hợp
3.2. Các nguyên lý đếm
3.2.1. Phép đếm
3.2.2. Nguyên lý cộng
3.2.3. Nguyên lý nhân
3.2.4. Nguyên lý bù trừ
3.2.5. Nguyên lý Dirichlet
Chƣơng 4. Quan hệ
4.1. Quan hệ hai ngôi
4.1.1. Định nghĩa quan hệ và ví dụ
4.1.2. Các tính chất của quan hệ
4.1.3. Biểu diễn quan hệ
4.2. Quan hệ tương đương
4.2.1. Khái niệm quan hệ tương đương
4.2.2. Lớp tương đương và tập hợp tương đương
4.3. Quan hệ thứ tự
4.3.1. Các định nghĩa
4.3.2. Biểu diễn quan hệ thứ tự
4.3.3. Tập hữu hạn có thứ tự
4.3.4. Sắp xếp topo
4.4. Dàn (lattice - tập bị chặn)
Chƣơng 5. Đại số Bool
5.1. Các phép toán
NỘI DUNG
TRANG
71
5.1.1. Các định nghĩa
5.1.2. Các tính chất của phép toán hai ngôi
5.2. Đại số Bool
73
78
5.2.1. Định nghiã và các tính chất
5.2.2. Đại số Bool và dàn
82
80
5.3. Các cổng logic và tổ hợp các cổng logic
5.3.1. Các cổng logic
85
85
5.3.2. Mạch logic
86
5.4. Cực tiểu hoá các mạch logic
5.4.1. Bản đồ Karnaugh
91
92
5.4.2. Phương pháp Quine-McCluskey
94
Tên học phần: Toán rời rạc
Loại học phần: 1
Tổng số TC: 2
Bộ môn phụ trách giảng dạy: Khoa học máy tính
Khoa phụ trách: CNTT
Mã học phần: 17203
TS tiết Lý thuyết Thực hành/Xemina Tự học Bài tập lớn
Đồ án môn học
45
45
0
0
0
0
Điều kiện tiên quyết:
Môn học có thể bố trí học từ học kỳ đầu tiên.
Mục tiêu của học phần:
Giúp sinh viên nắm được những kiến thức cơ bản về lý thuyết tổ hợp, toán logic, hệ toán
mệnh đề. Phương pháp suy diễn và chứng minh. Đại số Bool.
Nội dung chủ yếu
Giúp sinh viên nắm được những kiến thức cơ bản về lý thuyết tổ hợp, hệ toán mệnh đề,
các phương pháp đếm, khái niệm quan hệ, đại số Bool …và làm cơ sở cho các môn học
chuyên ngành khác.
Nội dung chi tiết của học phần:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
Chƣơng 1. Đại cƣơng về logic
TS LT TH/Xemina
BT
0
KT
0
16
16
0
1.1. Phép tính mệnh đề
2
1.1.1. Khái niệm về mệnh đề và chân trị
1.1.2. Các phép toán trên mệnh đề
1.2. Biểu thức logic
2
3
2
1.2.1. Định nghĩa và bảng chân trị của biểu thức logic
1.2.2. Sự tương đương logic
1.2.4. Giá trị của biểu thức logic
1.3. Các luật logic
1.3.1. Các luật logic
1.3.2. Các quy tắc thay thế
1.3.3. Ví dụ áp dụng
1.4. Các dạng chuẩn tắc
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
TÊN CHƢƠNG MỤC
1.4.1. Chuẩn tắc tuyển
KT
1.4.2. Chuẩn tắc hội
1.5. Quy tắc suy diễn
3
4
1.5.1. Đại cương về quy tắc suy diễn
1.5.2. Kiểm tra một quy tắc suy diễn
1.5.3. Các quy tắc suy diễn cơ bản
1.5.4. Các ví dụ áp dụng
1.6. Vị từ, lượng từ
1.6.1. Định nghĩa vị từ và ví dụ
1.6.2. Các phép toán trên vị từ
1.6.3. Lượng từ và mệnh đề có lượng từ
1.6.4. Quy tắc phủ định mệnh đề có lượng từ
1.6.5. Một số quy tắc dùng trong suy luận
Chƣơng 2. Các phƣơng pháp chứng minh
2.1. Các phương pháp chứng minh cơ bản
2.1.1. Khái niệm về chứng minh
2.1.2. Chứng minh trực tiếp
6
5
0
0
1
2
2.1.3. Chứng minh phản chứng
2.1.4. Chứng minh bằng cách phân chia trường hợp
2.1.5. Phản ví dụ
2.2. Nguyên lý quy nạp
3
2.2.1. Đại cương về quy nạp
2.2.2. Các nguyên lý quy nạp thường dùng
2.2.3. Các ví dụ
1
Chƣơng 3. Phƣơng pháp đếm
3.1. Tập hợp
5
5
2
3.1.1. Khái niệm tập hợp
3.1.2. Quan hệ “bao hàm trong” và tập hợp con
3.1.3. Các phép toán trên tập hợp
3.1.4. Tích Decartes của các tập hợp
3.2. Các nguyên lý đếm
3
3.2.1. Phép đếm
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
TÊN CHƢƠNG MỤC
3.2.2. Nguyên lý cộng
KT
3.2.3. Nguyên lý nhân
3.2.4. Nguyên lý bù trừ
3.2.5. Nguyên lý Dirichlet
Chƣơng 4. Quan hệ
1
7
7
4.1. Quan hệ hai ngôi
1
4.1.1. Định nghĩa quan hệ và ví dụ
4.1.2. Các tính chất của quan hệ
4.1.3. Biểu diễn quan hệ
4.2. Quan hệ tương đương
4.2.1. Khái niệm quan hệ tương đương
4.2.2. Lớp tương đương và tập hợp tương đương
4.3. Quan hệ thứ tự
2
3
4.3.1. Các định nghĩa
4.3.2. Biểu diễn quan hệ thứ tự
4.3.3. Tập hữu hạn có thứ tự
4.3.4. Sắp xếp topo
4.4. Dàn (lattice - tập bị chặn)
Chƣơng 5. Đại số Bool
1
10
2
11
0
0
1
5.1. Các phép toán
5.1.1. Các định nghĩa
5.1.2. Các tính chất của phép toán hai ngôi
5.2. Đại số Bool
2
5.2.1. Định nghĩa và các tính chất
5.2.2. Đại số Bool và dàn
5.3. Các cổng logic và tổ hợp các cổng logic
5.4. Cực tiểu hoá các mạch logic
2
4
1
Nhiệm vụ của sinh viên :
Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao,
tham dự các bài kiểm tra định kỳ và cuối kỳ.
Tài liệu học tập :
-
Kenneth Rosen, Toán học rời rạc và ứng dụng trong tin học, NXB KHKT Hà nội,
1998.
-
Nguyễn Tô Thành và Nguyễn Đức Nghĩa, Giáo trình toán học rời rạc, ĐHBK Hà
nội, 1994.
-
-
Phan Đình Diệu, Lý thuyết Ôtômát hữu hạn và thuật toán, NXB ĐHTHCN, 1977.
Vương Tất Đạt, Lôgic học đại cương, NXB Đại học quốc gia HN, 2002
Hình thức và tiêu chuẩn đánh giá sinh viên:
-
-
Hình thức thi cuối kỳ : Thi viết.
Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trường và của Bộ
Thang điểm: Thang điểm chữ A, B, C, D, F
Điểm đánh giá học phần: Z = 0,2X + 0,8Y.
CHƢƠNG 1
ĐẠI CƢƠNG VỀ LOGIC
1.1. Phép tính mệnh đề
1.1.1. Khái niệm về 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 trong chương nầy 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 đề. Ðó là 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. Tính chất cốt yếu 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 thường 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.
Ví dụ 1: Các phát biểu sau đây là các mệnh đề (toán học).
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. Nói cách khác chận trị
của các mệnh đề nầy là đúng. Các mệnh đề 1, 5 là những mệnh đề sai.
Ví dụ 2 : 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.
Trong việc khảo sát các mệnh đề, người ta còn phân ra làm hai loại: mệnh đề sơ cấp
(elementary), mệnh đề phức hợp (compound). Mệnh đề sơ cấp là các "nguyên tử" theo nghĩa
là nó không thể được phân tích thành một hay nhiều (từ hai trở lên) mệnh đề thành phần đơn
giản hơn. Còn mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác
1
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ụ : Xét các mệnh đề sau đây.
p = "15 chia hết cho 3".
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à".
1.1.2. Các phép toán trên mệnh đề
Ðiều mà chúng ta quan tâm ở đây không phải là xác định tính đúng hoặc sai của một
mệnh đề sơ cấp. Bởi vì những mệnh đề nầy thường là những phát biểu nói lên một ý tưởng
nào đó trong một phạm vi chuyên môn nhất định. Vấn đề mà ta quan tâm ở đây là 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 ở đây 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".
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ị chỉ
ra rõ ràng 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ủa các phép toán logic tất nhiên là phản
ánh ngữ nghĩa tự nhiên của các từ liên kết tương ứng. Về mặt tự nhiên của ngôn ngữ, trong
nhiều trường hợp c ng một từ nhưng có thể có nghĩa khác nhau trong những ngữ cảnh khác
nhau. Do đó, bảng chân trị không thể diễn đạt mọi nghĩa có thể có của từ tương ứng với ký
hiệu phép toán. Ðiều nầy cho thấy rằng đại số logic là rõ ràng hoàn chỉnh theo nghĩa là nó cho
ta một hệ thống logic đáng tin cậy. Ðại số logic còn đặc biệt quan trọng trong việc thiết kế
mạch cho máy tính.
Bảng chân trị không chỉ dùng để kê ra sự liên hệ chân trị giữa mệnh đề phức hợp với chân trị
của các mệnh đề sơ cấp cấu thành nó, mà bảng chân trị còn được dùng với mục đích rộng
hơn: 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.
1.1.2.1. Phép phủ định
Cho p là một mệnh đề, chúng ta dùng 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
0
1
p
1
0
2
Ký hiệu được đọc là "không" . Trong một số sách khác, người ta còn dùng các ký hiệu sau
đây để chỉ mệnh đề phủ định của một mệnh đề p: ~p,
p
Trong cột thứ nhất của bảng chân trị, ta liệt kê đầy đủ các trường hợp chân trị có thể có của
mệnh đề p. Ở cột thứ hai kê ra chân trị tương ứng của mệnh đề p theo từng trường hợp chân
trị của mệnh đề p. Ðịnh nghĩa nầy ph hợp với ngữ nghĩa tự nhiên của sự phủ định : 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).
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.
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):
p
0
1
p
1
( p)
0
1
0
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, vì điều nầy không có gì gây ra sự nhầm lẫn.
1.1.2.2. Phép hội
Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề "p hội 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
0
0
1
1
q
0
1
0
1
p q
0
0
0
1
Chân trị của mệnh đề p q phụ thuộc vào các chân trị của 2 mệnh đề p, q. Ta có 4 trường hợp
chân trị của p q ứng với 4 trường hợp chân trị của cặp mệnh đề (p,q) là (0,0), (0,1), (1,0),
(1,1). Trong 4 trường hợp chỉ có một trường hợp mệnh đề p q đúng, đó là trường hợp p
đúng và q đúng.
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 đề
3
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 L q sai, tức là có chân trị bằng 0, vì p = 1 và q = 0),
p r = 1 (p L r đúng, tức là có chân trị bằng 1, vì p = 1 và r = 1).
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).
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.
1.1.2.3. 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
0
0
1
1
q
0
1
0
1
p q
0
1
1
1
Chân trị của mệnh đề p q phụ thuộc vào các chân trị của 2 mệ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.
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 r = 1.
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
p
p
p p
4
0
1
0
1
1
1
ta có mệnh đề p p luôn luôn đúng.
2. Người ta còn sử dụng phép "hoặc" trong việc liên kết các mệnh đề. Cho p và q là hai
mệnh đề. Ta ký hiệu mệnh đề "p hoặc q" là p q. Phép "hoặc", ký hiệu là , được định
nghĩa bởi bảng chân trị sau đây:
p
q
p
q
0
0
1
1
0
1
0
1
0
1
1
0
Phép "hoặc" còn được gọi là "hay loại trừ". Chân trị của mệnh đề p q phụ thuộc vào
các chân trị của 2 mệnh đề p, q : mệnh đề p q đúng khi trong 2 mệnh đề p và q có một mệnh
đề đúng, một mệnh đề sai.
1.1.2.4. 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ết p 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
0
0
1
1
q
0
1
0
1
p q
1
1
0
1
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 la` điều kiện đủ cho q".
"q la` điều kiện cần cho p".
1.1.2.5. Phép kéo theo hai chiều
5
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
0
0
1
1
q
0
1
0
1
p q
1
0
0
1
Mệnh đề p q, được đọc là "p nếu và chỉ nếu q", còn được phát biểu dưới các dạng khác
sau đây:
"p khi và chỉ khi q".
"p la` điều kiện cần va` đủ cho q".
Mệnh đề p q có chân trị đúng (=1) trong các trường hợp p và q có c ng chân trị.
1.1.2.6. Ðộ ưu tiên của các toán tử logic.
Tương tự như đối với các phép toán số học, để tránh phải dùng nhiều dấu ngoặc trong các
biểu thức logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. Ở trên ta có 5 toán tử logic:
(không) , (và), (hay), (kéo theo), (tương đương)
ưu tiên mức 1 (cao nhất)
ưu tiên mức 2 (thấp hơn)
,
, ưu tiên mức 3 (thấp nhất)
trong đó, các toán tử liệt kê trên c ng dòng có c ng độ ưu tiên.
Ví dụ :
1. p q có nghĩa là (( p) q).
2. p q r s có nghĩa là ((( p) q) (r s)).
3. p q r là nhập nhằng. Cần phải dùng các dấu ngoặc để chỉ rõ nghĩa.
1.2. Biểu thức logic
1.2.1. Định nghĩa và bảng chân trị của biểu thức logic
Trong đại số ta có các biểu thức đại số được xây dựng từ các hằng số, các biến và các phép
toán. Khi thay thế các biến trong một biểu thức đại số bởi các hằng số thì kết quả thực hiện
6
các phép toán trong biểu thức sẽ là một hằng số. Trong phép tính mệnh đề ta cũng có các biểu
thức logic được xây dựng từ :
Các mệnh đề hay các giá trị hằng.
Các biến mệnh đề.
Các phép toán logic, và cả các dấu ngoặc "( )" để chỉ rõ thứ tự thực hiện của các phép toán.
Giả sử E, F là 2 biểu thức logic, khi ấy E, E F, E F, E F cũng là các biểu thức logic.
Ví dụ: Biểu diễn E(p, q, r) = ((( p) q) (r s)) là một biểu thức logic trong đó p, q, r là
các biến mệnh đề.
Bảng chân trị
Bảng chân trị của một biểu thức logic là bảng liệt kê chân trị của biểu thức logic theo các
trường hợp về chân trị của tất cả các biến mệnh đề trong biểu thức logic hay theo các bộ giá
trị của bộ biến mệnh đề. Với một biến mệnh đề, ta có 2 trường hợp là 0 (sai) hoặc 1 (đúng).
Với 2 biến mệnh đề p, q ta 4 trường hợp chân trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1),
(1,0), và (1,1). Trong trường hợp tổng quát, với n biến mệnh đề thì ta có 2n trường hợp chân
trị cho bộ n biến đó.
Ví dụ 1: Bảng chân trị của các biểu thức logic p q và p q theo các biến mệnh đề p,q
như sau:
p
0
0
1
1
q
0
1
0
1
p q
p
1
p q
1
1
0
1
1
1
0
1
1
0
0
Ví dụ 2: Bảng chân trị của các biểu thức logic p ( q r) theo các biến mệnh đề p, q, r
như sau:
Thứ tự
p
0
0
0
0
1
1
1
q
0
0
1
1
0
0
1
r
q r
p ( q r)
1
2
3
4
5
6
7
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
7
Thứ tự
p
1
q
1
r
q r
p ( q r)
8
1
1
1
1.2.2. Sự tƣơng đƣơng logic
Hai biểu thức logic E và F theo các biến mệnh đề nào đó được gọi là tương đương logic khi E
và F luôn luôn có c ng chân trị trong mọi trường hợp chân trị của bộ biến mệnh đề.
Khi đó ta viết: E F
đọc là "E tương đương với F".
Như vậy, theo định nghĩa ta có thể kiểm tra xem 2 biểu thức logic có tương đương hay
không bằng cách lập bảng chân trị của các biểu thức logic.
Ví dụ: từ bảng chân trị của các biểu thức logic p q và p q theo các biến mệnh đề p,
q ta có:( p q ) <=> ( p q )
1.2.3. Giá trị của biểu thức logic
Một biểu thức logic được tạo thành từ các biến logic kết hợp với phép toán logic, bởi
vậy nên giá trị biểu thức logic cũng chỉ nhận 1 trong 2 giá trị là “đúng” (true hoặc 1) hay “sai”
(false hoặc 0) t y thuộc vào giá trị của các biến logic và quy luật của các phép toán.
Ví dụ: Xét biểu thức logic ( p q ), nếu thay p = 1 và q = 0 ta có:
1 0 = 0 0 = 0
1.3. Các luật logic
Các luật logic là cơ sở để ta thực hiện các biến đổi trên một biểu thức logic để có được một
biểu thức logic mới tương đương logic với biểu thức logic có trước. Mỗi biểu thức logic cho
ta một sự khẳng định về sự tương đương của 2 biểu thức logic. Ta sẽ sử dụng các qui tắc thay
thế và các luật logic đã biết để thực hiện các phép biến đổi tương đương trên các biêu thức
logic.
Dưới đây, chúng ta sẽ liệt kê ra một số luật logic thường được sử dụng trong lập luận và
chứng minh. Các luật nầy có thể được suy ra trực tiếp từ các bảng chân trị của các biểu thức
logic.
1.3.1. Các luật logic
Các luật về phép phủ định
p p (luật phủ định của phủ định)
1 0
0 1
Luật giao hoán
8
p q q p
p q q p
Luật kết hợp
p (q r) (p q) r
p (q r) (p q) r
Luật phân bố
p (q r) (p q) (p r)
p (q r) (p q) (p r)
Luật De Morgan
(p q) p q
(p q) p q
Luật về phần tử bù
p p 1
p p 0
Luật kéo theo
p q p q
Luật tương đương
p q (p q) (q p)
Các luật đơn giản của phép tuyển
p p p (tính lũy đẳng của phép tuyển)
p 1 1 (luật này còn được gọi là luật thống trị)
p 0 p (luật này còn được gọi là luật trung hòa)
p (p q) p (luật này còn được gọi là luật hấp thụ)
Các luật đơn giản của phép hội
p p p (tính lũy đẳng của phép hội)
p 1 p (luật này còn được gọi là luật trung hòa)
9
p 0 0 (luật này còn được gọi là luật thống trị)
p (p q) p (luật này còn được gọi là luật hấp thụ)
Một số luật trong các luật trình bày ở trên có thể được suy ra từ các luật khác. Chúng ta
có thể tìm ra được một tập hợp luật logic tối thiểu mà từ đó ta có thể suy ra tất cả các luật
logic khác, nhưng điều nầy không quan trọng lắm đối với chúng ta. Những luật trên được
chọn lựa để làm cơ sở cho chúng ta thực hiện các biến đổi logic, suy luận và chứng minh. Tất
nhiên là còn nhiều luật logic khác mà ta không liệt kê ra ở đây.
phép toán tuyển . Do tính chất nầy, ta có thể viết các biểu thức logic hội và các biểu thức
tuyển dưới các dạng sau:
E1 E2 … Em
E1 E2 … Em
và việc tính toán chân trị có thể được thực hiện dựa trên một sự phân bố các cặp dấu ngoặc
vào biểu thức một cách t y ý để xác định một trình tự thực hiện các phép toán.
Ví dụ: Biểu thức E1 E2 E3 E4 có thể được tính toán chân trị bởi biểu thức sau:
(E1 E2) (E3 E4)
hay có thể tính toán theo biểu thức:
E1 ((E2 E3 ) E4)
1.3.2. Các quy tắc thay thế
Dưới đây là các qui tắc để cho ta có thể suy ra những biểu thức logic mới hay tìm ra các
biểu thức logic tương đương với một biểu thức logic cho trước.
Qui tắc 1
Trong một biểu thức logic E, nếu ta thay thế một biểu thức con bởi một biểu thức logic tương
đương với biểu thức con đó thì ta sẽ được một biểu thức mới E' tương đương với biểu thức E.
Ví dụ: Cho biểu thức logic E = q p. Thay thế q trong biểu thức E bởi biểu thức q
(tương đương với q) ta được một biểu thức mới E' = q p. Theo qui tắc thay thế 1 ta
có:
q p q p
Qui tắc 2
Giả sử biểu thức logic E là một hằng đúng. Nếu ta thay thế một biến mệnh đề p bởi một biểu
thức logic tuỳ ý thì ta sẽ được một biểu thức logic mới E' cũng là một hằng đúng.
10
Ví dụ: Ta có biểu thức E(p,q) = (p q) ( p q) là một hằng đúng. Thay thế biến q
trong biểu thức E bởi biểu thức q r ta được biểu thức logic mới:
E'(p,q,r) = (p (q r)) ( p (q r))
Theo qui tắc thay thế 2 ta có biểu thức E'(p,q,r) cũng là một hằng đúng.
1.3.3. Ví dụ áp dụng
Ví dụ 1: Chứng minh rằng (p q) ( q p).
Chứng minh :
(p q) p q (luật kéo theo)
q p (luật giao hoán)
q p (luật phủ định)
q p (luật kéo theo)
Ví dụ 2: Chứng minh rằng biểu thức
((p q) p) q
là một hằng đúng.
Chứng minh.
((p q) p) q
((p q) p) q (luật kéo theo)
( (p q) p) q (luật De Morgan)
(p q) ( p q) (luật kết hợp)
(p q) (p q) (luật kéo theo)
1 (luật về phần tử bù)
Vậy biểu thức ((p q) p) q là hằng đúng.
Ví dụ 3: Chứng minh rằng biểu thức
p q p
là một hằng đúng.
Chứng minh.
11
p q p ( p q) p (luật kéo theo)
( p q) p (luật De Morgan)
( q p) p (luật giao hoán)
q ( p p) (luật kết hợp)
q 1 (luật về phần tử bù)
1 (luật đơn giản)
Vậy mệnh đề p q p là hằng đúng.
Ví dụ 4: Chứng minh rằng biểu thức
p pq
là một mệnh đề hằng đúng.
Chứng minh.
p pq p (p q) (luật kéo theo)
( p p) q (luật kết hợp)
1 q (luật về phần tử bù)
1 (luật đơn giản)
Vậy mệnh đề p pq là hằng đúng.
Nhận xét: Các ví dụ trên cho ta thấy một quan hệ khác giữa các mệnh đề phức hợp hay các
mệnh đề : quan hệ "suy ra". Khi mệnh đề p q là hằng đúng, ta nói rằng p suy ra q (về mặt
logic). Chúng ta sẽ dùng ký hiệu để chỉ quan hệ "suy ra". Quan hệ suy ra nầy có tính
truyền (hay bắc cầu), nhưng không có tính chất đối xứng.
1.4. Các dạng chuẩn tắc
Dạng chuẩn tắc (chính tắc) của 1 biểu thức 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 đề.
1.4.1. Chuẩn tắc tuyển
Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2,
… , pn được gọi là một biểu thức hội cơ bản (hội sơ cấp) nếu nó có dạng sau:
F = q1 q2 … qn
với qj = pj hoặc qj = pj (j = 1, … , n).
12
Tải về để xem bản đầy đủ
111 trang
04/05/2022
4860
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_truong_dai_hoc_hang_hai.pdf
