15

bvd Live! Tập 1 - Phương pháp chứng minh

bvd đã đăng vào 30, Tháng 5, 2022, 13:21

Vào lúc 8h tối thứ Ba ngày 31 tháng 5 năm 2022, mình sẽ tổ chức buổi trình bày đầu tiên trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của buổi đầu tiên là "Phương pháp chứng minh." Để có thể nắm được nội dung bài trình bày, bạn chỉ cần biết trước về tập hợp số tự nhiên và tính chia hết, không nhất thiết phải biết lập trình.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

  • Các khái niệm logic đơn giản như "không" (not), "hoặc" (or), "và" (and), mệnh đề kéo theo, mệnh đề tương đương, với mọi, tồn tại
  • Tập hợp và hàm số
  • Ba phương pháp chứng minh phổ biến là phương pháp chia trường hợp, phương pháp phản chứng, và phương pháp quy nạp.

Mục tiêu của bài trình bày là giúp bạn:

  • Đọc hiểu được định nghĩa Toán học (ví dụ định nghĩa chữ O lớn, định nghĩa đồ thị, định nghĩa cây), làm nền tảng cho các buổi trình bày tiếp theo.
  • Giải thích tại sao một tập số nguyên dương khác rỗng luôn có số nhỏ nhất?
  • Nắm được cách chứng minh "tương đương" hoặc chứng minh "bằng nhau"
  • Nắm được cách dùng quy nạp để chứng minh các tính chất mà bạn mò ra được bằng tay khi xem xét các trường hợp nhỏ.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Xem tư liệu bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 3
    letangphuquy  đã bình luận lúc 13, Tháng 6, 2022, 17:48 ← chỉnh sửa

    Em không dự buổi live đấy nhưng có vài thắc mắc về nội dung bài giảng thì anh có sẵn lòng giải đáp không ạ? :(

    Ở trong slide, từ trang 105 trở về trước vài trang là nội dung : chứng minh tồn tại min S. Em thấy giải được như vậy (quy nạp) là do có ~S \in \mathbb{N}~, xong ta lấy "base case" của quy nạp là ~A(0)~. Vậy nếu đề bài là ~S \in \mathbb{Z}~ thì mình sẽ chứng minh như thế nào?

    Suy nghĩ của em: Giả sử tập ~S~ có hữu hạn phần tử. Mệnh đề (~\forall d \in S : \exists x < d \in S~) làm cho số lượng phần tử được tăng lên vô hạn (với mỗi giá trị ta lại tìm thấy giá trị nhỏ hơn nó). Do đó bằng trực quan ta sẽ thấy được mâu thuẫn. Tuy nhiên em lại không biết trình bày kiểu toán như thế nào và cũng còn lấn cấn về khái niệm "hữu hạn"/ "vô hạn".

    xin cảm ơn anh bvd đã đọc đến tận đây :(


    • 4
      bvd  đã bình luận lúc 14, Tháng 6, 2022, 2:32 ← sửa 11

      Nếu ~S \subset \mathbb{Z}~, ~S \ne \emptyset~ thì ~\min S~ có thể không tồn tại. Ví dụ như nếu ~S~ là tập số nguyên âm, ~S \subset \mathbb{Z}~ nhưng do không tồn tại số nguyên âm nhỏ nhất nên ~\min S~ không tồn tại.

      Nếu ~S \subset \mathbb{N}~, ~S \ne \emptyset~ thì kể cả khi ~S~ có vô hạn phần tử thì ~\min S~ vẫn tồn tại (theo như chứng minh trong slide)

      Một tập ~A~ là một tập hữu hạn khi và chỉ khi ~|A| \in \mathbb{N}~ (hoặc ~\exists n \in \mathbb{N}: n = |A|~). Em có thể hiểu khái niệm tập vô hạn là phủ định của khái niệm tập hữu hạn, tức tập ~A~ là tập vô hạn khi và chỉ khi ~|A| \notin \mathbb{N}~ (hoặc ~\forall n \in \mathbb{N}: |A| \ne n~)

      Em có thể thử chứng minh định lí sau:

      Nếu ~A \subset \mathbb{R}~, ~A \ne \emptyset~ và ~A~ hữu hạn (tức ta có thể chọn ~n \in \mathbb{N}~ sao cho ~|A| = n~) thì ~\min A~ tồn tại. (Gợi ý ở ô dưới)

      Ta có thể chứng minh định lí này bằng cách quy nạp theo số phần tử của ~A~


      • 2
        letangphuquy  đã bình luận lúc 15, Tháng 6, 2022, 6:05

        dạ cảm ơn anh bvd nhiều ạ, cái này trí quá nên giờ em mới "tiêu hóa" xong!