Bài toán tồn tại

Một số phương pháp chứng minh

Chứng minh trực tiếp

• “Nếu P, thì Q”

Chứng minh bằng phản chứng

• Để chứng minh “Nếu P thì Q”, giả thiết “P và !Q”, suy ra điều mâu thuẫn

Chứng minh bằng phản đề

• Để chứng minh “Nếu P thì Q”, ta chứng minh “Nếu !Q thì !P”

Chứng minh bằng quy nạp toán học

• Để chứng minh đúng với mọi n nguyên dương, ta chứng minh:
  • hoặc là đúng
  • Nếu đúng thì đúng

Nguyên lí Dirichlet

• Nếu xếp n đối tượng vào k cái hộp thì chắc chắn tìm được ít nhất một cái hộp chứa đối tượng