Đến nội dung

Hình ảnh

Tìm công thức tổng quát tính số tập hợp con của 1 tập hợp. ( theo cách quy nạp )


  • Please log in to reply
Chủ đề này có 3 trả lời

#1
sanghamhoc

sanghamhoc

    Hạ sĩ

  • Thành viên
  • 79 Bài viết

Tìm công thức tổng quát tính số tập hợp con của 1 tập hợp. ( theo cách quy nạp ) 



#2
tuan pham 1908

tuan pham 1908

    Trung sĩ

  • Thành viên
  • 137 Bài viết

WTF?

topic này dùng để làm gì vậy???



#3
Duy Thai2002

Duy Thai2002

    Sĩ quan

  • Thành viên
  • 433 Bài viết

Tập có n phần tử thì có $2^{n}$ tập con.


Sự khác biệt giữa thiên tài và kẻ ngu dốt là ở chỗ thiên tài luôn có giới hạn.


#4
IHateMath

IHateMath

    Thượng sĩ

  • Thành viên
  • 299 Bài viết

Ta xét tập rỗng trước. Tập này có đúng một tập con là chính nó.

Tiếp theo xét một tập có đúng $1$ phần tử. Tập này có đúng $2$ tập con là tập rỗng và chính nó.

Xét tập có hai phần tử $\{a,b\}$. Tập này có đúng $4$ tập con là $\varnothing, \{a\}, \{b\}, \{a,b\}$.

Dự đoán rằng tập có $n$ phần tử thì có đúng $2^n$ tập con. Chứng minh: Giả sử khẳng định của ta là đúng với trường hợp $n=k$ nguyên dương nào đó. Ta sẽ chứng minh điều đó đúng với $n=k+1$. Thật vậy, xét tập $S$ có $k+1$ phần tử. Gọi $x$ là một phần tử bất kỳ của $S$. Rõ ràng các tập con của $S$ đều có thể xếp vào đúng một trong hai lớp:

- Lớp thứ nhất gồm các tập con của $S\setminus \{x\}$, tức là không chứa $x$. Rõ ràng lớp này có $2^k$ phần tử theo giả thuyết quy nạp.

- Lớp thứ hai gồm các tập con của $S$ mà chứa $x$. Các tập này lại có dạng $T\cup \{x\}$ với $T$ là tập con của $S$ thuộc lớp thứ nhất. Vậy lớp này cũng sẽ có đúng $2^k$ phần tử.

Vậy tóm lại là $S$ có đúng $2^k+2^k=2^{k+1}$ tập con, chứng tỏ khẳng định của ta là đúng với mọi $n$ nguyên dương. $\square$






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh