hoàngvănthành : Chứng minh Toán học, 2018

TỰA

Nhiều sinh viên gặp trở ngại lần đầu tiên khi họ lấy lớp toán trong đó chứng minh rất cần thiết và quan trọng.

Sách này chuẩn bị cho sinh viên vào những lớp toán như thế bằng cách dạy họ những phương pháp viết và đọc những chứng minh.

Sinh viên chỉ cần học vấn bậc Trung học để đọc sách này.

Sách gồm có 3 phần:

Phần 1: Luận lý toán học

Sách bắt đầu với luận lý toán học để học sinh quen với ngôn ngữ toán học. Sự hiểu biết về ngôn ngữ toán họclà căn bản cho sự lý luận chi tiết về những phương pháp chứng minh, dùng chúng khi nào và kết hợp chúng thế nào trong những chứng minh phức tạp.

Phần 2: Phương pháp chứng minh

Có những chứng minh định lýthật đơn giản và dễ dàng bằng cách chứng minh trực tiếp qua những giảthiết và định nghĩa của các từ thuộc định lý.

Nhưng cũng có những chứng minh định lý thật phức tạp và khó khăn nếukhông nhờ vào sự dùng khéo léo của chứng minh gián tiếp - phản chứng, mâu thuẫn - hay những kỹ thuật chứng minh khác.

Chứng minh là một nghệ thuật có thể học qua kinh nghiệm, như viết chứng minh để người khác phê bình, đọc và phân tích những chứng minh khác.

Phần này cho vài hướng dẫn trong việc chứng minh định lý toán học. Những hướng dẫn này tuy là hữu ích, nhưng không thể thay thế cho việc thực hành. Có lẽ điều quan trọng nhất trong chứng minh định lý là kinh nghiệm chứng minh. Để chứng minh định lý, ta cần nhiều sáng tạo và hiểu quy tắc suy luận hợp lý.

Phần 3: Phụ lục

Tài liệu về tập hợp, hệ thống số, hàm số là nền tảng giá trị trong những lớp toán lý thuyết.

Phần này cung cấp những định nghĩa, định lý, và những bài tập dùng cho thực hành viết và đọc những chứng minh.

Tôi chân thành cảm ơn những đồng nghiệp và các bạn gần xa đã đọc bản thảo và cho ý kiến để hoàn thiện. Sách này sẽ chẳng được in ấn nếu không có những khuyến khích quý báuvà nồng nhiệt của các bạn.

Garden Grove, ngày 20 tháng 2năm 2018

Hoàng Văn Thành

Phần Thứ Nhất

Luận Lý Toán Học

Chương 1

Luận lý mệnh đề

1.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.
1.2 Giá trị
Giá trị của luận lý cổ điển là đúng (đ) hoặc sai (s).

1.3 Một câu phát biểu thường có chủ từ và vị từ.

Chủ từ là các đối tượng. Vị từ là tính chất của chủ từ. Tính chất có thể là mầu sắc, hình thể hay hành động của chủ từ.

1.4 Có ba loại câu phát biểu:

1. Chủ từ-Động từ

Ví dụ:

Anh đi.

Vị từ là động từ.

2. Chủ từ-Động từ-Túc từ

Ví dụ:

Anh đi học.

Vị từ là động từ và túc từ.

3. Chủ từ-Động từ liên kết-Bổ từ

Ví dụ:

Anh là sinh viên.

Anh có tiền.

Vị từ là động từ liên kết và bổ từ.
1.5 Mệnh đề
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à công thức.
Ví 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?

e) Trời nóng quá!
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 và e không phải là mệnh đề vì nó không là một câu phát biểu.
2. Mệnh đề đơn
a. Đị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.
b. Ký hiệu: Ta dùng chữ thường p, q, r,... để ký hiệu mệnh đề đơn.
Ví dụ: Cho mệnh đề đơn p như sau:
p: Tôi là sinh viên.
1.6 Các phép toán mệnh đề
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 mệnh đề phức.
Ta dùng chữ hoa P, Q, R,...để ký hiệu mệnh đề phức.
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.
1.7 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.
1.8 Phép phủ định
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. 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.
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.
1.9 Phép hội
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. 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.
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.
1.10 Phép tuyển
1. Định nghĩa: Cho hai mệnh đề p,q. Tuyển của p và q, ký hiệu pÚq, là mệnh đề p hoặc q.
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ì pÚq đúng nếu ít nhất một trong hai phần tử đúng; với nghĩa thứ hai thì pÚq đú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.
3. 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 đúng nếu ít nhất một trong hai phần tử đúng; sai trong những trường hợp khác.
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 hoặc Hà Nội là thủ đô của Việt Nam. Vậy, pÚq là đúng.
1.11 Phép điều kiện
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. 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.
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.
1.12 Phép tương đương
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. 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.
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.

1.13 Công thức

Cho các biến mệnh đề đơn p, q, r, ta có thể dùng các phép toán ở trên để liên kết các mệnh đề đơn thành các mệnh đề phức. Mệnh đề phức được gọi là công thức, biểu thức, hay dạng mệnh đề.

Công thức được định nghĩa đệ quy như sau:

1. Mệnh đề đơn là công thức.

2. Kết quả của việc áp dụng một số hữu hạn lần các phép toán trên các công thức là công thức.

3. Không còn cách lập công thức nào khác với những cách trên đây.

1.14 Thực trị của công thức

Một công thức F được cấu tạo từ những mệnh đề đơn thành phần Fi. Mỗi khi Fi có giá trị đ hoặc s thì F sẽ có giá trị đ hoặc s.

Để xét tất cả các trường hợp có thể có của một công thức, ta lập bảng thực trị.

Ví dụ: Tìm thực trị của công thức Ø(pÚØq)

Ta lập bảng thực trị theo những bước sau:

1. Liệt kê tất cả thực trị có thể có của biến mệnh đề thành phần p, q. Nếu công thức có n biến, ta có 2n hàng. Công thức này có 2 biến nên có 4 hàng.

p	q
đ	đ
đ	s
s	đ
s	s

2. Thêm cột Øq

p	q	Øq
đ	đ	s
đ	s	đ
s	đ	s
s	s	đ

3. Thêm cột pÚØq

p	q	Øq	pÚØq
đ	đ	s	đ
đ	s	đ	đ
s	đ	s	s
s	s	đ	đ

4. Thêm cột Ø(pÚØq)

p	q	Øq	pÚØq	Ø(pÚØq)
đ	đ	s	đ	s
đ	s	đ	đ	s
s	đ	s	s	đ
s	s	đ	đ	s

Công thức Ø(pÚØq) sai trong mọi trường hợp, trừ hàng ba đúng, nhưng p sai và q đúng.

1.15 Công thức hằng đúng và hằng sai

1. Công thức hằng đúng

Xét bảng thực trị của công thức p® (p Ú q)

p	q	p Ú q	p® (pÚ q)
đ	đ	đ	đ
đ	s	đ	đ
s	đ	đ	đ
s	s	s	đ

Bất cứ thực trị nào gán cho p và q cũng làm cho công thức p® (p Ú q) đúng. Ta gọi công thức này là hằng đúng.

2. Công thức hằng sai

Xét bảng thực trị của công thức (ØpÙq) Ù (pÚØq)

p	q	Øp	Øq	ØpÙq	pÚØq	(ØpÙq) Ù(pÚØq)
đ	đ	s	s	s	đ	s
đ	s	s	đ	s	đ	s
s	đ	đ	s	đ	s	s
s	s	đ	đ	s	đ	s

Bất cứ thực trị nào gán cho p và q cũng làm cho công thức (ØpÙq) Ù(pÚØq) sai. Ta gọi công thức này là

hằng sai.

Dĩ nhiên, phủ định của hằng đúng là hằng sai và ngược lại.

Định nghĩa:

Công thức là hằng đúng nếu nó đúng với mọi thực trị của các biến mệnh đề đơn thành phần.

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.

Công thức là hằng sai nếu nó sai với mọi thực trị của các biến mệnh đề đơn thành phần.

Chú ý: Ta có thể thay thế một mệnh đề đặc trưng cho biến mệnh đề trong công thức. Công thức nhận được gọi là một ví dụ thay thế. Sự thay thế vào công thức hằng đúng sẽ có một mệnh đề hằng đúng. Sự thay thế vào công thức hằng sai sẽ có một mệnh đề hằng sai.

Ví dụ:

Cho P = Hà nội là thủ đô của Việt Nam.

Q = Bangkok là thủ đô của Thái Lan.

R = Nếu Hà Nội là thủ đô của Việt Nam thì Hà Nội là thủ đô của Việt Nam hoặc Bangkok là thủ đô của Thái Lan.

Hai mệnh đề P và R đều là hằng đúng. Mệnh đề P đúng vì nội dung của nó, còn mệnh đề R đúng vì mệnh đề P và Q được thay vào công thức hằng đúng p®(p Ú q).

1.16 Hệ quả luận lý

Xét bảng thực trị của công thức Øp và Øp Ú Øq

p	q	Øp	Øq	Øp Ú Øq
đ	đ	s	s	s
đ	s	s	đ	đ
s	đ	đ	s	đ
s	s	đ	đ	đ

Bất cứ khi nào Øp đúng (hàng 3, 4), thìØp Ú Øq cũng đúng. Vậy, Øp Ú Øq là hệ quả luận lý cuả Øp.

Định nghĩa: Bất cứ khi nào p đúng thì q cũng đúng, ký hiệu p├ q, ta gọi q là hệ quả luận lý của p.

Nếu p và q sao cho p├ q, thì không có bất cứ trường hợp nào khi thực trị của biến mệnh đề làm p đúng và q sai. Đây chỉ là trường hợp khi mệnh đề điều kiện p®q sai.

Vậy, nếu p├ q thì p®q đúng cho mọi thực trị cuả biến mệnh đề thành phần và nó là hằng đúng. Ngược lại, nếu p và q sao cho p®q hằng đúng thì p├ q.

Chú ý: hệ thức p├ q chỉ cần q đúng trong mọi trường hợp mà p đúng. q có thể đúng trong vài trường hợp mà p sai. Thật vậy, hàng 2 cho thấy Øp sai và Øp Ú Øq đúng.

Nếu p├ q, ta biết rằng q đúng bất cứ khi nào p đúng. Tuy nhiên, nếu ta xét những trường hợp mà Øp Ú Øq đúng (tất cả trường hợp trừ hàng 1), ta thấy rằng Øp sai trong một trường hợp, vậy Øp không là hệ quả luận lý của Øp ÚØq.

1.17 Tương đương luận lý

Xét bảng thực trị cuả công thức p®q và Øp Ú q

p	q	Øp	p®q	Øp Ú q
đ	đ	s	đ	đ
đ	s	s	s	s
s	đ	đ	đ	đ
s	s	đ	đ	đ

Bất cứ khi nào p®q đúng thì Øp Ú q cũng đúng, vậy (p®q)├ (Øp Ú q). Ngược lại, bất cứ khi nào Øp Ú q đúng thì p®q cũng đúng, vậy (Øp Ú q)├(p®q).

Định nghĩa: Hai công thức Øp Ú q và p®q có cùng thực trị như nhau được gọi là tương đương luận lý và ta viết (Øp Ú q) º (p®q) hay (p®q) º (Øp Úq).

Chú ý: nếu p º q thì p├ q và q├ p.

Bảng 1.1 Quy tắc thay thế

1) Commutation (Com)

Giao hoán

2) Association (Assoc)

Phối hợp

3) Distribution (Dist)

Phân bố

4) De Morgan’s laws (De M)

Luật Morgan

5) Double negation (DN)

Phủ định kép

6) Transposition (Trans)

Hoán vị

7) Material Implication (Impl), Kéo theo

8) Material equivalence (Equi), Tương đương

9) Tautology (Taut)

Hằng đúng

10) Exportation (Exp)

Xuất cảng

p Ú q º q Ú p

p Ù q º q Ù p

p Ú (q Ú r) º (p Ú q) Ú r

p Ù (q Ù r) º (p Ù q) Ù r

p Ù (q Ú r) º (pÙq)Ú(pÙr)

p Ú (q Ù r) º (pÚq)Ù(pÚr)

Ø (p Ù q) º Øp Ú Øq

Ø (p Ú q) º Øp Ù Øq

p º Ø(Øp)

p®q º Øq®Øp

p®q º Øp Ú q

p«q º (p®q) Ù (q®p)

p«q º (p Ù q)Ú(ØpÙØq)

p Ù p º p

p Ú p º p

(p Ù q)®r º p®(q®r)

Ta có thể dùng những tương đương luận lý để chứng minh những công thức.

Ví dụ: Chứng minh rằng Ø(p Ù q) ºp®Øq.

Chứng minh:

Ta bắt đầu từ công thức bên trái, rồi dùng những luật thay thế ở trên để có những công thức mới, cho đến khi ta đạt được công thức bên phải. Mỗi bước ta nêu ra luật thay thế đã dùng.

Ø (p Ù q) º Øp Ú Øq (De M)

º p ® Øq (Impl). €

Chương 2

Luận lý vị từ

2.1 Vị từ
1. Mệnh đề trong luận lý mệnh đề thường không có khả năng diễn tả tất cả những mệnh đề toán học.
2. Định nghĩa:

Câu phát biểu ‘x là một số nguyên chẵn’ có 2 phần. Phần thứ nhất, biến x, là chủ từ. Phần thứ hai, vị từ P: ‘là một số nguyên chẵn’, là tính chất của chủ từ.

3. Ký hiệu:

Câu phát biểu được ký hiệu là P(x).

Chủ từ được ký hiệu bằng chữ nhỏ, như x.

Vị từ được ký hiệu bằng chữ lớn, như P.

4. Câu phát biểu có biến như trên là không đúng hay sai; nó không phải là mệnh đề, khi giá trị của biến chưa xác định.

Như thế, câu phát biểu P(x) là giá trị của hàm mệnh đề P tại x. Ngay khi giá trị được gán cho biến x, câu phát biểu P(x) trở thành mệnh đề và có thực trị.

2.2 Hàm mệnh đề

Định nghĩa: Vị từ còn được gọi là hàm mệnh đề.

Cho P(x) là một câu có biến x và D là một tập hợp.Ta gọi P 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 đối tượng của P.

Ví dụ:

Cho P(x): x là một số nguyên lẻ.

Cho D là tập hợp số nguyên dương. Vậy, P là hàm mệnh đề với miền đối tượng D. P(x) là một mệnh đề vì với mỗi x trong D, P(x) đúng hay sai, nhưng không cùng đúng hay sai.

Đó là:

Nếu x = 1, ta có mệnh đề đúng:

P(1): 1 là số nguyên lẻ.

Nếu x = 2, ta có mệnh đề sai:

P(2): 2 là số nguyên lẻ.

Chú ý:

Hàm mệnh đề P thì không đúng hay sai, vì nó chứa biến. Tuy nhiên, cho mỗi x trong miền đối tượng D, P(x) là một mệnh đề và nó đúng hay sai.

Ta có thể coi hàm mệnh đề xác định một tập hợp những mệnh đề, một cho mỗi đối tượng trong miền đối tượng.

Ví dụ 1: nếu P(x) là một hàm mệnh đề với miền đối tượng là tập hợp những số nguyên dương, ta có được tập hợp mệnh đề sau

P(1), P(2), …

Mỗi P(1), P(2), … là đúng hay sai.

Ví dụ 2:

Cho P(x): x2 – 10x + 16 = 0 và D là tập số thực. Cho mỗi số thực x trong miền đối tượng D, ta có một mệnh đề; do đó P(x) là một hàm mệnh đề.
1. Hằng mệnh đề
Mệnh đề trong luận lý mệnh đề, vì không có biến nên là một hằng mệnh đề.
Ví dụ:

P1: 1 + 1 = 3 có giá trị sai.
P2: 1 + 2 = 3 có giá trị đúng.
2. Hàm mệnh đề một biến
Cho P(x) là câu phát biểu có biến x và D là một tập hợp không rỗng. Ta gọi Plà 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 đối tượng của P.
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. Hàm mệnh đề hai biến
Cho P(x, y) là câu phát biểu có biến x và y; D là một tập hợp không rỗng. Ta gọi P 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 đối tượng của P.
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.
4. Hàm mệnh đề ba biến
Cho P(x, y, z) là câu phát biểu có biến x, y và z; D là một tập hợp không rỗng. Ta gọi P 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 đối tượng của P.
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.
5. Hàm mệnh đề n biến
Cho P(x1, x2, …, xn) là câu phát biểu có n biến x1,x2, …, xn; D là một tập hợp không rỗng. Ta gọi P là một hàm mệnh đề đối với D, nếu cho mỗi x1, x2, …, xntrong D, P(x1, x2, …, xn) là một mệnh đề. Ta gọi D là miền đối tượng của P.

Tổng quát, câu phát biểu có n biến x1, x2, …, xn được ký hiệu là P(x1, x2, …, xn).

P(x1, x2, …, xn) là giá trị của hàm mệnh đề P tại (x1, x2, …, xn), và P là vị từ.
2.3 Các phép toán của hàm mệnh đề
1. Phép phủ định
Cho p(x) là hàm mệnh đề một biến x trên tập X không rỗng. 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).
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 không rỗng. 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. 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 không rỗng. 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) hoặc q(x).
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 không rỗng. 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).
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 không rỗng. 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).

2.4 Lượng từ

Để hàm mệnh đề trở thành mệnh đề ta dùng lượng từ.

Có hai loại lượng từ:

1. Lượng từ phổ dụng

Định nghĩa:

Cho P là một hàm mệnh đề với miền đối tượng D.

Câu “Với mọi x, P(x)”, ký hiệu "xP(x), là câu lượng từ phổ dụng. Ký hiệu ", nghĩa là ‘Với mọi’, ‘Với mỗi’, hay ‘Với tất cả’, được gọi là lượng từ phổ dụng.

Câu "xP(x):

Đúng, nếu P(x) đúng với mọi x trong D.

Sai, nếu P(x) sai với ít nhất một x trong D.

2. Lượng từ hiện hữu

Định nghĩa: Cho P là một hàm mệnh đề với miền đối tượng D. Câu ‘Có một x, P(x)’, ký hiệu $xP(x), là câu lượng từ hiện hữu. Ký hiệu $, nghĩa là ‘Có một’, ‘Có ít nhất một’, hay ‘Có vài’, được gọi là lượng từ hiện hữu.

Câu $xP(x):

Đúng, nếu P(x) đúng với ít nhất một x trong D.

Sai, nếu P(x) sai với mọi x trong D.

2.5 Phạm vi của lượng từ

1. Ta gọi biến x trong P(x) là biến tự do, vì x là tự do trong miền đối tượng.

2. Ta gọi biến x trong "x hay $x là biến ràng buộc, vì x là ràng buộc bởi lượng từ " hay $.

Hàm mệnh đề không có thực trị vì nó chứa biến tự do. Nhưng, định nghĩa trên gán thực trị cho những câu có lượng từ. Tóm lại, câu với biến tự do không là mệnh đề, nhưng câu không có biến tự do là mệnh đề.

Đôi khi, để chỉ rõ miền đối tượng D, ta viết câu lượng từ phổ dụng như sau

Với mọi x trong D, P(x).

Và viết câu lượng từ hiện hữu như sau

Có một x trong D, P(x).

Tất cả những biến xảy ra trong hàm mệnh đề phải bị buộc để trở thành mệnh đề. Điều này có thể được làm bằng cách dùng tổ hợp những lượng từ phổ dụng, hiện hữu, và gán giá trị.

Định nghĩa: Biểu thức luận lý được lượng từ áp dụng gọi là phạm vi của lượng từ. Một biến là tự do nếu nó nằm ngoài phạm vi của tất cả các lượng từ trong biểu thức.

Ví dụ:

Trong câu $xQ(x,y), biến x bị buộc bởi lượng từ hiện hữu $x, nhưng biến y là tự do vì nó không bị buộc bởi lượng từ và không có giá trị nào được gán cho biến này.

Trong câu $x(P(x) Ù Q(x)) Ú "xR(x), tất cả biến bị buộc. Phạm vi của $x là P(x) Ù Q(x).Tương tự, phạm vi của "x là R(x).

Chú ý: Ta có thể viết câu $x(P(x) ÙQ(x)) Ú "xR(x) là $x(P(x) Ù Q(x)) Ú"yR(y) bằng cách dùng 2 biến khác nhau x và y, vì phạm vi của hai lượng từ không giao nhau.

2.6 Phủ định của các mệnh đề chứa lượng từ

Định lý De Morgan:

Nếu P(x) là hàm mệnh đề với biến x, thì:

a) Ø"xP(x) º $xØP(x)

b) Ø$xP(x) º "xØP(x)

Chứng minh:

a) Gỉa sử mệnh đề Ø"xP(x) đúng, thì mệnh đề "xP(x) sai. Bởi định nghĩa, "xP(x) sai, thì P(x) sai cho ít nhất một x trong miền đối tượng. Nhưng nếu P(x) sai cho ít nhất một x trong miền đối tượng, thì ØP(x) đúng cho ít nhất một x trong miền đối tượng. Như thế, bởi định nghĩa, nếu ØP(x) đúng cho ít nhất một x trong miền đối tượng, thì $xØP(x) đúng. Vậy, nếu Ø"xP(x) đúng, thì $xØP(x) đúng. Tương tự, nếu Ø"xP(x) sai, thì $xØP(x) sai.

Vậy, Ø"xP(x) º $xØP(x).

b) Chứng minh tương tự. €

Ví dụ 1:

Phủ định của "x(x2 ³ 0) là Ø"x(x2 ³ 0) º$xØ(x2 ³ 0) º $x(x2 < 0).

Ví dụ 2:

Phủ định của $x(x2 + 2 = 0) là Ø$x(x2 + 2 = 0) º"xØ(x2 + 2 = 0) º"x(x2 + 2 ¹ 0).

Ví dụ 3:

Phủ định của $x(x < 4) là Ø$x(x < 4) º"xØ(x < 4) º "x(x ³ 4).

2.7 Lượng từ lồng

1. Định nghĩa: Lượng từ lồng là lượng từ xảy ra trong phạm vi của một lượng từ khác.

Ví dụ:

Cho P(x,y): "x$y(x + y = 0).

Miền đối tượng là tập số thực.

Câu

Cho mọi x, cho vài y, x + y = 0.

Nghĩa là cho bất cứ x, có ít nhất một y, tuỳ theo sự chọn x, sao cho x + y = 0.

Ta có thể chứng tỏ rằng câu

Cho mọi x, cho vài y, x + y = 0.

là đúng. Cho bất cứ x, ta có thể tìm được ít nhất một y, như, y = -x, sao cho x + y = 0 là đúng. €

2. Phủ định của lượng từ lồng

Câu có lượng từ lồng có thể phủ định bằng cách áp dụng tiệm tiến những quy tắc phủ định của câu có lượng từ đơn.

Ví dụ:

Diễn tả phủ định của câu "x$y(2y=x) sao cho không có phủ định đứng trước lượng từ.

Giải:

Bởi áp dụng tiệm tiến những luật phủ định của câu có lượng từ đơn, ta có thể chuyển phủ định của Ø"x$y(2y=x) vào bên trong tất cả các lượng từ.

Vì Ø"x$y(2y=x) º $xØ$y(2y=x) º$x"yØ(2y=x). Và Ø(2y=x) º (2y¹x), ta kết luận câu phủ định là $x"y(2y¹x).

3. Thứ tự của những lượng từ

Thứ tự của những lượng từ rất quan trọng, trừ khi tất cả các lượng từ đều là lượng từ phổ dụng hay tất cả các lượng từ đều là lượng từ hiện hữu.

Ví dụ 1:

Cho P(x,y): x+y = y+x. Tìm thực trị của "x"yP(x,y).

Giải:

"x"yP(x,y) là mệnh đề “Mọi số thực x và mọi số thực y, x + y = y + x.”

Vì P(x,y) là đúng cho mọi số thực x và y, mệnh đề "x"yP(x,y) là đúng. €

Ví dụ 2:

Cho P(x,y): x + y = 0. Tìm thực trị của "x$yP(x,y) và $y"xP(x,y).

Giải:

a. "x$yP(x,y) là mệnh đề “Cho mỗi số thực x, có một số thực y sao cho x + y = 0” là đúng, vì có một giá trị của y thỏa mãn phương trình x + y = 0; đó là y = -x.

b. $y"xP(x,y) là mệnh đề “Có một số thực y sao cho mỗi số thực x, x + y = 0” là sai, vì không có giá trị của y thoả mãn phương trình x + y = 0 cho mọi giá trị của x. €

Ví dụ 3:

Cho P(x,y,z): x + y = z. Tìm thực trị của "x"y$zP(x,y,z) và $z"x"yP(x,y,z).

Giải:

a. "x"y$zP(x,y,z) là mệnh đề “Cho mỗi số thực x và cho mỗi số thực y, có một số thực z sao cho x + y = z” là đúng, vì có một giá trị của z thoả mãn phương trình x + y = z cho mọi giá trị của x và y.

b. $z"x"yP(x,y,z) là mệnh đề “Có một số thực z sao cho mỗi số thực x và cho mỗi số thực y, x + y = z” là sai, vì không có giá trị của z thoả mãn phương trình

x + y = z cho mọi giá trị của x và y. €

Chương 3

Suy luận

3.1 Sự rút ra một kết luận từ một dãy mệnh đề được gọi là suy luận.

Luận lý giúp ta phân tích sự suy luận có hợp lý hay không.

1. Suy luận thường có dạng

“Nếu p1 và p2 và … và pn, thì q.”

ký hiệu

p1, p2, …, pn / \q

Những mệnh đề p1, p2, …, pn được gọi là những tiền đề và mệnh đề q được gọi là kết luận.

2. Định nghĩa: Một dạng suy luận với tiền đề p1, p2, …, pn và kết luận q được gọi là hợp lý, nếu p1, p2, …, pn đều đúng, thì q cũng đúng. Nếu không thì dạng suy luận là không hợp lý. Đó là,

(p1 Ù p2 Ù…Ù pn)├ q hay (p1 Ù p2 Ù…Ù pn) Þ q.

3. Chú ý: Trong suy luận hợp lý, ta không nói kết luận là đúng; ta chỉ nói, nếu ta có tiền đề thì ta cũng có kết luận.Đó là, kết luận được suy ra từ tiền đề.

4. Suy luận hợp lý là do dạng suy luận của nó, chứ không phải vì nội dung của nó.

a. Định nghĩa: Một dạng suy luận với tiền đề p1, p2, …, pn và kết luận q được gọi là hợp lý, nếu (p1 Ù p2 Ù…Ù pn) ®q là hằng đúng. Nếu không thì dạng suy luận là không hợp lý.

b. Định nghĩa: Một suy luận là hợp lý nếu nó là một ví dụ thay thế của một dạng suy luận hợp lý. Nếu không thì suy luận là không hợp lý.

3.2 Chứng minh sự hợp lý của suy luận:

1. Phương pháp bảng thực trị.

Ví dụ: Xác định sự hợp lý của suy luận sau:

p®q

p .

Chứng minh:

Lập bảng thực trị

p	q	p®q	p	q
đ	đ	đ	đ	đ
đ	s	s	đ	s
s	đ	đ	s	đ
s	s	đ	s	s

Bất cứ khi nào tiền đề p®q và p đúng, thì kết luận q cũng đúng; vậy, suy luận là hợp lý. €

Phương pháp bảng thực trị để chứng minh sự hợp lý của suy luận sẽ phức tạp và không thực dụng, vì nếu tiền đề có n mệnh đề đơn, bảng thực trị cần đến 2n hàng.

2. Phương pháp chứng minh hình thức

Định nghĩa: Cho suy luận với tiền đề p1, p2, …, pn và kết luận q, một chứng minh hình thức sự hợp lý của suy luận là một danh sách những mệnh đề chấm dứt với q.

Mỗi mệnh đề trong danh sách phải thoả mãn một điều kiện sau:

a) là tiền đề của suy luận.

b) được suy ra từ những mệnh đề đã có trong danh sách bằng quy tắc suy luận.

c) tương đương một mệnh đề đã có trong danh sách bằng quy tắc thay thế.

3.3 Để chứng minh hình thức, ta cần những dạng suy luận hợp lý được gọi là những quy tắc suy luận.

1. Quy tắc suy luận cho mệnh đề

Bảng 3.1 Quy tắc suy luận

Quy tắc	Công thức hằng đúng	Tên
p \pÚq	p ® (p Ú q)	Cộng (Add)
pÙq \p	(p Ù q) ® p	Đơn giản (Simp)
p q \pÙq	(p Ù q) ® (p Ù q)	Hợp (Conj)
p p®q \q	[p Ù (p ® q)] ® q	Tách ra (MP)
Øq p®q \Øp	[Øq Ù (p ® q)] ® Øp	MT (Modus Tollens)
p®q q®r \p®r	[(p ® q) Ù (q ® r)] ® (p ®r)	Tam đoạn luận giả định (HS)
pÚq Øp \q	[(p Ú q) Ù Øp] ® q	Tam đoạn luận tuyển (DS)
p®q \p®(pÙq)	(p ® q)®[p®(pÙq)]	Hấp thụ (Abs)
pÚq ØpÚr \q Ú r	[(p Ú q) Ù (Øp Ú r)] ® (q Ú r)	Phân giải (Res)

Chú ý: Quy tắc suy luận là thay thế mệnh đề đúng vào một công thức hằng đúng.

Ví dụ:

Chứng minh hình thức sự hợp lý của suy luận sau:

Nếu Gia ở Saigon thì Mai ở Hanoi. Gia ở Saigon và Hoa ở Cantho. Vậy Mai ở Hanoi.

Giải:

Đặt G: Gia ở Saigon.

M: Mai ở Hanoi.

H: Hoa ở Cantho.

Tiền đề: G®M và G Ù H.

Kết luận: M.

Ta bắt đầu danh sách với các tiền đề:

1. G®M(tiền đề).

2. G Ù H(tiền đề).

Nếu mệnh đề G được thêm vào danh sách, thì ta có thể thêm kết luận vào danh sách bằng cách dùng luật tách ra (MP): G và G®M.

Để thêm G vào danh sách, ta dùng luật đơn giản (Simp) cho tiền đề thứ hai G Ù H.

Dưới đây là chứng minh đầy đủ:

1. G®M(tiền đề).

2. G Ù H(tiền đề).

3. G(2. Đơn giản).

4. M(1, 3. Tách ra).

Chú ý: Sau mỗi mệnh đề là những mệnh đề và luật suy luận.

2. Quy tắc suy luận cho lượng từ

1) Tức thì phổ dụng: Nếu "xP(x) đúng, thì P(c) đúng, khi c là một phần tử của miền giá trị.

2) Tổng quát phổ dụng: Nếu một phần tử bất kỳ c trong miền giá trị làm P(c) đúng, thì "xP(x) đúng.

3) Tức thì hiện hữu: Nếu $xP(x) đúng, thì có một phần tử c trong miền giá trị làm P(c) đúng.

4) Tổng quát hiện hữu: Nếu một phần tử c trong miền giá trị làm P(c) đúng, thì $xP(x) đúng.

Bảng 3.2 Quy tắc suy luận

Quy tắc suy luận	Tên
"xP(x) \P(c)	Tức thì phổ dụng (Universal instantiation)
P(c) cho bất kỳ c \"xP(x)	Tổng quát phổ dụng (Universal generalization)
$xP(x) . \P(c) cho vài phần tử c	Tức thì hiện hữu (Existential instantiation)
P(c) cho vài phần tử c \$xP(x)	Tổng quát hiện hữu (Existential generalization)

Ví dụ 1:

Dùng Tức thì phổ dụng để kết luận từ câu “Mọi đàn bà thông minh”, rằng “Liên thông minh,” khi Liên là một phần tử của miền giá trị của mọi đàn bà.

Ví dụ 2:

Chứng tỏ rằng tiền đề ‘sinh viên trong lớp này đã không đọc sách’ và ‘Mọi người trong lớp đã đậu bài thi’ suy ra kết luận ‘Vài người đậu bài thi đã không đọc sách’.

Giải:

Đặt C(x): x trong lớp này.

B(x): x đã đọc sách.

P(x): x đã đậu bài thi.

Tiền đề: $x(C(x)ÙØB(x))

"x(C(x)®P(x))

Kết luận: $x(P(x)ÙØB(x))

Những bước sau chứng tỏ kết luận là từ tiền đề:

1. $x(C(x)ÙØB(x)) (tiền đề)

2. C(a)ÙØB(a) (1. EI)

3. C(a) (2. Đơn giản)

4. "x(C(x)®P(x)) (tiền đề)

5. C(a)®P(a) (4. UI)

6. P(a) (3, 5. Tách ra)

7. ØB(a) (2. Đơn giản)

8. P(a)ÙØB(a) (6, 7. Hợp)

9. $x(P(x)ÙØB(x)) (8. EG)

3.4 Phương pháp chứng minh điều kiện (CP)

1. Dạng suy luận có tiền đề p1, p2, …, pn và kết luận có dạng mệnh đề điều kiện q®r là hợp lý nếu và chỉ nếu (p1 Ùp2 Ù … Ù pn) ® (q®r) là hằng đúng.

Thật vậy, bởi luật thay thế p®(q®r) º (p Ù q)®r, thì

(p1Ùp2Ù…Ùpn)®(q®r) º (p1Ùp2Ù…ÙpnÙq)®r.

2. Điều này cho ta cách chứng minh hình thức sự hợp lý của suy luận với kết luận là một mệnh đề điều kiện q®r. Ta chỉ cần thêm tiền đề q của kết luận vào danh sách những tiền đề p1, p2,…, pn của suy luận, rồi chứng minh kết luận r.

Ví dụ:

Nếu chúng ta có tiệc thì chúng ta sẽ mời Linh và Bích. Nếu chúng ta mời Linh hay Bích thì chúng ta phải mời Gia. Như vậy, nếu chúng ta có tiệc thì chúng ta phải mời Gia.

Giải thích:

Đặt P: Chúng ta có tiệc.

L: Chúng ta sẽ mời Linh.

B: Chúng ta sẽ mời Bích.

G: Chúng ta phải mời Gia.

Tiền đề: P® (L Ù B) và (L Ú B) ®G.

Kết luận: điều kiện P®G.

Chứng minh:

Ta bắt đầu chứng minh bằng cách liệt kê hai tiền đề. Rồi thêm tiền đề P của kết luận và coi nó như là tiền đề do phương pháp chứng minh điều kiện (CP).

Dưới đây là chứng minh đầy đủ:

1. P® (L Ù B)(tiền đề).

2. (L Ù B) ®G(tiền đề).

3. P(Điều kiện).

4. L Ù B(1, 3. Tách ra).

5. L (4. Đơn giản).

6. L Ù B (5. Cộng).

7. G(2, 6. Tách ra).

8. P®G(3-7. Điều kiện). €

Chú ý: Kết luận P®G có được là nhờ những mệnh đề bắt đầu ở hàng ba khi đó tiền đề của kết luận được thêm vào như những tiền đề của suy luận và hoàn tất ở hàng 7 nơi đó ta rút ra được kết luận G.

Phần Thứ Hai

Phương Pháp Chứng Minh

Chương 4

Chứng minh

4.1 Định nghĩa: Suy luận hợp lý thiết lập sự thực cho định lý được gọi là chứng minh.

4.2 Định lý thường bắt nguồn từ phỏng đoán mà nó là một sự tin tưởng rằng một kết quả là đúng. Người ta tin vào phỏng đoán vì nhiều ví dụ đặc biệt cho kết quả đúng và không có ví dụ nào cho kết quả sai.

Mặc dầu suy luận quy nạp thường dẫn đến phỏng đoán, nhưng chỉ có suy luận hợp lý và quy nạp toán học là được dùng để chứng minh toán học (Ch.13).

4.3 Định lý thường có bốn dạng sau:

1. Mệnh đề đơn P.

2. Mệnh đề điều kiện P® Q.

3. Hàm mệnh đề lượng từ hoá phổ dụng "xP(x).

4. Hàm mệnh đề điều kiện lượng từ hoá phổ dụng "x[P(x) ® Q(x)].

Bốn dạng định lý trên thường không tách biệt.

Ví dụ 1: Xét mệnh đề đơn sau:

47 là số nguyên tố.

Mệnh đề này có thể viết như mệnh đề điều kiện sau:

Nếu n = 47, thì n là số nguyên tố.

Ví dụ 2: Xét định lý sau:

Định lý: Mọi số nguyên chẵn có số bình phương chẵn.

Nếu miền đối tượng là số nguyên chẵn và P(x): x2 là chẵn, thì định lý là hàmmệnh đề lượng từ hoá phổ dụng "xP(x).

Nhưng, nếu miền đối tượng là số nguyên và E(x): x là số nguyên chẵn, thì định lý là hàm mệnh đề điều kiện lượng từ hoá phổ dụng "x[E(x)®E(x2)].

a) Để chứng minh "xP(x), ta áp dụng UI cho mệnh đề này để có P(a). Ta chứng minh P(a) cho bất cứ a trong miền đối tượng. Rồi dùng UG suy ra "xP(x).

b) Để chứng minh "x[P(x)®Q(x)], ta áp dụng UI cho mệnh đề này để cóPa®Qa. Ta chứng minh Pa®Qa, cho bất cứ a trong miền đối tượng. Rồi dùng UG suy ra "x(Px®Qx).

Vậy, bốn loại định lý trên chỉ còn hai loại sau:

1. Mệnh đề đơn P.

2. Mệnh đề điều kiện P®Q.

4.4 Chứng minh hình thức

1. Chứng minh hình thức mệnh đề đơnP

là dãy hữu hạn S1, S2, …, Sn mệnh đề, với Sn = P và mỗi Si thoả mãn một tiêu chuẩn sau:

1) là một tiên đề.

2) được suy ra từ những mệnh đề trước bằng quy tắc suy luận.

3) tương đương một mệnh đề trước bằng quy tắc thay thế.

Để chứng minh mệnh đề đơn P, ta bắt đầu bằng tiên đề, định nghĩa, hay định lý đã chứng minh, rồi suy ra kết luận.

2. Chứng minh hình thức mệnh đề điều kiện P®Q

là dãy hữu hạn S1, S2, …, Sn mệnh đề, với S1 = P,

Sn = Q và mỗi Si thoả mãn một tiêu chuẩn sau:

1) là một tiên đề.

2) được suy ra từ những mệnh đề trước bằng quy tắc suy luận.

3) tương đương một mệnh đề trước bằng quy tắc thay thế.

Để chứng minh mệnh đê điều kiện P®Q, ta dùng phương pháp chứng minh điều kiện (3.4). Đó là, ta giả sử P đúng,thêm phần giả thiết P này vào danh sách tiền đề (tiên đề, định nghĩa, định lý đã chứng minh), rồi suy ra kết luận Q.

4.5 Chứng minh không hình thức

Chứng minh hình thức thường có quá nhiều chi tiết.

Mục đích của chứng minh không hình thức là truyền thông hữu hiệu những lý lẽ cốt yếu, tại sao một kết quả đặc biệt lại đúng. Những điểm quan trọng được nhấn mạnh, còn những chi tiết có thể bỏ qua.

Ta có thể dùng chữ, ký hiệu, sơ đồ, sự tương tự để người đọc dễ hiểu một chứng minh.

4.6 Tìm cách chứng minh định lý dạng p ® q.

Đó là, làm sao tìm được dãy mệnh đề nối p với q.

Sau đây là những hướng dẫn:

1. Trước khi chứng minh, ta cần hiểu rõ ý nghĩa của định lý.

2. Từ phát biểu của định lý, ta phải xác định: cái gì ta có thể giả định (p) và cái gì ta phải chứng minh (q).

Ví dụ: Mệnh đề điều kiện được diễn tả bằng nhiều cách khác nhau:

a) Nếu p thì q.

b) p là đủ cho q hay p là điều kiện đủ cho q.

c) q là cần cho p hay q là điều kiện cần cho p.

d) p nếu chỉ q.

Những cách diễn tả trên đều có một ý nghĩa: p là giả thiết (điều được giả định) và q là kết luận (điều phải chứng minh).

3. Khi đã hiểu rõ định lý, ta xem định lý này có giống một định lý nào không? Nếu có thì định lý ấy được chứng minh như thế nào? Cách chứng minh ấy có dùng được cho định lý này không?

4. Để chứng minh mệnh đề điều kiện p® q, ta tìm một lối đi từ giả thiết p đến kết luận q. Mỗi bước đi đều có nhiều cách lựa chọn lối đi theo quy tắc suy luận. Có những cách lựa chọn không dẫn đến đâu, nhưng mỗi lựa chọn đều dẫn đến những điều mới có thể xảy ra, cho đến khi ta đạt được mục tiêu q. Điều quan trọng là luôn hướng tới mục tiêu q khi tìm cách chứng minh.

5. Ta có thể đi tới từ p hay đi lui từ q, với hy vọng là hai đường đi sẽ gặp nhau; lúc đó ta có một lối đi từ p đến qvà một chứng minh cho p ® q.

Trong chứng minh trực tiếp:

Đi tới là từ p ta tìm mệnh đề p1 sao cho p®p1, rồi tìm p2 sao cho p1®p2, …

Đi lui là từ q ta tìm mệnh đề q1 sao cho q1®q, rồi tìm q2 sao cho q2®q1, …

Nhờ đi tới và đi lui, ta tìm được hai dãy mệnh đề sau:

p®p1, p1®p2, … và …, q2®q1, q1®q.

Nếu hai dãy mệnh đề gặp nhau, ta cómột mệnh đề chung r sao cho pn®r và r®qm cho bất cứ trị số n và m nào. Như thế chứng minh là hoàn tất, ta chỉ cần nối hai dãy mệnh đề trên là ta có một chứng minh cho p®q:

p®p1®p2…pn®r®qm…q2®q1®q.

Ví dụ:

Định lý:

Nếu a, b, và c là những số thực, thì

a2 + b2 + c2 ³ ab + bc + ca.

Giải thích:

Giả thiết: a, b, và c là những số thực.

Kết luận: a2 + b2 + c2 ³ ab + bc + ca.

Chứng minh trực tiếp.

Đi tới:

Từ giả thiết, ta có:

a, b, và c là những số thực.

Cho mỗi số thực x, x2 ³ 0.

(a - b) 2 = a2 – 2ab + b2 ³ 0.

Ta bị kẹt tại đây?!

Đi lui:

Từ kết luận ta có:

a2 + b2 + c2 ³ ab + bc + ca

Nhân hai vế cho 2:

2a2 + 2b2 + 2c2 ³ 2ab + 2bc + 2ca

Chuyển vế:

2a2 - 2ab + 2b2 - 2bc + 2c2 – 2ca ³0

Sắp đặt lại:

(a2 -2ab+b2) + (b2 -2bc+c2) + (c2-2ca+a2) ³ 0

Hay

(a - b) 2 + (b - c) 2 + (c - a) 2 ³ 0

Chứng minh:

Chứng minh trực tiếp.

Giả sử a, b, và c là những số thực.

Vì cho mỗi số thực x, x2 ³ 0,

(a - b)2 + (b - c)2 + (c - a)2 ³ 0

Bình phương mỗi số hạng:

(a2 -2ab+b2) + (b2 -2bc+c2) + (c2-2ca+a2) ³ 0

Sắp đặt lại:

2a2 - 2ab + 2b2 - 2bc + 2c2 – 2ca ³0

Chuyển vế:

2a2 + 2b2 + 2c2 ³ 2ab + 2bc + 2ca

Chia 2 vế cho 2:

a2 + b2 + c2 ³ ab + bc + ca.

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

4.7 Chứng minh p®q: trực tiếp hay gián tiếp.

1. Định lý thường có dạng mệnh đềđ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.
2. 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. Đó là 3 trường hợp làm P ® Q đúng:

1) P đúng và Q đúng (hàng 1)

Ta có P đúng và Q đúng, thì P ® Q đúng.

Đây là phương pháp chứng minh trực tiếp: giả sử P đúng, qua những bước luận lý, kết luận Q đúng.

Ví dụ:

Định lý:

Nếu n là số nguyên lẻ, thì n2 lẻ.

Chứng minh:

Giả thiết: n là số nguyên lẻ

Kết luận: n2 lẻ

Chứng minh trực tiếp.

Giả sử n lẻ, thì theo định nghĩa, có số nguyên k sao cho n = 2k + 1. Vậy,

n2 = (2k+1)(2k+1) = 4k2+4k+1= 2(k2+2k)+1.

Vì (k2 + 2k) là số nguyên, nên n2 lẻ.

Ta đã chứng minh rằng nếu giả thiết đúng, thì kết luận đúng; vậy, định lýđược chứng minh.

2) P sai và Q đúng (hàng 3)

Ta có P sai và Q đúng, thì P ® Q đúng.

Ví dụ:

Chứng minh rỗng.

Chứng minh giả thiết p sai, thì p ® qđúng.

Ví dụ: Cho x Î R. Nếu x2 + 1 < 0, thì x5³ 4.

Chứng minh:

Vì x2 + 1 > x2 ³ 0 đúng, thì x2 + 1 < 0 là sai với mọi

x Î R.

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

3) p sai và q sai (h àng 4)

Ta có p sai và q sai, vì Øq®Øp º p®q, thì p®q đúng.

Đây là phương pháp chứng minh giántiếp p®q đúng. Có hai cách:

1. Chứng minh phản chứng(contrapositive)

Là chứng minh trực tiếp Øq ® Øp.

Giả sử Øq đúng, và chứng minh Øpđúng.

Ví dụ 1:

Cho x Î Z. Nếu 3x -15 chẵn, thì x lẻ.

Chứng minh:

Phản chứng của định lý là:

Nếu x chẵn, thì 3x – 15 lẻ.

Chứng minh phản chứng.

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

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. €

Ví dụ 2:

Định lý:

Giả sử m và b là những số thực với m ¹0 và f là hàm xác định bởi f(x) = mx+b. Nếu x ¹ y, thì f(x) ¹ f(y).

Giải thích:

Phản chứng của định lý là:

Nếu f(x) = f(y), thì x = y.

Chứng minh:

Chứng minh phản chứng.

Giả sử f(x) = f(y). Thì mx + b = my + b. Trừ b từ 2 vế, rồi chia m từ 2 vế, ta có x = y. Định lý được chứng minh. €

2. Chứng minh mâu thuẫn(contradiction)

Ta có Ø(p® q) º p Ù Øq.

Chứng minh mâu thuẫn thiết lập p® q bởi:

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.

Chứng minh mâu thuẫn là chứng minh gián tiếp, vì nó rút ra mâu thuẫn pʌØp, rồi kết luận p®q đúng.

Ví dụ 1: Nếu 3n + 2 lẻ, thì n lẻ.

Chứng minh:

Giả sử 3n + 2 lẻ và n chẵn. Thì n = 2k, có k ∈ N.

Suy ra, 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).

Vì (3k +1) ∈N, nên 3n + 2 chẵn, mâu thuẫn với giả thiết là 3n + 2 lẻ. Định lý được chứng minh. €

Ví dụ 2:

Cho mọi số thực x và y, nếu x + y ³ 2, thì hoặc x ³ 1 hoặc y ³1.

Chứng minh:

Giả sử kết luận sai. Thì x < 1 và y < 1.

Cộng những bất đẳng thức này ta có

x + y <1 + 1 = 2.

Như vậy, ta có mâu thuẫn p ʌ Øp, với

p: x + y ³ 2.

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

Tóm tắt, chứng minh p® q có 3 phương pháp sau:

1. Chứng minh trực tiếp:

Giả sử p đúng, qua những bước luận lý, kết luận q đúng.

2. Chứng minh phản chứng:

Giả sử Øq đúng, qua những bước luận lý, kết luận Øp đúng.

3. Chứng minh mâu thuẫn:

Giả sử p đúng và Øq đúng, qua những bước luận lý, kết luận mâu thuẫn.

Ví dụ:

Định lý:

Cho x và y là những số thực. Nếu x ¹ y, thì ex ¹ ey.

Chứng minh:

1. Trực tiếp:

Nếu x ¹ y, thì x>y hoặc y>x. Ta có thể giả sử x>y vì x và y là những số thực, và ta có thể đặt x lớn hơn cả hai số. Thìcó một số dương r sao cho x = y + r, và

ex = ey+r= eyer. Vì e>1 và r>0, er>1. Do đó, eyer > ey. Vậy, ex ¹ ey.

2. Phản chứng:

Giả sử ex = ey. Thì x = ln(ex) = ln(ey) = y. Định lý đưọc chứng minh.

3. Mâu thuẫn:

Giả sử x ¹ y và ex = ey. Bởi định lý Rolle, có một z giữa x và y sao cho ez = 0. Điều này là mâu thuẫn vì e > 0 và do đó eu >0 cho mỗi số thực u. Định lýđược chứng minh.

4.8 Chứng minh theo giả thiết hay theo kết luận

Chứng minh của định lý thường lệthuộc vào dạng luận lý của giả thiết vàkết luận.

1. Chứng minh theo dạng của giả thiết thường cho ta những mệnh đề đúng mới có thể dùng cho giả thiết của chứng minh.

Ví dụ:

Định lý:

Giả sử A Í B, a Î A, và cả hai a và b không là những phần tử của B. Thì b ÏB.

Giải thích:

Giả thiết:

A Í B

a Î A

Ø(a Î B Ù b Î B)

Kết luận:

b Ï B

Và

Ø(a Î B Ù b Î B) º a Ï B Ú b Ï B (DeMorgan)

º a Î B ® b Ï B (luật điều kiện)

Thêm kết quả trên vào giả thiết đã có,ta có

Giả thiết:

A Í B

a Î A

a Î B ® b Ï B

Kết luận:

b Ï B

Chứng minh:

Vì a Î A và A Í B, ta kết luận a Î B. Nhưng cả hai a và b không là những phần tử của B. Vậy, bÏB. €

2. Chứng minh theo dạng của kết luận thường cho ta những phương phápchứng minh tương đương nhưng dễdàng hơn.

Ta chú trọng đến những phương pháp chứng minh theo dạng của kết luậntrong những chương sau.

Chương 5

Chứng minh kết luận dạng q

5.1 Chứng minh kết luận dạng q

Là chứng minh định lý dạng p®q:

nếu p thì q, với p là giả thiết và q là kết luận.

Ta có thể dùng những cách chứng minh của (4.7).

Ví dụ 1:

Định lý:

Cho a là số thực. Thì |-a| = |a|.

Giải thích:

Giả thiết: a là số thực.

Kết luận: |-a| = |a|.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Nếu a = 0, thì kết luận đúng; không cógì đáng nói.

Vậy, ta giả sử a ¹ 0.

Nếu a>0, thì –a < 0; vậy, |a| = a và |-a| = -(-a) = a.

Nếu a<0, thì –a > 0; vậy, |a| = -a và |-a| = -a.

Vậy, cho mỗi lựa chọn của a, thì |-a| = |a|. €

Ví dụ 2:

Định lý:

Cho A, B, và C là những tập. Nếu A Í B và B Í C, thì A Í C.

Giải thích:

Giả thiết:

A, B, và C là những tập.

A Í B và B Í C.

Kết luận: A Í C.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử A Í B và B Í C. Nếu A = Æ, thì A Í C, vì

Æ Í C.

Giả sử A ¹ Æ và x Î A. Vì A Í B, xÎB. Vì B Í C, xÎC.

Vậy, A Í C. ð

Ví dụ 3:

Định lý:

Nếu n là một số nguyên chẵn, thì n2 chẵn.

Giải thích:

Giả thiết: n là một số nguyên chẵn.

Kết luận: n2 chẵn.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Ta cần hiểu rõ định nghĩa của những từ dùng trong định lý, như

Định nghĩa: n là một số nguyên chẵn nếu và chỉ nếu có một số nguyên k sao cho n = 2k.

Chứng minh:

Giả sử n là một số nguyên chẵn. Thì n = 2k cho số nguyên k và

n2 = (2k)2 = 4k2 = 2(2k2).

Vì 2k2 là số nguyên. Vậy, n2 là chẵn. €

5.2 Đôi khi ta diễn tả định lý dạng khẳng định q sang dạng phủ định Øq, rồi chứng minh phản chứng.

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ụ 1:

Định lý:

Giả sử a, b, và c là những số thực và a > b.

Nếu ac £ bc thì c £ 0.

Giải thích:

Giả thiết:

a, b, và c là những số thực

a > b

Kết luận: (ac £ bc) ® c £ 0

Phản chứng của kết luận là Ø(c £ 0) ®Ø(ac £ bc) hay (c > 0) ® (ac > bc).

Chứng minh kết luận dạng Øq ® Øp.

Chứng minh:

Chứng minh phản chứng.

Giả sử c > 0. Thì ta có thể nhân hai vếcủa bất đẳng thức a > b bởi c và kết luận rằng ac > bc. Vậy, nếu ac £ bc thìc £ 0. Định lý được chứng minh. ð

Ví dụ 2:

Định lý:

Giả sử a, b là những số thực. Thì |a + b| £ |a| + |b|.

Giải thích:

Giả thiết: a, b là những số thực.

Kết luận: |a + b| £ |a| + |b|.

Chứng minh kết luận dạng q với £trong trường hợp này khó hơn chứng minh phản chứng.

Ta chuyển kết luận dạng q sang dạng Øq, ta có:

Phủ định của |a+b| £ |a|+|b| là |a|+|b| < |a+b|.

Giả thiết: a, b là những số thực.

Kết luận: |a| + |b| < |a + b|.

Chứng minh kết luận dạng Øq bằng phản chứng.

Chứng minh:

Giả sử |a + b| £ |a| + |b| là không đúng; đó là, giả sử rằng |a| + |b| < |a + b| cho vài lựa chọn a, b.

Vì mỗi vế của bất đẳng thức này làkhông âm, ta có thể bình phương mỗi vế để có

|a|2 + 2|a||b| + |b|2 < |a + b|2

Đơn giản, ta có

a2 + 2|a||b| + b2 < (a + b)2

Hay

a2 + 2|a||b| + b2 < a2 + 2ab + b2

Hay

|a||b| < ab.

Nhưng đây là phủ định của ab £ |a||b|. Vậy, ta đã chứng minh rằng nếu |a + b| £ |a| + |b| không đúng, thì ab £ |a||b| không đúng. Nhưng ta biết rằng ab £|a||b| đúng; vậy, |a + b| £ |a| + |b| đúng. ð

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

Chứng minh kết luận q đúng, thì p ® qđúng.

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

Chứng minh:

Vì x2 ³ 0, cho mọi x ∈ R, thì x2 + 1 > x2³ 0 là đúng.

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

Chương 6

Chứng minh kết luận dạng Øq

Chứng minh kết luận dạng Øq có haicách:

6.1 Nếu có thể ta diễn tả dạng phủ định Øq sang dạng khẳng định q, vì chứng minh dạng khẳng định q thường dễ dàng hơn.

Ví dụ 1:

Định lý:

Giả sử A Ç C Í B và a Î C. Thì a ÏA \ B.

Giải thích:

Giả thiết: A Ç C Í B và a Î C

Kết luận: a Ï A \ B

Chứng minh kết luận dạng Øq.

Đổi dạng phủ định sang dạng khẳngđịnh:

a Ï A \ B º Ø(a Î A Ù a Ï B) (định nghĩa A\B)

º a Ï A Ù a Î B (luật De Morgan)

º a Î A ® a Î B (luật điều kiện)

Ta có:

Giả thiết: A Ç C Í B và a Î C

Kết luận: a Î A ® a Î B

Chứng minh kết luận dạng p ® q.

Thêm a Î A vào giả thiết ta có:

Giả thiết: A Ç C Í B, a Î C, và a Î A

Kết luận: a Î B

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử a Î A. Thì a Î A Ç C. Nhưng vì A Ç C Í B, ta suy ra a Î B. Vậy, không làtrường hợp a Î A, nhưng không là B; do đó, a Ï A \ B. €

6.2 Đôi khi ta không thể diễn tả định lý dạng phủ định Øq sang dạng khẳng định q, ta dùng chứng minh mâu thuẫn.

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.

Chứng minh mâu thuẫn là chứng minh gián tiếp, vì nó rút ra mâu thuẫn pʌØp, rồi kết luận p®q đúng.

Ví dụ 1:

Định lý:

Nếu x2 + y = 13 và y ¹ 4, thì x ¹ 3.

Giải thích:

Giả thiết: x2 + y = 13 và y ¹ 4

Kết luận: x ¹ 3

Chứng minh kết luận dạng Øq.

Vì x ¹ 3 º Ø(x = 3) không thể đổi sang dạng khẳng định, ta chứng minh mâu thuẫn:

Giả thiết: x2 + y = 13, y ¹ 4, và x = 3.

Kết luận: mâu thuẫn.

Chứng minh:

Giả sử x2 + y = 13 và y ¹ 4. Giả sử x = 3.

Thay thế x = 3 vào phương trình x2 + y = 13 ta có

9 + y = 13, suy ra y = 4.

Điều này mâu thuẫn với y ¹ 4. Do đó, x ¹ 3.

Vậy, nếu x2 + y = 13 và y ¹ 4, thì x ¹ 3. €

Ví dụ 2:

Định lý:

Giả sử A Í B, a Î A, và cả hai a và b không là những phần tử của B. Thì b ÏB.

Giải thích:

Giả thiết:

A Í B

a Î A

cả hai a và b không là những phần tử của B

Kết luận: b Ï B

Chứng minh kết luận dạng Øq.

Từ giả thiết suy ra kết luận.

Chứng minh:

Vì a Î A và A Í B, ta kết luận a Î B. Nhưng cả hai a và b không là những phần tử của B. Vậy, b Ï B. €

Ví dụ 3:

Định lý:

Giả sử A, B, và C là những tập hợp, A\B Í C, và x là bất cứ vật gì. Nếu x Î A \ C thì x Î B.

Giải thích:

Giả thiết:

A, B, và C là những tập hợp

A\B Í C

x là bất cứ vật gì.

Kết luận:

Nếu x Î A \ C thì x Î B.

Chứng minh kết luận dạng p ® q.

Thêm p vào giả thiết đã có, ta có:

Giả thiết:

A, B, và C là những tập hợp

A\B Í C

x là bất cứ vật gì.

x Î A \ C

Kết luận:

x Î B.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử x Î A \ C, nghĩa là x Î A và x Ï C.

Giả sử x Ï B. Thì x Î A \ B; vì A\B Í C, x Î C. Nhưng điều này mâu thuẫn với x Ï C. Do đó, x Î B.

Vậy, nếu x Î A \ C thì x Î B. €

Chương 7

Chứng minh kết luận dạng p ® q

(trực tiếp)

7.1 Chứng minh kết luận dạng p ® q

Ta có thể dùng những phương pháp chứng minh mệnh đề p®q (4.7) hay phương pháp chứng minh điều kiện(3.4).

Đó là, ta giả sử p đúng, thêm phần giảthiết p này vào danh sách tiền đề (tiên đề, định nghĩa, hay định lý đã chứng minh), rồi suy ra kết luận q.

7.2 Ví dụ

Ví dụ 1:

Định lý: Giả sử a và b là số thực. Nếu 0 < a < b, thì a2 < b2.

Giải thích:

Giả thiết:

a và b là những số thực

Kết luận:

(0 < a < b) ® (a2 < b2)

Chứng minh kết luận dạng p ® q.

Thêm 0 < a < b vào giả thiết đã có, ta có

Giả thiết:

a và b là những số thực

0 < a < b

Kết luận:

a2 < b2

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử 0 < a < b. Nhân a < b với a, ta có a2 < ab. Tương tự, nhân a < b với b, ta có ab < b2.

Vậy, a2 < ab < b2 hay a2 < b2. €

Ví dụ 2:

Cho x ∈ Z. Nếu 3x -15 chẵn, thì x lẻ.

Giải thích:

Giả thiết: x ∈ Z

Kết luận: Nếu 3x -15 chẵn, thì x lẻ.

Chứng minh kết luận dạng p ® q.

Thêm p vào giả thiết đã có, ta có:

Giả thiết:

x ∈ Z

3x -15 chẵn.

Kết luận:

x lẻ.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

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ẻ. €

Ví dụ 3:

Nếu n là một số nguyên lẻ, thì 4n3 + 2n - 1 là một số nguyên lẻ.

Giải thích:

Giả thiết:

n là một số nguyên lẻ.

Kết luận:

4n3 + 2n - 1 là một số nguyên lẻ.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử n là một số nguyên lẻ, thì n = 2k + 1, có kÎZ.

Vậy,

4n3 + 2n – 1 = 4(2k + 1)3 + 2(2k + 1) - 1

= 4(4k3 + 12k2 + 6k + 1) + 4k + 2 - 1

= 16k3 + 48k2 + 28k + 5

= 2(8k3 + 24k2 + 14k + 2) + 1

Vì 8k3 + 24k2 + 14k + 2 Î Z, nên 4n3 + 2n - 1 lẻ. €

Ví dụ 4:

Định lý: Giả sử m và n là số nguyên. Nếu mn chẵn, thì m chẵn hoặc n chẵn.

Giải thích:

Giả thiết:

m và n là số nguyên.

Kết luận:

Nếu mn chẵn, thì m chẵn hoặc n chẵn.

Chứng minh kết luận dạng p ® q.

Thêm p vào giả thiết đã có, ta có

Giả thiết:

m và n là số nguyên.

mn chẵn.

Kết luận:

m chẵn hoặc n chẵn.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử mn chẵn. Thì mn = 2k, có kÎZ.

Nếu m chẵn thì không còn gì chứng minh, vậy giả sử m lẻ, thì m = 2j + 1, có jÎZ. Thay 2j + 1 vào mn = 2k, ta có (2j + 1)n = 2k, vậy 2jn + n = 2k và n = 2k - 2jn = 2(k - jn).

Vì k - jn là số nguyên, nên n chẵn. €

Chương 8

Chứng minh kết luận dạng Øq ®Øp

(gián tiếp)

Chứng minh kết luận dạng Øq ® Øp.

Ta có thể dùng những phương pháp chứng minh gián tiếp (4.7).

Có hai cách:

8.1 Chứng minh phản chứng(contrapositive)

Là chứng minh trực tiếp Øq ® Øp.

Giả sử Øq đúng, và chứng minh Øpđúng.

Ví dụ 1:

Định lý:

Nếu bình phương của một số nguyên dương là chẵn, thì số nguyên dương là chẵn.

Giải thích:

Giả thiết: bình phương của một số nguyên dương là chẵn.

Kết luận: số nguyên dương là chẵn.

Phản chứng là:

Nếu số nguyên dương là lẻ, thìbình phương của nó là lẻ.

Chứng minh định lý dạng Øq ® Øp.

Chứng minh:

Chứng minh phản chứng.

Giả sử số nguyên dương là lẻ (không chẵn).

Theo định nghĩa thì bất cứ số nguyên dương lẻ đều có dạng 2k - 1, với kÎZ. Vậy, (2k-1)2 = 4k2 – 4k + 1 = 2(2k2 – 2k) + 1.

Vì (2k2 – 2k) là số nguyên, (2k-1)2 là số nguyên lẻ. Định lý được chứng minh. €

8.2 Chứng minh mâu thuẫn(contradiction)

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ụ 1:

Định lý:

Có vô hạn số nguyên tố.

Chứng minh:

Giả sử chỉ có hữu hạn số nguyên tố p1, p2, …,pn.

Đặt m = p1p2…pn + 1.

Bởi định lý căn bản của số học, m là số nguyên tố hay tích của những số nguyên tố. Tuy nhiên, không có pj chia m, vì nếu pj|m thì pj chia m - p1p2…pn = 1. Điều này mâu thuẫn với giả thiết làta đã liệt kê tất cả những số nguyên tố. Vậy, có vô hạn số nguyên tố. €

Ví dụ 2:

Định lý:

Nếu r là một số thực sao cho r2= 2, thì r là số vô tỉ.

Giải thích:

Giả thiết:

r là số thực sao cho r2= 2.

Kết luận:

r là số vô tỉ.

Chứng minh mâu thuẫn:

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.

Chứng minh:

Giả sử r2= 2 và r kh ông là số vô tỉ. Thìr là hữu tỉ, vậy, có những số nguyên m và n sao cho r = m/n. Ta có thể giả sử m và n không có số chia chung lớn hơn 1 vì nếu chúng có, ta có thể chia tử số và mẫu số cho số chia chung lớn nhất. Vậy, r2= m2/n2, suy ra

m2= r2 n2. Vì r2= 2, ta có m2= 2n2. Vậy, m2 chẵn và m chẵn. Do đó, có một số nguyên p sao cho m = 2p. Vậy, 2n2 = m2= 4p2 và n2 = 2p2. Suy ra n2 chẵn và n chẵn. Vì cả hai m và n chẵn, chúng có một số chia chung lớn hơn 1. Đây là một mâu thuẫn với giả thiết là m và n không có số chia chung lớn hơn 1. Định lý được chứng minh. €

Chương 9

Chứng minh kết luận dạng p Ù q

9.1 Chứng minh kết luận dạng p Ù qthật đơn giản.

Ta chứng minh p và q riêng biệt.

Ví dụ 1:

Chứng minh trực tiếp mệnh đề sau

Nếu d = min(d1, d2) và x £ d, thì x £d1 và x £ d2.

Giải thích:

Giả thiết: d = min(d1, d2) và x £ d

Kết luận: x £ d1 và x £ d2

Chứng minh kết luận dạng p Ù q.

Chứng minh riêng biệt p và q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử d, d1, d2, x là những số thực bất kỳ.

Giả sử

d = min(d1, d2) và x £ d

đúng, rồi chứng minh rằng

x £ d1 và x £ d2

đúng.

Từ định nghĩa của min, ta có d £d1 và d £ d2.

Vì x £ d và d £ d1, ta có x £ d1.

Tương tự, vì x £ d và d £ d2, ta có x £d2.

Vậy, x £ d1 và x £ d2. €

Ví dụ 2:

Định lý:

Giả sử A Í B, và A và C cách biệt. ThìA Í B\C.

Giải thích:

Giả thiết:

A Í B

A Ç C = Æ

Kết luận: A Í B\C

Theo định nghĩa thì A Í B\C là "x(x Î A ® x Î B\C). Vậy, ta đặt x bất kỳ, giả sử x Î A, và chứng minh rằng x Î B\C.

Bây giờ x Î B\C nghĩa là x Î B Ù x Ï C. Vậy, ta chứng minh riêng biệt x Î B vàx Ï C.

Giả thiết:

A Í B

A Ç C = Æ

x Î A

Kết luận: x Î B, x Ï C

Chứng minh kết luận dạng p Ù q.

Chứng minh riêng biệt x Î B và x Ï C

Từ giả thiết suy ra kết luận.

Chứng minh:

Giả sử x Î A.

Vì A Í B, suy ra x Î B.

Vì A và C cách biệt, ta có x Ï C.

Vậy, x Î B\C.

Vì x là phần tử bất kỳ của A, ta kết luậnA Í B\C. €

Ví dụ 3:

Định lý:

Nếu A Í B, thì A È C Í B È C và A Ç C Í B Ç C.

Giải thích:

Giả thiết:

A Í B

Kết luận:

A È C Í B È C và A Ç C Í B Ç C

Chứng minh kết luận dạng p Ù q.

Chứng minh riêng biệt AÈC Í BÈC vàAÇC Í BÇ C.

Từ giả thiết suy ra kết luận.

Chứng minh:

a. Chứng minh AÈC Í BÈC:

Giả sử A Í B và x Î AÈC. Để chứng tỏ xÎ BÈC, thì đủ để chứng tỏ nếu x Ï C, thìx Î B.

Vậy, giả sử x Ï C. Thì x Î A và A Í B, x ÎB.

b. Chứng minh A Ç C Í B Ç C:

Giả sử A Í B và x Î AÇC. Thì x Î A và x Î C.

Vì x Î A và A Í B, x Î B.

Suy ra x Î B và x Î C; vậy, x Î BÇC. €

9.2 Chứng minh dạng p « q

1. Vì p « q º (p ® q) Ù (q ® p).

p	q	p«q	p®q	q®p	p®q Ùq®p
đ	đ	đ	đ	đ	đ
đ	s	s	s	đ	s
s	đ	s	đ	s	s
s	s	đ	đ	s	đ

2. Để chứng minh p « q, ta phải chứng minh p ® q và q ® p riêng biệt.

Ví dụ 1:

Định lý:

Giả sử x là một số nguyên. Thì x chẵn nếu và chỉ nếu x2 chẵn.

Chứng minh:

(®) Giả sử x chẵn. Thì x = 2k, có k Î Z. Do đó,

x2 = (2k)2 = 4k2 = 2(2k2); vì 2k2 là số nguyên, nên

x2 chẵn.

Vậy, nếu x chẵn thì x2 chẵn.

(¬) Giả sử x lẻ. Thì x = 2k + 1, có k ÎZ. Do đó,

x2 = (2k + 1)2 = 4k2 + 4k +1 = 2(2k2 + 2k) + 1; vì 2k2 + 2k là số nguyên, nên x2 lẻ.

Vậy, nếu x2 chẵn thì x chẵn. €

Ví dụ 2:

Định lý: Cho mỗi số nguyên n, 6|n nếu và chỉ nếu 2|n và 3|n.

Chứng minh:

Đặt n là bất kỳ số nguyên.

(®) Giả sử 6|n. Thì ta chọn số nguyên k sao cho 6k = n. Vậy, n = 6k = 2(3k), nên 2|n. Tương tự, n = 3(2k), nên 3|n.

(¬) Giả sử 2|n và 3|n. Thì ta chọn số nguyên j và k sao cho n = 2j và n = 3k. Vậy, 6(j-k) = 6j – 6k = 3(2j) – 2(3k) = 3n – 2n = n, nên 6|n. €

Ví dụ 3:

Định lý:

Giả sử B là một tập hợp. {Ai|iÎI} là một họ có số chỉ của những tập hợp, và I ¹Æ.

Chứng minh rằng B Ç (ÈiÎIAi) = ÈiÎI (B Ç Ai).

Chứng minh:

Đặt x bất kỳ.

(®) Giả sử x Î B Ç (ÈiÎIAi). Thì x Î B và x Î ÈiÎIAi.

Ta có thể chọn i0 Î I sao cho x Î Ai0.

Vì x Î B và x Î Ai0, x Î B Ç Ai0.

Vậy, x Î ÈiÎI (B Ç Ai).

(¬) Giả sử x Î ÈiÎI (B Ç Ai). Thì ta cóthể chọn i0 Î I sao cho x Î B Ç Ai0. Vậy,x Î B và x Î Ai0.

Vì x Î Ai0, x Î ÈiÎI Ai.

Vì x Î B và x Î ÈiÎIAi, x Î B Ç (ÈiÎIAi).

Vì x bất kỳ, ta đã chứng minh rằng

"x[x Î B Ç (ÈiÎIAi) « x Î ÈiÎI (B Ç Ai)].

Vậy, B Ç (ÈiÎIAi) = ÈiÎI (B Ç Ai). €

Chương 10

Chứng minh kết luận dạng p Ú q

(trường hợp)

10.1 Chứng minh kết luận dạng p Ú q

Để chứng minh mệnh đề điều kiện dạng

(p1 Ú p2 Ú …Ú pn) ® q

Công thức hằng đúng

[(p1Úp2Ú…Úpn) ®q]«

[(p1®q)Ù(p2®q)Ù…Ù(pn®q)] ®q]

có thể được dùng như quy tắc suy luận.

Đó là, mệnh đề điều kiện (p1Ú p2Ú…Úpn) ® q có thể được chứng minh bởimỗi n mệnh đề pi ® q, với i=1, 2, …, n, riêng lẻ.

Cách chứng minh này là chứng minh trường hợp.

10.2 Ví dụ

Ví dụ 1:

Định lý:

Cho mọi số thực x và y, |xy| = |x||y|.

Chứng minh:

Vì |x|, trị số tuyệt đối của x, bằng x khi x ³ 0 và bằng

–x khi x < 0.

Có 4 trường hợp:

1. p1 ® q: Nếu x ³ 0 và y ³ 0, thì xy ³ 0.

Vậy, |xy| = xy = |x||y|.

2. p2 ® q: Nếu x ³ 0 và y < 0, thì xy £0.

Vậy, |xy| = -xy = x(-y) = |x||y|.

3. p3 ® q: nếu x < 0 và y ³ 0, thì xy £ 0.

Vậy, |xy| = x(-y) = -xy = |x||y|.

4. p4 ® q: Nếu x < 0 và y < 0, thì xy > 0.

Vậy, |xy| = xy = (-x)(-y) = |x||y|.

Vậy, |xy| = |x||y|. ð

Ví dụ 2:

Cho n∈Z, thì n2 + 3n + 5 là một số nguyên lẻ.

Chứng minh:

Có 2 trường hợp:

1. Khi n chẵn: Thì n = 2x, có x∈Z.

n2 + 3n + 5 = 4x2 + 6x + 5

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

2. Khi n lẻ: Thì n = 2x + 1, có x∈Z.

n2 + 3n + 5 = 4x2 + 4x + 1 + 6x + 3 + 5

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

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

Ví dụ 3:

Giả sử A, B, và C là những tập hợp. Nếu A Í C và

B Í C thì A È B Í C.

Chứng minh:

Giả sử A Í C và B Í C. Cho x là một phần tử bất kỳ của A È B. Thì x Î A hoặc x Î B.

Có 2 trường hợp:

1. x Î A.

Vì A Í C, x Î C.

2. x Î B.

Vì B Í C, x Î C.

Vì ta biết x Î A hoặc x Î B, những trường hợp này là tất cả; vậy, ta kết luận rằng x Î C.

Vì x là một phần tử bất kỳ của A È B, nghĩa là

A È B Í C. €

Ví dụ 4:

Định lý: Cho mọi số nguyên x, khi chia x2 cho 4 thì số dư là 0 hoặc 1.

Chứng minh:

Giả sử x là một số nguyên. Ta coi 2 trường hợp sau:

1. x chẵn. Thì x = 2k, có k Î Z.

Vậy, x2 = 4k2. Đó là, khi chia x2 cho 4 thì số dư là 0.

2. x lẻ. Thì x = 2k + 1, có k Î Z.

Vậy, x2 = 4k2 + 4k + 1. Đó là, khi chia x2 cho 4 thì số dư là 1. €

Ví dụ 5:

Định lý:

Cho mỗi số thực x, nếu x2 ³ x thì x £ 0 hay x ³ 1.

Chứng minh:

Giả sử x2 ³ x.

1. Nếu x £ 0, thì x £ 0 hay x ³ 1.

2. Nếu x > 0, thì ta có thể chia 2 vế của bất đẳng thức x2 ³ x bởi x để kết luận rằng x ³ 1.

Vậy, x £ 0 hay x ³ 1. €

Chương 11

Chứng minh kết luận dạng "xP(x)

11.1 Chứng minh VxP(x) là chứng minh phổ dụng.

Khi tất cả phần tử trong miền đối tượng D có thể liệt kê như x1,x2,…,xn thì "xP(x) giống như P(x1)ÙP(x2) Ù…ÙP(xn), vì phép hội này là đúng nếu và chỉ nếu mỗi P(x1), P(x2),…,P(xn) là đúng.

Câu "xP(x):

Đúng, nếu P(x) đúng với mọi x trong D.

Sai, nếu P(x) sai với ít nhất một x trong D.

1. Chứng minh VxP(x) đúng

Để chứng minh VxP(x) là đúng, với P là hàm mệnh đề, ta phải xét tất cả các giá trị trong miền đối tượng và chứng minh rằng với mọi x, P(x) là đúng.

Ví dụ 1: Câu

Với mọi số thực x, x2 ³ 0

Là câu lượng từ phổ dụng. Miền đối tượng là tập số thực. Câu này là đúng vì với mọi số thực x, bình phương của x là dương hoặc zero.

Ví dụ 2:

Cho P(x) là câu “x + 1 > x”. Tìm thực trị của "xP(x) với miền đối tượng là tất cả số thực.

Giải:

Vì P(x) là đúng cho tất cả số thực x, "xP(x) là đúng.

2. Chứng minh VxP(x) sai

1. Để chứng minh "xP(x) là sai, với P là hàm mệnh đề, ta chỉ cần tìm một đối tượng x trong miền đối tượng làm cho P(x) sai. Một đối tượng x như thế gọi là một phản ví dụ của "xP(x).

2. Định nghĩa:

Phương pháp tìm phần tử thích hợp a và chứng minh P(a) sai được gọi là chứng minh bằng phản ví dụ.

Ví dụ 1:

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 có:

1 = 02 + 02 + 12,

2 = 02 + 12 + 12,

3 = 12 + 12 + 12,

4 = 02 + 02 + 22,

5 = 02 + 12 + 22,

6 = 12 + 12 + 22.

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. €

Ví dụ 2:

Chứng minh mệnh đề “Cho mỗi số thực x, x2 – 1 > 0” là sai.

Chứng minh:

Cho mỗi số thực x, x2 - 1 > 0 là sai, vì nếu x = 1 thì mệnh đề

12 - 1 > 0

là sai.

Vậy, 1 là một phản ví dụ chứng tỏ rằng mệnh đề “Cho mỗi số thực x, x2 – 1 > 0” là sai. €

Ví dụ 3:

Chứng minh mệnh đề “Cho mỗi số nguyên dương n, nếu n chẵn, thì n2 + n + 19 là số nguyên tố” là sai.

Chứng minh:

Ta có một phản ví dụ khi n = 38, thì

382 + 38 + 19 = 38 x 38 + 38 + 19 = 19(2 x 38 + 2 + 1) = 19 x 79 là một số hợp. Vậy, 382 + 38 + 19 không là số nguyên tố. €

Ví dụ 4:

Tìm một phản ví dụ cho mệnh đề “Cho mọi tập A, B và C, thì A È (B - C) = (A È B) – C.”

Chứng minh:

Cho A = {1, 2, 3, 4, 5}, B = {2, 4, 6}, C = {2, 3, 5}.

Thì B – C = {4, 6} và A È (B - C) = {1, 2, 3, 4, 5, 6}.

Tuy nhiên A È B = {1, 2, 3, 4, 5, 6} và (A È B) – C = {1, 4, 6}.

Vậy, A È (B - C) ¹ (A È B) – C. €

11.2 Chứng minh lượng từ lồng:

Ví dụ:

Cho P(x,y): nếu x2 < y2, thì x < y.

Miền đối tượng là tập số thực.

1. Câu

Cho mọi x, cho mọi y, P(x, y)

Là sai. Một phản ví dụ là x=1, y=-2. Trong trường hợp này, ta có mệnh đề sai

nếu 12<(-2)2, thì 1<-2.

2. Câu

Cho mọi x, có một y, P(x, y)

Là đúng. Ta chứng tỏ rằng cho mọi x, mệnh đề

Có một y, nếu x2<y2, thì x< y

Là đúng bằng cách chỉ rõ một trị số của y sao cho

nếu x2<y2, thì x<y

là đúng. Thật vậy, nếu ta đặt y=0, ta có mệnh đề đúng

nếu x2<0, thì x<0.

(mệnh đề điều kiện đúng, vì giả thuyết x2<0 là sai). €

3. Câu

Cho mọi y, có một x, P(x, y)

Là đúng. Ta chứng tỏ rằng cho mọi y, mệnh đề

Có một x, nếu x2<y2, thì x<y

Là đúng bằng cách chỉ rõ một trị số cuả x sao cho

nếu x2<y2, thì x<y

là đúng. Thật vậy, nếu ta đặt x=|y|+1, ta có mệnh đề đúng

nếu (|y|+1)2<y2, thì |y|+1<y.

(Mệnh đề điều kiện là đúng, vì giả thuyết là sai). €

Chương 12

Chứng minh kết luận dạng ∃xP(x) (tồn tại)

và ∃!xP(x) (tồn tại và duy nhất)

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

Khi tất cả phần tử trong miền đối tượng D có thể liệt kê như x1,x2,…,xn thì $xP(x) giống như P(x1)ÚP(x2)Ú…ÚP(xn), vì phép tuyển này là đúng nếu và chỉ nếu ít nhất một của P(x1), P(x2),…,P(xn) là đúng.

Câu $xP(x):

Đúng, nếu P(x) đúng với ít nhất một x trong D.

Sai, nếu P(x) sai với mọi x trong D.

1. Câu:

Có một x trong D, P(x)

Là đúng cho ít nhất một x trong D.

Ví dụ 1: Chứng minh câu lượng từ hiện hữu

Có một số thực x, x/(x2+1) = 5/26

Là đúng.

Giải:

Vì 5/(52+1) = 5/26 là đúng, khi x = 5, $xP(x) đúng.

Ví dụ 2:

Cho P(x) là câu ‘x > 7’. Tìm thực trị của $xP(x) với miền đối tượng là tất cả số thực.

Giải:

Vì ‘x > 7’ là đúng, khi x = 8, $xP(x) đúng.

2. Câu:

Có một x trong D, P(x)

Là sai, nếu cho mỗi x trong miền đối tượng D, mệnh đề P(x) là sai.

Ví dụ: Chứng minh câu lượng từ hiện hữu

Có một số thực x, 1/(x2+1) > 1

Là sai, ta phải chứng tỏ rằng

1/(x2+1) > 1

Là sai cho mọi số thực x. Bây giờ

1/(x2+1) > 1

Là sai khi

1/(x2+1) £ 1

Là đúng. Vậy, ta phải chứng tỏ rằng

1/(x2+1) £ 1

Là đúng cho mọi số thực x.

Như vậy, cho x là bất cứ số thực nào. Vì 0 £ x2, ta có thể cộng 1 vào hai vế của bất đẳng thức để có

1 £ x2+1.

Nếu ta chia hai vế bởi x2+1, ta có

1/(x2+1) £ 1

Vậy câu

1/(x2+1) £ 1

Là đúng cho mọi số thực x.

Và câu

1/(x2+1) > 1

Là sai cho mọi số thực x.

Ta đã chứng minh câu lượng từ hiện hữu.

Có một số thực x, 1/(x2+1) > 1

là sai. €

Trong ví dụ trên, ta chứng minh rằng câu lượng từ hiện hữu là sai bởi chứng minh rằng câu lượng từ phổ dụng liên hệ là đúng.

12.2 Chứng minh tồn tại

Có hai cách:

1. 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 = 103 + 93 = 123 + 13.

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

2. 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 xy 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à xy 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 xy = (Ö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 xy 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. €

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

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

Có hai phần:

1. Tồn tại: Chứng minh tồn tại phần tửx có tính chất mong muốn.

2. 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ụ 1:

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. €

Ví dụ 2:

Định lý: Có duy nhất một tập hợp A sao cho mọi tập hợp B, thì A È B = B.

Chứng minh:

Tồn tại: Rõ ràng, "B(Æ È B = B), vậy, Æ có tính chất đòi hỏi.

Duy nhất: Giả sử "B(C È B = B) và "B(D È B = B).

Áp dụng giả sử 1 cho D, ta có C È D = D.

Áp dụng giả sử 2 cho C, ta có D È C = C.

Nhưng, C È D = D È C, vậy C = D. €

Chương 13

Chứng minh quy nạp

13.1 Chứng minh quy nạp

Chứng minh ∀nP(n) với nÎN.

13.2 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.

Ta phải chứng minh:

P(1) đúng.

Nếu P(n) đúng, thì P(n+1) đúng.

Vậy, P(n) đúng cho mọi số tự nhiên 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(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:

Định lý:

Nếu {x0, x1, …, xn} Í P, thì x0 + x1 + … + xn Î P.

Chứng minh:

Nếu n = 1, thì định lý đúng, vì đó làtính cách (a) của tiên đề thứ tự.

Giả sử định lý đúng khi n = k cho bất kỳ k Î N.

Vậy, nếu x0, x1, …, xn là bất kỳ k + 1 phần tử của P, thì x0 + x1 + … + xk Î P. (1)

Coi bất kỳ tập hợp của k + 2 phần tửcủa P, như {x0, x1, …, xk+1} Î P, và viết tổng của chúng như sau:

x0 + x1 + … + xk+1 = (x0 + … + xk) + xk+1.

Vế phải là tổng của hai phần tử của P: (x0 + … + xk) Î P bởi (1) và xk+1 là một của tập hợp của k + 2 số dương. Do đó, bởi tính cách (a), tổng của hai số dương này Î P.

Vậy, bởi nguyên tắc quy nạp toán học, định lý đúng cho bất kỳ tập hữu hạn của số dương. ð

13.3 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.

Ta phải chứng minh:

P(1) đúng.

Nếu P(1), P(2), …, P(n) đều đúng, thì P(n+1) đúng.

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(2) Ù... Ù P(k) đúng,

chứng minh P(k+1) đúng.

Ví dụ 1:

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 j, với j £ k, đó là P(1) Ù P(2) Ù... Ù P(k) đúng.

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

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

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

Nếu k+1 là số hợp, thì nó là tích của hai số nguyên a và b với 2 £ a £ b < 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à số hợp, 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. €

Ví dụ 2:

Chứng minh tổng của những số nguyên lẻ £ số nguyên lẻ n là (n+1)2/4.

Chứng minh:

Cho S = {nÎN|n chẵn hay n lẻ và tổng của những số nguyên lẻ £ số nguyên lẻn là (n+1)2/4. }

V ì (1+1)2/4=1, 1ÎS.

Giả sử n Î N và {1, 2,…, n}ÍS.

Nếu n+1chẵn, thì n+1Î S.

Giả sử n+1 lẻ, thì n-1 lẻ và vì n-1 Î S.

1+3+5+…+(n-1) = n2/4.

Cộng n+1 vào 2 vế của phương trình, ta có

1 + 3 +5+…+(n-1) + (n+1)= n2/4+ (n+1)

= [n2+4(n+1)])/4

= (n2+4n+4)/4.

=(n+2)2/4.

Vậy, n+1 Î S. Bởi quy nạp thứ hai, S = N. €

13.4 Chứng minh câu:

P(k), P(k +1), …, P(n) với k ¹ 1, đúng với mọi số tự nhiên k, nÎN.

Ta phải đổi bước cơ bản là:

P(k) là đúng.

Bước quy nạp thì không đổi.

Ví dụ 1:

Chứng minh P(n): 3n > 8n với mọi n ≥ 3.

Chứng minh:

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

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

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

Thật vậy, 3(k+1) = 3(3k). Theo giả thiết qui nạp thì

3k > 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. €

Ví dụ 2:

Chứng minh P(n): 2n < 2n-1 với mọi n ≥ 3.

Chứng minh:

Buớc cơ sở: P(3) đúng, vì 6 < 23-1.

Bước quy nạp: Giả sử P(k) đúng, đó là2k < 2k-1. Thì

2(n+1) = 2n + 2 < 2n – 1 + 2 = 2n +1.

Vì 2n +1 < 2n+1 -1, nên 2(n+1) < 2n+1 -1.

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

Chương 14

Những cách chứng minh khác

14.1 Chứng minh đẳng thức

1. Định lý:

Nếu a1, a2, …, an là những phần tử của một vũ trụ sao cho a1 = a2, a2 = a3,…, an-1 = an thì a1 = an.

Chứng minh:

Giả sử a1, a2, …, an là những phần tử của một vũ trụ sao cho a1 = a2, a2 = a3,…, an-1 = an.

Vì a1 = a2, a2 = a3 suy ra a1 = a3 theo tính truyền.

Vì a1 = a3, a3 = a4 suy ra a1 = a4 theo tính truyền.

Vậy, a1 = an. €

2. Nguyên tắc:

Giả sử a1, a2, …, an là những phần tử của một vũ trụ sao cho a1 = a2, a2 = a3,…, an-1 = an là những mệnh đề đúng.

Thì a1 = an là mệnh đề đúng.

3. Ví dụ:

Định lý:

Cho mọi số thực x, (x + 1)3 = (x3 + 1) + 3x(x + 1).

Chứng minh:

Đặt x là một số thực. Thì:

(x + 1)3 = x3 + 3x2 + 3x + 1

= (x3 + 1) + (3x2 + 3x)

= (x3 + 1) + 3x(x + 1). €

14.2 Chứng minh hiện hữu không xây dựng

1. Định lý đếm tập con:

Nếu A và B là những tập hữu hạn sao cho A Í B và

|A| ¹ |B| thì A Ì B. Vậy, có một phần tử của B không thuộc về A.

Chứng minh:

Cho mọi tập hữu hạn A và B, thì A= B ® |A|=|B|.

Nghịch đảo là: |A| ¹ |B|® A ¹ B.

Bây giờ giả sử rằng A và B là những tập hữu hạn sao cho A Í B và |A| ¹ |B|. Dùng kết quả ở trên suy ra

A Í B và A ¹ B. Vậy, A Ì B, nghĩa là có ít nhất một phần tử của B không thuộc về A. €

2. Nguyên tắc:

Giả sử A và B là những tập hữu hạn sao cho

1) A Í B

2) |A| ¹ |B|.

là những mệnh đề đúng.

Thì có ít nhất một phần tử của B không thuộc về A.

3. Ví dụ:

Định lý:

Có những số thực vô tỉ.

Chứng minh:

Vì mỗi số hữu tỉ là một số thực, ta có QÍ R. Tuy nhiên, |Q| ¹ |R| (Định lý Cantor). Do đó, có ít nhất một phần tử của R không là một phần tử của Q. Nói cách khác, có ít nhất một số thực không là hữu tỉ. €

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

1. Nguyên tắc lỗ bồ câu (Dirichlet):

Định lý 1:

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

Chứng minh:

Chứng minh mâu thuẫn.

Giả sử không có k thùng chứa hơn một vật thể. Thì tổng số vật thể sẽ là nhiều nhất k. Điều này là mâu thuẫn, vì có ít nhất k + 1 vật thể. €

Ví dụ 1:

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. €

Ví dụ 2:

Trong bất cứ nhóm 27 chữ Anh, phải có ít nhất 2 chữ

bắt đầu với cùng một chữ, vì chỉ có 26 chữ trong

mẫu tự Anh.

Ví dụ 3:

Bao nhiêu sinh viên phải có trong một lớp học để bảo đảm rằng ít nhất 2 sinh viên có cùng điểm trong kỳ thi cuối, nếu kỳ thi được cho điểm từ 0 đến 100?

Giải:

Có 101 điểm trong kỳ thi cuối. Nguyên tác lỗ bồ câu cho biết trong bất cứ 102 sinh viên phải có ít nhất 2 sinh viên cócùng điểm.

2. Nguyên tắc lỗ bồ câu tổng quát

Định lý 2:

Cho k và n là những số tự nhiên. Nếu kn + 1 vật thể được phân chia giữa n tập, thì một trong những tập chứa ít nhất k + 1 vật thể.

Chứng minh:

Chứng minh mâu thuẫn.

Giả sử không có những tập chứa ít nhấtk + 1 vật thể. Thì tổng số vật thể trong mỗi tập là nhiều nhất k. Vậy, bởi luật cộng, tổng số vật thể là nhiều nhất kn.Điều này là mâu thuẫn, vì ta đã có kn+ 1 vật thể. €

Ví dụ 1: Nếu 25 thư phân chia cho 6 hộp thư, thì 1 hộp thư sẽ chứa ít nhất 5 thư (k=4, n=6). €

Ví dụ 2:

Cho a1, a2, …, a17 là danh sách của 17 số nguyên dương. Thì có ít nhất 4 số nguyên trong danh sách có cùng thừa số khi chia cho 5.

Giải:

Ta có 17 vật thể và n = 5 thừa số (0, 1, 2, 3, 4).

Cho k=3, ta có kn+1 (đúng ra kn+2) vật thể chia cho 5 tập. (5 tập này là tập những số có thừa số 0 khi chia cho 5, những số có thừa số 1 khi chia cho 5, …).

Bởi nguyên tắc lỗ bồ câu, vài tập của 5 tập này có k+1 = 4 phần tử từ danh sách. €

Chú ý:

Hàm trần của x, éxù, là số nguyên nhỏnhất ³ x.

Ví dụ:

a) é6.1ù = 7, é-9.3ù = -9.

Hàm trần của x ‘cắt số lẻ của x và đưa lên số nguyên lớn hơn’.

b) Trong ví dụ 1 của định lý 2, ta có:

k + 1 = 4 + 1 = é25/6ù = é4.16ù= 5.

Vậy, định lý 2 tương đương định lý 3 sau đây.

Định lý 3:

Nếu N vật thể được đặt vào k hộp, thìcó ít nhất một hộp chứa ít nhất éN/kùvật thể.

Chứng minh:

Chứng minh mâu thuẫn.

Giả sử không có hộp chứa nhiều hơn éN/kù - 1 vật thể. Thì tổng số vật thể sẽlà nhiều nhất

k(éN/kù - 1) < k((N/k + 1) - 1) = N

với éN/kù < (N/k) + 1 được dùng.

Điều này là mâu thuẫn, vì có tổng số N vật thể. €

Ví dụ 1:

Trong 100 người, có ít nhất é100/12ù = 9 người sinh vào cùng tháng.

Ví dụ 2:

Số tối thiểu sinh viên cần trong lớp toán rời rạc để bảo đảm rằng ít nhất 6 sinh viên có cùng hạng điểm, nếu có 5 hạng điểm A, B, C, D, và F?

Giải:

Số tối thiểu sinh viên cần để bảo đảm rằng ít nhất 6 sinh viên có cùng hạng điểm là số nguyên nhỏ nhất N sao cho éN/5ù = 6. Số nguyên nhỏ nhất là N = 5.5 + 1 = 26. Vậy, 26 là số tối thiểu sinh viên cần để bảo đảm rằng ít nhất 6 sinh viên có cùng hạng điểm.

Chương 15

Bài giải

Chú ý: Khi viết một chứng minh, ta bắt đầu với “Chứng minh” và kết thúc với “€”.

15.1 Cho x, y Î Z. Chứng minh rằng nếu xy và x + y chẵn, thì cả hai x và y chẵn.

Chứng minh:

Giả sử x lẻ hay y lẻ, không mất tính tổng quát, ta nói x lẻ. Ta chứng minh rằng xy hay x+y lẻ. Thì x=2k+1,

có kÎZ. Vậy, y có thể chẵn hay lẻ.

Ta xét 2 trường hợp:

a. Trường hợp 1: y lẻ, thì y = 2l + 1, có lÎZ. Vậy,

xy = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1

= 2(2kl + k + l) + 1.

Vì 2kl + k + l là số nguyên, nên xy lẻ.

b. Trường hợp 2: y chẵn, thì y = 2l, có lÎZ. Vậy,

x + y = (2k + 1) + 2l = 2(k + l) + 1.

Vì k + l là số nguyên, nên x + y lẻ. €

15.2 Diễn tả phủ định của câu "x$y(xy = 1) sao cho không có phủ định đứng trước lượng từ.

Giải:

Bởi áp dụng tiệm tiến những luật phủ định của câu có lượng từ đơn, ta có thể chuyển phủ định của Ø"x$y(xy = 1) vào bên trong tất cả các lượng từ.

Vì Ø"x$y(xy = 1) º $xØ$y(xy = 1) º$x"yØ(xy = 1). Và Ø(xy = 1) º (xy ¹ 1), ta kết luận câu phủ định là $x"y(xy ¹ 1).

15.3 Dịch câu tiếng Việt sang câu có lượng từ lồng:

Định nghĩa của giới hạn “Cho mọi số thực e > 0, có một số thực d > 0 sao cho |f(x) - L| < e bất cứ khi nào 0 < |x - a| < d”.

Giải:

Đó là câu "e$d"x(0 < |x - a| < d ® |f(x) - L| < e), với miền đối tượng của biến e, d là tất cả số thực dương và của x là tất cả số thực. €

15.4 Định lý: Cho mỗi số tự nhiên n ³5, thì 2n > n2.

Chứng minh:

Bởi phép quy nạp toán học,

Bước cơ sở: Khi n = 5, thì 2n = 32 > 25 = n2.

Bước quy nạp: Cho bất kỳ n ³ 5, giả sử 2n > n2. Thì

2n+1 = 2.2n

> 2n2

= n2 + n2

³ n2 + 5n

= n2 + 2n + 3n

> n2 + 2n + 1 = (n + 1)2. €

15.5 Định lý: Giả sử f và g là hàm từ A tới B. Nếu "aÎA(f(a) = g(a)), thì f = g.

Chứng minh:

Giả sử "aÎA(f(a) = g(a)). Cho (a,b) là bất kỳ phần tử của f. Thì b = f(a). Nhưng theo giả thiết thì f(a) = g(a), nên b = g(a) và (a,b)Îg. Vậy, f Í g.

Tương tự thì g Í f. Vậy, f = g. €

15.6 Định lý:

Cho mỗi x > -1 và mỗi số tự nhiên n, thì (1+x)n > nx.

Chứng minh:

Cho bất kỳ x > -1. Ta sẽ chứng minh bằng quy nạp rằng cho mỗi số tự nhiên n, thì (1 + x)n > 1 + nx. Đó là (1 + x)n > nx.

Bước cơ sở: Nếu n = 0, thì (1 + x)n = (1 + x)0 = 1 = 1 + 0 = 1 + nx.

Bước quy nạp: Giả sử (1 + x)n ³ 1 + nx. Thì

(1 + x)n+1 = (1 + x)(1 + x)n

³ (1 + x)(1 + nx)

= 1 + x + nx + nx2

³ 1 + (n + 1)x, vì nx2 ³ 0. €

15.7 Định lý: Cho a, b, c là những số nguyên. Thì

a. Nếu a|b và a|c, thì a|(b+c).

b. Nếu a|b thì a|bc cho tất cả số nguyên c.

c. Nếu a|b và b|c, thì a|c.

Chứng minh:

a. Giả sử a|b và a|c. Thì theo định nghĩa của phép chia, ta có số nguyên s và t với b=as và c=at. Vậy,

b + c = as + at = a(s+t). Đó là a|(b + c).

b. và c. Chứng minh tương tự, €

15.8 Hệ quả: Nếu a, b, c là những số nguyên sao cho a|b và b|c, thì a|(mb+nc) với m, n là những số nguyên.

Chứng minh:

Bởi phần b của định lý trên, ta có a|mb và a|nc với m, n là những số nguyên.

Bởi phần a của định lý trên, ta có a|(mb + nc). €

15.9 Định lý: Mọi số nguyên > 1 có thể được diễn đạt như tích của số nguyên tố.

Chứng minh:

Cho n là bất cứ số nguyên > 1. Nếu n là số nguyên tố thì chẳng còn gì phải chứng minh, vì n được diễn đạt như tích của những số nguyên tố.

Nếu n không là số nguyên tố thì có n1>1 và n2>1 sao cho

n = n1 x n2.

Bây giờ ta xét n1 và n2. Nếu n1 là số hợp, thì nó có thể được diễn đạt như tích của hai số nguyên mà mỗi một số > 1, như n1 = m1 x m2. Tương tự, n2 là số nguyên tố hay nó có thể được diễn đạt như tích của hai số nguyên mà mỗi một số > 1, như n2 = m3 x m4.

Như vậy, ta có thể diễn đạt n như sau:

n = n1 x n2 (nếu n1 và n2 là nguyên tố)

n = m1 x m2 x n2, (nếu n1 là số hợp và n2 là nguyên tố)

n = n1 x m3 x m4, (nếu n1 là nguyên tố và n2 là số hợp)

n = m1 x m2 x m3 x m4 (nếu n1 và n2 là số hợp)

Bây giờ ta coi mỗi mi và tiếp tục thủ tục. Ở mỗi bước của thủ tục, mỗi mi là nguyên tố hay có thể phân ra làm hai số nguyên nhỏ. Vậy, sự phân chia này phải ngừng. Khi thủ tục ngừng, ta có kết quả

n = p1 x p2 x…x pk, với mỗi pi là sốnguyên tố.

Vậy, ta đã chứng minh rằng n có thể diễn đạt như tích cuả những số nguyên tố. €

15.10 Tìm phủ định của câu: “Mỗi sinh viên trong lớp đã học môn toán”.

Giải:

Câu “Mỗi sinh viên trong lớp đã học môn toán” có dạng "xP(x) với P(x) là “x đã học môn toán”.

Phủ định của câu này là “không là trường hợp mà mỗi sinh viên trong lớp đã học môn toán”, có dạng ~"xP(x). Câu này tương đương với câu “Có một sinh viên trong lớp đã không học môn toán” có dạng $x~P(x).

15.11 Tìm phủ dịnh của câu: “Có một sinh viên trong lớp đã học môn toán”.

Giải:

Câu “Có một sinh viên trong lớp đã học môn toán” có dạng $xQ(x) với Q(x) là “x đã học môn toán”.

Phủ định của câu này là “không là trường hợp mà có một sinh viên trong lớp đã học môn toán”, có dạng ~$xQ(x). Câu này tương đương với câu “Mỗi sinh viên trong lớp đã không học môn toán” có dạng "x~Q(x).

15.12 Bổ đề:

Chứng minh rằng cho mọi số thực a, a £ |a|.

Chứng minh:

Xét 2 trường hợp:

a) a ³ 0. Thì a = |a|.

b) a< 0. Thì a < 0 < |a|.

Vậy, a £ |a| cho mọi số thực a. €

15.13 Định lý:

Cho mọi số thực x và y, |x + y| £|x| + |y|.

Chứng minh:

Vì xy £ |xy|, suy ra x2 + 2xy + y2 £ x2 + 2|xy| + y2.

Vì x2 = |x|2, y2 = |y|2 và |xy| = |x||y| suy ra

x2 + 2xy + y2 £ |x|2 + 2|x||y| + |y|2

Vậy, (x + y)2 £ (|x| + |y|)2. Rút căn ta có

|x + y| £ |x| + |y|. €

15.14 Định lý:

Cho a, b là những số thực. Thì |ab| = |a|.|b|.

Giải thích:

Giả thiết: a, b là những số thực.

Kết luận: |ab| = |a|.|b|.

Chứng minh kết luận dạng q.

Từ giả thiết suy ra kết luận.

Chứng minh:

Nếu ab > 0, thì |ab| = ab; a và b phải cùng dấu;

nếu cả hai dương, thì |a| = a, |b| = b và |a||b| = ab hoặc nếu cả hai âm, thì |a| = -a, |b| = -b và

|a||b| = (-a)(-b) = ab.

Nếu ab < 0, thì |ab| = -(ab); a và b phải khác dấu. Không mất sự tổng quát, ta có thể giả sử a>0 và b<0, nói khác, ta có thể chuyển đổi nhiệm vụ của a và b.Thì |a|=a và |b|=-b, vậy, |a||b| = a(-b) = -(ab).

Vậy, cho mỗi lựa chọn của a và b, thì |ab| = |a||b|. €

15.15 Định lý: Cho {an} và {bn} là những dãy số thực hội tụ tới giới hạn a và b. Thì dãy {an+bn} cũng hội tụ tới giới hạn a+b.

Chứng minh:

Giả sử {an} và {bn} là hai dãy số thực hôi tụ tới giới hạn a và b.

Ta cần chứng minh {an+bn} hội tụ tớigiới hạn a+b. Đó là, cho bất cứ số thực dương e, ta tìm một số thực dương N sao cho

n>N ® |(an+bn)-(a+b)|<e

Bây giờ

|(an+bn)-(a+b)|=|(an-a)+(bn-b)|<|an-a|+|bn-b|

Vậy,

|(an+bn)-(a+b)|<e nếu

|an-a|<e/2 và |bn-b|<e/2

Vì {an} hội tụ tới a, có một số thực dương N1 sao cho n>N1®|an-a|<e/2. Tương tự, vì {bn} hội tụ tới b, có một số thực dương N2 sao cho n>N2®|bn-b|<e/2.

Cho N = cực đại {N1,N2}, thì n>N®n>N1 và n>N2

®|an-a|<e/2 và |bn-b|<e/2

®|(an+bn)-(a+b)<e. €

15.16 Định lý lỗ bồ câu:

Nếu f: A ® B là hàm giữa những tập hữu hạn với |A|>|B|, thì f không đơn.

Vậy, có a1, a2 Î A sao cho a1 ¹ a2 và f(a1) = f(a2).

Chứng minh:

Đặt f: A ® B là hàm giữa những tập hữu hạn với |A|>|B|.

Chứng minh dùng định lý đếm tập con.

Định nghĩa tập con C của A bởi

C = {aÎA: f(a) ¹ f(x) cho bất kỳ xÎA}.

Đó là, C là tập con của những vật thể được đặt vào lỗ bồ câu. Tập C chắc không có nhiều vật thể hơn B.

Vì |C| £ |B| và bởi giả thiết, |A|>|B|, ta có |C| < |A| nên |C| ¹ |A|. Điều này chứng tỏ rằng C và A thỏa mãn giả thiết của định lý đếm tập con. Vậy, có một phần tử a của A không thuộc về C. Vì a không thuộc về C, có một x Î A-{a} sao cho f(x) = f(a), vậy f là không đơn. €

15.17 Giả sử 101 thư phân chia cho 100 hộp thư. Thì 1 hộp thư phải chứa ít nhất 2 thư.

15.18 Đâu là số ít nhất của mã khu vựccần để bảo đảm rằng 25 triệu điện thoại trong tiểu bang có những số điện thoại 10 số hạng khác nhau? (Giả sử rằng số điện thoại có dạng NXX-NXX-XXXX, với 3 số hạng đầu là mã khu vực, N là số hạng từ 2 qua 9, và X là bất kỳ số hạng).

Giải:

Có 8 triệu số điện thoại khác nhau dạngNXX-XXXX. Vậy, bởi nguyên tắc lỗ bồ câu tổng quát, trong 25 triệu điện thoại, ít nhất é25,000,000/8,000,000ùđiện thoại phải có số điện thoại giống nhau. Vậy, ít nhất 4 mã khu vực cần đểbảo đảm rằng tất cả những số có 10 sốhạng khác nhau.

15.19 Phủ định của "x(x2 > x) là Ø"x(x2> x) º $xØ(x2 > x) º $x(x2 £ x).

15.20 Phủ định của $x(x2 = 2) là Ø$x(x2 = 2) º "xØ(x2 = 2) º "x(x2 ¹ 2).

Chương 16

Bài tập

16.1 Chứng tỏ rằng: (A Ì B và B Ì C) ®(A Ì C).

16.2 Chứng tỏ rằng: A – (B È C) = (A - B) Ç (A - C).

16.3 Chứng minh rằng |A È B| = |A| + |B| - |A Ç B|.

16.4 Cho tập vũ trụ U = {1, 2, 3, …, 10}.

Cho A = {1, 4, 7, 10}, B = {1, 2, 3, 4, 5}, và

C = {2, 4, 6, 8}. Liệt kê những phần tửcủa mỗi tập hợp sau:

1. A È B.

2. B Ç C.

3. A – B.

4. B – A.

5. U – C.

6. A È Æ.

7. B Ç Æ.

8. A È U.

9. B Ç U.

10. A Ç (B È C).

11. (A Ç B) - C.

12. (A È B) - C.

13. A’.

14. B’ Ç (C - A).

16.5 Chứng tỏ rằng:

(A - B) È (B - A) = (A È B) – (A Ç B).

16.6 Chứng minh rằng nếu A Í B và A ÍC thì

A Í B Ç C.

16.7 Cho tất cả tập hợp A, B, và C. Chứng minh rằng

A Ç (B È C) = (A Ç B) È (A Ç C).

16.8 Cho tất cả tập hợp A, B, và C. Chứng minh rằng

A È (B Ç C) = (A È B) Ç (A È C).

16.9 Cho tập hợp A, B. Chứng minh rằng

A È (A Ç B) = A.

16.10 Cho tập hợp A, B. Chứng minh rằng

A Ç (A È B) = A.

16.11 Chứng minh rằng cho mọi tập hữu hạn A và B, nếu B Ì A, thì |B| < |A|.

16.12 Cho tập hợp A = {a, b, c, d}.

Gọi P(A) là tập hợp các tập con của A.

Quy ước rằng A Î P(A) và Æ Î P(A), hãy kê khai các phần tử của P(A).

16.13 Chứng minh rằng nếu 3n + 2 lẻ, thì n lẻ.

16.14 Định lý: Cho xÎZ. Thì x2 lẻ nếu và chỉ nếu x lẻ.

16.15 Chứng minh rằng cho mọi nÎN, thì

1 + 3 + 5 + … + 2n – 1 = n2.

16.16 Chứng minh rằng cho mọi nÎN, thì

1.2 + 2.3 + 3.4 + … + n(n + 1) = n(n + 1)(n + 2)/3.

16.17 Chứng minh rằng cho mọi nÎN, thì

13 + 23 + … + n3 = [n(n + 1)/2]2.

16.18 Chứng minh rằng cho mọi nÎN, thì

12 + 22 + … + n2 = n(n +1)(2n + 1)/6.

16.19 Định lý: Giả sử f:A®B. Thì những mệnh đề sau tương đương:

a. f là đơn và đầy.

b. f-1:B®A.

c. Có hàm g:B®A sao cho gof = iA và fog = iB.

16.20 Chứng minh:

Nếu f là 1-1, thì fog là 1-1.

16.21 Chứng minh:

Nếu f và g là đầy, thì fog là đầy.

16.22 Chứng minh:

Nếu f và g là 1-1 và đầy, thì fog là 1-1 và đầy.

16.23 Chứng minh:

Nếu fog là 1-1, thì f là 1-1.

16.24 Chứng minh:

Nếu fog là 1-1, thì g là 1-1.

16.25 Chứng minh:

Nếu fog là đầy, thì f là đầy.

16.26 Chứng minh gián tiếp định lý: Nếu 3n + 2 lẻ, thì n lẻ.

16.27 Chứng minh rằng: Trong bất cứ nhóm 27 chữ Anh, phải có ít nhất 2 chữ bắt đầu với cùng một mẫu tự.

16.28 Định lý căn bản của Số học: Mỗi số nguyên dương >1 có thể được viết duy nhất như là một số nguyên tố hay tích của hai hay nhiều số nguyên tố mà những thừa số được viết theo thứ tự không giảm.

16.29 Chứng minh hàm số thực f(x) = x + 1 là 1-1.

16.30 Chứng minh rằng nếu x là một số thực, thì |-x| = |x|.

16.31 Trong bất cứ tập hợp của 750 nguời, có 3 người với cùng ngày sinh nhật (ngày, tháng, nhưng không cần năm sinh).

16.32 Cho mọi số thực x và y, |x – y| ³||x| – |y||.

16.33 Trong bất cứ hình n-cạnh (n ³ 3), tổng số góc bên trong là (n – 2)p.

16.34 Chứng minh rằng n < 2n cho mọi n Î N.

16.35 Chứng minh rằng n2 < 2n cho mọi n ³ 5.

16.36 Chứng minh rằng n3 < 3n cho mọi n ³ 4.

16.37 Chứng minh rằng cho mọi n Î Z+, số nguyên dương lẻ thứ hạng n là 2n – 1.

16.38 Cho những mệnh đề sau:

D: Dung chạy.

K: Kiên cười

S: Sanh nhảy

Dịch những mệnh đề sau sang tiếng Việt:

a) (D Ù K) ® S

b) ØD v (K Ù S)

c) (ØS ® ØK) Ù (D ® K)

d) (D v S) « ØK

16.39 Cho những mệnh đề sau:

S: Trời sáng.

W: Gió thổi.

R: Trời mưa.

T: Nhiệt độ tăng.

Tìm thực trị của mỗi mệnh đề sau:

a) (S Ù ØW) Ú (W Ù R)

b) Ø (R ® T) Ù W

c) W® Ø(T Ú R)

d) (R ® ØW) Ú (W ® T)

e) (R Ú ØT) « (W Ù ØS).

16.40 Xác định mỗi dạng mệnh đề sau là hằng đúng hay hằng sai?

a) (p ® q) « (p Ù Øq)

b) (p Ù Øp) ® (p ® r)

c) (p Ú q) « (q ® r)

16.41 Chứng minh rằng

[(p ® q) Ù (p ® r)] º [p ® (q Ù r)].

16.42 Cho phép áp f từ tập {a, b, c, d} tới tập

{1, 2, 3} với f(a) = 3, f(b) = 2, f(c) = 1, và f(d) = 3. Phép áp f có phải là đầy không?

16.43 Chứng minh sự hợp lý của suy luận sau:

“Anh giầu nếu anh thông minh hoặc bất chính. Anh không thông minh cũng chẳng bất chính. Vậy, anh không giầu.”

16.44 Định lý:

Nếu x < y và –z Î P, thì xz > yz.

16.45 Định lý:

Nếu x < y < z, thì x < z.

16.46 Định lý:

Nếu {x0, x1, …, xn} Í P, thì x0x1…xn Î P.

16.47 Định lý:

Nếu 0 < x < y và n là số dương, thì xn < yn.

16.48 Chứng minh:

Nếu x < y và a < b, thì x + a < y + b.

16.49 Chứng minh:

Nếu x và y Î P và x2 < y2, thì x < y.

16.50 Ta có P(Æ) = {Æ} và {Æ} ¹ Æ.

Vậy, cái gì là P({Æ})?

Phần Thứ Ba

Phụ Lục

Phụ lục A

Tập hợp

A.1 Khái niệm

Tập hợp là một khái niệm khởi đầu không định nghĩa của toán học. Ta cóthể xem tập hợp là một nhóm không thứ tự của các đối tượng phân biệt được. Mỗi đối tượng là một phần tử của tập hợp. Phần tử của tập hợp có thể là bất cứ cái gì ta muốn nói: sinh vật, đồ vật, tập hợp, ...

Tập hợp là căn bản cho tất cả các loại toán.

Tập hợp còn được gọi là tập.

A.2 Ký hiệu

Ta dùng chữ in hoa để chỉ các tập hợp: A, B, C, …

Và chữ thường để chỉ các phần tử: a, b, c, …

Ví dụ:

A = {1, 2, 3}.

1, 2, 3 là những phần tử của A.

2 thuộc về A, ta viết 2 Î A.

4 không thuộc về A, ta viết 4 Ï A.

A.3 Diễn tả tập hợp

Ta dùng dấu móc {...} để diễn tả tậphợp. Có 2 cách:

1. Cách kê khai:

Liệt kê các phần tử của tập hợp trong {}, nếu tập hợp hữu hạn và không quálớn.

Ví dụ:

A = {a, b, c}

Tập hợp được xác định bởi những phần tử, không theo thứ tự, được giả sử làkhác biệt, nhưng lỡ lập lại cũng không sao. Vậy, A có thể là

A = {a, b, c} = {b, c, a} = {c, a, b} = {c, a, b, c}.

2. Cách trưng tính:

Nêu đặc tính chung P(x) của các phần tử của tập hợp trong {}, nếu tập hợp hữu hạn và lớn hay vô hạn.
Ví dụ:

B = {x | x là một số tự nhiên}.
B là tập các số tự nhiên, P(x): x là một số tự nhiên.
Chú ý: Cách diễn tả này có dạng chung là:
{x | P(x)}
với P(x) là một mệnh đề của biến x. Dạng này diễn tả tập hợp của các phần tử x khi mệnh đề P(x) đúng.

Dấu hiệu x| đọc là: x có tính chất

x được xác định bởi

x sao cho

A.4 Tập trống

Định nghĩa: Tập trống hay rỗng, ký hiệu Æ, là tập không có phần tử nào.

Ta có Æ = {} = {x | x ≠ x}.

Ví dụ:

Tập tất cả các nghiệm số dương của phương trình x2 + 5x + 6 = 0 là một tập trống.

Chú ý:

{Æ} là tập hợp, có một phần tử là tập hợp Æ.

A.5 Tập con

Định nghĩa: Tập A là tập con của tập B, ký hiệu AÌ B, nếu và chỉ nếu mỗi phần tử của A là một phần tử của B. Đó là,

A Ì B Û (x Î A) Þ (x Î B).

Và đọc A ở trong B hay B chứa A.

Ví dụ:

Nếu A = {1, 3} và B = {1, 2, 3} thì A ÌB.

Chú ý:

1. Để chứng minh A Ì B, ta chứng minh xÎA Þ xÎB.

2. Nếu ta tìm được một phần tử của A không thuộc về

B thì điều ấy đủ làm cho A không ởtrong B hay

B không chứa A, ký hiệu A Ë B.

3. Tập rỗng, Æ, là tập con của mọi tập.

4. Mỗi tập là tập con của chính nó, đólà A Ì A.

5. Mọi phần tử x của tập A tạo thành tập con {x} của A, viết là {x} ⊂ A.

6. (A Ì B và B Ì C) Þ (A Ì C).

Đó là, Ì có tính truyền.

A.6 Tập hữu hạn. Tập vô hạn.

Định nghĩa: Cho tập S. Nếu có chính xác n phần tử khác biệt trong S với n là số nguyên không âm, ta nói rằng S là một tập hữu hạn và n là số phần tử của S, ký hiệu |S|.

Định nghĩa: Một tập là vô hạn nếu nó không hữu hạn.

Ví dụ 1: Tập hữu hạn

A = {x| x là ngày trong tuần}.

Ví dụ 2: Tập vô hạn

B = {x | x là một số tự nhiên}.

A.7 Tập bằng nhau

Định nghĩa: Tập A bằng tập B, ký hiệuA = B, nếu và chỉ nếu chúng có cùng các phần tử. Đó là, x Î A nếu và chỉ nếu x Î B.

A = B Û (x Î A) Û (x Î B).

Ví dụ 1:

A = {x| x chia đúng cho 10}

B = {x| x là số nguyên tận cùng bằng 0}

Ta có A = B.

Ví dụ 2: Các tập hợp trống đều bằng nhau.

Chú ý:

Để chứng minh A = B, ta chứng minh x Î A Û x Î B.

A.8 Hai tập A, B không bằng nhau, kýhiệu A ¹ B, là hai tập khác nhau.

Ví dụ: A = {1, 3, 5}

B = {2, 4, 6}

Ta có: A ¹ B

A.9 Tập lũy thừa

Định nghĩa: Tập lũy thừa của tập S, kýhiệu P(S), là tập của tất cả các tập con của S.

Ví dụ:

Cho tập S = {a, b, c}.

Thì tập S có 8 tập con.

P(S) = {Æ, {a}, {b}, {c}, {a, b}, {b, c}, {c, a}, S}.

Chú ý:

1. R Ì S Û R Î P(S).

x Î S Û {x} Î P(S).

S Î P(S).

Æ Î P(S).

2. Khi tập S có n phần tử khác nhau thìP(S) có 2n phần tử. |S|=3, |P(S)|=23=8.

3. P(Æ) = {Æ}.

4. Định nghĩa:

Hai tập A, B bằng nhau nếu A Ì B và B Ì A.

5. A Ì B: A là tập con và khác B.

6. A Í B: A là tập con và bằng B.

A.10 Hội của hai tập hợp

Định nghĩa: Hội của hai tập A và B, ký hiệu AÈB, là tập hợp gồm những phần tử thuộc về A, hoặc thuộc về B, hoặc thuộc về cả A lẫn B.

A È B = {x| x Î A hay xÎ B}.

Ví dụ:

A = {1, 3, 5}

B = {4, 5, 6}

A È B = {1, 3, 4, 5, 6}.

Chú ý:

1. A È B = {x| x Î A hay xÎ B}

B È A = {x| x Î B hay xÎA}

= {x| x Î A hay xÎ B}

= A È B.

Vậy, A È B = B È A.

Phép hội hai tập hợp có tính cách giao hoán.

2. A là tập con của A È B, đó là A Ì (A È B).

B là tập con của A È B, đó là B Ì (A È B).

3. Hai tập hợp cách biệt nhau vẫn cóphần hội.

Ví dụ:

A = {1, 2, 3}

B = {5, 7, 8}

A È B = {1, 2, 3, 5, 7, 8}

4. A È Æ = A

A.11 Giao của hai tập hợp

Định nghĩa: Giao của hai tập A và B, ký hiệu AÇB, là tập hợp gồm những phần tử chung cho A và B.

A Ç B = {x| x Î A và xÎ B}

Ví dụ:

A = {1, 3, 5}

B = {4, 5, 6}

A Ç B = {5}

Chú ý:

1. Ta có A Ç B = {x| x Î A và xÎ B}

Ta có B Ç A = {x| x Î B và xÎ A}

= {x| x Î A và xÎ B}

= A Ç B.

Vậy, A Ç B = B Ç A.

Phép giao hai tập hợp có tính cách giao hoán.

2. A Ç B là tập con của A, đó là (A ÇB) Ì A.

A Ç B là tập con của B, đó là (A Ç B) Ì B.

3. A Ç Æ = Æ.

A.12 Hai tập hợp cách biệt

Định nghĩa:

Hai tập A và B gọi là cách biệt khi A ÇB = Æ.

Ví dụ:

Tập hợp

A = {1, 4, 5}

B = {2, 6}

Là cách biệt, vì

A Ç B = Æ

Định nghĩa: Một nhóm tập con của S là đôi một cách biệt, nếu bất cứ khi nào A và B là những tập khác biệt trong S, thìA và B là cách biệt.

Ví dụ:

Nhóm của những tập con của S:

S = {{1, 4, 5}, {2, 6}, {3}, {7, 8}}

là đôi một cách biệt.

A.13 Phần bù
Định nghĩa: Phần bù tương đối của B trong A, ký hiệu A\B hay A-B, là tập gồm tất cả các phần tử thuộc A nhưng không thuộc B. Ta gọi A-B là hiệu của hai tập. Đó là,
A-B = A\B = {x | x Î A và x Ï B}.

Ví dụ:

A = {1, 3, 5}

B = {4, 5, 6}

A – B = {1, 3}

B – A = {4, 6}

Chú ý:

1. A – B = {x| x Î A và x Ï B}

B – A = {x| x Î B và x Ï A}

Vậy, (A – B) ¹ (B – A).

2. A – B là tập con của A, đó là (A – B) Ì A.

3. A - Æ = A.

Định nghĩa: Tập vũ trụ là một tập gồm tất cả những phần tử mà chúng ta muốn nói đến.
Ví dụ 1: Vũ trụ trong số học là tập các số tự nhiên.
Ví dụ 2: Vũ trụ trong giải tích là tập các số thực.
Định nghĩa: Cho tập vũ trụ U và tập con A của U, thì U – A là phần bù tuyệt đối của A, ký hiệu CA hay Ac.

Ví dụ:

U = {1, 2, 3, 4, 5, 6, 7, 8, 9}

A = {1, 2, 3, 4}

Ac = {5, 6, 7, 8, 9}
A.14 Tính chất của các phép tính tập hợp
1. Tính kết hợp
a) A È (B È C) = (A È B) È C.
b) A Ç (B Ç C) = (A Ç B) Ç C.

2. Tính giao hoán

a) A È B = B È A.

b) A Ç B = B Ç A.

3. Tính phân phối
a) A È (B Ç C) = (A È B) Ç (A È C).

b) A Ç (B È C) = (A Ç B) È (A Ç C).

4. Luật De Morgan

a) A \ (B È C) = (A \ B) Ç (A \ C).

b) A \ (B Ç C) = (A \ B) È (A \ C).

Khi tập B, C thuộc vũ trụ A, luật De Morgan là:
a) (B È C)c = Bc Ç Cc
b) (B Ç C)c = Bc È Cc

Phụ lục B

Số thực R

B.1 Tập số thực, ký kiệu R, là vô hạn, vì

N Ì Z Ì Q Ì R.

B.2 Tiên đề của hệ số thực:

1. Cho tất cả số thực x và y, thì xy = yx.

2. Có một tập con P của những số thựcthoả mãn những tính cách sau:

1) Nếu x và y Î P, thì x + y và xy Î P.

2) Nếu x là một số thực, thì chỉ mộtđiều kiện sau là đúng:

a) x = 0

b) x Î P

c) -x Î P

B.3 Định nghĩa:

1. Phép nhân được định nghĩa ngầm bởi tiên đề 1.

2. x Î P gọi là số thực dương.

3. -x Î P gọi là số thực âm.

4. Những luật số học của số dương và âm đều được giả định; ví dụ, tích của hai số thực là âm nếu và chỉ nếu một số là dương và số khác là âm.

5. Trị số tuyệt đối |x| của số thực x được định nghĩa là x nếu x ³ 0 và –xnếu x < 0.

6. Bất đẳng thức “ít hơn” được định nghĩa như sau:

x < y (“x ít hơn y”) nghĩa là x và y Î R và y – x Î P.

Tương tự, “x < y < z” nghĩa là x < y vày < z.

B.4 Định lý:

1. Cho mỗi số thực x, thì x.0 = 0.

2. Cho mọi số thực x, y, và z, nếu x £ y và y £ z, thì

x £ z.

3. Bổ dề:

Nếu n là số nguyên dương, thì n – 1 làsố nguyên dương hoặc n – 1 = 0.

B.5 Dùng tiên đề và bất đẳng thức, ta chứng minh những định lý sau:

1. Định lý:

Nếu x < y và z Î R, thì x + z < y + z.

Chứng minh:

Giả thiết x < y nghĩa là y – x Î P.

Và y – x = (y + z) – (x + z).

Vậy, (y + z) - (x + z) Î P, nghĩa là x + z < y + z. ð

2. Định lý:

Nếu x < y và z Î P, thì xz < yz.

Chứng minh:

Giả sử x < y, thì y – x Î P.

Ta cũng giả sử z Î P, thì tính cách đóng của P với phép nhân, tính cách a của tiên đề thứ tự, bảo đảm rằng (y - x)z Î P. Bởi luật phân bố, thì “yz - xz” Î P.

Vậy, xz < yz. ð

3. Định lý:

Nếu 0 < x < y, thì x2 < y2.

Chứng minh:

Vì x < y, ta có thể dùng định lý 2 đểnhân hai vế với x hay y. (vì cả hai đều dương).

Những phép nhân này cho ta x2 < xy vàxy < y2.

Vậy, x2 < y2. ð

Phụ lục C

Hàm

C.1 Định nghĩa 1:

Cho X và Y là hai tập không rỗng.

Hàm hay phép áp f từ X tới Y là một quy tắc gán một phần tử duy nhất y Î Y cho mỗi phần tử x Î X.
Ta viết y = f(x) là ảnh của x hay giá trị của f tại x.
Ta gọi x là biến độc lập, y là biến phụ thuộc. Tập X là miền (miền xác định, tập tiền ảnh), tập f(X) là miền giá trị (tập ảnh), tập Y là đối miền của hàm f.

Định nghĩa 2:

Hàm f từ X tới Y là một quan hệ từ X tới Y, có những tính chất sau:

a. Miền xác định của f là X.

b. If (x, y), (x, y’) Î f, thì y = y’.

Ví dụ 1:

Hàm f = {(1, a), (2, b), (3, a)}

từ X = {1, 2, 3} tới Y = {a, b, c} là hàm từ X tới Y. Miền xác định của f là X và miền giá trị của f là {a,b}.
Chú ý 1: Nếu f(X) ⊂ Y thì hàm f là hàm từ X vào Y.
Chú ý 2: Nếu f(X) = Y thì hàm f là hàm từ X lên Y.
Chú ý 3: Nhiều phần tử của X có thể có duy nhất một phần tử của Y.

Chú ý 4: Hàm f giống như một cái máy hay cái hộp đen, nếu ta cho một x vào hàm f, thì hàm f cho ra một f(x).

Ví dụ 2:

Quan hệ R = {(1, a), (2, b), (2, c), (4, d)}

từ X = {1, 2, 3, 4} tới Y = {a, b, c, d} không là hàm từ X tới Y, vì:

a. Miền xác định của R, {1, 2, 4},không là X.

b. (2, b) và (2, c) trong R nhưng b¹ c.

Ví dụ 3: Quan hệ R = (1, a), (2, b), (3, b), (4, d)} là hàm từ X = {1, 2, 3, 4} vào Y = {a, b, d}, theo định nghĩa.

2. Ký hiệu
Hàm f với miền X và đối miền Y được ký hiệu là
                 f : X ® Y
hay


Ví dụ:      f : N ® Z
Hàm f là một hàm từ N (tập số tự nhiên) tới Z (tập số nguyên).
Chú ý: Cho hàm f: X ® Y:
Nếu Y là tập các số thực, thì f là hàm số thực.
Nếu Y là tập các số phức thì f là hàm số phức.

Nếu Y là tập {đúng, sai}, thì f là hàm luận lý.
C.2 Xác định hàm
Có 3 phương pháp để xác định một hàm f: X ® Y:
1. Phương pháp liệt kê những cặp thứ tự của hàm
Ta liệt kê những cặp thứ tự của hàm với những phần tử của miền X ở vị trí thứ nhất, những phần tử của miền giá trị f(X) ở vị trí thứ hai trong mỗi cặp thứ tự.
Ví dụ: Cho những cặp thứ tự
f = {(1, a), (2, b), (3, c), (4, c)}
Những cặp thứ tự này xác định một hàm f

từ X = {1, 2, 3, 4} lên Y = {a, b, c}.
2. Phương pháp bảng
Ta liệt kê những phần tử của miền X ở cột thứ nhất, những phần tử của miền giá trị f(X) ở cột thứ hai của bảng.
Thí dụ: Cho bảng f
                 X_____f(X)
                 1          a
                 2          b
                 3          c
                 4          c
Bảng này xác định một hàm f từ X = {1, 2, 3, 4} lên Y = {a, b, c}.
3. Phương pháp giải tích
Ta dùng một biểu thức để xác định một hàm.
Thí dụ: f(x) = 2x.

Từ biểu thức này, nếu miền X = {1, 2, 3, 4}, thì miền giá trị của hàm f phải là Y = {2, 4, 6, 8}.
C.3 Biểu diễn hàm
Đồ thị của hàm f : X ® Y trên mặt phẳng toạ độ Descartes gồm tất cả các điểm có toạ độ (x, f(x)).

Chú ý: Với mỗi x Î X, f(x) là giá trị của f tại x, f(X) là miền giá trị của f.

Ví dụ: Đồ thị của hàm f(x) = 2x

C.4 Hàm 1-1
Định nghĩa: Nếu mỗi phần tử của Y có nhiều nhất một phần tử của X, thì hàm f từ X tới Y là 1-1 (đơn).

Đó là, hai phần tử khác nhau, x và x’ thuộc X, có hai ảnh f(x) và f(x’) khác nhau thuộc Y.

Hàm đơn f Û (x ¹ x’ Û f(x) ¹f(x’)).

Hàm đơn f Û (x = x’ Û f(x) = f(x’)).

Ví dụ:

Hàm f(x) = 2x là 1-1, vì nếu a ≠ b, thì 2a ≠ 2b.

Hoặc f(x) = 2x là 1-1, vì nếu 2a = 2b, thì a = b.

C.5 Toàn hàm
Định nghĩa: Nếu mỗi phần tử của Y có ít nhất một phần tử của X, thì hàm f từ X tới Y là toàn hàm (đầy). Đó là,

("b Î Y)($a Î X): f(a) = b.

Hay, miền giá trị f(X) = Y.

Ví dụ:   Hàm f = {(1, a), (2, b), (3, c), (4, d)}   từ X= {1,2,3,4} lên Y={a,b,c,d} là toàn hàm và 1-1.
C.6 Song hàm
Định nghĩa: Nếu mỗi phần tử của X có một phần tử của Y và mỗi phần tử của Y có một phần tử của X, thì hàm từ X tới Y là song hàm (đơn đầy).
Chú ý: Song hàm vừa là hàm 1-1 vừa là toàn hàm.
Ví dụ: Hàm f = {(1, a), (2, b), (3, c), (4, d)}
từ X = {1, 2, 3, 4} lên Y = {a, b, c, d} là song hàm vì nó là hàm 1-1 và toàn hàm.   C.7 Hàm ngược
Định nghĩa: Nếu hàm f: X ® Y là song hàm (vừa là hàm 1-1 vừa là toàn hàm), thì hàm f−1: Y ® X được gọi là hàm ngược.
Ví dụ: f = {(1, a), (2, b), (3, c), (4, d)} từ X = {1, 2, 3, 4} lên Y = {a, b, c, d} là hàm 1-1 và toàn hàm.
f−1 = {(a, 1), (b, 2), (c, 3), (d, 4)} từ Y = {a, b, c, d}    lên X = {1, 2, 3, 4} là hàm ngược của f.
C.8 Hàm hợp
Định nghĩa: Cho hàm g: X ®Y và f: Y ® Z. Nếu x Î X, có đúng một y = g(x) Î Y và có đúng một z = f(y) = f(g(x)) Î Z, thì ta có hàm hợp h: X ® Z.
Hàm h là hàm hợp của hàm f và g, ký hiệu fog, với định nghĩa sau:
h(x) = (fog)(x) = f(g(x)) với mọi x Î X.

Ví dụ 1: Cho f(x) = sinx và g(x) = 2x, thì (fog)(x) = f(g(x)) = sin2x.
Chú ý 1: Hàm hợp fog chỉ đưọc định nghĩa khi miền giá trị của g là miền của f.
Chú ý 2: Thông thường, fog ≠ gof, nên thứ tự của hàm hợp rất quan trọng.
Ví dụ 2: Cho f(x) = sinx và g(x) = 2x, ta có:
          f(g(x)) = sin2x ≠ g(f(x)) = 2sinx   C.9 Hàm bằng nhau
Định nghĩa: Nếu với mọi x Î X, f(x) = g(x), thì hàm f: X ® Y bằng hàm g: X® Y.
Ví dụ:   f(x) = x2 - 1 và g(x) = (x-1)(x+1) là bằngnhau.
C.10 Hàm đồng nhất
Định nghĩa: Hàm đồng nhất, ký hiệu IX, là hàm từ X lên X cho phép mỗi phần tử là chính nó. Ví dụ:   Với mỗi x Î X, f(x) = x.
Định nghĩa: Nếu f là hàm từ X tới Y thì ta có hàm hợp sau
          f o IX = f
          IY o f = f
IX  là hàm đồng nhất Î X, IY là hàm đồng nhất Î Y.

Bảng Ký Hiệu

Ký hiệu	Tên	Nội dung
Ø	Phủ định	Không
Ù	Hội	Và
Ú	Tuyển	Hoặc
®	Điều kiện	Nếu…thì
«	Tương đương	Nếu và chỉ nếu
"	Phổ dụng	Tất cả, Mọi, Mỗi
$	Hiện hữu, tồn tại	Có một, Có ít nhất
├	Hệ quả luận lý	p├ q
Þ	Hệ quả luận lý	p Þ q, kéo theo
Û	Tương dương luận lý	p Û q, tương đương
º	Tương đương luận lý	A º B
¹	Khác	0 ¹ 1
Î	Thuộc về	x Î A
Ì	Tập con	A Ì B
Í	Tập con và bằng	C Í D
È	Hội của hai tập hợp	A È B
Ç	Giao của hai tập hợp	A Ç B
Æ	Tập rỗng	{}
N	Tập số nguyên tự nhiên	N = {0,1,2,3,…}
Z	Tập số nguyên tương đối	Z = {…,-2,-1,0,1,2,…}
Z+	Tập số nguyên dương	Z+ = {1,2,3,…}
Q	Tập số hữu tỷ	Q = {p/q\|p, qÎZ,q¹0}
R	Tập số thực	N Ì Z Ì Q Ì R
\	Vậy
ÿ	Chứng minh xong

Tự Vựng Việt Anh

Chữ Việt Chữ Anh

Áp (phép), Ánh xạ mapping, function

Bài trung excluded middle

Bảng ký tự alphabet

Bảng thực trị truth table

Biến variable

Biến mệnh đềpropositional variable

Biến ràng buộc bound variable

Biến tự do free variable

Biểu thức expression

Biểu thức consubexpression

Biểu thức đơnsimple expression

Biểu thức mệnh đề propositional expression

Biểu thức hàm function expression

Biểu thức vị từ predicate expression

Bổ đề lemma

Bội số multiple

Câu sentence

Câu khai báo declarative sentence

Cây ngữ nghĩasemantic tree

Chia (phép) division

Chứng minh proof

Chứng minh mâu thuẫn proof by contradiction

Chứng minh đến cùng proof by exhaustion

Chứng minh hình thức formal proof

Chứng minh không hình thức informal proof

Chứng minh rỗng vacuous proof

Chứng minh tầm thường trivial proof

Công thức formula

Công thức đóng closed formula

Công thức hoàn hảo well-formed formula

Cộng (phép) addition

Cơ sở base

Cú pháp, ngữ pháp syntax

Dạng form

Dạng mệnh đề propositional form

Diễn dịch interpretation

Đại số bool boolean algebra

Đặc biệt-tổng quát specialization-generalisation

Đẳng cấu isomorphism

Đếm được countable

Định đề postulate, axiom

Định lý theorem

Định nghĩa definition

Điều kiện condition

Điều kiện kép bicondition

Đệ quy recursion

Độc lập independent

Đối miền codomain

Đối xứng symmetry

Đúng true

Giao intersection

Giao hoán commutation

Giới hạn limit

Hàm function

Hàm đơn, 1-1 1-1, injective

Hàm đầy, toàn hàm onto, surjective

Hàm đồng nhất identity function

Hàm sàn floor function

Hàm trần ceiling function

Hằng constant

Hằng đúng tautology

Hằng sai contradiction

Hệ chứng minh proof system

Hệ luận corollary

Hệ quả luận lý logical consequence

Hệ suy diễn deductive system

Hiện hữu occurrence

Hiện hữu ràng buộc bound occurrence

Hiện hữu tự do free occurrence

Hoặc or

Hoán vị transposition

Hoàn bị complete

Họ collection, family

Họ có số chỉ indexed family

Hội union

Hợp conjunction, compound

Hợp lý valid

Hữu hạn finite

Kết luận conclusion

Kết nối join

Không not

Không đếm được uncountable

Không nhất quán inconsistent

Ký hiệu symbol

Ký tự character

Liên từ connective

Loại trừ hỗ tương mutually exclusive

Luận lý cấp 1 first order logic

Luận lý học logic

Luận lý ký hiệu symbolic logic

Luận lý mệnh đề propositional logic

Luận lý toán học mathematical logic

Luận lý vị từ predicate logic

Luật law, rule

Luật cp conditional proof

Luật De Morgan De Morgan’s law

Luật eg existentialgeneralization

Luật es existential specification

Luật mâu thuẫn law of contradiction

Luật rút gọn contraction rule

Luật p(giả thiết)premise rule

Luật mp (tách ra) modus ponens

Luật suy diễn rule of inference

Luật t tautology rule

Luật thay thế substitution rule

Luật ug universal generalization

Luật us universal specification

Lượng từ quantifier

Lượng từ hiện hữu existential quantifier

Lượng từ phổ dụng universal quantifier

Lý luận reasoning, argument

Lý luận quy nạp inductive reasoning

Lý luận suy diễn deductive reasoning

Lý luận không đúng incorrect reasoning, fallacy

Lý thuyết chứng minh proof theory

Lý thuyết tiên đề axiomatic theory

Mã khu vực area codes

Mâu thuẫn contradiction

Mệnh đề proposition

Miền đối tượng universe of discourse

Miền domain

Mơ hồ ambiguous

Một one

Mọi every

Mô hình model

Mô hình lý tưởng ideal model

Mô hình cụ thể concrete model

Nghịch lý paradox

Ngôn ngữ hình thức formal language

Ngụy biện fallacy

Nguyên từ term

Ngữ nghĩa semantics

Nhất quán consistent

Nhân (phép) multiplication

Nhóm collection, group

Phạm vi scope

Phản hồi reflexive

Phản chứng contrapositive

Phân bố distribution

Phân giải resolution

Phỏng đoán conjecture

Phối hợp association

Phủ định negation

Phủ định kép double negation

Phức (tạp) complex

Phương pháp method

Quy tắc rule

Sai false

Siêu lý thuyếtmetatheory

Siêu toán họcmetamathematics

Song hàm (đơn đầy) bijectivefunction

Số phần tử của tập hợp cardinality of the set

Số hữu tỉ rational number

Số nguyên tố prime number

Số nguyên tự nhiên N natural number N

Số nguyên tương đối Z integer Z

Số vô tỉ irrational number

Sự đơn giản simplicity

Sự kiện fact

Sự phát biểu statement

Tập hợp, tập set

Tập rỗng empty set

Thay thế substitution

Thuật ngữ không định nghĩa undefined term

Thuật ngữ nguyên thuỷ primitive term

Thuật ngữ phổ dụng universal term

Thừa số factor

Thực trị truth value

Thoả mãn satisfiable

Tiên đề axiom

Tiền đề antecedent, premise

Tính truyền transitivity

Toán áp dụng applied mathematics

Toán thuần túy pure mathematics

Toàn hàm (đầy) onto, surjective function

Trừ (phép) subtraction

Tổng quát hiện hữu existential generalization

Tổng quát phổ dụng universal generalization

Tức thì hiện hữu existential instantiation

Tức thì phổ dụng universal instantiation

Tương đươngequivalent

Tương thích compatible

Và and

Ví dụ thay thế substitution instance

Vị từ predicate

Vô hạninfinite

Vũ trụ universe

Xuất cảng exportation

Số không zero

Tài Liệu Tham khảo

1. Elliott Mendelson, Introduction to Mathematical Logic, Chapman & Hall/CRC, 1997.

2. Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill, 1988.

3. Daniel J. Velleman, How to prove it, Cambridge University Press, 1994.

4. G. Polya, How to solve it, Princeton University Press, 2004.

5. Nguyễn Văn Phú, Đại số học, lớp 10A, B (Đệ tam A, B), Đường Sáng xuất bản, Saigon, 1970.

Mục Lục

Tựa	5
Phần thứ nhất: Luận lý toán học	7
Chương 1. Luận lý mệnh đề	9
Chương 2. Luận lý vị từ	21
Chương 3. Suy luận	30
Phần thứ hai: Phương pháp chứng minh	37
Chương 4. Chứng minh	39
Chương 5. Chứng minh kết luận dạng q	49
Chương 6. Chứng minh kết luận dạng Øq	53
Chương 7. Chứng minh kết luận dạng p®q	57
Chương 8. Chứng minh kết luận dạng Øq®Øp	60
Chương 9. Chứng minh kết luận dạng p Ù q	63
Chương 10. Chứng minh kết luận dạng p Ú q	67
Chương 11. Chứng minh dạng "xP(x)	70
Chương 12. Chứng minh dạng $xP(x) và $!xP(x)	74
Chương 13. Chứng minh quy nạp	78
Chương 14. Những cách chứng minh khác	82
Chương 15. Bài giải	87
Chương 16. Bài tập	95
Phần thứ ba: Phụ lục	101
Phụ lục A. Tập hợp	103
Phụ lục B. Số thực R	110
Phụ lục C. Hàm	112
Bảng ký hiệu	121
Tự vựng Việt Anh	122
Tài liệu tham khảo	130
Mục lục	131

131

hoàngvănthành

Tuesday, December 4, 2018

Chứng minh Toán học, 2018

No comments:

Post a Comment