Aljabar Boolean

Aljabar Boolean adalah sistem matematika yang hanya mengenal dua nilai, yaitu 0 dan 1. Nilai 0 menyatakan keadaan salah (false), sedangkan 1 menyatakan keadaan benar (true). Sistem ini tidak memiliki angka lain. Sebuah variabel dalam Aljabar Boolean hanya dapat diisi dengan salah satu dari dua nilai tersebut. Variabel lazim ditulis dengan satu huruf kapital, misalnya A, B, atau X. Variabel-variabel ini dapat dirangkai menggunakan operator logika untuk membentuk ekspresi Boolean. Ekspresi Boolean adalah untaian simbol yang ketika dihitung selalu menghasilkan 0 atau 1.

Operasi

Operasi NOT (komplemen/inversi) bekerja pada satu variabel. Operasi ini membalik nilai variabel: jika masukan 0 hasilnya 1, jika masukan 1 hasilnya 0. Simbolnya berupa tanda petik tunggal di belakang variabel, misalnya A′ (dibaca "bukan A").

Operasi AND (konjungsi/perkalian logika) bekerja pada dua variabel atau lebih. Hasil operasi ini bernilai 1 hanya jika seluruh masukan bernilai 1. Jika ada satu saja masukan 0, hasilnya 0. Simbolnya berupa titik (·) atau variabel ditulis berdampingan tanpa tanda, misalnya A·B atau AB.

Operasi OR (disjungsi/penjumlahan logika) bekerja pada dua variabel atau lebih. Hasil operasi ini bernilai 1 jika setidaknya satu masukan bernilai 1. Hasilnya 0 hanya apabila seluruh masukan 0. Simbolnya adalah tanda tambah (+).

Tabel Kebenaran

Setiap ekspresi Boolean dapat diwakili secara lengkap oleh sebuah tabel kebenaran. Tabel kebenaran mendaftar seluruh kemungkinan kombinasi nilai masukan beserta hasil keluarannya. Jika sebuah fungsi memiliki n variabel masukan, tabelnya akan terdiri dari 2ⁿ baris. Setiap baris memuat satu kombinasi nilai masukan dan satu nilai keluaran yang dihitung dari ekspresi tersebut. Tabel kebenaran menjadi alat utama untuk menguji apakah dua ekspresi Boolean berbeda sebenarnya memiliki fungsi yang sama. Dua ekspresi dianggap sama jika dan hanya jika kolom keluarannya identik di semua baris.

A	B	F = A + B
0	0	0
0	1	1
1	0	1
1	1	1

Tabel ini menunjukkan bahwa F hanya bernilai 0 ketika A dan B keduanya 0. Untuk semua kombinasi lain, hasilnya 1. Tabel kebenaran juga digunakan untuk membuktikan hukum-hukum aljabar Boolean yang akan dijelaskan berikutnya.

Hukum

Identity A + 0 = A dan A ⋅ 1 = A. Hukum ini menyatakan bahwa 0 adalah elemen netral pada operasi OR, dan 1 adalah elemen netral pada operasi AND.

Null A + 1 = 1 dan A ⋅ 0 = 0. Hukum ini menunjukkan bahwa 1 mendominasi operasi OR (hasilnya selalu 1) dan 0 mendominasi operasi AND (hasilnya selalu 0), tanpa memandang nilai variabel lainnya.

Idempotent A + A = A dan A ⋅ A = A. Menggabungkan variabel dengan dirinya sendiri menggunakan OR maupun AND tidak mengubah nilainya.

Inverse A + A′ = 1 dan A ⋅ A′ = 0. Sebuah variabel jika di-OR-kan dengan kebalikannya selalu menghasilkan 1, dan jika di-AND-kan dengan kebalikannya selalu menghasilkan 0.

Commutative A + B = B + A dan A ⋅ B = B ⋅ A. Urutan variabel pada operasi OR dan AND dapat ditukar tanpa mengubah hasil akhir.

Teorema De Morgan

Teorema De Morgan menghubungkan operasi NOT dengan AND dan OR ketika komplemen diterapkan pada suatu ekspresi yang berada di dalam tanda kurung. Teorema ini terdiri dari dua aturan. Aturan pertama: (A + B)′ = A′ · B′. Artinya, komplemen dari hasil penjumlahan dua variabel sama dengan perkalian komplemen masing-masing variabel. Aturan kedua: (A · B)′ = A′ + B′. Artinya, komplemen dari hasil perkalian dua variabel sama dengan penjumlahan komplemen masing-masing variabel. Perhatikan bahwa operator di dalam kurung bertukar: OR menjadi AND, dan AND menjadi OR. Teorema ini sangat berguna untuk mengurai ekspresi yang memiliki komplemen besar menjadi bentuk yang lebih sederhana.

Reduksi Ekspresi

Tujuan utama mempelajari hukum-hukum di atas adalah untuk memperoleh bentuk ekspresi Boolean yang paling ringkas. Ekspresi yang lebih ringkas memiliki jumlah suku dan variabel yang lebih sedikit. Secara tradisional, penyederhanaan dilakukan dengan menerapkan hukum demi hukum secara bertahap. Sebagai contoh, ekspresi F = A′B′C + A′BC + AB′C + ABC dapat disederhanakan sebagai berikut.

Langkah pertama, kelompokkan suku-suku yang memiliki faktor persekutuan:
F = (A′B′C + A′BC) + (AB′C + ABC)

Langkah kedua, faktorkan A′C dari kelompok pertama dan AC dari kelompok kedua:
F = A′C(B′ + B) + AC(B′ + B)

Langkah ketiga, gunakan Inverse Law (B′ + B = 1):
F = A′C·1 + AC·1 → F = A′C + AC

Langkah keempat, faktorkan C:
F = C(A′ + A)

Langkah terakhir, kembali gunakan Inverse Law (A′ + A = 1):
F = C·1 → F = C

Hasil akhir menunjukkan bahwa ekspresi awal yang melibatkan tiga variabel ternyata hanya bergantung pada C.

Peta Karnaugh

Peta Karnaugh adalah metode penyederhanaan ekspresi Boolean secara visual menggunakan grid dua dimensi. Setiap sel pada grid mewakili satu kombinasi masukan. Susunan sel diatur sedemikian rupa sehingga sel yang bersebelahan (kiri-kanan, atas-bawah) hanya berbeda satu bit nilai variabel. Prosedur penyederhanaannya dimulai dengan mengisi sel bernilai 1 sesuai ekspresi yang diberikan. Selanjutnya, sel-sel bernilai 1 dikelompokkan menjadi persegi panjang dengan ukuran 1, 2, 4, 8, atau kelipatan dua lainnya. Satu kelompok boleh mencakup sel yang berada di tepi yang saling berhadapan karena sifat perbedaan satu bit. Dari setiap kelompok, kita mencatat variabel yang nilainya tidak berubah di dalam kelompok tersebut. Variabel yang berubah nilainya diabaikan. Hasil akhir adalah gabungan dari semua kelompok menggunakan operasi OR.

Untuk fungsi yang sama, F = A′B′C + A′BC + AB′C + ABC, disusun ke dalam K-Map tiga variabel (A, B, C) dengan susunan kolom BC: 00, 01, 11, 10.

A \ BC	00	01	11	10
0	0	1	1	0
1	0	1	1	0

Semua sel bernilai 1 terletak di kolom 01 dan 11. Kedua kolom ini dapat digabung menjadi satu kelompok besar yang meliputi seluruh baris (A = 0 dan A = 1). Di dalam kelompok ini, variabel C selalu bernilai 1, sedangkan A dan B berubah-ubah. Karena C tidak berubah, maka hasil penyederhanaannya adalah F = C. Metode ini memberikan hasil yang sama dengan cara aljabar, tetapi jauh lebih cepat dan minim kesalahan, terutama untuk fungsi dengan banyak variabel.