Fungsi boolean

Dalam matematika, fungsi Boolean adalah sebuah fungsi yang argumen (nilai masukan/input) dan hasilnya mengasumsikan nilai dari himpunan dua elemen (biasanya {ya, tidak}, {benar, salah}, {0,1} atau {-1,1}).^[1][2] Fungsi Boolean digunakan terutama dalam literatur ilmu komputer yang lebih tua,^[2][3] dan fungsi kebenaran (atau fungsi logis) yang digunakan dalam logika. Fungsi Boolean adalah subjek dari aljabar Boolean dan teori peralihan.^[3]

Fungsi Boolean mengambil bentuk ${\displaystyle \displaystyle {f:\{0,1\}^{k}\to \{0,1\}}}$, di mana ${\displaystyle \displaystyle \{0,1\}}$ dikenal sebagai domain Boolean dan ${\displaystyle \displaystyle {k}}$ adalah bilangan bulat non-negatif yang disebut dengan aritas dari fungsi tersebut. Dalam kasus di mana ${\displaystyle \displaystyle {k=0}}$, fungsi tersebut adalah elemen konstan dari ${\displaystyle \displaystyle \{0,1\}}$. Fungsi Boolean dengan beberapa keluaran, ${\displaystyle \displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$ dengan ${\displaystyle \displaystyle {m>1}}$adalah sebuah fungsi Boolean yang bernilai vektor.

Ada ${\displaystyle \displaystyle 2^{2^{k}}}$ fungsi Boolean yang berbeda dengan argumen sebanyak ${\displaystyle \displaystyle {k}}$ ; sama dengan jumlah tabel kebenaran yang berbeda dengan ${\displaystyle \displaystyle 2^{k}}$ entri .Setiap ${\displaystyle \displaystyle k}$-ariti fungsi Boolean dapat diekspresikan sebagai rumus proposisional dalam ${\displaystyle \displaystyle k}$ variabel ${\displaystyle \displaystyle x_{1},...,x_{k}}$ dan dua rumus proposisional secara logika setara jika dan hanya jika keduanya mengekspresikan fungsi Boolean yang sama.