Fungsi boolean

Sebuah diagram keputusan biner dan tabel kebenaran dari 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}). Fungsi Boolean digunakan terutama dalam literatur ilmu komputer yang lebih tua, dan fungsi kebenaran (atau fungsi logis) yang digunakan dalam logika. Fungsi Boolean adalah subjek dari aljabar Boolean dan teori peralihan.

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

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