Teorema DeMorgan

Seorang matematikawan bernama DeMorgan mengembangkan sepasang aturan penting mengenai komplementasi grup dalam aljabar Boolean.

Oleh grup komplementasi, yang saya maksud adalah komplemen dari sekelompok istilah, yang diwakili oleh bilah panjang di lebih dari satu variabel.

Anda harus ingat dari bab tentang gerbang logika bahwa membalikkan semua input ke gerbang membalikkan fungsi penting gerbang itu dari AND ke OR, atau sebaliknya, dan juga membalikkan output.

Jadi, gerbang OR dengan semua input dibalik (gerbang OR Negatif) berperilaku sama dengan gerbang NAND, dan gerbang AND dengan semua input dibalik (gerbang AND Negatif) berperilaku sama dengan gerbang NOR.

Teorema DeMorgan menyatakan ekivalensi yang sama dalam bentuk “mundur”:bahwa membalik output dari setiap gerbang menghasilkan fungsi yang sama dengan jenis gerbang yang berlawanan (AND vs. OR) dengan input terbalik:

Sebuah batang panjang yang memanjang di atas suku AB bertindak sebagai simbol pengelompokan, dan karena itu sama sekali berbeda dari perkalian A dan B yang dibalik secara bebas.

Dengan kata lain, (AB)’ tidak sama dengan A’B’. Karena simbol “prima” (’) tidak dapat diregangkan pada dua variabel seperti kaleng batang, kita terpaksa menggunakan tanda kurung untuk membuatnya berlaku untuk seluruh istilah AB dalam kalimat sebelumnya.

Sebuah bar, bagaimanapun, bertindak sebagai simbol pengelompokannya sendiri ketika direntangkan pada lebih dari satu variabel.

Ini memiliki dampak besar pada bagaimana ekspresi Boolean dievaluasi dan dikurangi, seperti yang akan kita lihat.

Teorema DeMorgan

Teorema DeMorgan dapat dianggap sebagai breaking simbol batang panjang.

Ketika batang panjang dipatahkan, operasi tepat di bawah pemutusan berubah dari penjumlahan ke perkalian, atau sebaliknya, dan potongan batang yang patah tetap berada di atas variabel individual. Sebagai ilustrasi:

Saat beberapa "lapisan" bilah ada dalam sebuah ekspresi, Anda hanya boleh mematahkan satu batang dalam satu waktu , dan biasanya lebih mudah untuk memulai penyederhanaan dengan mematahkan bilah terpanjang (paling atas) terlebih dahulu.

Untuk mengilustrasikannya, mari kita ambil ekspresi (A + (BC)’)’ dan kurangi menggunakan Teorema DeMorgan:

Mengikuti saran untuk memecahkan bilah terpanjang (paling atas) terlebih dahulu, saya akan mulai dengan memecahkan bilah yang menutupi seluruh ekspresi sebagai langkah pertama:

Akibatnya, rangkaian asli direduksi menjadi gerbang AND tiga masukan dengan masukan A terbalik:

Anda seharusnya tidak pernah memecahkan lebih dari satu batang dalam satu langkah, seperti yang diilustrasikan di sini:

Meskipun tergoda untuk menghemat langkah dan mematahkan lebih dari satu batang dalam satu waktu, hal ini sering kali menyebabkan hasil yang salah, jadi jangan lakukan!

Dimungkinkan untuk mengurangi ekspresi ini dengan benar dengan memecah bilah pendek terlebih dahulu, daripada bilah panjang terlebih dahulu:

Hasil akhirnya sama, tetapi diperlukan lebih banyak langkah dibandingkan dengan menggunakan metode pertama, di mana batang terpanjang dipatahkan terlebih dahulu.

Perhatikan bagaimana pada langkah ketiga kami mematahkan palang panjang di dua tempat.

Ini adalah operasi matematika yang sah, dan tidak sama dengan mematahkan dua batang dalam satu langkah!

Larangan melanggar lebih dari satu batang dalam satu langkah tidak larangan melanggar palang di lebih dari satu tempat.

Mendobrak lebih dari satu tempat dalam satu langkah tidak apa-apa; melanggar lebih dari satu bar dalam satu langkah tidak.

Anda mungkin bertanya-tanya mengapa tanda kurung ditempatkan di sekitar sub-ekspresi B’ + C’, mengingat fakta bahwa saya baru saja menghapusnya di langkah berikutnya.

Saya melakukan ini untuk menekankan aspek penting tetapi mudah diabaikan dari teorema DeMorgan.

Karena batang panjang berfungsi sebagai simbol pengelompokan, variabel yang sebelumnya dikelompokkan oleh batang patah harus tetap dikelompokkan agar prioritas yang tepat (urutan operasi) hilang.

Dalam contoh ini, tidak masalah jika saya lupa memasukkan tanda kurung setelah melanggar bilah pendek, tetapi dalam kasus lain mungkin saja.

Perhatikan contoh ini, dimulai dengan ekspresi yang berbeda:

Seperti yang Anda lihat, mempertahankan pengelompokan yang tersirat oleh bilah pelengkap untuk ekspresi ini sangat penting untuk mendapatkan jawaban yang benar.

Mari kita terapkan prinsip-prinsip teorema DeMorgan pada penyederhanaan rangkaian gerbang:

Seperti biasa, langkah pertama kita dalam menyederhanakan rangkaian ini harus menghasilkan ekspresi Boolean yang setara.

Kita dapat melakukan ini dengan menempatkan label sub-ekspresi pada output setiap gerbang, saat input diketahui. Inilah langkah pertama dalam proses ini:

Selanjutnya, kita dapat memberi label output dari gerbang NOR pertama dan gerbang NAND.

Ketika berhadapan dengan gerbang keluaran terbalik, saya merasa lebih mudah untuk menulis ekspresi untuk keluaran gerbang tanpa inversi terakhir, dengan panah menunjuk tepat sebelum gelembung inversi.

Kemudian, di kawat yang mengarah keluar dari gerbang (setelah gelembung), saya menulis ekspresi lengkap yang dilengkapi.

Ini membantu memastikan saya tidak melupakan bilah pelengkap di sub-ekspresi, dengan memaksa diri saya untuk membagi tugas penulisan ekspresi menjadi dua langkah:

Akhirnya, kami menulis ekspresi (atau pasangan ekspresi) untuk gerbang NOR terakhir:

Sekarang, kita kurangi ekspresi ini menggunakan identitas, properti, aturan, dan teorema (DeMorgan) dari aljabar Boolean:

Rangkaian gerbang ekivalen untuk ekspresi yang sangat disederhanakan ini adalah sebagai berikut:

TINJAUAN:

• Teorema DeMorgan menggambarkan kesetaraan antara gerbang dengan input terbalik dan gerbang dengan output terbalik. Sederhananya, gerbang NAND setara dengan gerbang Negatif-OR, dan gerbang NOR setara dengan gerbang Negatif-AND.
• Saat "memecahkan" bilah pelengkap dalam ekspresi Boolean, operasi tepat di bawah jeda (penjumlahan atau perkalian) dibalik, dan potongan batang yang rusak tetap berada di atas persyaratan masing-masing.
• Sering kali lebih mudah untuk mendekati masalah dengan memecahkan batang terpanjang (paling atas) sebelum mematahkan batang apa pun di bawahnya. Anda harus tidak pernah mencoba mematahkan dua batang dalam satu langkah!
• Bilah pelengkap berfungsi sebagai simbol pengelompokan. Oleh karena itu, ketika batang dipatahkan, istilah di bawahnya harus tetap dikelompokkan. Tanda kurung dapat ditempatkan di sekitar istilah yang dikelompokkan ini sebagai bantuan untuk menghindari perubahan prioritas.

LEMBAR KERJA TERKAIT:

• Lembar Kerja Aljabar Boolean