tailieunhanh - Giáo trình Toán rời rạc - GS. Nguyễn Hữu Anh

Giáo trình Toán rời rạc do GS. Nguyễn Hữu Anh biên soạn, cung cấp cho người học những kiến thức như: cơ sở logic; phương pháp đếm; quan hệ; đại số bool và hàm bool. Mời các bạn cùng tham khảo! | HỮU ANH TOAÙN RÔØI RAÏC NHÀ XUẤT BẢN LAO ĐỘNG XÃ HỘI MỤC LỤC CHƯƠNG 1 CƠ SỞ LOGIC . 4 1 PHÁP TÍNH MỆNH ĐỀ . 4 2 DẠNG MỆNH ĐỀ . 7 3 QUY TẮC SUY DIỄN .12 4 VỊ TỪ VÀ LƯỢNG TỪ .18 5 NGUYÊN LÝ QUY NẠP .23 BÀI TẬP CHƯƠNG 1 .25 CHƯƠNG 2 PHƯƠNG PHÁP 1 TẬP HỢP .36 2 ÁNH XẠ .38 3 PHÉP ĐẾM .40 4 GIẢI TÍCH TỔ HỢP .45 5 NGUYÊN LÝ CHUỒNG BỒ CÂU .48 BÀI TẬP CHƯƠNG 2 .50 CHƯƠNG 3 QUAN 1 QUAN HỆ .57 2 QUAN HỆ TƯƠNG ĐƯƠNG .60 3 THỨ TỰ .62 4 DÀN .66 5 DÀN 2 .69 6 DÀN .70 BÀI TẬP CHƯƠNG 3 .76 CHƯƠNG 4 ĐẠI SỐ BOOL VÀ HÀM BOOL .83 1 ĐẠI SỐ BOOL .83 2 HÀM BOOL .88 3 MẠNG CÁC CỔNG VÀ CÔNG THỨC ĐA THỨC TỐI TIỂU .92 4 PHƯƠNG PHÁP BIỂU ĐỒ KARNAUGH .96 5 PHƯƠNG PHÁP THỎA THUẬN. 104 BÀI TẬP CHƯƠNG 4 . 110 GIẢI ĐÁP MỘT SỐ BÀI TẬP . 114 GS. Nguyễn Hữu Anh 2 GS. Nguyễn Hữu Anh 3 CHƯƠNG 1 CƠ SỞ LOGIC 1 PHÁP TÍNH MỆNH ĐỀ Trong toán học ta quan tâm đến những mệnh đề có giá trị hân lý xác định đúng hoặc sai nhưng không thể vừa đúng vừa sai . Các khẳng định như vậy được gọi là mệnh đề. Các mệnh đề đúng được nói là có giá trị chân lý đúng hay chân trị đúng các mệnh đề sai được nói là có chân trị sai. Ví dụ 1. Các khẳng định sau là mệnh đề Môn Toán rời rạc là môn bắt buộc cho ngành Tin học. 1 1 2. 4 là số nguyên tố. Hai mệnh đề đầu có chân trị 1 mệnh đề thứ ba có chân trị 0. 2. Các khẳng định dưới dạng tán than hoặc mệnh lệnh không phải mệnh đề vì nó không có chân trị xác định. 3. Khẳng định là số nguyên tố không phải mệnh đề. Tuy nhiên nếu thay n bằng một số nguyên cố định thì ta sẽ có một mệnh đề chẳng hạn với 3 ta có một mệnh đề đúng trong khi với 4 ta có một mệnh đề sai. Khẳng định này được gọi là một vị từ và cũng là đối tượn khảo sát của logic. Ta thường ký hiệu các mệnh đề bởi các chữ và chân trị đúng sai được ký hiệu bởi 1 0 . Đôi khi ta còn dùng các ký hiệu để chỉ chân trị đúng và dể chỉ chân trị sai. Phân tích kỹ các ví dụ ta thấy các mệnh đề được chia ra làm 2 loại Các mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết chúng lại bằng các liên từ và hay nếu thì hoặc