ĐẶT VẤN ĐỀ
Trong chuyên đề này ta sẽ xét các bài toán mà đối tượng nghiên cứu là các đại lượng rời rạc. Trong cuộc sống ta có thể hiểu các hiện tượng rời rạc là những hiện tượng mà giữa các thời điểm xuất hiện cần có một khoảng thời gian nào đó. Trong toán học ta có thể định nghĩa các đại lượng rời rạc như sau:
Định nghĩa 1. Phần tử \(x \in A\) được gọi là phần tử rời rạc của tập \(A\) nếu:
\[ \exists \epsilon > 0, \text{đủ bé, sao cho } V(x; \epsilon) \cap A = \{x\} \]trong đó ta ký hiệu \(V(x; \epsilon) := (x - \epsilon; x + \epsilon)\) và gọi là \(\epsilon\)-lân cận của điểm \(x\).
Định nghĩa 2. Tập \(A\) được gọi là tập rời rạc nếu nó chỉ gồm các phần tử rời rạc. Các phần tử của tập rời rạc cũng được gọi là các phần tử rời rạc nhau.
Chẳng hạn các tập: \(\mathbb{N}\), \(\mathbb{Z}\), \(\overline{0..9} := \{0; 1; 2; 3; 4; 5; 6; 7; 8; 9\}\), ... là những tập rời rạc.
Toán rời rạc nghiên cứu các tập rời rạc cũng như các phần tử của tập rời rạc. Vì các khái niệm của Giải tích như giới hạn, đạo hàm, nguyên hàm, tích phân cũng như các hàm số sơ cấp được học trong chương trình phổ thông chỉ được áp dụng cho các hàm số liên tục nên trong Toán rời rạc không thể áp dụng các phương pháp và kiến thức của Giải tích (Trừ một số trường hợp đặc biệt).
1. PHƯƠNG PHÁP PHẢN CHỨNG
1.1. Tiểu dẫn
Phương pháp phản chứng có lẽ là một trong những phương pháp chứng minh sớm nhất mà loài người đã biết đến, đặc biệt trong nghệ thuật diễn thuyết và tranh luận. Trong Toán học, phương pháp phản chứng (FC hay là CM: Contra-Method) cũng là một phương pháp rất thường được sử dụng, đặc biệt khi cần chứng minh tính duy nhất của một đối tượng \(T\) nào đó thoả mãn điều kiện \((*)\) cho trước (mà sự tồn tại của \(T\) đã được chứng minh trước đó) ta thường giả sử còn \(\forall T' \neq T\), \(T'\) cũng thoả mãn điều kiện \((*)\), từ đó suy ra một điều vô lý. Vậy điều giả sử của chúng ta là sai, tức là \(T\) duy nhất.
1.2. Cơ sở lý thuyết
Cơ sở lý thuyết của phương pháp FC là các định luật trong Logic: Gọi \(p; q; r\) là các mệnh đề toán học nào đó thì:
Định lý 1 (Các định luật cơ bản).
1. (Phi mâu thuẫn): \(p \ \& \ \bar{p} \equiv F\)
2. (Bài trung): \(p \text{ hoặc } \bar{p} \equiv T\)
Định lý 2 (Các định luật phản chứng).
1. (Phản chứng): \(\models (p \Rightarrow q) \Leftrightarrow (\bar{q} \Rightarrow \bar{p})\).
2. (Phản chứng suy rộng):
\[ \models \left( \begin{cases} p \\ q \end{cases} \Rightarrow r \right) \Leftrightarrow \left( \begin{cases} p \\ \bar{r} \end{cases} \Rightarrow \bar{q} \right) \quad (\alpha) \]3. \(\models (p \Rightarrow q \ \& \ \bar{q}) \Rightarrow \bar{p}\).
4. \(\models (\bar{q} \Rightarrow F) \Rightarrow q\).
Chứng minh định luật phản chứng suy rộng \((\alpha)\):
Các định luật trên có thể được chứng minh chẳng hạn bằng phương pháp lập bảng giá trị chân lý hoặc phương pháp biến đổi tương đương. Chẳng hạn, ta có thể chứng minh \((\alpha)\) như sau:
\[ \begin{aligned} (p \ \& \ q \Rightarrow r) &\Leftrightarrow \bar{p} \text{ hoặc } \bar{q} \text{ hoặc } r \quad (\text{do } a \Rightarrow b \Leftrightarrow \bar{a} \text{ hoặc } b) \\ &\Leftrightarrow \bar{p} \text{ hoặc } \bar{r} \text{ hoặc } \bar{q} \quad (\text{do } \bar{a} \ \& \ \bar{b} \Leftrightarrow \bar{a} \text{ hoặc } \bar{b}) \\ &\Leftrightarrow (\bar{p} \text{ hoặc } \bar{r}) \text{ hoặc } \bar{q} \quad (\text{giao hoán, kết hợp và } \bar{\bar{r}} \Leftrightarrow r) \\ &\Leftrightarrow \overline{p \ \& \ \bar{r}} \text{ hoặc } \bar{q} \\ &\Leftrightarrow (p \ \& \ \bar{r} \Rightarrow \bar{q}) \quad (\text{đpcm}). \end{aligned} \]1.3. Nội dung phương pháp phản chứng
Để chứng minh khẳng định: \(p \Rightarrow q \quad (\alpha)\) bằng phương pháp phản chứng ta giả sử \(q\) sai (tức là \(\bar{q}\) là mệnh đề đúng). Nếu từ đó thu được một điều vô lý (\(vl\)) thì điều đó chứng tỏ giả sử là sai, tức là khẳng định đúng.