Sirkuit Digital - Aljabar Boolean

Boolean Algebraadalah aljabar, yang berhubungan dengan bilangan biner & variabel biner. Oleh karena itu, ini juga disebut sebagai Aljabar Biner atau Aljabar logis. Seorang ahli matematika bernama George Boole telah mengembangkan aljabar ini pada tahun 1854. Variabel yang digunakan dalam aljabar ini disebut juga sebagai variabel Boolean.

Kisaran tegangan yang sesuai dengan Logika 'Tinggi' diwakili dengan '1' dan kisaran tegangan yang sesuai dengan logika 'Rendah' ​​diwakili dengan '0'.

Postulat dan Hukum Dasar Aljabar Boolean

Pada bagian ini, mari kita bahas tentang postulat Boolean dan hukum dasar yang digunakan dalam aljabar Boolean. Ini berguna dalam meminimalkan fungsi Boolean.

Postulat Boolean

Pertimbangkan bilangan biner 0 dan 1, variabel Boolean (x) dan komplemennya (x '). Baik variabel Boolean atau komplemennya dikenal sebagailiteral. Empat kemungkinanlogical OR operasi antara literal dan bilangan biner ini ditampilkan di bawah.

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

Demikian pula empat kemungkinan logical AND operasi antara literal dan bilangan biner tersebut ditunjukkan di bawah ini.

x.1 = x

x.0 = 0

xx = x

x.x '= 0

Ini adalah postulat Boolean sederhana. Kita dapat memverifikasi dalil ini dengan mudah, dengan mengganti variabel Boolean dengan '0' atau '1'.

Note- Komplemen dari setiap variabel Boolean sama dengan variabel itu sendiri. yaitu, (x ')' = x.

Hukum Dasar Aljabar Boolean

Berikut adalah tiga hukum dasar Aljabar Boolean.

  • Hukum komutatif
  • Hukum asosiatif
  • Hukum distributif

Hukum Komutatif

Jika ada operasi logis dari dua variabel Boolean memberikan hasil yang sama terlepas dari urutan kedua variabel tersebut, maka operasi logis tersebut dikatakan Commutative. Operasi logika OR & logika AND dari dua variabel Boolean x & y ditunjukkan di bawah ini

x + y = y + x

xy = yx

Simbol '+' menunjukkan operasi OR logis. Begitu pula dengan simbol '.' menunjukkan operasi AND yang logis dan bersifat opsional untuk diwakili. Hukum komutatif mematuhi operasi logis OR & logis AND.

Hukum Asosiatif

Jika operasi logika dari dua variabel Boolean dilakukan terlebih dahulu dan kemudian operasi yang sama dilakukan dengan variabel yang tersisa memberikan hasil yang sama, maka operasi logis tersebut dikatakan Associative. Operasi logika OR & logika AND dari tiga variabel Boolean x, y & z ditunjukkan di bawah ini.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

Hukum asosiatif mematuhi untuk operasi logis OR & logis AND.

Hukum distributif

Jika ada operasi logika yang dapat didistribusikan ke semua istilah yang ada dalam fungsi Boolean, maka operasi logis tersebut dikatakan Distributive. Distribusi operasi logika OR & logika AND dari tiga variabel Boolean x, y & z ditunjukkan di bawah ini.

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

Hukum distributif mematuhi operasi logika OR dan logika AND.

Ini adalah hukum dasar aljabar Boolean. Kita dapat memverifikasi hukum ini dengan mudah, dengan mengganti variabel Boolean dengan '0' atau '1'.

Teorema Aljabar Boolean

Dua teorema berikut digunakan dalam aljabar Boolean.

  • Teorema dualitas
  • Teorema DeMorgan

Teorema Dualitas

Teorema ini menyatakan bahwa dualdari fungsi Boolean diperoleh dengan menukar operator logika AND dengan operator logika OR dan nol dengan satu. Untuk setiap fungsi Boolean, akan ada fungsi Ganda yang sesuai.

Mari kita buat persamaan Boolean (relasi) yang telah kita bahas di bagian postulat Boolean dan hukum dasar menjadi dua kelompok. Tabel berikut menunjukkan dua kelompok ini.

Grup 1 Kelompok2
x + 0 = x x.1 = x
x + 1 = 1 x.0 = 0
x + x = x xx = x
x + x '= 1 x.x '= 0
x + y = y + x xy = yx
x + (y + z) = (x + y) + z x. (yz) = (xy) .z
x. (y + z) = xy + xz x + (yz) = (x + y). (x + z)

Di setiap baris, ada dua persamaan Boolean dan keduanya rangkap satu sama lain. Kita dapat memverifikasi semua persamaan Boolean dari Grup1 dan Grup2 ini dengan menggunakan teorema dualitas.

Teorema DeMorgan

Teorema ini berguna untuk mencari complement of Boolean function. Ini menyatakan bahwa komplemen logika OR dari setidaknya dua variabel Boolean sama dengan logika AND dari setiap variabel komplemen.

Teorema DeMorgan dengan 2 variabel Boolean x dan y dapat direpresentasikan sebagai

(x + y) '= x'.y'

Rangkap dari fungsi Boolean di atas adalah

(xy) '= x' + y '

Oleh karena itu, komplemen logika AND dari dua variabel Boolean sama dengan logika OR dari setiap variabel komplemen. Demikian pula, kita dapat menerapkan teorema DeMorgan untuk lebih dari 2 variabel Boolean juga.

Penyederhanaan Fungsi Boolean

Sampai sekarang, kita membahas postulat, hukum dasar dan teorema aljabar Boolean. Sekarang, mari kita sederhanakan beberapa fungsi Boolean.

Contoh 1

Biarkan kami simplify fungsi Boolean, f = p'qr + pq'r + pqr '+ pqr

Fungsi ini dapat disederhanakan dengan dua metode.

Method 1

Mengingat fungsi Boolean, f = p'qr + pq'r + pqr '+ pqr.

Step 1- Pada suku pertama dan kedua r umum dan pada suku ketiga dan keempat pq umum. Jadi, ambillah istilah umum dengan menggunakanDistributive law.

⇒ f = (p'q + pq ') r + pq (r' + r)

Step 2- Istilah yang ada dalam tanda kurung pertama dapat disederhanakan menjadi operasi Ex-OR. Istilah yang ada dalam tanda kurung kedua dapat disederhanakan menjadi '1' menggunakanBoolean postulate

⇒ f = (p ⊕q) r + pq (1)

Step 3- Istilah pertama tidak dapat disederhanakan lebih lanjut. Namun, suku kedua dapat disederhanakan menjadi pq menggunakanBoolean postulate.

⇒ f = (p ⊕q) r + pq

Oleh karena itu, fungsi Boolean yang disederhanakan adalah f = (p⊕q)r + pq

Method 2

Mengingat fungsi Boolean, f = p'qr + pq'r + pqr '+ pqr.

Step 1 - Gunakan Boolean postulate, x + x = x. Itu berarti, operasi Logical OR dengan variabel Boolean 'n' kali akan sama dengan variabel yang sama. Jadi, kita bisa menulis pqr suku terakhir dua kali lagi.

⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Step 2 - Gunakan Distributive lawuntuk 1 st dan 4 th istilah, 2 nd dan 5 th istilah, 3 rd dan 6 th istilah.

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Step 3 - Gunakan Boolean postulate, x + x '= 1 untuk menyederhanakan suku-suku yang ada di setiap tanda kurung.

⇒ f = qr (1) + pr (1) + pq (1)

Step 4 - Gunakan Boolean postulate, x.1 = x untuk menyederhanakan ketiga suku di atas.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Oleh karena itu, fungsi Boolean yang disederhanakan adalah f = pq + qr + pr.

Jadi, kami mendapatkan dua fungsi Boolean yang berbeda setelah menyederhanakan fungsi Boolean yang diberikan di setiap metode. Secara fungsional, kedua fungsi Boolean tersebut sama. Jadi, berdasarkan kebutuhan, kita bisa memilih salah satu dari dua fungsi Boolean tersebut.

Contoh 2

Mari kita temukan complement dari fungsi Boolean, f = p'q + pq '.

Komplemen dari fungsi Boolean adalah f '= (p'q + pq') '.

Step 1 - Gunakan teorema DeMorgan, (x + y) '= x'.y'.

⇒ f '= (p'q)'. (Pq ')'

Step 2 - Gunakan teorema DeMorgan, (xy) '= x' + y '

⇒ f '= {(p') '+ q'}. {P '+ (q') '}

Step3 - Gunakan postulat Boolean, (x ')' = x.

⇒ f '= {p + q'}. {P '+ q}

⇒ f '= pp' + pq + p'q '+ qq'

Step 4 - Gunakan postulat Boolean, xx '= 0.

⇒ f = 0 + pq + p'q '+ 0

⇒ f = pq + p'q '

Oleh karena itu, complement dari fungsi Boolean, p'q + pq 'adalah pq + p’q’.