Xem mẫu
- TOÁN RỜI RẠC
(DISCRETE MATHEMATICS)
Bùi Thị Thủy
Đặng Xuân Thọ
- Support
2
TS. Đặng Xuân Thọ
Mobile: 091.2629.383
Email: thodx@hnue.edu.vn
Website: http://fit.hnue.edu.vn/~thodx/
Toán rời rạc - ĐHSPHN
- NỘI DUNG
3
Chương 1. Logic mệnh đề
Chương 2. Lý thuyết tập hợp
Chương 3. Một số công thức tổ hợp
Chương 4. Suy luận và kiểm chứng chương trình
Chương 5. Đại số Boole và cấu trúc mạch logic
Chương 6. Thuật toán
Chương 7. Lý thuyết đồ thị
Toán Rời Rạc - ĐHSPHN
- Chương 4. Suy luận và kiểm chứng
chương trình
4
Điều cần nhất cho người học CNTT là tư duy
chính xác phải được hình thành ngay từ đầu.
Mục tiêu của chương là cung cấp
Những suy luận đúng đắn
Những công cụ xây dựng nên các suy luận đó
Làm thế nào để kiếm chứng 1 chương trình
máy tính?
Thử với dữ liệu có sẵn?
Tính đúng đắn chỉ có thể bảo đảm được bằng
chứng minh nó luôn tạo ra kết quả đúng.
Toán Rời Rạc - ĐHSPHN
- 5 Các quy tắc suy luận
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
6
Suy diễn trực tiếp
Ví dụ:
p: “Trời mưa”; q: “Chúng ta không đi làm”
𝑝 → 𝑞: “Nếu trời mưa thì chúng ta không đi làm”
Nếu p xảy ra, và nếu suy diễn này là đúng thì q
xảy ra
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
7
Luật cộng
Ví dụ:
p: “Bây giờ trời đang mưa”; q: ”Trời tối”
Luật cộng có thể nói: “Bây giờ trời đang mưa
hoặc trời tối”.
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
8
Luật rút gọn
Ví dụ:
p ^ q: “Bây giờ trời đang mưa và trời tối”
Thì ta có thể suy ra: “Bây giờ trời đang mưa”
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
9
Luật gián tiếp
Ví dụ:
p: “Trời mưa”; q: “Trời sấm chớp”
Như vậy nếu mệnh đề “Trời mưa thì trời sấm
chớp” là đúng và không có “Trời sấm chớp” thì
suy ra không có “Trời mưa”.
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
10
Tam đoạn luận
Ví dụ:
p: “Trời mưa”; q: “Chúng ta không đi chơi ngoài
trời hôm nay”; r: “Chúng ta đi chơi ngoài trời ngày
mai”
Như vậy chúng ta suy ra là “Trời mưa hôm nay
thì chúng ta đi chơi ngoài trời ngày mai”.
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
11
Luật loại trừ
Ví dụ:
p: “Tôi có mặt tại hiện trường vụ án”; q: “Anh có
mặt tại hiện trường vụ án”.
Nếu (p v q) và p là đúng thì suy ra “Anh có mặt
tại hiện trường vụ án”.
Toán Rời Rạc - ĐHSPHN
- Các suy diễn có cơ sở
12
- Các suy diễn có cơ sở
13
- Luyện tập
14
Quy tắc suy diễn nào được sử dụng trong các lập luận sau:
1. Ai học giỏi môn Toán cũng sẽ học giỏi môn Toán hoặc môn
Tin.
2. Nêu bạn giỏi cả hai môn Toán và Văn thì bạn học giỏi môn
Toán.
3. Nếu trời mưa thì trận bóng đá sẽ bị hoãn lại. Hôm nay trời
mưa thật, thế thì trận bóng đá chắc chắn sẽ bị hoãn lại rồi.
4. Nếu hôm nay trời mưa thì trận đá bóng sẽ bị hoãn lại. Trận
bóng đá đã diễn ra, do vậy hôm nay trời không mưa.
5. Nếu bạn bơi lâu dưới nắng thì da bạn sẽ bị rám nắng. Da bạn
bị rám nắng thì trông thật là đen. Vậy nếu bạn bơi lâu dứoi
nắng thì trông bạn thật đen.
6. Nếu bạn làm bài tập thật chăm chỉ thì bạn có thể nắm vững
giáo trình này. Nếu bạn nắm vững giáo trình thì bạn sẽ thi đỗ
kỳ thi tốt nghiệp. Vậy nếu bạn làm bài tập thật chăm chỉ thì bạn
sẽ thi đỗ kỳ thi tốt nghiệp.
Toán Rời Rạc - ĐHSPHN
- 15 Vị ngữ, lượng từ, định lý
Toán Rời Rạc - ĐHSPHN
- Biến và vị ngữ
16
Ví dụ:
“x là số nguyên”
“x thuộc đoạn [0, 1]”
Biến là chủ ngữ, khẳng định tính chất của x là
vị ngữ.
Sau đây ta sẽ xét câu có dạng P(x), mệnh đề
của x, tức là câu nói mà giá trị chân lý của nó
phụ thuộc vào biến x.
Ví dụ: x = 3
Toán Rời Rạc - ĐHSPHN
- Lượng từ với mọi
17
Định nghĩa: Cho trước một hàm mệnh đề P(x)
xác định trên một tập X. Khi đó câu “P(x) đúng
cho mọi giá trị x X” là một mệnh đề, kí hiệu
x P(x). Mệnh đề này gọi là lượng từ với mọi
của hàm mệnh đề P(x) cho trước.
Ví dụ:
P(x): “x tốt nghiệp”; x là biến “sinh viên”; X là miền
“sinh viên khóa 53”
xP(x):“mọi sinh viên khóa 53 đều đã tốt nghiệp”
Toán Rời Rạc - ĐHSPHN
- Lượng từ với mọi
18
Chú ý:
Lượng tử với mọi sai nếu có ít nhất một giá trị
của biến làm hàm mệnh đề sai.
Nếu miền xác định của P(x) có n phần tử (1, 2,
…, n) thì xP(x) P(1) P(2) … P(n)
Toán Rời Rạc - ĐHSPHN
- Lượng từ tồn tại
19
Định nghĩa: Cho trước một hàm mệnh đề P(x)
xác định trên một tập X. Khi đó câu “tồn tại x
X sao cho P(x) đúng” là một mệnh đề, kí hiệu
x P(x). Mệnh đề này gọi là lượng từ tồn tại
của hàm mệnh đề P(x) cho trước.
Ví dụ:
Cho P(x): “x2 + 1 = 0” trên miền số thực
xP(x): “tồn tại x sao cho x2 + 1 = 0” có giá trị F
Toán Rời Rạc - ĐHSPHN
- Lượng từ tồn tại
20
Chú ý:
Lượng tử tồn tại chỉ sai khi mọi giá trị của biến
đều làm hàm mệnh đề bị sai.
Nếu miền xác định của P(x) có n phần tử (1, 2,
…, n) thì xP(x) P(1) P(2) … P(n)
Toán Rời Rạc - ĐHSPHN
nguon tai.lieu . vn
