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!
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc - GS. Nguyễn Hữu Anh GS.NGUYỄN HỮU ANH TOAÙNRÔØI RAÏC NHÀ XUẤT BẢN LAO ĐỘNG XÃ HỘI MỤC LỤCCHƯƠ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 .......................................................................................25CHƯƠNG 2: PHƯƠNG PHÁP ĐẾM......................................................................36 §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 .......................................................................................50CHƯƠNG 3: QUAN HỆ......................................................................................57 §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 .......................................................................................76CHƯƠ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 ..................................................................................... 110GIẢI ĐÁP MỘT SỐ BÀI TẬP .............................................................................. 114GS. Nguyễn Hữu Anh 2GS. Nguyễn Hữu Anh 3CHƯƠ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 (đúnghoặ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 trạng từ “khô ...