Chương 1: Kiến Thức Cơ Bản Về Tổ Hợp, Logic Mệnh Đề, Tập Hợp Và Ánh Xạ

Khám phá b2 logic tap hop anh xa 2021, tìm hiểu các chiến lược và xu hướng mới trong lĩnh vực này để nâng cao hiệu quả kinh doanh.

• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Toán Học
• Đề tài: Kiến Thức Cơ Bản Về Tổ Hợp Và Logic Mệnh Đề
• Loại tài liệu: Bài Giảng
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: Kiến thức cơ bản tổ hợp, Logic mệnh đề, Tập hợp, và Ánh xạ
• 1.1. Bài toán tổ hợp
• 1.2. Logic mệnh đề
• 1.3. Logic vị từ và lượng từ
• 1.4. Một số ứng dụng trong tin học
• 1.5. Lý thuyết tập hợp và ứng dụng
• 1.6. Ánh xạ

Tóm tắt

I. Tổng Quan Về Kiến Thức Cơ Bản Tổ Hợp Và Logic Mệnh Đề

Kiến thức về tổ hợp và logic mệnh đề là nền tảng quan trọng trong toán học và khoa học máy tính. Tổ hợp nghiên cứu cách sắp xếp và phân bố các phần tử trong các tập hữu hạn. Logic mệnh đề giúp xác định giá trị chân lý của các mệnh đề, từ đó xây dựng các biểu thức logic phức tạp. Việc hiểu rõ hai lĩnh vực này không chỉ giúp giải quyết các bài toán lý thuyết mà còn có ứng dụng thực tiễn trong lập trình và phân tích dữ liệu.

1.1. Khái Niệm Cơ Bản Về Tổ Hợp

Tổ hợp là lý thuyết về các tập hữu hạn, nghiên cứu các cấu hình khác nhau của các phần tử. Các bài toán tổ hợp thường gặp bao gồm bài toán đếm, tồn tại, liệt kê và tối ưu tổ hợp.

1.2. Logic Mệnh Đề Là Gì

Logic mệnh đề nghiên cứu các mệnh đề có giá trị chân lý đúng hoặc sai. Các phép toán logic như AND, OR, NOT được sử dụng để xây dựng các biểu thức phức tạp từ các mệnh đề đơn giản.

II. Các Vấn Đề Thách Thức Trong Tổ Hợp Và Logic Mệnh Đề

Trong nghiên cứu tổ hợp và logic mệnh đề, nhiều thách thức xuất hiện. Các bài toán như đếm cấu hình, xác định sự tồn tại của cấu hình, và tối ưu hóa là những vấn đề phức tạp. Việc áp dụng các nguyên lý cơ bản và các phương pháp giải quyết là cần thiết để tìm ra lời giải cho những bài toán này.

2.1. Bài Toán Đếm Tổ Hợp

Bài toán đếm tổ hợp yêu cầu xác định số lượng cấu hình thỏa mãn các điều kiện cho trước. Phương pháp đếm thường dựa vào các nguyên lý cơ bản và kết quả đếm đơn giản.

2.2. Bài Toán Tồn Tại Trong Tổ Hợp

Bài toán tồn tại yêu cầu xác định xem có tồn tại cấu hình tổ hợp thỏa mãn các tính chất đã cho hay không. Đây là một vấn đề quan trọng trong lý thuyết tổ hợp.

III. Phương Pháp Giải Quyết Bài Toán Tổ Hợp

Có nhiều phương pháp để giải quyết các bài toán trong tổ hợp và logic mệnh đề. Các phương pháp này bao gồm đếm trực tiếp, sử dụng nguyên lý bao hàm, và áp dụng các thuật toán tối ưu. Mỗi phương pháp có ưu điểm và nhược điểm riêng, tùy thuộc vào tính chất của bài toán.

3.1. Nguyên Lý Bao Hàm Và Loại Trừ

Nguyên lý bao hàm và loại trừ là một công cụ mạnh mẽ trong tổ hợp, cho phép tính toán số lượng phần tử trong các tập hợp phức tạp bằng cách sử dụng các phép toán logic.

3.2. Thuật Toán Tối Ưu Trong Tổ Hợp

Thuật toán tối ưu giúp tìm ra cấu hình tốt nhất trong số các cấu hình thỏa mãn điều kiện cho trước. Các thuật toán này có ứng dụng rộng rãi trong thực tiễn.

IV. Ứng Dụng Thực Tiễn Của Tổ Hợp Và Logic Mệnh Đề

Kiến thức về tổ hợp và logic mệnh đề có nhiều ứng dụng trong thực tiễn, đặc biệt trong lĩnh vực công nghệ thông tin. Các ứng dụng này bao gồm lập trình, phân tích dữ liệu, và thiết kế thuật toán. Việc áp dụng lý thuyết tổ hợp và logic mệnh đề giúp tối ưu hóa quy trình và nâng cao hiệu quả công việc.

4.1. Ứng Dụng Trong Lập Trình

Trong lập trình, các khái niệm tổ hợp và logic mệnh đề được sử dụng để xây dựng các thuật toán và cấu trúc dữ liệu hiệu quả.

4.2. Ứng Dụng Trong Phân Tích Dữ Liệu

Phân tích dữ liệu sử dụng các phương pháp tổ hợp để xác định các mẫu và xu hướng trong dữ liệu lớn, từ đó đưa ra quyết định chính xác.

V. Kết Luận Về Tổ Hợp Và Logic Mệnh Đề

Tổ hợp và logic mệnh đề là hai lĩnh vực quan trọng trong toán học và khoa học máy tính. Việc nắm vững kiến thức cơ bản về chúng không chỉ giúp giải quyết các bài toán lý thuyết mà còn có ứng dụng thực tiễn rộng rãi. Tương lai của nghiên cứu trong hai lĩnh vực này hứa hẹn sẽ mang lại nhiều phát triển mới và ứng dụng sáng tạo.

5.1. Tương Lai Của Nghiên Cứu Tổ Hợp

Nghiên cứu tổ hợp sẽ tiếp tục phát triển, đặc biệt trong bối cảnh công nghệ thông tin ngày càng phát triển mạnh mẽ.

5.2. Tương Lai Của Logic Mệnh Đề

Logic mệnh đề sẽ đóng vai trò quan trọng trong việc phát triển các hệ thống trí tuệ nhân tạo và các ứng dụng công nghệ mới.

Nội dung chính

Tổng quan về giáo trình

Giáo trình thuộc khối kiến thức toán học cơ sở ngành, được thiết kế cho chương trình đào tạo bậc đại học thuộc các ngành Khoa học Máy tính, Công nghệ Thông tin và Kỹ thuật Phần mềm. Về mặt vị trí trong chương trình đào tạo, nội dung giáo trình đóng vai trò cấu trúc nền tảng, thiết lập cầu nối trực tiếp giữa toán học rời rạc thuần túy và các nguyên lý tính toán trong khoa học máy tính.

Mục tiêu học tập (learning outcomes) của giáo trình tập trung vào việc trang bị cho người học:

• Khả năng nhận diện, phân loại và xây dựng mô hình cho 4 dạng bài toán tổ hợp cơ bản: bài toán đếm (Counting Problem), bài toán tồn tại (Existence Problem), bài toán liệt kê (Enumeration Problem) và bài toán tối ưu tổ hợp (Combinatorial Optimization Problem).
• Khả năng xử lý hình thức các biểu thức logic thông qua logic mệnh đề, bảng chân lý, các phép biến đổi tương đương ngữ nghĩa và đưa biểu thức về dạng chuẩn hội.
• Năng lực làm việc với logic vị từ và các phép lượng hóa, kết nối trực tiếp với logic rẽ nhánh trong cấu trúc lệnh lập trình.
• Năng lực vận hành các phép toán tập hợp, xác định lực lượng tập hợp, tập lũy thừa ($2^A$) và tích Đề-các.
• Khả năng áp dụng logic nhị phân và lý thuyết biểu diễn bit vào các thuật toán số học nhị phân (thuật toán cộng, thuật toán nhân) trên bộ xử lý máy tính.

Cấu trúc giáo trình tiếp cận theo hướng toán học hình thức kết hợp ứng dụng tin học: đi từ định nghĩa tiên đề, phân tích ví dụ logic, thiết lập công thức và chuyển hóa thành các giải thuật thao tác trên hệ thống máy tính. Điểm đặc thù của tài liệu là việc tích hợp trực tiếp các cấu trúc lệnh lập trình (như lệnh điều kiện if...then) và các phép toán cấp bit (AND, OR, XOR) vào hệ thống lý thuyết logic và tập hợp.

---

Nội dung kiến thức cốt lõi

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

Nội dung trọng tâm của học phần bao gồm 6 chủ đề chính có quan hệ logic chặt chẽ:

1. Lý thuyết tổ hợp và phân loại bài toán tổ hợp:

   • Khái niệm cốt lõi: Tổ hợp được định nghĩa là lý thuyết nghiên cứu sự sắp xếp và phân bố các phần tử vào các tập hữu hạn; mỗi cách sắp xếp hoặc phân bố được gọi là một cấu hình tổ hợp.
   • Phân loại bài toán:
     • Bài toán đếm (Counting Problem): Xác định số lượng cấu hình thỏa mãn điều kiện cho trước, ứng dụng trong tính xác suất và đánh giá độ phức tạp thuật toán.
     • Bài toán tồn tại (Existence Problem): Xác định sự tồn tại của cấu hình tổ hợp. Khẳng định tồn tại chỉ cần chỉ ra một cấu hình; chứng minh không tồn tại đòi hỏi lập luận logic chặt chẽ (ví dụ: bài toán phủ bàn cờ kích thước $8 \times 8$ bị khuyết 2 ô góc đối diện bằng 31 quân domino).
     • Bài toán liệt kê (Enumeration Problem): Tìm tất cả các cấu hình có thể có thông qua thuật toán vét cạn có sự hỗ trợ của máy tính.
     • Bài toán tối ưu tổ hợp (Combinatorial Optimization Problem): Gán giá trị số (chi phí hoặc giá trị sử dụng) cho mỗi cấu hình để tìm cấu hình có giá trị lớn nhất hoặc nhỏ nhất.

2. Logic mệnh đề và dạng chuẩn tắc:

   • Khái niệm cốt lõi: Mệnh đề là câu khẳng định có giá trị chân lý hoặc đúng (True) hoặc sai (False), không thể vừa đúng vừa sai (ví dụ: "Hà Nội là thủ đô của Việt Nam", "$1 + 1 = 2$", "$2 + 2 = 3$").
   • Các cấu trúc logic: Bảng chân lý, tương đương ngữ nghĩa, mệnh đề hằng đúng (tautology), mệnh đề mâu thuẫn.
   • Dạng chuẩn hội: Biến đổi công thức logic về dạng hội của các mệnh đề tuyển để phục vụ lập trình tự động hóa thao tác trên máy tính.

3. Logic vị từ và lượng từ:

   • Khái niệm cốt lõi: Vị từ $P(x)$ xác định trên trường/miền xác định $M$ chuyển thành mệnh đề khi biến $x$ nhận giá trị cụ thể $x_0 \in M$.
   • Mối liên hệ lập trình: Minh họa qua lệnh if (x > 3) then x := x + 1;, trong đó mệnh đề điều kiện quyết định luồng thực thi của biến.
   • Lượng từ hóa: Phương pháp biến đổi hàm vị từ thành mệnh đề thông qua lượng từ mà không cần kiểm chứng từng giá trị riêng lẻ.

4. Ứng dụng logic mệnh đề trong tin học:

   • Biểu diễn thông tin: Gán giá trị đúng tương ứng bit 1, giá trị sai tương ứng bit 0.
   • Phép toán cấp bit: Các phép toán AND, OR, XOR trên các xâu nhị phân có cùng độ dài (ví dụ: thực hiện phép toán bit trên hai xâu nhị phân 01101 10110 và 11000 11101).
   • Thuật toán số học nhị phân: Xây dựng thuật toán cộng và nhân các số nguyên trên khai triển nhị phân phục vụ bộ xử lý số học (ALU).

5. Lý thuyết tập hợp và tích Đề-các:

   • Khái niệm cốt lõi: Tập hợp, phần tử, tập vũ trụ $U$, các tập số chuẩn ($R, N, Z, Z^+$), cách xác định tập hợp bằng danh sách hoặc mệnh đề logic ($S = {x \mid P(x)}$ như ví dụ $S = {x \mid x \text{ là sinh viên ĐHBK HN}}$).
   • Quan hệ tập con và tập lũy thừa: Quan hệ $A \subseteq B \iff \forall x [x \in A \to x \in B]$, tập rỗng $\emptyset$, tập lũy thừa $2^A$ có lực lượng $|2^A| = 2^n$ với $|A| = n$.
   • Các phép toán tập hợp: Giao ($A \cap B$), Hợp ($A \cup B$), Hiệu ($A \setminus B$), Hiệu đối xứng ($A \oplus B$), Phần bù ($A^c = U \setminus A$).
   • Tích Đề-các (Cartesian product): Lý thuyết xây dựng bởi René Descartes (1596–1650), định nghĩa $A \times B = {(a, b) \mid a \in A \land b \in B}$ và mở rộng cho $m$ tập hợp $A_1 \times A_2 \times \dots \times A_m$.

6. Ánh xạ: Thiết lập quy tắc tương ứng giữa các tập hợp, làm cơ sở hình thức cho các cấu trúc ánh xạ dữ liệu.

Progression Logic của Nội dung:
[Lý thuyết Tổ hợp: 4 lớp bài toán] 

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

• Fundamental theories: Lý thuyết tập hữu hạn, lý thuyết logic toán cổ điển (logic mệnh đề và logic vị từ), lý thuyết đại số tập hợp và tích Đề-các.
• Core principles: Nguyên lý bất biến và chẵn lẻ trong chứng minh bài toán tồn tại; nguyên lý đếm cấu hình; nguyên lý tương đương logic và chuẩn hóa công thức về dạng chuẩn hội; nguyên lý biểu diễn nhị phân của dữ liệu số nguyên.
• Essential frameworks: Khung phân loại 4 lớp bài toán tổ hợp (Đếm - Tồn tại - Liệt kê - Tối ưu); mô hình bảng chân lý cho các liên từ logic; mô hình ánh xạ giữa logic toán và cổng logic cấp bit trong kiến trúc máy tính.

Kỹ năng phát triển

• Technical skills: Kỹ năng thao tác các phép toán bit (AND, OR, XOR) trên xâu nhị phân; kỹ năng triển khai thuật toán cộng và nhân số nguyên ở dạng biểu diễn nhị phân; kỹ năng chuyển đổi công thức logic về dạng chuẩn hội.
• Analytical skills: Kỹ năng phân tích bài toán tồn tại thông qua các chứng minh logic chặt chẽ; kỹ năng tính lực lượng tập hợp, xác định không gian tập lũy thừa ($2^n$); kỹ năng phân biệt sự khác nhau giữa bài toán đếm và bài toán tồn tại.
• Practical competencies: Khả năng hình thức hóa điều kiện rẽ nhánh trong ngôn ngữ lập trình thành biểu thức vị từ; khả năng xác định tính hợp lệ của phần tử trong tập hợp số học.

---

Phương pháp giảng dạy và học tập

Giáo trình áp dụng phương pháp sư phạm diễn dịch kết hợp mô hình hóa thuật toán. Mỗi chủ đề lý thuyết đều bắt đầu bằng định nghĩa toán học chính xác, tiếp nối bằng các bảng chân lý hoặc biểu đồ quan hệ, sau đó gắn với ví dụ thực tế và giải thuật tương ứng trong khoa học máy tính.

Quy trình sư phạm:
Định nghĩa Tiên đề / Khái niệm 

Hệ thống bài tập và nghiên cứu tình huống được xây dựng dựa trên các trường hợp cụ thể:

• Case study bàn cờ domino $8 \times 8$: Phân tích bài toán phủ 31 quân domino ($2 \times 1$) lên bàn cờ $8 \times 8$ bị đục 2 ô ở hai góc đối diện. Giáo trình hướng dẫn chứng minh không tồn tại cách phủ dựa trên tính chất: mỗi quân domino luôn phủ đúng 1 ô trắng và 1 ô đen, trong khi việc cắt bỏ 2 ô cùng màu ở góc đối diện làm số lượng ô trắng và đen còn lại trên bàn cờ không bằng nhau (62 ô còn lại không cân bằng màu).
• Case study bài toán đếm cấu hình phủ: So sánh trường hợp trên với bài toán phủ bàn cờ nguyên $8 \times 8$ bằng 32 quân domino, chỉ ra sự tồn tại là hiển nhiên nhưng việc đếm dẫn đến kết quả 12.988.816 cách phủ hình học; đối chiếu với bàn cờ $2 \times 2$ có đúng 2 cách phủ.
• Bài toán kiểm tra phần tử tập hợp: Phân tích độ phức tạp khi xác định một số nguyên lớn (ví dụ $x = 121212...111$) có thuộc tập số nguyên tố $P$ hay không.
• Bài tập thực hành thao tác bit: Cho hai xâu nhị phân cụ thể (như 01101 10110 và 11000 11101), yêu cầu tính toán chính xác các kết quả của phép toán AND bit, OR bit và XOR bit.
• Bài tập tập hợp số học: Cho tập vũ trụ $U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ cùng hai tập con $A = {1, 2, 3, 4, 5}$ và $B = {4, 5, 6, 7, 8}$, yêu cầu tìm các tập hợp kết quả của $A \cap B$, $A \cup B$, $A \setminus B$, $B \setminus A$, $A \oplus B$ và $A^c$.

Phương pháp đánh giá kết quả học tập bao gồm: kiểm tra khả năng lập bảng chân lý, đánh giá kỹ năng rút gọn biểu thức logic về dạng chuẩn hội, kiểm tra khả năng thực hiện phép toán trên xâu bit và đánh giá lập luận chứng minh tính tồn tại hoặc tối ưu của cấu hình tổ hợp.

Đối với việc tự học, sinh viên được hướng dẫn làm việc tuần tự: tái hiện các bảng chân lý, tự kiểm chứng các ví dụ về tập lũy thừa, viết mã giả (pseudo-code) cho các thuật toán cộng/nhân nhị phân và đối chiếu miền xác định của các biến vị từ.

---

Điểm nổi bật và cập nhật

Nội dung giáo trình phản ánh sự liên kết trực tiếp giữa cấu trúc toán học cổ điển và các nguyên lý tính toán hiện đại:

Khía cạnh	Nội dung thể hiện trong giáo trình	Ứng dụng trong Khoa học máy tính
Biểu diễn logic	Chuẩn hóa biểu thức về Dạng chuẩn hội	Viết chương trình máy tính thao tác tự động trên công thức logic
Logic toán học	Vị từ $P(x)$ và miền xác định $M$	Xử lý câu lệnh điều kiện if (x > 3) then... trong trình biên dịch
Đại số logic	Phép toán bit AND, OR, XOR cấp bit	Thao tác trên xâu nhị phân, xử lý số nguyên 16-bit
Số học máy tính	Khai triển nhị phân của số nguyên	Xây dựng thuật toán cộng, nhân trong bộ xử lý số học ALU
Cấu trúc dữ liệu	Tích Đề-các ($A \times B$) và quan hệ	Thiết lập cơ sở dữ liệu quan hệ và mô hình hàm số

Giáo trình tích hợp các ứng dụng thực tế thông qua việc gắn lý thuyết đếm với bài toán tính xác suất sự kiện và phân tích độ phức tạp thuật toán. Các bài toán liệt kê được định hướng giải quyết bằng thuật toán vét cạn trên các hệ thống máy tính, trong khi bài toán tối ưu tổ hợp được gắn với các bài toán phân bổ chi phí và sử dụng tài nguyên trong thực tế.

---

Đối tượng sử dụng giáo trình

• Sinh viên: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ nhất và năm thứ hai thuộc các ngành:
  • Khoa học Máy tính
  • Kỹ thuật Phần mềm
  • Công nghệ Thông tin
  • Hệ thống Thông tin
  • Toán - Tin ứng dụng
• Yêu cầu tiên quyết (Prerequisites): Người học cần nắm vững kiến thức đại số phổ thông, các phép toán tập hợp cơ bản trên các tập số thực $R$, số tự nhiên $N$, số nguyên $Z$, số nguyên không âm $Z^+$, cùng với các khái niệm lập trình căn bản (biến, câu lệnh điều kiện rẽ nhánh).
• Giảng viên: Tài liệu cung cấp cấu trúc bài giảng chuẩn hóa cho học phần Toán rời rạc/Toán cho Tin học, kèm theo hệ thống định nghĩa, phản ví dụ kinh điển (bàn cờ domino) và các bài toán mẫu về xâu bit và đại số tập hợp.
• Tự học và tham khảo: Dành cho người học cần củng cố kiến thức logic hình thức, chuẩn hóa công thức logic phục vụ nghiên cứu trí tuệ nhân tạo, thiết kế thuật toán hoặc lập trình hệ thống cấp thấp.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng người học nào?

Giáo trình được thiết kế cho sinh viên đại học khối ngành Công nghệ thông tin, Khoa học máy tính và Kỹ thuật phần mềm đang theo học các học phần nền tảng về Toán rời rạc và Cấu trúc dữ liệu.

2. Người học cần chuẩn bị kiến thức nền tảng gì trước khi học?

Người học cần có kiến thức đại số sơ cấp bậc trung học phổ thông, hiểu biết về các tập số học cơ bản ($R, N, Z$) và nắm được cấu trúc lệnh điều khiển cơ bản trong một ngôn ngữ lập trình bất kỳ (như lệnh if...then).

3. Giáo trình này có điểm gì khác biệt so với các tài liệu toán học thuần túy?

Tài liệu không dừng lại ở việc chứng minh định lý toán học thuần túy mà luôn ánh xạ các khái niệm (mệnh đề, vị từ, tập hợp) sang các đối tượng tương ứng trong tin học như xâu bit, toán tử bitwise (AND, OR, XOR), thuật toán ALU và dạng chuẩn hội để máy tính xử lý.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả?

Người học cần tự lập lại các bảng chân lý, thực hành tính toán cụ thể trên các xâu nhị phân mẫu, viết mã chương trình mô phỏng các thuật toán cộng/nhân nhị phân và giải quyết các bài toán chứng minh tính tồn tại bằng phản chứng logic.

5. Giáo trình cung cấp những dạng bài tập và dữ liệu mẫu nào?

Tài liệu cung cấp các bài tập về 4 lớp bài toán tổ hợp, bài toán phủ bàn cờ domino, bài tập biến đổi tương đương logic, bài tập thao tác cấp bit trên xâu nhị phân độ dài bất kỳ và các phép toán trên tập con của tập vũ trụ hữu hạn.

---

Kết luận

Nội dung giáo trình thiết lập cơ sở lý thuyết toán học hoàn chỉnh cho ngành khoa học máy tính thông qua việc tích hợp 4 mảng kiến thức: lý thuyết tổ hợp và phân loại bài toán, logic mệnh đề - vị từ và dạng chuẩn tắc, ứng dụng phép toán bit và thuật toán số học nhị phân, cùng lý thuyết tập hợp và tích Đề-các.

Lộ trình học tập được khuyến nghị triển khai theo trình tự:

1. Nghiên cứu 4 lớp bài toán tổ hợp (Đếm, Tồn tại, Liệt kê, Tối ưu).
2. Xây dựng nền tảng logic mệnh đề, bảng chân lý và biến đổi dạng chuẩn hội.
3. Mở rộng sang logic vị từ, lượng từ và liên hệ với lệnh điều kiện lập trình.
4. Thực hành tính toán trên xâu bit, thuật toán cộng và nhân số nguyên nhị phân.
5. Hoàn thiện lý thuyết tập hợp, tập lũy thừa $2^A$, các phép toán tập hợp và tích Đề-các theo René Descartes.

Tài liệu là nguồn tham khảo phục vụ trực tiếp cho các học phần tiếp theo như Cấu trúc dữ liệu và giải thuật, Kiến trúc máy tính, Lý thuyết độ phức tạp tính toán và Cơ sở dữ liệu quan hệ.

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

Chương 1 Kiến thức cơ bản tổ hợp, Logic mệnh đề, Tập hợp, và Ánh xạ Nội dung  Bài toán tổ hợp  Logic mệnh đề  Logic vị từ và lượng từ  Một số ứng dụng trong tin học  Lý thuyết tập hợp và ứng dụng  Ánh xạ Lí thuyết tổ hợp  Lý thuyết tổ hợp gắn liền với việc nghiên cứu sự sắp xếp của các phần tử trong các tập hữu hạn và sự phân bố của các phần tử vào các tập hữu hạn. Mỗi cách sắp xếp hoặc phân bố như thế được gọi là một cấu hình tổ hợp.  Có thể nói vắn tắt: Tổ hợp là lý thuyết về các tập hữu hạn. Bài toán tổ hợp  Trong các tài liệu về tổ hợp, thường gặp các dạng bài toán dưới đây: 1.

Bài toán đếm tổ hợp (Counting Problem) 2. Bài toán tồn tại tổ hợp (Existence Problem) 3. Bài toán liệt kê tổ hợp (Enumeration Problem) 4. Bài toán tối ưu tổ hợp (Combinatorial optimization Problem) Bài toán đếm – Counting Problem  Đây là các bài toán nhằm trả lời câu hỏi: “Có bao nhiêu cấu hình thoả mãn các điều kiện cho trước?".

 Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấu hình đơn giản.  Bài toán đếm được áp dụng một cách có hiệu quả vào những công việc mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phức tạp của một thuật toán,. Bài toán tồn tại tổ hợp (Existence Problem)  Khác với bài toán đếm, trong bài toán tồn tại tổ hợp chúng ta cần trả lời câu hỏi: “Tồn tại hay chăng cấu hình tổ hợp thoả mãn các tính chất đã cho?”  Rõ ràng nếu có thể đếm được số lượng cấu hình tổ hợp thoả mãn các tính chất đó cho thì ta cũng giải quyết được bài toán tồn tại tương ứng!  Có thể coi bài toán tồn tại như trường hợp riêng của bài toán đếm được không? Ví dụ  Bài toán phủ bàn cờ quốc tế bởi các quân bài domino: “Cho bàn cờ quốc tế kích thước 88 bị đục đi 2 ô ở hai góc đối diện và bộ bài domino, mỗi quân bài phủ kín 2 ô của bàn cờ. Hỏi có thể phủ kín bàn cờ đã cho bởi 31 quân bài domino?” Bàn cờ quốc tế và quân bài domino Bàn cờ quốc tế và quân bài domino Có thể phủ bàn cờ như vậy bởi 31 quân bài domino?  Bàn cờ còn 62 ô  31 quân bài có thể phủ kín được 62 ô  Về diện tích là có thể phủ được Không tồn tại cách phủ bàn cờ như vậy bởi 31 quân bài domino!  Chứng minh  Mỗi quân bài phủ kín 1 ô trắng và một ô đen.

 Suy ra số lượng ô trắng và ô đen bị phủ bởi 31 quân domino là bằng nhau.  Thế nhưng số lượng ô trắng và ô đen trên phần còn lại của bàn cờ là khác nhau  Từ đó suy ra không tồn tại cách phủ! Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino?  Sự tồn tại cách phủ là hiển nhiên. Dễ dàng có thể chỉ ra vài cách phủ  Vấn đề “Có bao nhiêu cách phủ?”  Không dễ dàng trả lời! Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino?  Nếu chỉ phân biệt hai cấu hình bởi dạng hình học của cách phủ thì có tất cả 12 988 816 cách phủ. Có 2 cách phủ bàn cờ kích thước 22 Phân biệt hai bài toán đếm và tồn tại  Trong bài toán đếm, sự tồn tại cấu hình là hiển nhiên và vấn đề là cần đếm xem có bao nhiêu.

 Trong bài toán tồn tại, bản thân sự tồn tại cấu hình là vấn đề nghi vấn. Cần giải quyết vấn đề “có hay không có” cấu hình như vậy.  Việc chỉ ra được một cấu hình là đủ để khẳng định là tồn tại  Nhưng để chỉ ra sự không tồn tại cấu hình đòi hỏi phải đưa ra những lập luận tin cậy Bài toán liệt kê tổ hợp (Enumeration Problem) Bài toán liệt kê: bài toán liệt kê quan tâm đến tất cả các cấu hình có thể có được,  Lời giải của nó được biểu diễn dưới dạng thuật toán “vét cạn” tất cả các cấu hình.  Bài toán liệt kê thường được làm nền cho nhiều bài toán khác.

Hiện nay, một số bài toán tồn tại, bài toán tối ưu, bài toán đếm vẫn chưa có cách nào giải quyết ngoài phương pháp liệt kê.  Phương pháp liệt kê càng trở nên quan trọng hơn khi nó được hỗ trợ bởi các hệ thống máy tính. Bài toán tối ưu tổ hợp (Combinatorial Problem)  Khác với bài bài toán liệt kê, bài toán tối ưu chỉ quan tâm đến một cấu hình "tốt nhất" theo một nghĩa nào đấy.  Trong các bài toán tối ưu, mỗi cấu hình được gán cho một giá trị số (là giá trị sử dụng hoặc chi phí xây dựng cấu hình), và bài toán đặt ra là trong số những cấu hình thoả mãn các điều kiện cho trước hãy tìm cấu hình với giá trị số gán cho nó là lớn nhất hoặc nhỏ nhất.

 Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng được những thuật toán hữu hiệu. Nội dung  Bài toán tổ hợp  Logic mệnh đề  Logic vị từ và lượng từ.  Một số ứng dụng trong tin học  Lý thuyết tập hợp và ứng dụng  Ánh xạ Logic mệnh đề Đối tượng nghiên cứu của logic là các mệnh đề. Một mệnh đề được hiểu là một câu khẳng định hoặc đúng hoặc sai chứ không thể vừa đúng vừa sai.

Ví dụ: Những câu khẳng định sau đây là một mệnh đề:  “Hà nội là thủ đô của Việt nam.”  1 + 1 = 2  2 + 2 = 3 Định nghĩa và phép toán Định nghĩa và phép toán (tiếp) Định nghĩa và phép toán (tiếp) Bảng chân lý các phép toán Tương đương giữa các mệnh đề Vấn đề thay thế một mệnh đề bằng một mệnh đề khác có cùng giá trị chân lý. Hai mệnh đề có cùng một giá trị chân lý hiểu theo cách thông thường là chúng tương đương nhau về ngữ nghĩa. Do vậy, ta sẽ tiếp cận và phân loại các mệnh đề phức hợp thông qua các giá trị chân lý của chúng. Một mệnh đề phức hợp luôn luôn đúng với bất kể các giá trị chân lý của các mệnh đề thành phần được gọi là hằng đúng (tautology).

Một mệnh đề luôn luôn sai với mọi giá trị chân lý của các mệnh đề thành phần được gọi là mâu thuẫn. Tương đương giữa các mệnh đề (tiếp) Bảng các tương đương logic mệnh đề Dạng chuẩn tắc  Các công thức (mệnh đề) tương đương được xem như các biểu diễn khác nhau của cùng một mệnh đề. Để dễ dàng viết các chương trình máy tính thao tác trên các công thức, chúng ta cần chuẩn hóa các công thức, đưa chúng về dạng biểu diễn chuẩn được gọi là dạng chuẩn hội. Một công thức được gọi là ở dạng chuẩn hội nếu nó là hội của các mệnh đề tuyển.

Phương pháp để biến đổi một công thức bất kỳ về dạng chuẩn hội bằng cách áp dụng các thủ tục sau: Nội dung  Bài toán tổ hợp  Logic mệnh đề  Logic vị từ và lượng từ  Một số ứng dụng trong tin học  Lý thuyết tập hợp và ứng dụng  Ánh xạ Vị từ Trong toán học hay trong các chương trình máy tính chúng ta rất hay gặp những khẳng định chưa phải là một mệnh đề. Những khẳng định đó đều có liên quan đến các biến. Chẳng hạn khẳng đinh:  P(x) = “x > 3” không phải là một mệnh đề nhưng tại những giá trị cụ thể của x=x0 nào đó thì P(x0) lại là một mệnh đề. Hoặc trong những đoạn chương trình gặp câu lệnh:  if ( x > 3 ) then x:= x +1; thì chương trình sẽ đặt giá trị cụ thể của biến x vào P(x), nếu mệnh đề P(x) cho giá trị đúng x sẽ được tăng lên 1 bởi câu lệnh x:=x+1, P(x) có giá trị sai giá trị của x được giữ nguyên sau khi thực hiện câu lệnh if.

Vị từ (tiếp) Tổng quát, giả sử M là một tập hợp các phần tử nào đó. M thường được gọi là trường hay miền xác định của các phẩn tử thuộc M. Khi đó, biểu thức P(x) gọi là vị từ xác định trên trường M nếu khi thay x bởi một phần tử bất kỳ của trường M thì P(x) sẽ trở thành một mệnh đề trên trường M. Lượng từ Khi tất cả các biến của hàm mệnh đề đều được gán những giá trị cụ thể, thì mệnh đề tạo ra sẽ xác định giá trị chân lý.

Tuy nhiên, có một phương pháp quan trọng khác để biến một hàm mệnh đề thành một mệnh đề mà không cần phải kiểm chứng mọi giá trị chân lý của hàm mệnh đề tương ứng với các giá trị của biến thuộc trường đang xét. Phương pháp đó gọi là sự lượng hoá hay lượng từ. Nội dung  Bài toán tổ hợp  Logic mệnh đề  Logic vị từ và lượng từ  Một số ứng dụng trong tin học  Lý thuyết tập hợp và ứng dụng  Ánh xạ Ứng dụng mệnh đề logic trên máy tính Các phép toán bít: Các hệ thống máy tính thường dùng các bit (binary digit) để biểu diễn thông tin. Một bít có hai giá trị chân lý hoặc 0 hoặc 1.

Vì giá trị chân lý của một biểu thức logic cũng có hai giá trị hoặc đúng (T) hoặc sai (F). Nếu ta coi giá trị đúng có giá trị 1 và giá trị sai là 0 thì các phép toán với các bít trong máy tính được tương ứng với các liên từ logic. Một xâu bít (hoặc xâu nhị phân) là dãy không hoặc nhiều bít. Chiều dài của xâu là số các bít trong xâu đó.

Ví dụ xâu nhị 101010011 có độ dài là 9. Một số nguyên đuợc biểu diễn như một xâu nhị phân có độ dài 16 bít. Các phép toán với bít được xây dựng trên các xâu bít có cùng độ dài, bao gồm : AND bít (phép và cấp bít), OR (phép hoặc cấp bít), XOR (phép tuyển loại trừ cấp bít). Ví dụ: cho hai xâu bít 01101 10110 và 11000 11101 hãy tìm xâu AND bít, OR bít, XOR bít.

Ứng dụng mệnh đề logic trên máy tính (tiếp) Thuật toán các phép tính số nguyên: Các thuật toán thực hiện các phép tính với các số nguyên khi dùng khai triển nhị phân là hết sức quan trọng trong bộ xử lý số học của máy tính.