Teorema DeMorgan: Menguasai Komplementasi Boolean dan Kesetaraan Gerbang
Konsep dasar dalam aljabar Boolean, Teorema DeMorgan menghubungkan perilaku gerbang logika saat input atau outputnya dibalik. Aturan ini, yang dinamai berdasarkan ahli matematika Augustus DeMorgan, memungkinkan insinyur untuk mentransformasikan gerbang AND, OR, NAND, dan NOR satu sama lain, menyederhanakan baik ekspresi logis maupun desain rangkaian fisik.
Dalam aljabar Boolean, “komplementasi grup” direpresentasikan oleh bar panjang di atas beberapa variabel, yang menunjukkan bahwa seluruh produk atau jumlah dibalik. Ini berbeda dari simbol prima ('), yang hanya dapat membalik satu variabel. Misalnya, (AB)′ tidak sama dengan A′B′; kurung penting untuk menandakan bahwa bar berlaku untuk seluruh produk.
Ketika setiap input ke gerbang dibalik, fungsi inti gerbang terbalik: gerbang OR dengan semua input dibalik berperilaku identik dengan gerbang NAND, sementara gerbang AND dengan input yang dibalik setara dengan gerbang NOR. Teorema DeMorgan formalisasi pengamatan ini dengan menunjukkan bahwa membalik output gerbang menghasilkan efek yang sama dengan mengubah jenis gerbang dan membalik inputnya.
Berikut adalah ilustrasi visual dari kesetaraan inti:
Ketika bar panjang “dipecah” dalam ekspresi Boolean, operasi langsung di bawah pecahan terbalik—penjumlahan berubah menjadi perkalian dan sebaliknya—sedangkan potongan bar yang dipecah tetap berada di atas variabel individu. Aturan halus ini mengatur bagaimana ekspresi disederhanakan.
Dalam ekspresi yang berisi beberapa lapisan bar, strategi teraman adalah memecah bar terpanjang dan teratas terlebih dahulu. Mencoba memecah dua bar sekaligus dapat menghasilkan hasil yang salah.
Misalnya, menyederhanakan (A + (BC)′)′ dilakukan sebagai berikut:
Pertama, kita pecah bar luar:
Hasilnya adalah gerbang AND tiga input dengan input A yang dibalik.
Jangan pernah memecah lebih dari satu bar dalam satu langkah:
Sebaliknya, Anda bisa pertama-tama memecah bar inner yang lebih pendek, tetapi ini membutuhkan langkah tambahan:
Perhatikan bahwa memecah satu bar di beberapa tempat dalam satu langkah diperbolehkan; pembatasan hanya berlaku untuk memecah beberapa bar yang berbeda sekaligus.
Kurung memerankan peran kritis karena bar berfungsi sebagai simbol pengelompokan. Setelah bar dipecah, istilah yang dikelompokkan harus tetap bersama untuk mempertahankan prioritas operator yang benar.
Pertimbangkan ekspresi ini yang menunjukkan pentingnya pengelompokan yang tepat:
Sekarang mari kita terapkan Teorema DeMorgan pada rangkaian gerbang nyata. Langkah pertama adalah menterjemahkan rangkaian menjadi ekspresi Boolean dengan melabeli output setiap gerbang:
Melanjutkan secara sistematis, kita tulis output gerbang NOR dan NAND pertama, memastikan bar komplementasi tidak terlewat dengan memisahkan ekspresi sebelum inversi dari output yang dikomplementasi akhir:
Akhirnya, kita ungkapkan output gerbang NOR terakhir:
Mengurangi ekspresi yang dihasilkan menggunakan identitas Boolean dan Teorema DeMorgan menghasilkan bentuk yang efisien:
Rangkaian yang setara dan disederhanakan ditunjukkan di bawah ini:
Kesimpulan Utama
- Teorema DeMorgan ungkapkan bahwa membalik output gerbang setara dengan mengubah jenisnya (AND ↔ OR) sambil membalik inputnya.
- Memecah bar komplementasi membalik operasi dasar; potongan yang dipecah tetap di atas variabel yang terpengaruh.
- Selalu pecah bar terpanjang dan teratas terlebih dahulu dan jangan pernah mencoba memecah dua bar yang berbeda dalam satu langkah.
- Bar berfungsi sebagai simbol pengelompokan; setelah dipecah, pertahankan pengelompokan yang tepat dengan kurung untuk menjaga prioritas.
Lembar Kerja Terkait
