Chương 4 · Tập hợp & Logic

第だい4章しょう 集合しゅうごうと論理ろんり — Tập hợp & Logic

Nền tảng tư duy toán học. Hiểu tập hợp, mệnh đề, điều kiện cần & đủ giúp diễn đạt và chứng minh chặt chẽ — kỹ năng then chốt cho đề thi tự luận.
13

§1 集合しゅうごう — Tập hợp & phép toán tập hợp Định nghĩa, phần tử, bao hàm, hợp, giao, hiệu, phần bù, công thức đếm

Tập hợp & phần tử

Tập hợp (集合しゅうごう): một nhóm các đối tượng xác định rõ ràng. Mỗi đối tượng là một phần tử (要素ようそ).

Ký hiệu: $a \in A$ ($a$ là phần tử của $A$), $a \notin A$.

Hai cách viết: liệt kê $A = \{1, 2, 3\}$ hoặc chỉ tính chất $A = \{x \mid x^2 \le 9\}$.

Tập rỗng: $\varnothing$ (không có phần tử nào).

Quan hệ bao hàm (包含ほうがん関係かんけい)

$A \subset B$ (A là tập con của B): mọi phần tử của $A$ đều thuộc $B$.

$A = B \iff A \subset B$ và $B \subset A$.

Tập rỗng $\varnothing$ là tập con của mọi tập hợp.

Số tập con của tập có $n$ phần tử: $2^n$. Trong đó số tập con có $k$ phần tử là $\binom{n}{k}$.

Các phép toán tập hợp

Hợp: $A \cup B = \{x \mid x \in A \text{ hoặc } x \in B\}$.

Giao: $A \cap B = \{x \mid x \in A \text{ và } x \in B\}$.

Hiệu: $A \setminus B = \{x \mid x \in A \text{ và } x \notin B\}$.

Phần bù trong U: $\overline{A} = U \setminus A$.

Định luật De Morgan (ド・モルガンの法則ほうそく):

$\overline{A \cup B} = \overline{A} \cap \overline{B}$  ,  $\overline{A \cap B} = \overline{A} \cup \overline{B}$
U A B A ∪ B (hợp) $A \cup B$: vùng được tô phủ.
U A B A ∩ B (giao) $A \cap B$: phần chung của hai tập.
U A B A \ B (hiệu) $A \setminus B$: phần thuộc A mà không thuộc B.
U A Ā Phần bù Ā $\overline{A}$: phần ngoài $A$ trong $U$.
Công thức đếm số phần tử (cực kỳ hay thi)
$|A \cup B| = |A| + |B| - |A \cap B|$
$|A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$

(Nguyên lý bao hàm – loại trừ / Inclusion-Exclusion / 包ほう除じょ原理げんり)

VÍ DỤ 1 Bài toán đếm
Lớp có 40 học sinh, 25 em học giỏi Toán, 20 em học giỏi Anh, 8 em không giỏi cả hai môn. Hỏi bao nhiêu em giỏi cả hai môn?
LỜI GIẢI
B1 Gọi $T$ = giỏi Toán, $A$ = giỏi Anh. $|T| = 25, |A| = 20$.
B2 Số em giỏi ít nhất 1 môn: $40 - 8 = 32 = |T \cup A|$.
B3 $|T \cap A| = |T| + |A| - |T \cup A| = 25 + 20 - 32 = 13$.
13 học sinh giỏi cả 2 môn.

Bài tập tự luyện — Bài 13

13.1. Cho $A = \{1,2,3,4,5,6\}, B = \{2,4,6,8,10\}, U = \{1,2,\dots,12\}$. Tìm $A \cup B, A \cap B, A \setminus B, \overline{A \cap B}$.
$A \cup B = \{1,2,3,4,5,6,8,10\}$. $A \cap B = \{2,4,6\}$. $A\setminus B = \{1,3,5\}$.
$\overline{A \cap B} = U \setminus \{2,4,6\} = \{1,3,5,7,8,9,10,11,12\}$.
14

§2 命題めいだいと論理ろんり — Mệnh đề · Điều kiện cần & đủ · Chứng minh Mệnh đề, phủ định, kéo theo, đảo, phản đảo, phản chứng, quy nạp

Mệnh đề (命題めいだい)

Mệnh đề: câu khẳng định có giá trị xác định là đúng (真しん) hoặc sai (偽にせ).

Mệnh đề chứa biến (条件じょうけん): ví dụ $P(x)$: "$x > 0$" — chỉ là mệnh đề khi gán giá trị cụ thể cho $x$.

Phép phủ định: $\overline{P}$ (hay $\neg P$). $P$ đúng ⟺ $\overline{P}$ sai.

Quy tắc phủ định
$\overline{P \text{ và } Q} = \overline{P} \text{ hoặc } \overline{Q}$ (De Morgan)
$\overline{P \text{ hoặc } Q} = \overline{P} \text{ và } \overline{Q}$
$\overline{\forall x, P(x)} = \exists x, \overline{P(x)}$
$\overline{\exists x, P(x)} = \forall x, \overline{P(x)}$

Ví dụ: phủ định "$x > 0$" là "$x \le 0$" (không phải $x < 0$!). Phủ định "$x = 2$" là "$x \ne 2$".

Mệnh đề kéo theo & điều kiện cần – đủ

$P \Rightarrow Q$ ("P kéo theo Q"): nếu $P$ đúng thì $Q$ đúng. $P$ chỉ sai khi $P$ đúng và $Q$ sai.

Khi $P \Rightarrow Q$ đúng:

• $P$ là điều kiện đủ (十じゅう分ふん条件じょうけん) cho $Q$.
• $Q$ là điều kiện cần (必要ひつよう条件じょうけん) cho $P$.

Khi cả $P \Rightarrow Q$ và $Q \Rightarrow P$ đúng (ký hiệu $P \iff Q$): $P$ là điều kiện cần và đủ (必要ひつよう十じゅう分ふん条件じょうけん) cho $Q$ (và ngược lại).

Mệnh đề đảo, mệnh đề phản đảo
TênDạngQuan hệ với P⇒Q
Mệnh đề thuận$P \Rightarrow Q$—
Mệnh đề đảo (逆ぎゃく)$Q \Rightarrow P$không tương đương
Mệnh đề phủ định (裏うら)$\overline{P} \Rightarrow \overline{Q}$không tương đương
Mệnh đề phản đảo (対偶たいぐう)$\overline{Q} \Rightarrow \overline{P}$tương đương với $P \Rightarrow Q$

Định lý quan trọng: Để chứng minh $P \Rightarrow Q$, có thể chứng minh phản đảo $\overline{Q} \Rightarrow \overline{P}$ — đây là phương pháp đối ngẫu (対偶たいぐう証明しょうめい).

VÍ DỤ 1 Cần và đủ
Cho $P$: "$x > 2$", $Q$: "$x > 1$". Xét quan hệ giữa $P$ và $Q$.
LỜI GIẢI
B1 $P \Rightarrow Q$: "$x > 2 \Rightarrow x > 1$" — đúng.
B2 $Q \Rightarrow P$: "$x > 1 \Rightarrow x > 2$" — sai (vd $x = 1.5$).
$P$ là điều kiện đủ nhưng không cần cho $Q$. $Q$ là điều kiện cần nhưng không đủ cho $P$.
Các phương pháp chứng minh
5 phương pháp chứng minh chính

1. Chứng minh trực tiếp: Từ giả thiết suy ra kết luận bằng biến đổi tương đương.

2. Chứng minh phản đảo (対偶たいぐう): Chứng minh $\overline{Q} \Rightarrow \overline{P}$ thay vì $P \Rightarrow Q$. Dùng khi $\overline{Q}$ dễ thao tác hơn $P$.

3. Chứng minh phản chứng (背理はいり法ほう): Giả sử kết luận sai, suy ra mâu thuẫn → kết luận đúng.

4. Quy nạp toán học (数学すうがく的てき帰納きのう法ほう): Chứng minh: (i) đúng với $n=1$; (ii) nếu đúng với $n=k$ thì đúng với $n=k+1$ → đúng mọi $n$.

5. Chứng minh bằng phản ví dụ (反例はんれい): Để bác bỏ "$\forall x, P(x)$", chỉ cần đưa ra 1 ví dụ vi phạm.

VÍ DỤ 2 Phản chứng kinh điển: $\sqrt{2}$ vô tỉ
Chứng minh $\sqrt{2}$ là số vô tỉ.
LỜI GIẢI (phản chứng)
B1 Giả sử $\sqrt{2}$ hữu tỉ → $\sqrt{2} = \dfrac{p}{q}$ với $p, q \in \mathbb{Z}^+$, $\gcd(p,q) = 1$.
B2 Bình phương: $2q^2 = p^2$ → $p^2$ chẵn → $p$ chẵn. Đặt $p = 2k$.
B3 Thay vào: $2q^2 = 4k^2 \Rightarrow q^2 = 2k^2$ → $q^2$ chẵn → $q$ chẵn.
B4 Cả $p, q$ đều chẵn → $\gcd(p,q) \ge 2$, mâu thuẫn với $\gcd = 1$.
Vậy $\sqrt{2}$ là số vô tỉ. ∎
Dùng phản chứng khi: đề có từ "không tồn tại", "vô tỉ", "không thể", "duy nhất".
Dùng phản đảo khi: kết luận có dạng phủ định ("$x \ne 0$", "không chia hết") — phủ định kết luận ra giả thiết thuận tay hơn.
Dùng quy nạp khi: mệnh đề về tất cả số tự nhiên $n$ (tổng, tích, chia hết, bất đẳng thức theo $n$).

Bài tập tự luyện — Bài 14

14.1. Xét quan hệ giữa $P$: "$x^2 = 1$" và $Q$: "$x = 1$".
$P \Rightarrow Q$: sai (vì $x = -1$ thỏa $P$ nhưng không thỏa $Q$).
$Q \Rightarrow P$: đúng.
Vậy $Q$ là điều kiện đủ nhưng không cần cho $P$; $P$ là điều kiện cần nhưng không đủ cho $Q$.
14.2. Phủ định mệnh đề: "$\forall x \in \mathbb{R}, x^2 + 1 > 0$".
Phủ định: "$\exists x \in \mathbb{R}, x^2 + 1 \le 0$". (Mệnh đề phủ định này sai, mệnh đề gốc đúng.)
14.3. Dùng phản đảo chứng minh: "Nếu $n^2$ chẵn thì $n$ chẵn".
Phản đảo: "Nếu $n$ lẻ thì $n^2$ lẻ".
Giả sử $n$ lẻ → $n = 2k+1$ → $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$ là lẻ. ∎