Giáo Trình Toán Rời Rạc - TS. Võ Văn Tuẫn Dũng

Khám phá giáo trình Toán rời rạc với các khái niệm cơ bản, bài tập và ứng dụng thực tiễn trong lĩnh vực khoa học máy tính và toán học.

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Toán Rời Rạc
• Đề tài: Giáo Trình Toán Rời Rạc cho Sinh Viên Công Nghệ Thông Tin
• Loại tài liệu: Giáo Trình

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: CƠ SỞ LOGIC
• 1.1. Khái niệm về mệnh đề
• 1.1.1. Phân loại mệnh đề
• 1.1.2. Các phép toán logic
• 1.1.2.1. Phép phủ định
• 1.1.2.2. Phép hội
• 1.1.2.3. Phép tuyển
• 1.1.2.4. Phép kéo theo
• 1.1.2.5. Phép tương đương
• 1.1.2.6. Độ ưu tiên của các phép toán
• 1.2. Dạng mệnh đề
• 1.2.1. Các định nghĩa
• 1.2.2. Các qui tắc thay thế
• 1.2.3. Các qui luật logic
• 1.3. Qui tắc suy diễn
• 1.3.1. Suy luận và qui tắc suy diễn
• 1.3.2. Một số qui tắc suy diễn
• 1.3.2.1. Qui tắc Modus Ponens (phương pháp khẳng định)
• 1.3.2.2. Qui tắc Modus Tollens (phương pháp phủ định)
• 1.3.2.3. Tam đoạn luận (Syllogism)
• 1.3.2.4. Qui tắc mâu thuẫn (chứng minh bằng phản chứng)
• 1.4. Vị từ và lượng từ
• 1.4.1. Vị từ
• 1.4.2. Lượng từ
• 1.4.2.1. Các lượng từ 2 biến

Tóm tắt

I. Tổng Quan Giáo Trình Toán Rời Rạc Cho Sinh Viên CNTT

Giáo trình Toán rời rạc là môn học nền tảng, có vai trò cốt lõi trong chương trình đào tạo kỹ sư Công nghệ Thông tin (CNTT). Môn học này cung cấp khối kiến thức tối thiểu về cơ sở Toán cho Tin học, giúp sinh viên có nền tảng vững chắc để tiếp thu các môn chuyên ngành phức tạp hơn. Nội dung của Toán rời rạc cho sinh viên CNTT không chỉ là lý thuyết suông mà còn là công cụ tư duy sắc bén, giúp hình thành khả năng phân tích, mô hình hóa và giải quyết vấn đề một cách logic. Theo tài liệu của TS. Võ Văn Tuấn Dũng, giáo trình được biên soạn dựa trên kinh nghiệm giảng dạy nhiều năm, sắp xếp nội dung một cách tinh giản và hợp lý. Mục tiêu chính là trang bị cho sinh viên các khái niệm cơ bản về logic học, lý thuyết đếm, thuật toán, lý thuyết quan hệ và đại số Boole. Các kiến thức này là tiền đề quan trọng cho việc nghiên cứu và phát triển trong các lĩnh vực như cấu trúc dữ liệu, giải thuật, trí tuệ nhân tạo, và an toàn thông tin. Việc nắm vững các nguyên tắc trong giáo trình toán rời rạc giúp sinh viên xây dựng tư duy thuật toán, hiểu rõ bản chất của các cấu trúc dữ liệu và cách máy tính xử lý thông tin. Đây là kỹ năng không thể thiếu đối với bất kỳ lập trình viên hay kỹ sư phần mềm chuyên nghiệp nào. Hiểu đúng và đủ về môn học này là bước khởi đầu vững chắc trên con đường chinh phục ngành Công nghệ Thông tin.

1.1. Vai trò của toán học rời rạc trong ngành tin học

Toán học rời rạc đóng vai trò là ngôn ngữ và công cụ cơ bản của khoa học máy tính. Các đối tượng trong tin học, như bit, byte, cấu trúc dữ liệu (cây, đồ thị), và các bước thực thi của một thuật toán, đều có bản chất rời rạc. Do đó, việc nghiên cứu các cấu trúc rời rạc là cực kỳ cần thiết. Môn học này cung cấp nền tảng cơ sở logic để xây dựng các mệnh đề, thực hiện suy luận và chứng minh tính đúng đắn của chương trình. Bên cạnh đó, các phương pháp chứng minh toán học như quy nạp, phản chứng giúp rèn luyện tư duy phản biện và khả năng giải quyết vấn đề một cách có hệ thống. Kiến thức về giải tích tổ hợp và phép đếm là cơ sở để phân tích độ phức tạp của thuật toán, một kỹ năng sống còn trong việc tối ưu hiệu năng phần mềm. Hơn nữa, lý thuyết đồ thị, một phần quan trọng của toán rời rạc, có ứng dụng sâu rộng trong mạng máy tính, mạng xã hội, và logistics.

1.2. Cấu trúc cốt lõi của giáo trình TS. Võ Văn Tuấn Dũng

Giáo trình của TS. Võ Văn Tuấn Dũng được cấu trúc thành 5 chương chính, bao quát các khía cạnh quan trọng nhất của Toán rời rạc. Chương 1 tập trung vào Cơ sở logic, trình bày về mệnh đề, các quy tắc suy diễn, vị từ và lượng từ. Chương 2 đi sâu vào Phép đếm và giải tích tổ hợp, giới thiệu các nguyên lý đếm cơ bản và nguyên lý Dirichlet. Chương 3 giới thiệu khái niệm thuật toán và phân tích độ phức tạp của thuật toán. Chương 4 trình bày về khái niệm quan hệ, bao gồm quan hệ tương đương, quan hệ thứ tự và biểu đồ Hasse. Cuối cùng, Chương 5 tập trung vào hàm Boole, đại số Boole và các phương pháp tối thiểu hóa hàm, là kiến thức nền tảng cho thiết kế mạch logic. Cấu trúc này giúp sinh viên tiếp cận kiến thức một cách tuần tự, từ các khái niệm cơ bản đến các ứng dụng phức tạp hơn trong ngành Công nghệ Thông tin.

II. Các Thách Thức Khi Học Toán Rời Rạc Cho Người Mới Bắt Đầu

Mặc dù có vai trò quan trọng, Toán rời rạc thường được xem là một môn học đầy thách thức đối với sinh viên năm nhất, đặc biệt là những người chưa quen với tư duy toán học trừu tượng. Một trong những khó khăn lớn nhất là việc phải chuyển đổi từ lối tư duy tính toán liên tục (như giải tích) sang tư duy trên các cấu trúc rời rạc. Các khái niệm như mệnh đề, vị từ, và các quy tắc suy diễn đòi hỏi sự chính xác tuyệt đối trong lập luận, khác biệt với sự ước lượng trong nhiều lĩnh vực khác. Sinh viên thường gặp khó khăn trong việc xây dựng các phương pháp chứng minh toán học một cách chặt chẽ. Việc áp dụng các quy tắc logic để chứng minh một định lý hay tính đúng đắn của một thuật toán không phải là một kỹ năng dễ dàng hình thành. Thêm vào đó, khối lượng kiến thức trong giáo trình toán rời rạc khá lớn, bao gồm nhiều chủ đề đa dạng từ logic, tổ hợp đến lý thuyết đồ thị và đại số Boole. Sự đa dạng này đòi hỏi sinh viên phải có khả năng tổng hợp và liên kết kiến thức từ nhiều chương khác nhau để giải quyết một bài toán tổng thể. Nếu không có phương pháp học tập đúng đắn, sinh viên rất dễ bị choáng ngợp và mất phương hướng, dẫn đến kết quả học tập không như mong đợi và không thấy được sự kết nối giữa lý thuyết và thực tiễn ngành Công nghệ Thông tin.

2.1. Khó khăn với các khái niệm logic và chứng minh trừu tượng

Phần cơ sở logic thường là rào cản đầu tiên. Các khái niệm như phép kéo theo (P → Q) hay phép tương đương (P ↔ Q) có định nghĩa chặt chẽ trong toán học, đôi khi khác với cách hiểu trong ngôn ngữ tự nhiên. Ví dụ, mệnh đề "Nếu P thì Q" chỉ sai khi P đúng và Q sai, còn lại đều đúng. Điều này có thể gây nhầm lẫn ban đầu. Hơn nữa, việc xây dựng một chứng minh bằng phản chứng hay chứng minh bằng quy nạp đòi hỏi một quy trình lập luận không có lỗ hổng. Sinh viên phải học cách giả định phủ định của kết luận và dẫn dắt đến một mâu thuẫn logic, hoặc chứng minh một mệnh đề đúng với trường hợp cơ sở và sau đó chứng minh bước quy nạp. Đây là những kỹ năng tư duy trừu tượng cần thời gian để rèn luyện và làm quen.

2.2. Thử thách liên kết lý thuyết toán học với lập trình thực tế

Một thách thức lớn khác là việc nhìn thấy mối liên hệ trực tiếp giữa lý thuyết Toán rời rạc và công việc lập trình hàng ngày. Sinh viên có thể học thuộc lòng công thức tính tổ hợp, chỉnh hợp nhưng lại không biết cách áp dụng nó để giải quyết một bài toán tối ưu hóa hay sinh ra tất cả các cấu hình có thể. Tương tự, đại số Boole và các phương pháp tối thiểu hóa hàm Boole có thể có vẻ xa vời cho đến khi họ hiểu rằng đó chính là nền tảng của các cổng logic trong CPU và cách các biểu thức điều kiện (if-else, switch-case) được xử lý ở mức độ thấp. Việc bắc cầu giữa lý thuyết trừu tượng và ứng dụng thực tiễn trong tin học đòi hỏi sự hướng dẫn của giảng viên và nỗ lực tự tìm tòi, thực hành thông qua các bài tập lập trình cụ thể.

III. Hướng Dẫn Nắm Vững Cơ Sở Logic Trong Toán Rời Rạc

Để vượt qua những thách thức của Toán rời rạc, việc nắm vững nền tảng cơ sở logic là bước đi quan trọng nhất. Đây là chương đầu tiên trong hầu hết các giáo trình toán rời rạc và là chìa khóa để hiểu các phần sau. Logic học không chỉ là về đúng và sai, mà còn là về cách xây dựng các lập luận hợp lệ. Bắt đầu bằng việc hiểu rõ định nghĩa của một mệnh đề - một khẳng định có giá trị chân lý xác định. Sau đó, cần làm quen với các phép toán logic cơ bản như phép phủ định (¬), phép hội (∧), phép tuyển (∨), phép kéo theo (→) và phép tương đương (↔). Lập bảng chân trị là một công cụ hữu ích để kiểm tra tính tương đương logic giữa các dạng mệnh đề. Ví dụ, việc chứng minh (p → q) ↔ (¬p ∨ q) bằng bảng chân trị sẽ giúp củng cố sự hiểu biết sâu sắc về bản chất của phép kéo theo. Tiếp theo, cần tập trung vào các quy tắc suy diễn như Modus Ponens và Modus Tollens. Đây là những mẫu lập luận cơ bản được sử dụng liên tục trong các chứng minh toán học và trong việc kiểm tra logic của mã nguồn. Việc thực hành với nhiều ví dụ về suy luận sẽ giúp kỹ năng này trở nên tự nhiên hơn. Cuối cùng, các khái niệm về vị từ và lượng từ (với mọi ∀, tồn tại ∃) mở rộng logic mệnh đề để áp dụng cho các tập hợp đối tượng, một khái niệm rất gần với vòng lặp và câu lệnh điều kiện trong lập trình.

3.1. Tìm hiểu về mệnh đề và các phép toán logic cơ bản

Một mệnh đề là một khẳng định có thể xác định là đúng (chân trị 1) hoặc sai (chân trị 0), nhưng không thể vừa đúng vừa sai. Ví dụ, "6 là số chẵn" là một mệnh đề đúng. Từ các mệnh đề sơ cấp, các mệnh đề phức hợp được xây dựng thông qua các phép toán logic. Phép hội (P ∧ Q) chỉ đúng khi cả P và Q đều đúng. Phép tuyển (P ∨ Q) chỉ sai khi cả P và Q đều sai. Phép phủ định (¬P) đảo ngược giá trị chân lý của P. Hiểu rõ các bảng chân trị của những phép toán này là yêu cầu bắt buộc. Đây là nền tảng để xây dựng các biểu thức logic phức tạp hơn, tương tự như việc xây dựng các biểu thức điều kiện trong lập trình.

3.2. Áp dụng quy tắc suy diễn và các phương pháp chứng minh

Suy luận là quá trình rút ra kết luận từ các tiền đề cho trước. Các quy tắc suy diễn đảm bảo rằng nếu các tiền đề đúng thì kết luận cũng phải đúng. Quy tắc Modus Ponens [(p → q) ∧ p] → q là một ví dụ điển hình: "Nếu trời mưa thì đường ướt. Trời đang mưa. Vậy đường ướt." Các phương pháp chứng minh toán học chính bao gồm chứng minh trực tiếp, chứng minh bằng phản chứng, và chứng minh quy nạp. Chứng minh phản chứng đặc biệt mạnh mẽ, trong đó ta giả sử kết luận là sai và chỉ ra rằng điều đó dẫn đến mâu thuẫn với giả thiết. Nắm vững các phương pháp này không chỉ giúp giải bài tập Toán rời rạc mà còn rèn luyện tư duy logic chặt chẽ cho việc gỡ lỗi (debug) và kiểm thử phần mềm.

IV. Phương Pháp Đếm Và Giải Tích Tổ Hợp Cho Lập Trình Viên

Phép đếm và giải tích tổ hợp là một trong những phần có ứng dụng thực tiễn rõ ràng nhất của Toán rời rạc cho sinh viên CNTT. Lĩnh vực này nghiên cứu cách đếm số lượng các cấu hình hoặc đối tượng thỏa mãn một số điều kiện nhất định mà không cần liệt kê tất cả chúng. Đối với lập trình viên, kỹ năng này cực kỳ quan trọng trong việc phân tích hiệu suất và độ phức tạp của thuật toán. Hai nguyên lý cơ bản và mạnh mẽ nhất là nguyên lý cộng và nguyên lý nhân. Nguyên lý cộng được áp dụng khi một công việc có thể được thực hiện theo nhiều phương án loại trừ lẫn nhau. Nguyên lý nhân được sử dụng khi một công việc bao gồm nhiều bước thực hiện liên tiếp. Từ hai nguyên lý này, các khái niệm phức tạp hơn như hoán vị, chỉnh hợp, và tổ hợp được xây dựng. Hoán vị liên quan đến việc sắp xếp thứ tự các phần tử, trong khi tổ hợp chỉ quan tâm đến việc lựa chọn các phần tử mà không cần thứ tự. Hiểu rõ sự khác biệt giữa chúng là chìa khóa để áp dụng đúng công thức cho từng bài toán. Ngoài ra, nguyên lý bù trừ cung cấp một phương pháp để đếm các phần tử trong hợp của nhiều tập hợp, và nguyên lý Dirichlet (chuồng bồ câu) là một công cụ đơn giản nhưng hiệu quả để chứng minh sự tồn tại của một tính chất nào đó.

4.1. Nguyên lý cộng và nhân trong các bài toán đếm cơ bản

Nguyên lý cộng phát biểu rằng nếu có m₁ cách để thực hiện công việc 1 và m₂ cách để thực hiện công việc 2, và hai công việc này không thể thực hiện đồng thời, thì có m₁ + m₂ cách để chọn một trong hai công việc. Nguyên lý nhân phát biểu rằng nếu một quy trình gồm hai bước, với m₁ cách thực hiện bước 1 và m₂ cách thực hiện bước 2 sau khi bước 1 đã hoàn thành, thì có m₁ × m₂ cách để hoàn thành toàn bộ quy trình. Hầu hết các bài toán đếm phức tạp đều có thể được phân rã thành các bài toán con sử dụng hai nguyên lý này. Ví dụ, việc đếm số lượng mật khẩu hợp lệ có thể được giải quyết bằng cách áp dụng nguyên lý nhân cho từng ký tự.

4.2. Khái niệm hoán vị chỉnh hợp và tổ hợp trong giải thuật

Một hoán vị của n phần tử là một cách sắp xếp có thứ tự của n phần tử đó. Số hoán vị là Pn = n!. Một chỉnh hợp chập k từ n phần tử là một cách chọn k phần tử có thứ tự. Số chỉnh hợp là A(n, k) = n! / (n-k)!. Một tổ hợp chập k từ n phần tử là một cách chọn k phần tử không phân biệt thứ tự. Số tổ hợp là C(n, k) = n! / (k!(n-k)!). Các khái niệm này là nền tảng cho nhiều thuật toán quan trọng, chẳng hạn như các thuật toán sinh tất cả các hoán vị của một chuỗi, hay các bài toán quy hoạch động liên quan đến việc chọn một tập con tối ưu.

4.3. Ứng dụng nguyên lý Dirichlet để chứng minh sự tồn tại

Nguyên lý Dirichlet, hay nguyên lý chuồng bồ câu, là một công cụ chứng minh đơn giản nhưng đầy sức mạnh. Nguyên lý cơ bản phát biểu rằng nếu xếp n + 1 con bồ câu vào n chuồng, thì phải có ít nhất một chuồng chứa hai con bồ câu trở lên. Trong tin học, nguyên lý này được sử dụng để chứng minh sự tồn tại của các tình huống nhất định. Ví dụ, trong một hàm băm (hash function) ánh xạ một tập lớn các khóa vào một tập nhỏ hơn các chỉ số, nguyên lý Dirichlet đảm bảo rằng sự va chạm (collision) chắc chắn sẽ xảy ra. Hiểu và áp dụng nguyên lý này giúp lập trình viên lường trước được các trường hợp biên và thiết kế các giải pháp xử lý phù hợp.

V. Top Ứng Dụng Của Toán Rời Rạc Trong Công Nghệ Thông Tin

Toán rời rạc không phải là một môn lý thuyết thuần túy; nó là xương sống của rất nhiều lĩnh vực trong Công nghệ Thông tin. Các kiến thức từ giáo trình toán rời rạc được áp dụng trực tiếp để giải quyết các vấn đề thực tế, từ thiết kế phần cứng đến phát triển phần mềm và phân tích dữ liệu. Một trong những ứng dụng quan trọng nhất là làm nền tảng cho thuật toán và cấu trúc dữ liệu. Lý thuyết đồ thị, một nhánh của toán rời rạc, được sử dụng để mô hình hóa mọi thứ, từ mạng máy tính, mạng xã hội, đến bản đồ đường đi. Các thuật toán tìm đường đi ngắn nhất như Dijkstra hay thuật toán sắp xếp topo đều dựa trên lý thuyết đồ thị. Lĩnh vực cơ sở dữ liệu cũng phụ thuộc rất nhiều vào khái niệm quan hệ. Mô hình cơ sở dữ liệu quan hệ, mô hình phổ biến nhất hiện nay, được xây dựng dựa trên lý thuyết tập hợp và logic vị từ. Các câu truy vấn SQL về bản chất là các biểu thức logic được thực thi trên các tập hợp dữ liệu. Trong lĩnh vực phần cứng và kiến trúc máy tính, đại số Boole và tối thiểu hóa hàm Boole là kiến thức cốt lõi. Chúng được sử dụng để thiết kế các mạch logic kỹ thuật số, là thành phần cơ bản của bộ vi xử lý và các chip máy tính. Việc tối ưu hóa các biểu thức Boole giúp giảm số lượng cổng logic cần thiết, từ đó giảm chi phí và tăng tốc độ xử lý.

5.1. Nền tảng cho thuật toán và cấu trúc dữ liệu hiệu quả

Mọi thuật toán đều hoạt động trên các cấu trúc dữ liệu, và cả hai đều được định nghĩa và phân tích bằng các công cụ của Toán rời rạc. Phân tích độ phức tạp của thuật toán (Big O) sử dụng các kỹ thuật đếm và chuỗi số để ước tính thời gian chạy và bộ nhớ cần thiết. Các cấu trúc dữ liệu như cây (trees) và đồ thị (graphs) là các đối tượng toán học rời rạc. Các phép duyệt cây, tìm kiếm trên đồ thị, hay kiểm tra tính liên thông đều là các bài toán kinh điển trong môn học này. Hiểu biết sâu sắc về các cấu trúc này cho phép các kỹ sư phần mềm lựa chọn công cụ phù hợp nhất để giải quyết vấn đề một cách hiệu quả.

5.2. Vai trò của quan hệ và logic trong cơ sở dữ liệu

Mô hình cơ sở dữ liệu quan hệ dựa trên khái niệm quan hệ trong toán học, trong đó một bảng (table) được xem như một tập hợp các bộ (tuples). Các phép toán trên cơ sở dữ liệu như phép chọn (SELECT), phép chiếu (PROJECT), và phép kết nối (JOIN) đều có gốc rễ từ đại số quan hệ, một nhánh của cơ sở logic. Ngôn ngữ truy vấn có cấu trúc (SQL) cung cấp một cách để diễn đạt các phép toán này. Ví dụ, mệnh đề WHERE trong SQL tương ứng với phép chọn dựa trên một vị từ logic. Do đó, kiến thức về logic và lý thuyết tập hợp là rất quan trọng để thiết kế và truy vấn cơ sở dữ liệu một cách hiệu quả.

5.3. Tối thiểu hóa hàm Boole trong thiết kế mạch logic số

Máy tính hoạt động dựa trên hệ nhị phân (0 và 1). Đại số Boole cung cấp một khung toán học để làm việc với các biến chỉ nhận hai giá trị này. Mọi chức năng tính toán trong CPU đều được thực hiện bởi các mạch logic được xây dựng từ các cổng AND, OR, NOT. Một hàm Boole có thể được biểu diễn bằng một biểu thức logic. Việc tối thiểu hóa hàm Boole bằng các phương pháp như bìa Karnaugh hay Quine-McCluskey cho phép tạo ra các mạch điện tử tương đương nhưng sử dụng ít cổng logic hơn. Điều này trực tiếp dẫn đến việc giảm kích thước, giảm năng lượng tiêu thụ và tăng tốc độ của các chip máy tính.

VI. Bí Quyết Học Tốt Toán Rời Rạc Và Tương Lai Môn Học

Để chinh phục Toán rời rạc, một môn học đòi hỏi tư duy trừu tượng và logic cao, sinh viên cần áp dụng một chiến lược học tập chủ động và có hệ thống. Thay vì chỉ ghi nhớ công thức, điều quan trọng là phải hiểu được bản chất và ý nghĩa đằng sau mỗi khái niệm. Một bí quyết hiệu quả là luôn cố gắng liên kết lý thuyết với các ví dụ thực tế trong Công nghệ Thông tin. Khi học về giải tích tổ hợp, hãy thử viết một đoạn mã nhỏ để sinh ra các hoán vị. Khi học về cơ sở logic, hãy phân tích các câu lệnh điều kiện phức tạp trong một chương trình có sẵn. Việc chủ động thực hành và giải quyết nhiều dạng bài tập khác nhau, từ cơ bản đến nâng cao, là cách tốt nhất để củng cố kiến thức. Đừng ngần ngại làm việc nhóm để thảo luận về các vấn đề khó, bởi việc giải thích một khái niệm cho người khác là cách tuyệt vời để kiểm tra sự hiểu biết của chính mình. Nhìn về tương lai, vai trò của Toán rời rạc ngày càng trở nên quan trọng hơn với sự phát triển của các lĩnh vực mới. Các mô hình trong trí tuệ nhân tạo, học máy, và khoa học dữ liệu đều dựa trên các cấu trúc toán học rời rạc. Lý thuyết đồ thị là nền tảng cho mạng nơ-ron và các thuật toán phân cụm. Logic và lý thuyết xác suất là cốt lõi của các hệ thống suy luận và mô hình thống kê. Do đó, việc đầu tư thời gian và nỗ lực để nắm vững giáo trình toán rời rạc không chỉ giúp vượt qua môn học mà còn mở ra nhiều cơ hội nghề nghiệp hấp dẫn trong tương lai.

6.1. Phương pháp học tập hiệu quả và tài liệu tham khảo thêm

Một phương pháp học tập hiệu quả bao gồm ba bước: hiểu lý thuyết, thực hành bài tập, và ứng dụng vào lập trình. Trước hết, hãy đọc kỹ giáo trình toán rời rạc, tập trung vào các định nghĩa và định lý. Sau đó, làm tất cả các bài tập trong sách giáo khoa, bắt đầu từ những bài dễ nhất. Cuối cùng, tìm kiếm các bài toán lập trình trên các nền tảng như LeetCode, HackerRank có liên quan đến chủ đề đang học (ví dụ: các bài toán về tổ hợp, đồ thị). Ngoài giáo trình chính của TS. Võ Văn Tuấn Dũng, sinh viên có thể tham khảo thêm các tài liệu quốc tế uy tín như "Discrete Mathematics and Its Applications" của Kenneth H. Rosen để có cái nhìn đa chiều và sâu sắc hơn.

6.2. Xu hướng phát triển của toán rời rạc trong AI và Data Science

Tương lai của Toán rời rạc gắn liền với sự bùng nổ của Trí tuệ nhân tạo (AI) và Khoa học dữ liệu (Data Science). Lý thuyết đồ thị được sử dụng để phân tích mạng xã hội, phát hiện gian lận và xây dựng các hệ thống gợi ý. Các phép đếm và xác suất tổ hợp là nền tảng cho nhiều thuật toán học máy. Logic mờ (Fuzzy Logic), một sự mở rộng của logic cổ điển, được ứng dụng trong các hệ thống điều khiển thông minh. Mật mã học, một lĩnh vực quan trọng của an toàn thông tin, phụ thuộc rất nhiều vào lý thuyết số và các cấu trúc đại số hữu hạn. Do đó, kiến thức vững chắc về Toán rời rạc sẽ là một lợi thế cạnh tranh lớn cho các kỹ sư tin học muốn theo đuổi các lĩnh vực tiên tiến này.

Nội dung chính

Giáo trình Toán rời rạc – TS. Võ Văn Tuấn Dũng

Tổng quan về giáo trình (250-300 từ)

Giáo trình Toán rời rạc do TS. Võ Văn Tuấn Dũng (Khoa Công nghệ Thông tin, Trường Đại học Dân lập Kỹ thuật Công nghệ TP. Hồ Chí Minh) biên soạn vào đầu năm 2004. Tài liệu được xây dựng để phục vụ giảng dạy môn học "Toán rời rạc" với thời lượng chuẩn 3 đơn vị học trình (tương đương 45 tiết giảng dạy lý thuyết và bài tập) trong chương trình đào tạo kỹ sư Công nghệ Thông tin, đồng thời đóng vai trò tài liệu tham khảo cho sinh viên ngành Toán – Tin học.

Mục tiêu học tập của giáo trình là trang bị cho người học khối kiến thức tối thiểu và có hệ thống về cơ sở toán học rời rạc cho khoa học máy tính. Sinh viên sau khi hoàn thành tài liệu sẽ nắm vững logic hình thức, các phương pháp chứng minh toán học, kỹ thuật giải tích tổ hợp, nền tảng thuật toán, lý thuyết quan hệ và kỹ thuật tối thiểu hóa đại số Boole làm tiền đề cho các môn học chuyên ngành.

Giáo trình được cấu trúc thành 5 chương tuần tự. Cách tiếp cận của tác giả tập trung vào tính tinh giản, chuẩn xác về mặt toán học nhưng giảm bớt các chứng minh quá trừu tượng, thay vào đó ưu tiên định hình phương pháp luận và gắn kết trực tiếp với các bài toán nền tảng của tin học.

Điểm đặc trưng của giáo trình là việc kết hợp song song giữa lý thuyết toán học thuần túy với các mô hình ứng dụng trong xử lý dữ liệu và máy tính, thể hiện qua các ví dụ về phân tích vòng lặp chương trình, không gian mật khẩu hệ thống, xâu nhị phân và tối ưu hóa cổng logic số.

---

Nội dung kiến thức cốt lõi (500-600 từ)

Các chương/chủ đề chính

Toàn bộ giáo trình bao gồm 5 chương chuyên đề:

• Chương 1: Cơ sở logic: Khảo sát khái niệm mệnh đề (sơ cấp, phức hợp); các phép toán logic (phủ định $\neg P$, hội $P \wedge Q$, tuyển không chặt $P \vee Q$, tuyển chặt $P \underline{\vee} Q$, kéo theo $P \rightarrow Q$, tương đương $P \leftrightarrow Q$) và độ ưu tiên phép toán; dạng mệnh đề, hằng đúng, hằng sai (mâu thuẫn); các quy tắc thay thế và 10 quy luật logic cơ bản (phủ định của phủ định, De Morgan, giao hoán, kết hợp, phân bố, lũy đẳng, trung hòa, phần tử bù, thống trị, hấp thụ); quy tắc suy diễn (Modus Ponens, Modus Tollens, tam đoạn luận Syllogism, chứng minh phản chứng); vị từ, biến tự do, lượng từ khái quát $\forall$, lượng từ tồn tại $\exists$ và quy tắc phủ định lượng từ; ứng dụng logic trong cấu trúc định lý (điều kiện cần, điều kiện đủ, điều kiện cần và đủ) cùng 3 phương pháp chứng minh: trực tiếp, phản chứng và quy nạp toán học (kèm phân tích sai lầm lịch sử của P. Fermat đối với số $2^{2^n}+1$ được Euler kiểm chứng lại ở $n=5$).
• Chương 2: Phép đếm: Nhắc lại lý thuyết tập hợp (tập con, tập rỗng, biểu đồ Venn, các phép toán tập hợp, tích Descartes) và ánh xạ (đơn ánh, toàn ánh, song ánh, ánh xạ ngược, ánh xạ hợp, ánh xạ đồng nhất $\text{id}X$); ba nguyên lý đếm cơ bản (nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ); giải tích tổ hợp (hoán vị $P_n = n!$, chỉnh hợp $A_n^k$, tổ hợp $C_n^k$, chỉnh hợp lặp $n^k$, tổ hợp lặp $C{n+k-1}^k$); công thức nhị thức Newton và tam giác Pascal; nguyên lý Dirichlet (nguyên lý chuồng bồ câu) dạng cơ bản và dạng tổng quát.
• Chương 3: Thuật toán: Trình bày khái niệm thuật toán, cấu trúc thuật toán, một số thuật toán tiêu biểu và phương pháp phân tích độ phức tạp của thuật toán.
• Chương 4: Quan hệ: Giới thiệu khái niệm quan hệ hai ngôi, kỹ thuật biểu diễn quan hệ bằng ma trận, quan hệ tương đương, quan hệ thứ tự và biểu đồ Hasse của tập sắp thứ tự hữu hạn.
• Chương 5: Đại số Boole và hàm Boole: Khảo sát hàm Boole, biểu thức Boole, đại số Boole, nguyên lý đối ngẫu; kỹ thuật thiết kế tổ hợp các cổng logic theo biểu thức Boole; các phương pháp tối thiểu hóa hàm Boole gồm biến đổi đại số, biểu đồ Karnaugh và thuật toán Quine-McCluskey.

Logic phát triển nội dung đi từ công cụ suy luận hình thức (Chương 1) đến công cụ định lượng tổ hợp (Chương 2), mô hình hóa cấu trúc dữ liệu và giải thuật (Chương 3, 4), kết thúc ở nền tảng phần cứng logic (Chương 5).

Kiến thức nền tảng được xây dựng

• Lý thuyết nền tảng: Hệ thống logic toán học mệnh đề và vị từ; lý thuyết tập hợp và cấu trúc ánh xạ; lý thuyết tổ hợp và đại số Boole trừu tượng.
• Nguyên lý cốt lõi: Nguyên lý suy diễn hợp lý (Modus Ponens, Modus Tollens); nguyên lý cộng, nhân và bù trừ tập hợp; nguyên lý Dirichlet; nguyên lý đối ngẫu trong đại số Boole.
• Khung phân tích: Khung chứng minh quy nạp toán học; khung biểu diễn quan hệ qua ma trận và đồ hình Hasse; khung tối ưu hóa hàm logic đa biến.

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Lập bảng chân trị; rút gọn biểu thức logic; tính toán hoán vị, chỉnh hợp, tổ hợp; tối thiểu hóa hàm Boole bằng bảng Karnaugh và phương pháp Quine-McCluskey.
• Kỹ năng phân tích (Analytical skills): Phân tích tính đúng đắn của chuỗi suy luận diễn dịch; phân biệt điều kiện cần và điều kiện đủ; nhận diện cấu hình tổ hợp thỏa mãn điều kiện ràng buộc.
• Kỹ năng thực hành (Practical competencies): Mô hình hóa bài toán thực tế (tính chu kỳ lặp chương trình Pascal, tính số lượng mật khẩu độ dài 6–8 ký tự, xác thực chuỗi bit nhị phân) thành các bài toán đếm và logic giải được bằng thuật toán.

---

Phương pháp giảng dạy và học tập (300-350 từ)

Phương pháp sư phạm của giáo trình được thiết kế theo hướng suy diễn chặt chẽ kết hợp minh họa quy nạp. Mỗi khái niệm lý thuyết trừu tượng đều được đặt trong một cấu trúc định nghĩa toán học chính xác, ngay sau đó là các bảng chân trị hoặc ví dụ mẫu dạng số học và ngữ nghĩa đời sống để làm rõ nội hàm.

Hệ thống bài toán mẫu và tình huống minh họa phong phú, gắn liền với các ngữ cảnh cụ thể:

• Phân tích suy luận logic từ các câu thành ngữ, tục ngữ Việt Nam ("Trăng quầng trời hạn, trăng tán trời mưa"), tình huống suy luận xe hỏng, bài toán điều tra nghi vấn gian lận thi cử của nhóm sinh viên A, B, C.
• Ứng dụng toán học trong tin học: đếm số phép toán của đoạn lệnh for lặp liên tiếp trong ngôn ngữ Pascal, đếm số chuỗi nhị phân 8-bit có điều kiện tiền tố/hậu tố, tính tổng số mật khẩu hệ thống gồm ký tự chữ in hoa và chữ số ($36^n - 26^n$).
• Bài toán phân nhóm tổ hợp: bài toán cắt giấy $S(n) = 6n + 1$, bài toán phân bố người sinh cùng tháng, thống kê số sinh viên học các thứ tiếng Anh, Pháp, Đức qua công thức bù trừ.

Về phương pháp thực hành và đánh giá, cuối Chương 1 cung cấp 30 bài tập và Chương 2 cung cấp 30 bài tập bao quát nhiều dạng: nhận diện mệnh đề, xác định chân trị, chứng minh tương đương logic không dùng bảng, tìm hệ quả logic, chứng minh quy nạp, và các bài toán phân phối, xếp chỗ, lập mã số.

Đối với người học tự nghiên cứu, giáo trình định hướng lộ trình tiếp cận tuần tự: làm chủ bảng chân trị và 10 quy luật logic cơ bản trước khi chuyển sang các phương pháp chứng minh toán học và giải tích tổ hợp phức tạp.

---

Điểm nổi bật và cập nhật (250-300 từ)

Giáo trình Toán rời rạc của TS. Võ Văn Tuấn Dũng được xây dựng với định hướng tinh giản tối đa dung lượng lý thuyết thuần túy để phù hợp với khung thời gian 45 tiết chuẩn, khắc phục tình trạng quá tải kiến thức toán lý thuyết đối với sinh viên kỹ thuật.

Nội dung giáo trình thể hiện tính thực tiễn cao thông qua việc tích hợp trực tiếp các bài toán nền tảng của ngành Công nghệ Thông tin:

• Biểu diễn cấu trúc giải thuật: Phân tích số bước thực hiện của các vòng lặp đơn và lặp liên tiếp trong chương trình Pascal thông qua nguyên lý cộng.
• An toàn hệ thống và mã hóa: Đưa bài toán xác định số lượng mật khẩu máy tính có độ dài từ 6 đến 8 ký tự với tập ký tự chữ hoa và chữ số thành bài toán đếm bù trừ.
• Xử lý dữ liệu nhị phân: Bài toán đếm và xử lý các dãy bit có độ dài xác định (7-bit, 8-bit) với các ràng buộc về bit đầu và bit cuối.
• Thiết kế phần cứng: Chương 5 kết nối trực tiếp toán rời rạc với kỹ thuật phần cứng máy tính qua việc khảo sát tổ hợp cổng logic và phương pháp Quine-McCluskey để tối ưu hóa mạch số.

Các nội dung này tạo tiền đề trực tiếp cho các học phần tiếp theo trong chương trình đào tạo kỹ sư công nghệ thông tin như Cấu trúc dữ liệu và giải thuật, Cơ sở dữ liệu, Kiến trúc máy tính và Thiết kế vi mạch.

---

Đối tượng sử dụng giáo trình (200-250 từ)

• Sinh viên chuyên ngành: Tài liệu phục vụ trực tiếp cho sinh viên năm thứ nhất hoặc năm thứ hai ngành Công nghệ Thông tin tại các trường đại học và cao đẳng kỹ thuật. Đồng thời, giáo trình là tài liệu tham khảo cơ sở cho sinh viên ngành Toán – Tin học.
• Yêu cầu kiến thức tiên quyết: Người học cần nắm vững kiến thức toán học phổ thông, bao gồm đại số cơ bản, lý thuyết chia hết trên tập số nguyên, phương trình và bất phương trình đại số, cùng các khái niệm sơ cấp về tập hợp số.
• Giảng viên đại học: Tài liệu cung cấp đề cương chi tiết, hệ thống định lý chuẩn hóa và ngân hàng 60 bài tập mẫu (cho 2 chương đầu) có phân cấp độ, phù hợp để thiết kế bài giảng lý thuyết, bài tập thảo luận và đề thi kết thúc học phần 3 đơn vị học trình.
• Tự học và tham khảo: Phù hợp cho lập trình viên và người tự học cần củng cố tư duy logic toán học, kỹ thuật phân tích độ phức tạp thuật toán và cấu trúc đại số Boole.

---

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với ai? Giáo trình được biên soạn cho sinh viên đại học ngành Công nghệ Thông tin và ngành Toán – Tin học đang theo học học phần Toán rời rạc với thời lượng 3 đơn vị học trình (45 tiết).

2. Cần kiến thức nền nào để học? Người học chỉ cần kiến thức toán trung học phổ thông (đại số cơ bản, tập hợp, hàm số và các phép tính số học cơ bản). Giáo trình đã tự nhắc lại và định nghĩa lại hệ thống lý thuyết tập hợp và ánh xạ ở Chương 2.

3. Điểm khác biệt với giáo trình khác là gì? Tài liệu tập trung vào sự tinh giản, tích hợp trực tiếp các cấu trúc toán học với các ví dụ tin học (mã giả vòng lặp Pascal, xâu nhị phân, không gian mật khẩu) và cung cấp phương pháp tối thiểu hóa hàm Boole bằng cả Karnaugh lẫn Quine-McCluskey.

4. Làm sao để tự học giáo trình hiệu quả? Người học nên học tuần tự theo từng chương: nắm chắc 10 quy luật logic và quy tắc suy diễn ở Chương 1, thực hành lập bảng chân trị, sau đó áp dụng vào các bài toán đếm ở Chương 2 và giải quyết đầy đủ hệ thống 30 bài tập cuối mỗi chương.

5. Giáo trình có bài tập ứng dụng không? Có. Giáo trình có 60 bài tập phân loại chi tiết ở Chương 1 và Chương 2, đi kèm nhiều ví dụ thực tế như bài toán lịch thi đấu bóng chuyền, bài toán chọn ban đại diện, bài toán xếp chỗ ngồi và bài toán nguyên lý Dirichlet.

---

Kết luận (150 từ)

Giáo trình Toán rời rạc của TS. Võ Văn Tuấn Dũng là tài liệu học thuật cung cấp hệ thống kiến thức toán học rời rạc nền tảng và tinh giản cho khối ngành Công nghệ Thông tin và Toán – Tin học. Với 5 chương nội dung bao quát từ Logic học, Phép đếm tổ hợp, Thuật toán, Quan hệ cho đến Đại số Boole, giáo trình thiết lập cơ sở lý thuyết và công cụ phân tích giải thuật vững chắc.

Lộ trình học tập đề xuất là hoàn thành tuần tự từ nền tảng suy luận hình thức (Chương 1–2), chuyển tiếp sang mô hình hóa dữ liệu (Chương 3–4), và ứng dụng vào thiết kế mạch logic (Chương 5). Người học có thể kết hợp tài liệu này với các giáo trình chuyên sâu về Cấu trúc dữ liệu và giải thuật và Kiến trúc máy tính để hoàn thiện khối kiến thức cơ sở ngành.

Trích đoạn nội dung tài liệu

Chương 1: Cơ sở logic 4. Một số phương pháp chứng minh toán học hợp riêng của việc Các phương pháp chứng mình trong toán học là các trường đây, ta giới thiệu áp dụng các qui tắc logic vào quá trình suy luận toán. Dưới với các qui tắc cơ một sô phương pháp chứng minh toán và quan hệ của chúng bản của logic. Phương pháp chứng mình trực tiếp Để chứng minh mệnh đề đúng có dạng E>F biểu thị đưới đạng: ta xây đựng một dãy các dạng mệnh đề E¡, Eạ., lạ được | Bp By, By > Pas ons Bar > Bas Pn => F Ap dung qui tắc Modus Ponens ta có E, E => E, dung thi E; dung E;, Er => Ea đúng thì Eạ đúng Ea, Ea = F đúng thì F đúng Tức là từ E đúng, suy ra F đúng.

nˆ— 1 chia hết cho 24. Vị dụ Chứng minh rằng nếu n là số nguyên tế lớn hơn 5 thì GIẢI: Xây dựng chứng minh: (1) n là nguyên tố vàn > 5 =n-l, nt[ là các số chẵn 8 (2) nel và n+l là hai số chẵn liên tiếp > (n-I)(n+1) chia hết cho hét cho 3 (3) n, n-1, n+] la ba số tự nhiên liên tiếp => n(n-1)(n+1) chia | (4) n là nguyên tố lớn hơn 5 => n không chia hết cho 3 (5) Tw (3) va (4) ta co (n-1)(nt+1) chia hét cho 3 hết cho 8 (6) n nguyên tố và n> 5 => (n-1)(n+1) chia hết cho 3 và chia (7) Số 3 và 8 là hai số nguyên tổ cùng nhau (8) ‘Tir (7) => (n-1)(n+1) chia hét cho 8x3=24 (9) n là nguyên tế vàn > 5 = nŸ ~ 1 chia hết cho 24. Phương pháp chứng minh phản chứng đề nào đó ta Để chứng minh bằng phản chứng một khăng định hay một mệnh thực hiện như sau: đã cho để suy ra Giả sử mệnh để cần chứng minh là sai, kêt hợp với giả thiết 18 Chương 1: Cơ sở logic được một điều mâu thuẫn nào đó rồi từ đó kết luận răng mệnh đề cho là đúng. Cơ sở của phương pháp chứng minh này là qui tắc mâu thuẫn p~>q<© [(p^ ¬q) — Ú|.

Ví dụ - Ta sẽ chứng minh mệnh đề ở ví dụ ở (1.2 -I) bằng phương pháp phản chứng. Giải: Các bước lập luận sẽ là: (1) Giả thiết, n là số nguyên tế > 5, n -- I không chia hết cho 24. (3) n-1, n+! là 2 số chẵn liên tiếp nên tích (n-1)(n+L) chia hết cho 4. (4) nˆ-1 không chia hết cho 24 nên nŸ - không chia hết cho 6.

(5) Suy ra nỶ -l không chia hết cho 2 hoặc không chia hết cho 3. (6) Xét hai trường hợp: + Nếu n’ — 1 không chia hết cho 2 thì n-Í và n+[ là hai số lẻ suy ra n là số chăn. Vậy n không là số nguyên tô lớn hơn 5. ¿+ Nếu nˆ- Í không chia hết cho 3 thì n phải chia hết cho 3, vì (n- L)n@ntÏ) chia hết cho 3 (ba số tự nhiên liên tiếp).Vậy n không là số nguyên tổ lớn hơn 5.

(7) Từ (6) suy ra n không là số nguyên tố lớn hơn 5. Điều này mâu thuẫn với giả thiệt. Suy ra điều phải chứng minh. Phương pháp quy nap Phương pháp quy nạp có vai trò rất quan trọng trong toán học, và thường dược sử dụng để chứng minh đối với những mệnh đề toán học có liên hệ chặt chẽ với tập hợp các sô tự nhiên.

Nguyên lý qui nạp: Mệnh đề Vn e N, p(n) là hệ qua cha ménh dé p() A [Vn EN, p(n) -> p(ntly] Phương pháp chứng minh bằng qui nap: Theo nguyên lý trên để chứng minh p(n) đúng với n e N tuỳ ý, ta thực hiện 2 bước : - Bước Ï (cơ sở) : kiểm chứng để khẳng định p(0) đúng. Ta chittng minh p(nt 1) đúng. Nguyên lý qui nạp trên có thể băt đâu từ nạ c N: nghĩa là: D7777 77 Chương †: Cơ sở logic [p(no) A [Vn 2 no, p(n) —> p(nt+l)|J] -> [Vn 3 mạ, p(n)| # “a z `. & Cha y Trong qua trinh qui nap nêu không thực hiện đây đủ cả hai bước cơ sở và quy nạp, thì có thê dân đên kết luận sai lâm.

Chăng hạn, do bỏ qua khâu quy nạp nên nhà toán học Pháp P. Fermat (1601 -- 1665) đã cho rằng các số dạng 2“ +1 dêu là sô nguyên tô. Fermat xét 5 số đầu tiên: - Vớin=0cho 2Ÿ +1=2!+1=3 là số nguyên tô. - Vớin= Icho 2” +I=2”+1=5 là số nguyên (6.

- Với n=2 cho 2” +]=2? +1 =17 là số nguyên tố. - Với n= 3 cho 2? +1=2#+1=257 là số nguyên tố. - Vớin=4cho 2” +1= 2" +I=65537 là số nguyên tế. Nhưng vào thế kỷ 18, Euler đã phát hiện với n = 5 khẳng định trên không đúng, bởi vì: 2” +1=2” +I= 4294967297 :: 641x6700417.

Vị dụ Í Chứng mình Vn e N ta có: 0212, .+n= TƯD, 2 GIẢI: Xét vị từ p(n):0+[+.tn= nặ+]) , 2 : › X ĐA À 0xI A ae 2 , Bước cơ sở: Khi n = 0 thì p(0) la ménh dé: 0 = > Về phải của đăng thức trong mệnh để tính ra bằng 0, nên p(0) ding. Bước qui nạp: CHả sử p(n) đúng vớt n € N tuỳ ý: 0421+.+n= 7+) 2 Khi ấy n{n +]) +n+1= ứ+ ni + 2) 0+1+. Do đó theo nguyên lý qui nạp ta có điều phải chứng mình. ne Chương 1: Cơ sở logic mảnh, sau đó nhặt một trong Vidu2 Cô Lan cầm một tờ giấy và lay kéo cắt thành 7 Và cô Lan cứ tiếp tục cắt giây những mảnh giây đã cắt và lại cắt thành 7 mảnh.

giấy đã cắt và đếm được 122 như vậy. Sau một hồi cô Lan thu tất cả các mẫu mảnh. Hỏi xem cô Lan đếm đúng hay sai? Giải: là tạo thêm 6 mảnh. Do đó công Với mỗi lần cắt | mảnh giấy thành 7 mảnh, tức ¡ mảnh thành 7 mảnh co dang: thức tính số mảnh giấy sau n bước thực hiện cắt S(n) = 6n + I.

bằng qui nạp theo n. Ta khang định tính đúng đắn của công thức S(n) 7. Trong trường hợp này cô Bước cơ SỞ: Khin= | thì S(1)=6. Lan cắt mảnh giấy có trong tay thành 7 mảnh nên S(1) được số mảnh giây là: Bước qui nạp: Giả sử sau k bước cô Lan đã nhận S(k)= 6k + I.

mảnh giây nhận được trong k Sang budc k + 1, cé Lan lấy một trong những và tức là cô Lan đã lấy đi một trong S(k) mảnh bước trước và cắt thành 7 mảnh, thay vào đó 7 mảnh được cắt ra, do đó: S(k+Il)=S(Œ()—1+7=6k+l~1+7=6k+7 =6k+6+1=6(kt1)+ 1. nghia la S(k+1) dung. Vay số mảnh giấy cô Lan nhận được sau n bước + 2 = 2(mod 6). Vậy cô Lan đã Do S(n) = 6n + 1 = 1(mod 6), nhưng 122 = 6.

TRƯỜNG ĐH -en | ¡ TH VIỄN | x } Số -_4000O2. | 21 Chương 1: Cơ sở logic BÀI TẬP CHƯƠNG 1 (cơ sở logic) nào là mệnh dề : Bail Trong các khẳng định sau, cho biết khẳng định a) 6 là một số nguyên tô. b) Cô ta rất thông minh. c) Tam giác cân có hai cạnh bằng nhau.

d) Hãy làm bài tập Toán cao cấp di! e) Nếu bạn đến trễ thì tôi sẽ đi học trước. f) xlàmột số lẻ. g) Ban có thích xem bóng đá không ? Bài2 Gọi P, Q là các mệnh đề : P: “Hùng thích bóng đá” Q: “Hùng phét nấu ăn” thức trong đó sử dụng các phép nôi. Hãy viết lại các mệnh đề sau dưới dạng hình a) Hùng không thích bóng đã lẫn nấu ăn.

b)_ Hùng thích bóng đá nhưng ghét nấu ăn. ăn vừa ghét bóng đá. c) Hung thich bóng đá hay Hùng vừa thích nâu bóng đá nhưng thích nấu ăn. đ) Hùng thích bóng đá và nấu ăn hay Hùng ghét Bài 3 Xét chân trị các mệnh dé sau : a) (V2 <1) A (1 <3) , 1<0) b) (244 =6) v (log In „ & ( S c (1>5) >6 +3<@ Bài 4 Hãy lấy phủ định các mệnh dé sau : ên.

a) Nếu xỶ là một số nguyên thì x là một số nguy b) Nếu ngày mai thứ tư thì hôm nay phải thứ hai. c) Tôi không thể ngủ nếu tôi đói bụng. g ngu hom qua. đ) Nếu [Lan dậy sớm ngày mai và dị học thi Lan di khén e) Moi tam giác dều có các góc bằng 60°.

0_ Tuổi của Tuấn khoảng từ lŠ đến 20. Bài 5 Xác định chân trị của các mệnh đề sau : a) Nếu2+5=6thì 2+ 4= 10 Chương 1: Cơ sở logic b) Nếu2x4=§thi5-2=3 c) Néul+2=3thi 1+3=5 Bai6 Lap bang chan tri cho cac dang ménh dé sau : a) ¬p — (pvq) b) =p —>(¬qvr) c) pv (qar) đ) (pvq)Ar €) (pAq) © (qAr) ^A (¬q) Bài7 Hãy chỉ ra các hãng đúng trong các dạng mệnh đề sau : a) (pvq) > (paq) b) (pAq) -> (pvq) c) p> (-q > p) d) p> (p> q) ©) (pq) > [(q> 1) > (p> n)] Bai 8 Chitng minh cac tuong duong légic sau : a) p>(q>p) © rvr b) (pAq)v¬q © pv¬q €) p—>q © ¬q->-p d) (pAq)->r © p>(q—>r) Bài 9 Chứng minh dạng mệnh đề sau là hăng đúng [(r—>§) ^A [(r->s) —> (—¬tvu)]] > (¬tvu) Bài 10 Ba sinh viên A, B. C bị nghi là đã gian lận trong bài thi. Khi bị thầy hỏi thì họ khai như sau : A.:”B đã chép bài và C vô tội" B: "Nếu A có tội thì C cũng có tội" C : "Tôi vô tội" Hãy trả lời các câu hỏi sau : a) Nếu A đã nói thật và B nói láo thì ai vô tội và ai đã chép bài ? b) Nếu mọi người vô tội thì ai đã nói thật và ai nói láo ? c) Nếu A nói láo và B, C nói thật thì ai có tội ? Bài 11 Có thể nói gì về một dạng mệnh đề: 23 anaes hương 1: Cơ sở logic a) Có hệ quả logiclà một mâu thuẫn ? b) Có hệ quả logic là một hằng đúng ? ©) Là hệ quả logic của một mâu thuẫn ? đ) Là hệ quả logic của một hằng đúng ? Bài 12 Các cặp mệnh đề (vị từ) sau đây có phải là phủ định của nhau không: a) 2>3; 3>2.

b) x là số âm; x là số đương. ©) phương trình x + 5 = 2 có nghiệm; phương trình x + 5 = 2 vô nghiệm. đ) có một số là ước của 15; có một số không phải là ước của 15. Bài 13 Cho biết suy luận nào trong các suy luận dưới đây là đìng và qui (ắc suy diễn nào đã được sử dụng? a) Điều kiện đủ đê đội bóng chuyên Việt Nam (hăng trận là đối thủ đừng, gỡ lại vào phút cuỗi : Mà đội bóng chuyển Việt Nam đã thắng trận Vậy đối thủ của đội bóng chuyển Việt Nam không gỡ lại vào phút cuối.