Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 8 phút

Chứng minh tồn tại kiến thiết

Đây là chứng minh duy nhất mà bạn được phép chỉ tay vào một thứ. Điều khó là chỉ tay mới chỉ là một nửa công việc — và nửa còn lại là nơi có điểm.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Cứ chỉ vào một cái#

Có người khẳng định: “Có một người trong phòng này sở hữu một chiếc xe màu đỏ.” Bạn sẽ chứng minh điều đó thế nào? Hãy tự nghĩ ra trước khi đọc tiếp.

Hầu hết mọi người dừng ở “chỉ vào người nào có một chiếc.” Đó mới là nửa câu trả lời, và nửa còn lại là nơi có điểm.

Bạn chỉ vào một người và bạn cho xem chiếc xe, và chiếc xe màu đỏ. Cả hai nửa. Chỉ tay một mình chỉ là một khẳng định; việc kiểm tra mới biến nó thành một chứng minh.

Đó là một chứng minh tồn tại kiến thiết, và nó là loại chứng minh duy nhất mà việc chỉ tay có giá trị.

Bằng ký hiệu, một mệnh đề như ∃x P(x) — đọc là “tồn tại một x có tính chất P” — nói rằng có ít nhất một thứ có tính chất đó. Thứ bạn chỉ vào được gọi là một nhân chứng (witness).

Hai việc phải làm, và việc người ta bỏ qua#

Kiến thiếtKhông kiến thiết
Bạn làm gìĐưa ra một thứ cụ thể và kiểm tra nó đúngChỉ ra rằng việc không có thứ nào là điều không thể
Bạn kết thúc vớiMột ví dụ thật trong tayBiết rằng một thứ tồn tại, mà không có nó trong tay
Công cụ thường dùngMột công thức, một cách làm, một phép tính trực tiếpPhản chứng, đếm, nguyên lý chuồng bồ câu
Hai nghĩa vụ

1. Nêu một nhân chứng cụ thể. Không phải “một số nào đó” — mà là một số thật.
2. Kiểm tra nó. Chỉ ra rằng tính chất thực sự đúng với thứ đó.

Bỏ qua nghĩa vụ thứ hai là cách thường gặp nhất để mất điểm ở đây. Một nhân chứng đứng một mình là một khẳng định mà người đọc bị yêu cầu kiểm tra thay bạn.

Ví dụ nhỏ nhất có thể#

Khẳng định. Tồn tại một số nguyên tố chẵn.

Chứng minh. Lấy n = 2. Nó chẵn, vì 2 = 2·1. Nó là số nguyên tố, vì các ước dương duy nhất của nó là 1 và chính nó. Vậy n = 2 thỏa cả hai điều kiện. ∎

Đó là một chứng minh hoàn chỉnh, và nó hoàn chỉnh vì có câu thứ hai. “Lấy n = 2. ∎” không phải là một chứng minh.

Khi thứ bạn chỉ vào không phải là một số#

Các khẳng định tồn tại trở nên khó đọc hơn khi thứ bạn phải chỉ vào bị chôn giữa các ký hiệu khác. Công việc không thay đổi.

Một hàm f được gọi là tuần hoàn nếu nó lặp lại — như một làn sóng trông giống hệt mỗi khi bạn dịch nó đi một khoảng cố định nào đó. Viết ra đầy đủ:

∃T > 0 (∀x ∈ ℝ, f(x + T) = f(x))

Đọc nó: có một khoảng dịch T nào đó, lớn hơn không, sao cho với mọi x, dịch đi T thì giá trị không đổi. Ở đây T là một số bình thường — độ lớn của khoảng dịch, gọi là chu kỳ.

“Tồn tại” gắn với T. Vậy T là thứ bạn chỉ vào, và mọi thứ sau nó là điều bạn phải kiểm tra.

Khẳng định. Hàm phần thập phân f(x) = x − ⌊x⌋ là tuần hoàn. (⌊x⌋ nghĩa là “làm tròn xuống thành số nguyên”, nên f chỉ giữ lại phần sau dấu thập phân.)

Chứng minh. Lấy T = 1, là số dương. Cho x là một số thực bất kỳ. Phép làm tròn xuống thỏa ⌊x + 1⌋ = ⌊x⌋ + 1, vì cộng một số nguyên làm giá trị đã làm tròn xuống dịch đi đúng bằng lượng đó. Vậy

f(x + 1) = (x + 1) − ⌊x + 1⌋ = (x + 1) − (⌊x⌋ + 1) = x − ⌊x⌋ = f(x)

Vì x là bất kỳ, điều này đúng với mọi số thực x, nên T = 1 thỏa và f tuần hoàn. ∎

Hai điều về cấu trúc đã làm nên kết quả. Nhân chứng T = 1 được nêu ngay dòng đầu tiên. Rồi x được đưa vào như một số bất kỳ — “với mọi x” phải được tôn trọng một cách trung thực, không phải bằng cách thử hai giá trị rồi nhún vai.

“Nhỏ nhất” là một khẳng định khác#

Chỉ ra rằng một T nào đó đúng thì không chỉ ra T nào là nhỏ nhất. Đó là một khẳng định riêng cần một lập luận riêng, thường có dạng “cái này đúng, và không có cái nào nhỏ hơn đúng.”

Với phần thập phân: giả sử có một T với 0 < T < 1 cũng là một chu kỳ. Kiểm tra tại x = 0. Khi đó f(0) = 0, trong khi f(0 + T) = T − ⌊T⌋ = T, vì T nằm giữa 0 và 1. Tính tuần hoàn sẽ buộc T = 0, mâu thuẫn với T > 0. Vậy không có chu kỳ nhỏ hơn, và chu kỳ chính xác là 1.

Một mẫu đáng mang theo

“Tồn tại” và “nhỏ nhất như vậy” là hai câu hỏi khác nhau. Hãy trả lời câu bạn được hỏi, và đừng cho rằng câu trả lời đầu giải quyết luôn câu thứ hai.

Chứng minh một thứ tồn tại mà không tìm ra nó#

Một số chứng minh tồn tại không bao giờ đưa ra ví dụ nào cả. Chúng chỉ ra rằng việc không có thứ nào là điều không thể, rồi dừng ở đó. Những chứng minh này gọi là không kiến thiết.

Ví dụ kinh điển: có vô hạn số nguyên tố. Chứng minh cho thấy mọi danh sách hữu hạn các số nguyên tố đều thiếu một số. Nhưng nó không bao giờ đưa cho bạn số nguyên tố bị thiếu đó. Nó không nêu tên một số nguyên tố lớn cụ thể nào. Bạn kết thúc với việc biết chúng tồn tại mà không cầm được một số nào.

Cả hai loại đều là chứng minh hợp lệ. Nhưng nếu một câu hỏi nói “hãy tìm” hoặc “hãy xây dựng”, một lập luận không kiến thiết không trả lời nó, dù đúng đến đâu.

“Đúng một” lại là một khẳng định khác#

“Có đúng một” đòi hỏi hai điều: có ít nhất một tồn tại, và không có hai cái khác nhau nào cùng tồn tại.

Chứng minh tồn tại bằng cách chỉ tay, như ở trên. Sau đó chứng minh tính duy nhất theo cách trực tiếp: lấy hai đối tượng cùng có tính chất đó, và chỉ ra chúng phải là cùng một thứ. Bạn không cần giả sử chúng khác nhau rồi đi tìm mâu thuẫn — con đường trực tiếp thường ngắn hơn và luôn đủ.

Những chỗ dễ sai#

  • Nêu một nhân chứng rồi dừng. Việc kiểm tra là một nửa của chứng minh và là nửa mà người ta hay bỏ.
  • Một nhân chứng mơ hồ. “Một số lớn nào đó” không phải là nhân chứng. Hãy nêu tên nó.
  • Quên các điều kiện phụ. Nếu khẳng định nói thứ đó phải dương, thì việc nói điều đó là một phần của chứng minh. Một nhân chứng không thỏa ràng buộc thì không phải là nhân chứng.
  • Kiểm tra một khẳng định “với mọi” trên vài ví dụ. Khi bạn đã chỉ tay, phần còn lại thường là một khẳng định phổ quát và cần một phần tử bất kỳ, không phải các mẫu thử.
  • Trả lời câu “hãy tìm” bằng một lập luận không kiến thiết. Đúng, nhưng vẫn không phải điều được hỏi.
  • Coi “tồn tại” như thể nó giải quyết “nhỏ nhất”. Hai khẳng định, hai chứng minh.
  • Chứng minh tính duy nhất bằng phản chứng theo thói quen. Lấy hai đối tượng và chỉ ra chúng trùng nhau thì ngắn hơn và luôn dùng được.

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Toán rời rạc là miễn phí và dùng được khi không có mạng, với các bài luyện chọn theo chủ đề về phương pháp chứng minh, lượng từ và quy nạp.

Luyện các phương pháp chứng minh →

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

Chứng minh tồn tại kiến thiết là gì?

Là chứng minh một thứ tồn tại bằng cách đưa ra một ví dụ cụ thể và kiểm tra nó đúng. Ví dụ đó gọi là một nhân chứng (witness). Cần cả hai nửa: nêu một nhân chứng mà không kiểm tra thì chỉ là một khẳng định, không phải một chứng minh.

Nhân chứng (witness) trong một chứng minh là gì?

Là đối tượng cụ thể bạn chỉ vào để giải quyết một khẳng định “tồn tại”. Với “có một số nguyên tố chẵn”, nhân chứng là 2. Với “hàm này tuần hoàn”, nhân chứng là khoảng dịch thực sự, chẳng hạn T = 1.

Chứng minh kiến thiết và chứng minh không kiến thiết khác nhau ở đâu?

Một chứng minh kiến thiết đưa cho bạn một ví dụ. Một chứng minh không kiến thiết cho thấy việc không có ví dụ nào là điều không thể, mà không bao giờ đưa ra ví dụ đó. Chứng minh có vô hạn số nguyên tố là trường hợp kinh điển. Cả hai đều hợp lệ, nhưng một câu hỏi nói “hãy tìm” thì không được trả lời bằng loại thứ hai.

Chứng minh một thứ tồn tại có chứng minh nó là nhỏ nhất không?

Không. Đó là hai khẳng định riêng cần hai lập luận riêng. Chỉ ra một chu kỳ nào đó đúng thì chưa nói lên chu kỳ nào là nhỏ nhất; điều đó cần chứng minh riêng, thường có dạng “cái này đúng và không có cái nào nhỏ hơn đúng.”

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.