Aljabar Boolean

Aljabar boolean adalah cabang matematika yang mendasari setiap chip di dalam komputer, yakni rangkaian logika yang dibuat sebagai satu komponen fisik. Topik ini membahas tiga operasi dasar beserta operasi XOR, tabel kebenaran yang mendefinisikannya, dan hukum-hukum penyederhanaan ekspresi boolean. Notasi yang diperkenalkan di sini menjadi notasi baku untuk seluruh jalur. Pada bagian akhir, hukum de Morgan dan hukum distributif diverifikasi dengan program Python yang menelusuri seluruh kombinasi nilai masukan.

Operasi dasar AND, OR, dan NOT#

Aljabar boolean bekerja atas nilai yang hanya mengenal dua keadaan, yaitu 1 untuk benar dan 0 untuk salah. Satu angka biner semacam ini disebut bit, yakni satuan data terkecil pada perangkat keras. Tiga operasi dasar merangkai bit-bit itu: AND menghasilkan 1 hanya apabila kedua masukannya bernilai 1, OR menghasilkan 1 apabila salah satu masukannya bernilai 1, dan NOT membalik nilai masukannya. Perilaku setiap operasi didefinisikan lengkap oleh tabel kebenaran (truth table), yaitu daftar keluaran untuk seluruh kemungkinan masukan.

Notasi mengikuti kebiasaan buku teks perangkat keras. Konjungsi AND ditulis dengan titik, $A \cdot B$, disjungsi OR ditulis dengan tanda tambah, $A + B$, sedangkan negasi NOT ditulis sebagai garis di atas variabel, $\overline{A}$. Tanda titik sering ditiadakan sehingga $A \cdot B$ juga ditulis $AB$. Urutan pengerjaannya sejajar aritmetika biasa: NOT bekerja lebih dahulu, kemudian AND, dan OR paling akhir. Dua ekspresi yang menghasilkan tabel kebenaran yang sama dinyatakan ekuivalen, dan tanda sama dengan menunjukkan ekuivalensi itu.

XOR, literal, dan minterm#

Operasi gabungan yang paling sering dipakai di sepanjang jalur ini adalah XOR (exclusive or), yang menghasilkan 1 tepat apabila kedua masukannya berbeda. Operasi ini ditulis $A \oplus B$ dan dinyatakan dalam operasi dasar sebagai

Pembacaan ekspresi boolean memakai dua istilah yang muncul berulang kali pada jalur ini. Literal adalah satu variabel dalam bentuk aslinya atau bentuk ternegasi, misalnya $A$ dan $\bar{A}$ pada ekspresi di atas. Minterm adalah suku AND yang memuat setiap variabel tepat satu kali, dalam bentuk asli atau ternegasi, sehingga suku itu bernilai 1 hanya untuk satu kombinasi masukan. Ekspresi XOR di atas tersusun dari dua minterm, dan masing-masing minterm menutupi satu baris tabel kebenaran XOR yang bernilai 1. Bentuk penjumlahan minterm semacam ini menjadi titik awal standar ketika sebuah fungsi diterjemahkan dari tabel kebenaran menjadi rangkaian, karena setiap baris bernilai 1 langsung menjadi satu suku.

Hukum-hukum penyederhanaan#

Ekspresi boolean jarang muncul dalam bentuk paling ringkasnya. Hukum-hukum aljabar boolean menyediakan cara mengubah bentuk ekspresi tanpa mengubah perilakunya, dan hasil penyederhanaannya berarti lebih sedikit gerbang pada chip. Berikut hukum-hukum yang dipakai di sepanjang jalur ini untuk setiap nilai $A$, $B$, dan $C$.

• Hukum komutatif menyatakan $A + B = B + A$ dan $A \cdot B = B \cdot A$.
• Hukum asosiatif menyatakan $(A + B) + C = A + (B + C)$ dan $A \cdot (B \cdot C) = (A \cdot B) \cdot C$.
• Hukum distributif menyatakan $A \cdot (B + C) = A \cdot B + A \cdot C$ serta bentuk keduanya, $A + (B \cdot C) = (A + B) \cdot (A + C)$.
• Hukum identitas menyatakan $A + 0 = A$ dan $A \cdot 1 = A$, sedangkan hukum idempoten menyatakan $A + A = A$ dan $A \cdot A = A$.
• Hukum komplemen menyatakan $A + \bar{A} = 1$ dan $A \cdot \bar{A} = 0$.
• Hukum absorpsi menyatakan $A + A \cdot B = A$ dan $A \cdot (A + B) = A$.
• Hukum de Morgan menyatakan $\overline{A \cdot B} = \bar{A} + \bar{B}$ dan $\overline{A + B} = \bar{A} \cdot \bar{B}$.

Hukum de Morgan mendapat peran khusus pada perangkat keras karena menghubungkan AND dengan OR. Kedua bentuknya menyatakan bahwa negasi dapat bergeser melewati operator asalkan operatornya ikut bertukar. Hukum absorpsi memperlihatkan kejutan yang tidak dimiliki aritmetika biasa, yaitu suku yang memuat $A$ dapat hilang seluruhnya karena kasus $A = 0$ dan kasus $A = 1$ sama-sama menentukan hasil ekspresi tersebut. Transformasi semacam inilah yang mengubah tabel kebenaran mentah menjadi rangkaian yang hemat.

Membuktikan hukum dengan enumerasi#

Kekuatan aljabar boolean terletak pada domainnya yang kecil. Hanya ada empat kombinasi nilai untuk dua variabel dan delapan untuk tiga variabel, sehingga sebuah hukum dapat dibuktikan dengan memeriksa seluruh kombinasi itu satu per satu. Program berikut mendefinisikan operasi AND, OR, dan NOT untuk nilai 0 dan 1, mencetak tabel kebenaran kedua bentuk de Morgan, lalu menguji hukum de Morgan dan hukum distributif terhadap semua kombinasi masukan. Fungsi all() pada Python mengembalikan True hanya apabila setiap pengujian bernilai benar.

"""Verifikasi hukum de Morgan dan hukum distributif lewat enumerasi lengkap.

Setiap operasi didefinisikan untuk nilai 0 dan 1, lalu setiap hukum diuji
terhadap seluruh kombinasi nilai variabelnya.
"""


def dan(a, b):
    """Operasi AND pada nilai 0 dan 1."""
    return a & b


def atau(a, b):
    """Operasi OR pada nilai 0 dan 1."""
    return a | b


def tidak(a):
    """Operasi NOT pada nilai 0 dan 1."""
    return 1 - a


dua_bit = [(0, 0), (0, 1), (1, 0), (1, 1)]
tiga_bit = [(a, b, c) for a in (0, 1) for b in (0, 1) for c in (0, 1)]

print(f"A B | {'~(A.B)':^6} {'~A+~B':^6}")
for a, b in dua_bit:
    print(f"{a} {b} | {tidak(dan(a, b)):^6} {atau(tidak(a), tidak(b)):^6}")

print(f"\nA B | {'~(A+B)':^6} {'~A.~B':^6}")
for a, b in dua_bit:
    print(f"{a} {b} | {tidak(atau(a, b)):^6} {dan(tidak(a), tidak(b)):^6}")

de_morgan_dan = all(tidak(dan(a, b)) == atau(tidak(a), tidak(b)) for a, b in dua_bit)
de_morgan_atau = all(tidak(atau(a, b)) == dan(tidak(a), tidak(b)) for a, b in dua_bit)
distributif_satu = all(
    dan(a, atau(b, c)) == atau(dan(a, b), dan(a, c)) for a, b, c in tiga_bit
)
distributif_dua = all(
    atau(a, dan(b, c)) == dan(atau(a, b), atau(a, c)) for a, b, c in tiga_bit
)

print("\nKesimpulan enumerasi lengkap:")
print(f"~(A.B) = ~A+~B berlaku untuk semua kombinasi: {de_morgan_dan}")
print(f"~(A+B) = ~A.~B berlaku untuk semua kombinasi: {de_morgan_atau}")
print(f"A.(B+C) = A.B+A.C berlaku untuk semua kombinasi: {distributif_satu}")
print(f"A+(B.C) = (A+B).(A+C) berlaku untuk semua kombinasi: {distributif_dua}")

A B | ~(A.B) ~A+~B 
0 0 |   1      1   
0 1 |   1      1   
1 0 |   1      1   
1 1 |   0      0   

A B | ~(A+B) ~A.~B 
0 0 |   1      1   
0 1 |   0      0   
1 0 |   0      0   
1 1 |   0      0   

Kesimpulan enumerasi lengkap:
~(A.B) = ~A+~B berlaku untuk semua kombinasi: True
~(A+B) = ~A.~B berlaku untuk semua kombinasi: True
A.(B+C) = A.B+A.C berlaku untuk semua kombinasi: True
A+(B.C) = (A+B).(A+C) berlaku untuk semua kombinasi: True

Laporan True pada keluaran berlaku untuk seluruh kombinasi yang mungkin, bukan sekadar untuk beberapa contoh yang dipilih. Argumen semacam ini adalah bentuk pembuktian paling sederhana pada domain dua nilai. Pada aritmetika biasa, cara yang sama tidak dapat dilakukan karena bilangan bulat berjumlah tak terbatas, sehingga pembuktian di sana memerlukan jalur deduksi.

Kesalahan umum#

Kesalahan pertama yang sering terjadi adalah menerapkan hukum de Morgan tanpa menukar operatornya, sehingga $\overline{A \cdot B}$ disederhanakan menjadi $\bar{A} \cdot \bar{B}$. Bentuk kedua itu keliru karena bernilai 1 hanya pada $A = 0$, $B = 0$, sedangkan bentuk yang benar bernilai 1 pada tiga kombinasi lain. Kesalahan kedua adalah membaca $\overline{A \cdot B}$ seolah-olah hanya $A$ yang dinegasikan. Garis yang membentang di atas seluruh ekspresi berarti seluruh ekspresi dinegasikan lebih dahulu sebelum dibaca. Kesalahan ketiga adalah memindahkan kebiasaan aritmetika ke aljabar boolean, misalnya menuliskan $A + A = 2A$. Angka dua tidak memiliki arti di sini karena nilai hanya mengenal 0 dan 1, dan hukum idempoten justru menyatakan $A + A = A$. Apabila sebuah penyederhanaan terasa meragukan, tulis tabel kebenaran kedua sisinya lalu bandingkan baris demi baris.

Ringkasan#

• AND, OR, dan NOT didefinisikan lengkap oleh tabel kebenarannya, dan XOR dinyatakan sebagai $A \cdot \bar{B} + \bar{A} \cdot B$.
• Notasi jalur ini memakai titik untuk AND, tanda tambah untuk OR, dan garis atas untuk NOT.
• Hukum komutatif, asosiatif, distributif, absorpsi, dan de Morgan menyederhanakan ekspresi tanpa mengubah perilakunya.
• Pada domain dua nilai, sebuah hukum dibuktikan dengan enumerasi seluruh kombinasi masukan.

Referensi#

• Computation Structures, Spring 2017 — MIT OpenCourseWare — Materi kuliah yang memperkenalkan aljabar boolean dan hukum-hukumnya sebagai dasar rangkaian digital.
• The Elements of Computing Systems, Second Edition — Nand2Tetris — Proyek yang membangun seluruh komputer dari gerbang NAND dan memakai notasi boolean yang sama.