Luận Lý Toán Học

1. Khái niệm
Luận lý là khoa học về lý luận, đặc biệt là lý luận đúng.
Luận lý toán học khảo sát sự quan hệ của những mệnh đề, không khảo sát ý nghĩa của nó.
Phương pháp luận lý được dùng trong toán học để chứng minh những định lý.
Luận lý toán học rất đa dạng, ta chỉ khảo sát dạng cổ điển là luận lý mệnh đề, luận lý vị từ, và phương pháp chứng minh.
2. Luận lý mệnh đề
2.1 Giá trị
Giá trị của luận lý cổ điển là đúng (đ) hoặc sai (s).
2.2 Mệnh đề
2.2.1 Định nghĩa: Mệnh đề là một câu phát biểu có giá trị đúng hay sai, không cả hai. Mệnh đề còn được gọi là một công thức.
2.2.2 Thí dụ:
a) Hà Nội là thủ đô của Việt Nam.
b) Sàigon là thủ đô của Việt Nam.
c) x + 2 = 5.
d) Mấy giờ rồi?    
Câu a là mệnh đề đúng. Câu b là mệnh đề sai. Câu c không phải là mệnh đề vì nó không đúng hay sai, biến số x trong câu chưa được xác định. Câu d không phải là mệnh đề vì nó không là một câu phát biểu.
2.3 Mệnh đề đơn
2.3.1 Định nghĩa: Mệnh đề đơn là một mệnh đề độc lập, đơn thuần, không có bất kỳ một liên từ nào.
2.3.2 Ký hiệu: Ta dùng chữ thường như p, q, r, ... để ký hiệu một mệnh đề đơn.
2.3.3 Ví dụ: Cho mệnh đề đơn p như sau:
         p: 1 + 2 = 3
2.4 Các phép toán mệnh đề
2.4.1 Định nghĩa: Các phép toán mệnh đề dùng để kết hợp những mệnh đề đơn thành những mệnh đề phức.
Ta dùng chữ hoa như P, Q, R, ... để ký hiệu mệnh đề phức.
2.4.2 Ứng với năm liên từ mệnh đề trong ngôn ngữ thông thường, ta có năm phép toán mệnh đề trong luận lý toán học.
2.4.3 Phép phủ định, ký hiệu ~, là phép toán cấp 1, được dùng với một mệnh đề.
2.4.4 Phép hội, ký hiệu ∧, là phép toán cấp 2, được dùng với hai mệnh đề. 
2.4.5 Phép tuyển, ký hiệu v, là phép toán cấp 2, được dùng với hai mệnh đề.
2.4.6 Phép điều kiện, ký hiệu =>, là phép toán cấp 2, được dùng với hai mệnh đề.
2.4.7 Phép tương đương, ký hiệu <=>, là phép toán cấp 2, được dùng với hai mệnh đề.
2.5 Bảng thực trị
Bảng thực trị của mệnh đề phức P, gồm những mệnh đề đơn p1, ..., pn, liệt kê tất cả những kết hợp của những giá trị (đ, s) của p1, ..., pn, và cho mỗi kết hợp một giá trị (đ, s) của P.
2.6 Phép phủ định
2.6.1 Định nghĩa: Cho một mệnh đề p. Phủ định của p, ký hiệu ~p, là mệnh đề không p.
2.6.2 Bảng thực trị: Giá trị của mệnh đề ~p được định nghĩa trong bảng thực trị sau.
                              p     ~p                                              
                              đ       s
                              s       đ
                             
Mệnh đề ~p đúng nếu p sai; ~p sai nếu p đúng.
2.6.3 Ví dụ:
Cho p : Hà Nội là thủ đô của Việt Nam, thì ~p : Hà Nội không là thủ đô của Việt Nam.
Vậy, p đúng, ~p sai.
2.7 Phép hội
2.7.1 Định nghĩa: Cho hai mệnh đề p, q. Hội của p và q, ký hiệu p∧q, là mệnh đề p và q.
2.7.2 Bảng thực trị: Giá trị của mệnh đề p∧q được định nghĩa trong bảng thực trị sau.
                               p     q     p∧q 
                              đ      đ        đ
                              đ      s         s
                              s      đ         s
                              s      s         s
Mệnh đề p∧q đúng nếu cả hai phần tử đúng; sai trong những trường hợp khác.
2.7.3 Ví dụ:
Nếu
p: 2 + 2 = 5.
q: Hà Nội là thủ đô của Việt Nam.
thì p sai, q đúng.
Đó là, p∧q: 2 + 2 = 5 và Hà Nội là thủ đô của Việt Nam.
Vậy, p∧q là sai.
2.8 Phép tuyển
2.8.1 Định nghĩa: Cho hai mệnh đề p, q. Tuyển của p và q, ký hiệu pvq, là mệnh đề p hoặc q.
2.8.2 Chú ý:
Trong ngôn ngữ hàng ngày thì từ hoặc được dùng theo hai nghĩa khác nhau. Với nghĩa thứ nhất thì pvq đúng nếu ít nhất một trong hai phần tử đúng; với nghĩa thứ hai thì pvq đúng nếu một trong hai phần tử đúng.
Trong toán học thì từ hoặc được dùng với nghĩa thứ nhất.
2.8.3 Bảng thực trị: Giá trị của mệnh đề pvq được định nghĩa trong bảng thực trị sau.
                               p     q      pvq 
                              đ      đ        đ
                              đ      s        đ
                              s      đ        đ
                              s      s         s
Mệnh đề pvq đúng nếu ít nhất một trong hai phần tử đúng; sai trong những trường hợp khác.
2.8.4 Ví dụ:
Nếu
p: 2 + 2 = 5.
q: Hà Nội là thủ đô của Việt Nam.
thì p sai, q đúng.
Đó là, pvq: 2 + 2 = 5 hoặc Hà Nội là thủ đô của Việt Nam.
Vậy, pvq là đúng.
2.9 Phép điều kiện
2.9.1 Định nghĩa: Cho hai mệnh đề p, q. Điều kiện của p và q, ký hiệu p=>q, là mệnh đề nếu p thì q.
2.9.2 Bảng thực trị: Giá trị của mệnh đề p=>q được định nghĩa trong bảng thực trị sau.
                               p     q     p=>q 
                              đ      đ       đ
                              đ      s       s
                              s      đ       đ
                              s      s       đ
Mệnh đề p=>q sai nếu và chỉ nếu phần tử p đúng và phần tử q sai;
đúng trong những trường hợp khác.
2.9.3 Ví dụ:
Nếu
p: Tôi có tiền.
q: Tôi mua nhà.
thì p đúng, q đúng.
Đó là, p=>q: nếu Tôi có tiền, thì Tôi mua nhà.
Vậy, p=>q là đúng.
2.10 Phép tương đương
2.10.1 Định nghĩa:
Cho hai mệnh đề p, q. Tương đương của p và q, ký hiệu p<=>q, là mệnh đề p nếu và chỉ nếu q.
2.10.2 Bảng thực trị: Giá trị của mệnh đề p<=>q được định nghĩa trong bảng thực trị sau.
                               p     q     p<=>q 
                              đ      đ         đ
                              đ      s          s
                              s      đ          s
                              s      s          đ
Mệnh đề p<=>q đúng, nếu cả hai phần tử p và q đều đúng hoặc đều sai.
2.10.3 Ví dụ:
Nếu
p: Tôi có tiền.
q: Tôi mua nhà.
thì p đúng, q đúng.
Đó là, p=>q: nếu Tôi có tiền, thì Tôi mua nhà.
Hay là, q=>p: nếu Tôi mua nhà, thì Tôi có tiền.
Cả hai câu trên đều đúng.
Ta có thể phát biểu là p<=>q: Tôi có tiền nếu và chỉ nếu Tôi mua nhà.
Vậy, p=>q là đúng.
2.11 Công thức hằng đúng
2.11.1 Định nghĩa: Công thức hằng đúng  là mệnh đề đúng trong mọi truờng hợp.
2.11.2 Ví dụ: [(P => Q) ∧ (Q => R)] => (P => R) là một công thức hằng đúng.
2.11.3 Chú ý: Giá trị đúng của mệnh đề trên là hoàn toàn độc lập với P và Q có đúng hay sai.
Ta có thể lập một công thức hằng đúng bởi một bảng thực trị.
2.12 Quy tắc suy luận
2.12.1 Định nghĩa: Quy tắc suy luận là thay thế mệnh đề đúng vào một công thức hằng đúng.
2.12.2 Ví dụ:
Tất cả những con chó là vật sống.
Tất cả những vật sống có thể di chuyển.
Do đó, tất cả những con chó có thể di chuyển.
Sự suy luận này là một sự thay thế vào công thức hằng đúng trong thí dụ 2.11.2 ở trên với:
P = x là một con chó.
Q = x là một vật sống.
R = x có thể di chuyển.
2.13 Công thức hằng sai
2.13.1 Định nghĩa: Công thức hằng sai là mệnh đề sai trong mọi truờng hợp.
2.13.2 Ví dụ: P ∧ ~P là một công thức hằng sai.
2.13.3 Chú ý: Công thức hằng sai là phủ định của một công thức hằng đúng, và ngược lại, công thức hằng đúng là phủ định của một công thức hằng sai.
3. Luận lý vị từ
3.1 Khái niệm
Mệnh đề trong luận lý mệnh đề thường không có khả năng diễn tả những mệnh đề toán học.
Ví dụ:
Câu khai báo p: n là một số nguyên chẵn.
Câu khai báo p không phải là mệnh đề, vì p đúng hay sai còn tuỳ thuộc vào giá trị của n.
Nếu n = 1 thì p sai, nếu n = 2 thì p đúng.
Hầu hết những câu khai báo trong toán học đều dùng biến, ta phải mở rộng luận lý toán học để gồm những câu khai báo có biến ở trên.
3.2 Định nghĩa: Vị từ còn được gọi là hàm mệnh đề.
3.2.1 Hàm mệnh đề không biến
Mệnh đề trong luận lý mệnh đề, vì không có biến nên là một hàm mệnh đề không biến.
Ví dụ:
P: 1 + 2 = 3 có giá trị đúng.
3.2.2 Hàm mệnh đề một biến
Cho P(x) là câu khai báo có biến x và D là một tập hợp. Ta gọi P(x) là một hàm mệnh đề đối với D, nếu cho mỗi x trong D, P(x) là một mệnh đề. Ta gọi D là miền (của cuộc nói chuyện) của P(x).
Ví dụ:
Cho P(x): x > 5.
Khi giá trị được gán cho biến x, P(x) có giá trị thực (thực trị) của hàm mệnh đề một biến.
Tìm thực trị của P(4) và P(6)?
Giải:
Cho x = 4 thì P(4): 4 > 5 là mệnh đề sai.
Cho x = 6 thì P(6): 6 > 5 là mệnh đề đúng.
3.3 Các phép toán hàm mệnh đề
3.3.1 Phép phủ định
Cho p(x) là một hàm mệnh đề của biến x trên tập X ≠ ∅. Một phần tử
a∈X thỏa mãn hàm mệnh đề ~p(x) nếu và chỉ nếu mệnh đề ~p(x) đúng. Đó là:
Với mọi a∈X, a thoả mãn ~p(x) nếu và chỉ nếu a không thỏa mãn p(x)
3.3.2 Phép hội
Cho p(x) và q(x) là hai hàm mệnh đề một biến x trên tập X. Một phần tử a∈X thỏa mãn hàm mệnh đề
p(x) ∧ q(x) nếu và chỉ nếu mệnh đề p(a) ∧ q(a) đúng. Đó là:
Với mọi a∈X, a thoả mãn p(x) ∧ q(x) nếu và chỉ nếu a thỏa mãn p(x) và q(x).
3.3.3 Phép tuyển
Cho p(x) và q(x) là hai hàm mệnh đề một biến x trên tập X. Một phần tử a∈X thỏa mãn hàm mệnh đề
p(x) v q(x) nếu và chỉ nếu mệnh đề p(a) v q(a) đúng. Đó là: 
Với mọi a∈X, a thoả mãn p(x) v q(x) nếu và chỉ nếu a thỏa mãn p(x) và q(x).
3.3.4 Phép điều kiện
Cho p(x) và q(x) là hai hàm mệnh đề một biến x trên tập X. Một phần tử a∈X thỏa mãn hàm mệnh đề
p(x) => q(x) nếu và chỉ nếu mệnh đề p(a) => q(a) đúng. Đó là:
Với mọi a∈X, a thoả mãn p(x) => q(x) nếu và chỉ nếu a không thỏa mãn p(x) hoặc a thỏa mãn q(x).
3.3.5 Phép tương đương
Cho p(x) và q(x) là hai hàm mệnh đề một biến x trên tập X. Một phần tử a∈X thỏa mãn hàm mệnh đề
p(x) <=> q(x) nếu và chỉ nếu mệnh đề p(a) <=> q(a) đúng. Đó là:
Với mọi a∈X, a thoả mãn p(x) <=> q(x) nếu và chỉ nếu a thỏa mãn
(p(x) => q(x)) và (q(x) => p(x)).
3.3.6 Hàm mệnh đề hai biến
Cho P(x, y) là câu khai báo có biến x và y; D là một tập hợp. Ta gọi P(x, y) là một hàm mệnh đề đối với D, nếu cho mỗi x và y trong D, P(x, y) là một mệnh đề. Ta gọi D là miền (của cuộc nói chuyện) của P(x, y).
Ví dụ:
Cho P(x, y): x = y + 5.
Khi giá trị được gán cho biến x và y, thì P(x, y) có thực trị của hàm mệnh đề hai biến.
Tìm thực trị của P(3, 4) và P(6, 7)?
Giải:
Cho x = 3 và y = 4, thì P(3, 4): 3 = 4 + 5 là mệnh đề sai.
Cho x = 5 và y = 0, thì P(5, 0): 5 = 0 + 5 là mệnh đề đúng.
3.3.7 Hàm mệnh đề ba biến
Cho P(x, y, z) là câu khai báo có biến x, y và z; D là một tập hợp. Ta gọi P(x, y, z) là một hàm mệnh đề đối với D, nếu cho mỗi x, y và z trong D, P(x, y, z) là một mệnh đề. Ta gọi D là miền (của cuộc nói chuyện) của P(x, y, z).
Ví dụ:
Cho P(x, y, z): x + 2y = 3z.
Khi giá trị được gán cho biến x, y và z, thì P(x, y, z) có thực trị của hàm mệnh đề ba biến.
Tìm thực trị của P(0, 0, 1) và P(1, 1, 1)?
Giải:
Cho x = 0, y = 0, và z = 1, thì P(0, 0, 1): 0 + 0 = 3 là mệnh đề sai.
Cho x = 1 , y = 1, và z = 1, thì P(1, 1, 1): 1 + 2 = 3 là mệnh đề đúng.
3.3.8 Hàm mệnh đề n biến
Cho P(x₁, x₂, …, x_n) là câu khai báo có biến x₁, x₂, …, x_n; D là một tập hợp. Ta gọi P(x₁, x₂, …, x_n) là một hàm mệnh đề đối với D, nếu cho mỗi  x₁, x₂, …, x_n trong D, P(x₁, x₂, …, x_n) là một mệnh đề. Ta gọi D là miền (của cuộc nói chuyện) của P(x₁, x₂, …, x_n).
4. Phương pháp chứng minh

4.1. Định nghĩa

4.1.1 Tiên đề: giả thiết cơ sở của các cấu trúc toán học.

4.1.2 Giả thiết: giả thiết của định lý.

4.1.3 Kết luận: kết luận của định lý.

4.1.4 Sự chứng minh: là một dãy mệnh đề liên hệ với nhau bởi những quy tắc luận lý, định nghĩa, định lý, và tiên đề.

4.1.5 Quy tắc suy luận: cách rút ra kết luận từ các khẳng định khác.

4.1.6 Phỏng đoán là một mệnh đề toán học mà giá trị đúng chưa được biết.

4.1.7 Định lý: mệnh đề toán học được chứng minh là đúng.

4.1.8 Bổ đề: Định lý đơn giản dùng chứng minh định lý khác.

4.1.9 Hệ quả: Mệnh đề đúng suy ra từ định lý.

4.1.10 Mệnh đề toán học thường được phát biểu như một điều kiện, P => Q: nếu P thì Q, với P là giả thiết và Q là kết luận.

4.1.11 Theo luận lý, ta có bảng chân trị sau:

P Q P=>Q  ~Q  ~P  ~Q => ~P

T T     T         F    F          T

T F     F         T    F          F

F T     T         F    T          T

F F     T         T    T          T

Đó là, P=>Q và ~Q=>~P là tương đương luận lý.

4.2. Phương pháp:

Cho S là tập vũ trụ, với x ∈ S, P(x) và Q(x) là hai mệnh đề.

4.2.1 Chứng minh trực tiếp P => Q:

Giả sử P đúng, và chứng minh Q đúng.

Ví dụ: Cho x ∈ Z. Nếu 3x -15 chẵn, thì x lẻ.

Chứng minh:

Giả sử 3x -15 chẵn, thì theo định nghĩa 3x -15 = 2k, có k ∈ Z. Vậy,

x = (3x – 15) – (2x -15)

   = 2k – 2x + 15

   = 2(k – x + 7) + 1.

Vì k – x + 7 ∈ Z, nên x lẻ.

4.2.2 Chứng minh gián tiếp P => Q:

Là chứng minh trực tiếp ~Q => ~P.

Giả sử ~Q đúng, và chứng minh ~P đúng.

Ví dụ: Cho x ∈ Z. Nếu 3x -15 chẵn, thì x lẻ.

Chứng minh:

Giả sử x chẵn, thì theo định nghĩa x = 2k, có k ∈ Z. Vậy,

3x – 15 = 3(2k) -15

             = 6k – 15

             = 2(3k – 8) + 1.

Vì 3k – 8 ∈ Z, nên 3x -15 lẻ. Định lý được chứng minh.

4.2.3 Chứng minh rỗng

Khi giả thiết P của P => Q là hằng sai.

Ví dụ: Cho x ∈ R. Nếu x² + 1 < 0, thì x⁵ > 4.

Chứng minh:

Vì x² + 1 > x² > 0, nên x² + 1 < 0 là hằng sai với mọi x ∈ R.

Đó là chứng minh rỗng đúng.

4.2.4 Chứng minh tầm thường

Khi kết luận Q của P => Q là hằng đúng.

Ví dụ: Cho x ∈ R. Nếu x > 0, thì x² + 1 > 0.

Chứng minh:

Vì x² > 0, cho mọi x ∈ R, nên x² + 1 > x² > 0 là hằng đúng.

Đó là chứng minh tầm thường đúng.

4.2.5 Chứng minh phản chứng

Ta có P=>Q và ~Q=>~P tương đương luận lý.

Giả sử P và ~Q đúng, chứng minh trưc tiếp ~Q=>~P thì ~P đúng, tức P sai, mâu thuẫn với giả thiết là P đúng.

Ví dụ: Chứng minh phản chứng: Nếu 3n + 2 lẻ, thì n lẻ.

Chứng minh:

Giả sử 3n + 2 lẻ và n chẵn. Thì n = 2k. Suy ra, 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).

Đó là 3n + 2 chẵn, mâu thuẫn với giả thiết là 3n + 2 lẻ. Định lý được chứng minh.

4.2.6 Chứng minh quy nạp

Chứng minh mệnh đề ∀nP(n) với n∈N.   

a. Phương pháp quy nạp thứ nhất:

Chứng minh P(n) đúng với mọi số tự nhiên n∈N.   

Đó là, (P(1) ∧ ∀n(P(n) → P(n+1))) → ∀nP(n).

Gồm 2 bước:

Bước cơ sở: Chứng minh P(1) là đúng.

Bước quy nạp: Giả sử P(k) đúng với bất kì k∈N, chứng minh P(k+1) đúng.

Ví dụ 1: Chứng minh P(n): 1 + 2 + … + n = n(n+1)/2, với n∈N.

Chứng minh:

Bước cơ sở: P(1) đúng, vì 1 = 1(1+1)/2.

Bước quy nạp: Giả sử P(k) đúng, đó là:

1 + 2 + … + k = k(k+1)/2.

Chứng minh P(k+1) đúng, đó là:

1 + 2 + … + k + (k+1) = (k+1)[(k+1) + 1]/2

                                      = (k+1)(k+2)/2.

Thật vậy, từ giả thiết qui nạp ta có:

1 + 2 + … + k + (k+1) = k(k+1)/2  + (k+1)                                      

                                      = [(k/2) + 1](k+1)

                                      = (k+1)(k+2)/2.

Vậy, P(n) đúng với mọi n∈N.

Ví dụ 2: Chứng minh rằng P(n): 3ⁿ > 8n với mọi n ≥ 3.

Chứng minh:

Bước cơ sở: P(3) đúng, vì 3³ = 27 > 24 = 8.3

Bước quy nạp: Giả sử P(k) đúng, đó là 3^k > 8k.

Chứng minh P(k+1) đúng, đó là 3^(k+1) > 8(k+1).

Thật vậy, 3^(k+1) = 3.3^k. Theo giả thiết qui nạp thì 3^k > 8k nên 3^(k+1) > 3.8k = 24k = 8k + 16k.

Vì k ≥ 3 nên 16k ≥ 48. Do đó, 3^(k+1) > 8k + 16k > 8k + 48 > 8k + 8 = 8(k+1).

Vậy, P(n) đúng với mọi n ≥ 3.

b. Phương pháp quy nạp thứ hai:

Chứng minh P(n) đúng với mọi số tự nhiên n∈N.   

Đó  là, (P(1) ∧ ... ∧ P(n)) → P(n+1), ∀n∈N.

Gồm 2 bước:

Bước cơ sở: Chứng minh P(1) là đúng.

Bước quy nạp: Giả sử P(1) ∧ ... ∧ P(k) đúng,

Chứng minh P(k+1) đúng, ∀n∈N.

Ví dụ: Cho n∈N, nếu n>1, thì P(n): n là tích của những số nguyên tố.

Chứng minh:

Bước cơ sở: P(2) đúng, vì 2 = 1 x 2.

Bước quy nạp: Giả sử P(j) đúng cho mọi số tự nhiên, với j<k, đó là P(1) ∧ ... ∧ P(k) đúng.

Chứng minh P(k+1) đúng, ∀n∈N.

Có hai trường hợp: k+1 là số nguyên tố hay k+1 là hợp số.

Nếu k+1 là số nguyên tố, thì P(k+1) đúng.

Nếu k+1 là hợp số, thì nó là tích của hai số nguyên a và b với 2 < a < n² + 3n + 5b < k+1.

Theo giả thiết quy nạp, thì a và b là tích của những số nguyên tố.

Vậy, nếu k+1 là hợp số, thì nó là tích của những số nguyên tố của những số nguyên a và b.

Đó là, P(k+1) đúng.

Vậy, P(n) đúng với mọi số tự nhiên n∈N, n>1.

4.2.7 Chứng minh trường hợp

Ví dụ: Cho n∈Z, thì n² + 3n + 5 là một số nguyên lẻ.

Chứng minh:

Có 2 trường hợp là n chẵn hay lẻ:

a. Trường hợp 1 khi n chẵn: Thì n = 2x, có x∈Z.

n² + 3n + 5 = 4x² + 6x + 5

                   = 2(2x² + 3x + 2) + 1.

b. Trường hợp 2 khi n lẻ: Thì n = 2x + 1, có x ∈Z.

n² + 3n + 5 = 4x² + 4x + 1 + 6x + 3 + 5

                    = 2(2x² + 5x + 4) + 1.

Vậy, n² + 3n + 5 là một số nguyên lẻ.

4.2.8 Chứng minh tương đương P<=>Q:

Có hai phần:

a. Chứng minh P => Q:

Giả sử P đúng, chứng minh Q đúng.

b. Chứng minh Q => P:

Giả sử Q đúng, chứng minh P đúng.

Ví dụ: Chứng minh số nguyên n lẻ nếu và chỉ nếu n² lẻ.

Chứng minh:

Có hai phần:

a. Chứng minh P => Q: nếu n lẻ, thì n² lẻ.

Giả sử n lẻ, n = 2k + 1, k∈N.

Thì n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 lẻ.

b. Chứng minh Q => P: nếu n² lẻ, thì n lẻ.

Gián tiếp, giả sử n chẵn, n = 2k, k∈N.

Thì n² = (2k)² = 4k² = 2(2k²) chẵn. Vậy, nếu n² lẻ, thì n lẻ.

4.2.9 Chứng minh tồn tại

Chứng minh ∃xP(x) là chứng minh tồn tại.

Có hai cách:

a. Chứng minh tồn tại xây dựng:

Tìm a sao cho P(a) đúng.

Ví dụ: Chứng minh rằng có hai cách khác nhau để viết một số nguyên dương như là tổng của những số nguyên dương luỹ thừa ba.

Chứng minh:

Vì 1729 = 10³ + 9³ = 12³ + 1³.

Định lý được chứng minh.

b. Chứng minh tồn tại không xây dựng:

Chứng minh ~∃xP(x) dẫn đến mâu thuẫn.

Ví dụ: Chứng minh rằng tồn tại những số vô tỷ x và y sao cho x^y là số hữu tỷ.

Chứng minh:

Ta biết Ö2 là số vô tỷ. Cho số Ö2^Ö2.

Nếu nó là số hữu tỷ, ta có hai số vô tỷ x và y mà x^y là hữu tỷ với x = Ö2  và y = Ö2.

Nếu nó là số vô tỷ, ta có x = Ö2^Ö2 và y = Ö2 sao cho x^y = (Ö2^Ö2) ^Ö2 = 2.

Đây là chứng minh tồn tại không xây dựng vì ta đã không tìm những số vô tỷ x và y sao cho x^y là hữu tỷ. Nhưng ta đã chứng minh rằng cặp x = Ö2, y = Ö2 hay cặp x = Ö2^Ö2, y = Ö2 có tính chất mong muốn.

4.2.10 Chứng minh tồn tại duy nhất

Có hai phần:

a. Tồn tại: Chứng minh tồn tại phần tử x với tính chất mong muốn.

b. Duy nhất: Chứng minh nếu y khác x, thì y không có tính chất mong muốn.

Ví dụ: Chứng minh rằng mỗi số nguyên có duy nhất một số nghịch đảo cộng. Đó là, nếu p là một số nguyên, thì tồn tại duy nhất một số nguyên q sao cho p + q = 0.

Chứng minh:

a. Tồn tại: Nếu p là một số nguyên, ta có p + q = 0 khi q = -p và q là số nguyên. Vậy, có một số nguyên q sao cho p + q = 0.

b. Duy nhất: Để chứng minh rằng số nguyên p và q đã cho với p + q = 0 là duy nhất. Giả sử r là một số nguyên với r khác q sao cho p + r = 0. Thì p + q = p + r. Trừ p từ hai vế, ta có q = r, mâu thuẫn với giả thiết q khác r. Vậy, tồn tại duy nhất một số nguyên q sao cho p + q = 0.

4.2.11 Chứng minh bằng phản ví dụ

Chứng minh mệnh đề ∀xP(x) là sai nếu ta tìm được một phản ví dụ. Đó là, tìm x sao cho P(x) sai.

Ví dụ: Chứng minh mệnh đề “Mỗi số nguyên dương là tổng của bình phương của ba số nguyên.” là sai.

Chứng minh:

Ta thấy rằng

1 = 0² + 0² + 1²,

2 = 0² + 1² +1²,

3 = 1² + 1² + 1²,

4 = 0² + 0² + 2²,

5 = 0² + 1² + 2²,

6 = 1² + 1² + 2².

Nhưng ta không có cách nào viết 7 như tổng của bình phương của ba số nguyên. Vậy, 7 là một phản ví dụ chứng tỏ rằng mệnh đề “Mỗi số nguyên dương là tổng của bình phương của ba số nguyên.” là sai.

4.2.12 Chứng minh bằng lỗ bồ câu

a. Nguyên tắc lỗ bồ câu:

Nếu số bồ câu nhiều hơn số lỗ, thì phải có ít nhất một lỗ chứa hai bồ câu.

Nguyên tắc này còn được dùng cho những vật thể khác với bồ câu như sau:

Nếu k + 1 hay nhiều hơn vật thể được đặt vào k thùng, thì có ít nhất một thùng chứa hai hay nhiều hơn vật thể.

b. Ví dụ: Chứng minh rằng trong bất cứ nhóm 366 người nào, nhất định phải có hai người cùng một ngày sinh nhật.

Chứng minh:

Theo nguyên tắc lỗ bồ câu, chỉ có 365 ngày trong một năm nên phải có 2 người trong nhóm 366 người có cùng một ngày sinh nhật.