Bài giảng Toán rời rạc: Chương 4 - TS. Đặng Xuân Thọ

Chia sẻ: Elysale Elysale | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

48
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Chương 4 Suy luận và kiểm chứng chương trình cung cấp cho người học những kiến thức như: Đ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; Làm thế nào để kiếm chứng 1 chương trình máy tính.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 4 - TS. Đặng Xuân Thọ

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