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. | 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 Email thodx@ Website http 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à .
