Tentang himpunan kuasa

Himpunan kuasa (power set) dari suatu himpunan $A$ adalah himpunan yang berisi semua subhimpunan (subset) dari $A$ . Himpunan kuasa dari himpunan $A$ akan kita notasikan dengan $P(A)$ . Sebagai contoh, jika $A=\{1,2,3\}$ , maka $P(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} \}$ .

Postingan saya kali ini adalah tentang sifat himpunan kuasa yang masih saya anggap sebagai sebuah kebetulan karena belum saya pahami sebelumnya.

Di salah satu ujian Matematika Diskret I, saya membuat soal yang menanyakan apakah untuk sembarang himpunan $A$ dan $B$ , berlaku $P(A) \cup P(B) = P(A \cup B)$ . Jawabannya adalah tidak karena dengan mudah kita dapat memberikan contoh penyangkal $A=\{1\}$ dan $B=\{2\}$ , yang memberikan

$P(A)=\{ \emptyset, \{1\} \}$ , $P(B)=\{ \emptyset,\{2\} \}$

sehingga

$P(A) \cup P(B) = \{\emptyset, \{1\}, \{2\} \}$ ,

sementara itu, $P(A \cup B) = P(\{1,2\})=\{ \emptyset, \{1\}, \{2\}, \{1,2\} \}$ , sehingga $P(A \cup B) \ne P(A) \cup P(B)$ .

Secara khusus, ini juga merupakan contoh penyangkal untuk pernyataan bahwa untuk sembarang himpunan $A$ dan $B$ berlaku $P(A \cup B) \subseteq P(A) \cup P(B)$ .

Namun, pernyataan berikut benar:

Teorema. Untuk setiap himpunan $A$ dan $B$ , berlaku $P(A) \cup P(B) \subseteq P(A \cup B)$ .

Bukti. Asumsikan $x \in P(A) \cup P(B)$ . Akan dibuktikan bahwa $x \in P(A \cup B)$ . Perhatikan bahwa $x \in P(A) \cup P(B)$ berakibat $x \in P(A)$ atau $x \in P(B)$ .

Jika $x \in P(A)$ , maka $x \subseteq A$ . Karena $A \subseteq A \cup B$ , maka juga berlaku $x \subseteq A \cup B$ , sehingga $x \in P(A \cup B)$ .

Sementara itu, dengan cara yang serupa, jika $x \in P(B)$ , kita dapat tunjukkan bahwa $x \subseteq A \cup B$ , sehingga juga diperoleh $x \in P(A \cup B)$ .

Terbukti bahwa untuk kedua kasus, berlaku $x \in P(A \cup B)$ jika $x \in P(A) \cup P(B)$ . $\blacksquare$

Sebagaimana yang sudah saya jabarkan sebelumnya, arah sebaliknya tidak benar: $P(A \cup B)$ belum tentu merupakan subset dari $P(A) \cup P(B)$ .

Oke, hal ini cukup intuitif.

Kemudian, untuk soal ujian susulan, saya membuat soal yang menanyakan apakah untuk setiap himpunan $A$ dan $B$ , berlaku $P(A) \cap P(B) = P(A \cap B)$ . Awalnya saya hanya asal bikin dan saya berekspektasi bahwa jawabannya juga tidak. Sepertinya saya juga mencoba coret-coret sedikit dan berhasil menemukan contoh penyangkal yang tidak terlalu sulit namun sepertinya saat itu saya terlalu capek sehingga justru ngawur.

Satu hari sebelum ujian susulan diadakan, saya baru menyadari bahwa jawaban dari soal tersebut ternyata adalah benar, yaitu untuk setiap himpunan $A$ dan $B$ memang berlaku $P(A) \cap P(B) = P(A \cap B)$ . Kita buktikan sekarang.

Teorema. Untuk setiap himpunan $A$ dan $B$ , berlaku $P(A) \cap P(B) = P(A \cap B)$ .

Bukti. Kita buktikan dua pernyataan: $P(A) \cap P(B) \subseteq P(A \cap B)$ dan $P(A \cap B) \subseteq P(A) \cap P(B)$ . Kedua pernyataan ini berakibat $P(A) \cap P(B) = P(A \cap B)$ , yaitu yang ingin kita buktikan.

Bukti untuk $P(A) \cap P(B) \subseteq P(A \cap B)$ .

Asumsikan $x \in P(A) \cap P(B)$ . Ini berarti $x \in P(A)$ dan $x \in P(B)$ . Akibatnya, $x \subseteq A$ dan $x \subseteq B$ . Dari kedua pernyataan ini mudah dibuktikan bahwa $x \subseteq A \cap B$ sehingga berlaku $x \in P(A \cup B)$ .

Bukti untuk $P(A \cap B) \subseteq P(A) \cap P(B)$ .

Asumsikan $x \in P(A \cap B)$ . Ini berarti $x \subseteq A \cap B$ . Karena $A \cap B \subseteq A$ , maka berlaku $x \subseteq A$ sehingga $x \in P(A)$ . Dengan cara serupa, karena $A \subseteq B \subseteq B$ , kita juga simpulkan $x \in P(B)$ . Ini berarti $x \in P(A) \cap P(B)$ .

Terbukti. $\blacksquare$

Jika Anda perhatikan, pembuktian di atas sebenarnya hanya murni menggunakan logika matematika; tidak ada banyak matematika di dalamnya karena kita cukup meng-unfold definisi yang diberikan. Namun ternyata terjadi sesuatu yang tidak simetris pada teorema tentang irisan atau gabungan dari himpunan kuasa, yang notabene merupakan operasi yang saling dual. Hal ini sempat membuat saya resah namun saya belum sempat merenungkannya. Mungkin jika saya menemukan jawabannya saya akan bagikan.

Jarak dua fungsi Boolean

Definisi 9. Diberikan dua fungsi $f,g:\{\pm 1\}^n \rightarrow \{ \pm 1\}$ , jarak $\text{dist}(f,g)$ kedua fungsi ini didefinisikan sebagai

$\text{dist}(f,g) = \mathbb{P}_{x \sim \{\pm 1 \}^n}[f(x) \ne g(x)] = \dfrac{1}{2^n} |\{x \in \{\pm 1\}^n: f(x) \ne g(x)\}$ ,

yaitu proporsi banyaknya masukan $x$ sehingga $f(x)$ dan $g(x)$ berbeda.

Perhatikan bahwa $\text{dist}$ merupakan metrik:

(i) $\text{dist}(f,g) \ge 0$ ,

(ii) dan $\text{dist}(f,g)=0$ jika dan hanya jika $f=g$ ,

(iii) untuk setiap $f,g$ , berlaku $\text{dist}(f,g)=\text{dist}(g,f)$ ,

(iv) untuk setiap $f,g,h$ , berlaku $\text{dist}(f,g)+\text{dist}(g,h) \ge \text{dist}(f,h)$ .

Teorema Plancherel

Selain Teorema Parseval, ada juga teorema Plancherel sebagai berikut.

Teorema 8. (Teorema Plancherel) Untuk semua fungsi $f,g:\{\pm 1\}^n \rightarrow \mathbb{R}$ , berlaku

$\displaystyle \langle f,g \rangle = \mathbb{E}_{x \sim \{\pm 1\}^n}[f(x)g(x)] = \sum_{S \subseteq [n]} \widehat{f}(S)\widehat{g}(S)$ .

Bukti. Kita dapat hitung

$\displaystyle \langle f,g \rangle = \left \langle \sum_{S \subseteq [n]} \widehat{f}(S)\chi_S, \sum_{T \subseteq [n]} \widehat{g}(T)\chi_T \right \rangle$

$\displaystyle = \sum_{S,T \subseteq [n]} \widehat{f}(S)\widehat{g}(T) \langle \chi_S, \chi_T \rangle = \sum_{S,T \subseteq [n]} \widehat{f}(S)\widehat{g}(T) {\bf 1}_{S=T} = \sum_{S \subseteq [n]} \widehat{f}(S)\widehat{g}(S)$ ,

as desired. $\blacksquare$

Teorema Parseval

Teorema Parseval di analisis Discrete Fourier Transform biasanya adalah teorema tentang jumlah kuadrat dari nilai fungsi dan jumlah kuadrat nilai hasil transformasi Fouriernya. Di analisis fungsi Boolean, kita punyai Teorema Parseval sebagai berikut.

Teorema 7. (Teorema Parseval) Untuk sembarang $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ ,

$\displaystyle \langle f,f \rangle = \mathbb{E}_{x \sim \{\pm 1\}^n}[f(x)^2] = \sum_{S \subseteq [n]}\widehat{f}(S)^2$ .

Khususnya, jika $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ merupakan fungsi bernilai Boolean,

$\displaystyle \sum_{S \subseteq [n]} \widehat{f}(S)^2 = 1$ .

Bukti. Kita dapat hitung langsung

$\displaystyle \langle f,f \rangle = \left \langle \sum_{S \subseteq [n]} \widehat{f}(S)\chi_S, \sum_{T \subseteq [n]} \widehat{f}(T)\chi_T \right \rangle = \sum_{S,T \subseteq [n]} \widehat{f}(S) \widehat{f}(T) \langle \chi_S, \chi_T \rangle$

$\displaystyle = \sum_{S,T \subseteq [n]} \widehat{f}(S)\widehat{f}(T) {\bf 1}_{S=T} = \sum_{S \subseteq [n]} \widehat{f}(S)^2.$

Jika $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ bernilai Boolean, maka $f(x)^2=1$ untuk semua $x \in \{\pm 1\}^n$ , sehingga

$\displaystyle \langle f,f\rangle = \mathbb{E}_{x \sim \{\pm 1\}^n}[f(x)^2] = 1$

sehingga diperoleh

$\displaystyle \sum_{S \subseteq [n]} \widehat{f}(S)^2 = \langle f,f\rangle=1$ .

$\blacksquare$

Menghitung koefisien Fourier

Di post ini, saya akan memberikan formula untuk menghitung koefisien Fourier.

Proposisi 6. Misalkan $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ dan $S \subseteq [n]$ . Koefisien Fourier $\widehat{f}(S)$ dapat dihitung dengan rumus berikut:

$\widehat{f}(S)=\langle f,\chi_S \rangle = 2^{-n} \sum_{x \in \{\pm 1\}^n} f(x)\chi_S(x)$ .

Bukti. Ini dapat diverifikasi langsung menggunakan Teorema 3.

$\displaystyle \langle f,\chi_S\rangle = \left \langle \sum_{T \subseteq [n]} \widehat{f}(T)\chi_T, \chi_S \right \rangle = \sum_{T \subseteq [n]} \widehat{f}(T) \langle \chi_T, \chi_S \rangle = \sum_{T \subseteq [n]} \widehat{f}(T) {\bf 1}_{S=T} = \widehat{f}(S)$ . $\blacksquare$

Kita lihat contoh untuk $f$ fungsi AND and $S = \emptyset$ :

$\widehat{f}(\emptyset) = 2^{-2} \left( f(-1,-1)\chi_\emptyset(-1,-1)+f(-1,1)\chi_{\emptyset}(-1,1)+f(1,-1)\chi_{\emptyset}(1,-1)+f(1,1)\chi_{\emptyset}(1,1) \right)$

$= 2^{-2} \left( -1 \cdotp 1 + (-1) \cdotp 1 + (-1) \cdotp 1 + 1 \cdotp 1 \right) = -\dfrac{2}{4}=-\dfrac{1}{2}$ .

Basis ruang vektor fungsi Boolean

Untuk setiap subhimpunan $S \subseteq [n]$ , definisikan fungsi $\chi_S:\{\pm 1\}^n \rightarrow \{\pm 1\}$ sehingga untuk setiap $x \in \{\pm 1\}^n$ ,

$\chi_S(x)=x^S=\prod_{i \in S} x_i$ .

Ada sebanyak $2^n$ fungsi $\chi_S$ karena ada $2^n$ subhimpunan $S \subseteq [n]$ . Kita tunjukkan bahwa $2^n$ fungsi ini merupakan basis ortonormal dari himpunan semua fungsi Boolean $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ .

Teorema 3. $2^n$ fungsi $\chi_S:\{\pm 1\}^n \rightarrow \{\pm 1\}$ membentuk basis ortonormal dari ruang vector $V$ semua fungsi $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ . Secara khusus, $\langle \chi_S, \chi_T \rangle = {\bf 1}_{S=T}$ .

Untuk membuktikan teorema ini, kita buktikan terlebih dahulu lemma terkait fungsi $\chi_S$ yang akan kita gunakan.

Lemma 4. Untuk setiap $S,T \subseteq [n]$ , $\chi_S(x)\chi_T(x)=\chi_{S \Delta T}(x)$ , di mana $S \Delta T=(S \setminus T) \cup (T \setminus S)$ (symmetric difference).

Bukti. Perhatikan bahwa

$\chi_S(x)\chi_T(x)=\prod_{i \in S} x_i \prod_{i \in T} x_i = \prod_{i \in S \cap T} x_i^2 \prod_{i \in S \Delta T} x_i = \prod_{i \in S \Delta T} x_i = \chi_{S \Delta T}(x)$ . $\blacksquare$

Lemma 5. Untuk setiap $S,T \subseteq [n]$ , $\mathbb{E}_{x \sim \{\pm 1\}^n} [\chi_S(x)]={\bf 1}_{S=\emptyset}$ .

Bukti. Jika $S=\emptyset$ , maka $\chi_\emptyset(x)=1$ untuk semua $x \in \{\pm 1\}^n$ , sehingga $\mathbb{E}_{x \sim \{\pm 1\}^n} [\chi_S(x)]={\bf 1}_{S=\emptyset}$ . Jika $S \ne \emptyset$ , maka $\mathbb{E}_{x \sim \{\pm 1\}^n} [\chi_S(x)]= \mathbb{E}_{x \sim \{\pm 1\}^n} \left[ \prod_{i \in S} x_i \right] = \prod_{i \in S} \mathbb{E}_{x_i \sim \{\pm 1\}} [x_i] = \prod_{i \in S} 0 = 0$ , di mana persamaan kedua adalah karena $x_1,\dots,x_n$ independen dan persamaan ketiga karena $\mathbb{E}_{x_i \sim \{\pm 1\}}[x_i] = \frac12 \cdotp 1 + \frac12 \cdotp (-1)=0$ . $\blacksquare$

Sekarang kita akan buktikan Teorema 3.

Bukti teorema 3. Berdasarkan Teorema 1, fungsi-fungsi $\chi_S$ merentang semua fungsi $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ , yaitu untuk setiap $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ , berlaku

$f \in \text{span} \{\chi_S: S \subseteq [n]\}$ .

Kita cukup tunjukkan bahwa $\langle \chi_S,\chi_T \rangle = {\bf 1}_{S=T}$ .

Perhatikan bahwa

$\langle \chi_S, \chi_T \rangle = \mathbb{E}_{x \sim \{\pm 1\}^n} [\chi_S(x)\chi_T(x)] = \mathbb{E}_{x \sim \{\pm 1\}^n} [\chi_{S \Delta T}(x)] = {\bf 1}_{S \Delta T = \emptyset}$ , di mana persamaan pertama berdasarkan Lemma 4 dan persamaan kedua berdasarkan Lemma 5. Karena $S \Delta T = \emptyset$ jika dan hanya jika $S=T$ , maka $\langle \chi_S, \chi_T \rangle = {\bf 1}_{S=T}$ . $\blacksquare$

Inner product fungsi Boolean

Di post-post selanjutnya, saya akan menuliskan $\{-1,+1\}$ sebagai $\{\pm 1\}$ .

Perhatikan bahwa himpunan semua fungsi Boolean $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ merupakan ruang vektor!

Kita dapat mendefinisikan inner product di ruang vektor ini sebagai berikut.

Definisi 2. Inner product $\langle \cdotp, \cdotp \rangle$ dari dua fungsi $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ didefinisikan sebagai

$\displaystyle \langle f,g \rangle = \mathbb{E}_{x \sim \{\pm 1\}^n} [f(x)g(x)]= 2^{-n} \sum_{x \in \{\pm 1\}^n} f(x)g(x).$

di mana notasi $x \sim \{\pm 1 \}^n$ menyatakan distribusi seragam (uniform) pada string-string di $\{\pm 1\}^n$ .

Kita juga definisikan norm-2 dari sebuah fungsi $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ sebagai

$\|f\| = \sqrt{\langle f,f \rangle}$ .

Lebih umum, kita definisikan norm- $p$ dari sebuah fungsi $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ sebagai

$\|f\|_p = \mathbb{E}_{x \sim \{\pm 1\}^n}[|f(x)|^p]^{\frac{1}{p}}$ .

Mudah diperiksa bahwa inner-product pada Definisi 2 di atas well-defined sehingga norm-2 dan norm- $p$ juga well-defined seperti di ruang vektor pada umumnya.

Inner product ini akan menjadi alat pertama kita untuk menganalisis fungsi-fungsi Boolean.

Referensi

O’Donnell, Ryan. Analysis of boolean functions. Cambridge University Press, 2014.