Ekspresi & Fungsi Boolean

Aljabar Boolean adalah aljabar logika. Ini berkaitan dengan variabel yang dapat memiliki dua nilai diskrit, 0 (Salah) dan 1 (Benar); dan operasi yang memiliki makna logis. Metode paling awal untuk memanipulasi logika simbolik ditemukan oleh George Boole dan kemudian dikenal sebagai Aljabar Boolean.

Aljabar Boolean kini telah menjadi alat yang sangat diperlukan dalam ilmu komputer karena penerapannya yang luas dalam teori switching, membangun sirkuit elektronik dasar, dan desain komputer digital.

Fungsi Boolean

A Boolean functionadalah jenis khusus dari fungsi matematika $ f: X ^ n \ rightarrow X $ derajat n, di mana $ X = \ lbrace {0, 1} \ rbrace $ adalah domain Boolean dan n adalah bilangan bulat non-negatif. Ini menjelaskan cara mendapatkan keluaran Boolean dari masukan Boolean.

Example- Misalkan, $ F (A, B) = A'B '$. Ini adalah fungsi derajat 2 dari himpunan pasangan terurut variabel Boolean ke himpunan $ \ lbrace {0, 1} \ rbrace $ di mana $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ dan $ F (1, 1) = 0 $

Ekspresi Boolean

A Boolean expressionselalu menghasilkan nilai Boolean. Ekspresi Boolean terdiri dari kombinasi konstanta Boolean (True atau False), variabel Boolean, dan penghubung logis. Setiap ekspresi Boolean mewakili fungsi Boolean.

Example - $ AB'C $ adalah ekspresi Boolean.

Identitas Boolean

Hukum Pelengkap Ganda

$ \ sim (\ sim A) = A $

Hukum Pelengkap

$ A + \ sim A = 1 $ (ATAU Formulir)

$ A. \ sim A = 0 $ (DAN Formulir)

Hukum Idempoten

$ A + A = A $ (ATAU Formulir)

$ A. A = A $ (DAN Formulir)

Hukum Identitas

$ A + 0 = A $ (ATAU Formulir)

$ A. 1 = A $ (DAN Formulir)

Hukum Dominasi

$ A + 1 = 1 $ (ATAU Formulir)

$ A. 0 = 0 $ (DAN Formulir)

Hukum Komutatif

$ A + B = B + A $ (ATAU Formulir)

$ A. B = B. A $ (DAN Formulir)

Hukum Asosiatif

$ A + (B + C) = (A + B) + C $ (ATAU Formulir)

$ A. (B. C) = (A. B). C $ (DAN Formulir)

Hukum Penyerapan

$ A. (A + B) = A $

$ A + (A. B) = A $

Hukum Penyederhanaan

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

Hukum distributif

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

Hukum De-Morgan

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

Bentuk Kanonis

Untuk ekspresi Boolean, ada dua jenis bentuk kanonis -

  • Bentuk Jumlah minterms (SOM)
  • Produk dari bentuk maxterms (POM)

Formulir Jumlah Minterms (SOM) atau Jumlah Produk (SOP)

Minterm adalah produk dari semua variabel yang diambil baik dalam bentuk langsung atau komplemen. Setiap fungsi Boolean dapat diekspresikan sebagai penjumlahan dari 1-menitnya dan kebalikan dari fungsinya dapat diekspresikan sebagai jumlah dari 0-mintermnya. Karenanya,

F (daftar variabel) = ∑ (daftar indeks jangka waktu 1 menit)

dan

F '(daftar variabel) = ∑ (daftar indeks jangka waktu 0 menit)

SEBUAH B C Istilah Minterm
0 0 0 x'y'z ' m 0
0 0 1 x'y'z m 1
0 1 0 x'yz ' m 2
0 1 1 x'yz m 3
1 0 0 xy'z ' m 4
1 0 1 xy'z m 5
1 1 0 xyz ' m 6
1 1 1 xyz m 7

Example

Misalkan, $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $

Atau, $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

Karenanya,

$ F (x, y, z) = \ jumlah (0, 5, 6, 7) $

Sekarang kita akan menemukan komplemen dari $ F (x, y, z) $

$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $

Atau, $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

Karenanya,

$ F '(x, y, z) = \ jumlah (3, 1, 2, 4) = \ jumlah (1, 2, 3, 4) $

Bentuk Product of Maxterms (POM) atau Product of Sums (POS)

Maxterm adalah penjumlahan dari semua variabel yang diambil baik dalam bentuk langsung atau komplemen. Setiap fungsi Boolean dapat diekspresikan sebagai hasil kali 0-maxterms dan kebalikan dari fungsinya dapat diekspresikan sebagai produk dari 1-maxterms-nya. Karenanya,

F (daftar variabel) = $ \ pi $ (daftar indeks 0-maxterm).

dan

F '(daftar variabel) = $ \ pi $ (daftar indeks 1-maxterm).

SEBUAH B C Istilah Maxterm
0 0 0 x + y + z M 0
0 0 1 x + y + z ' M 1
0 1 0 x + y '+ z M 2
0 1 1 x + y '+ z' M 3
1 0 0 x '+ y + z M 4
1 0 1 x '+ y + z' M 5
1 1 0 x '+ y' + z M 6
1 1 1 x '+ y' + z ' M 7

Contoh

Misalkan $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $

Atau, $ F (x, y, z) = M_0. M_1. M_2. M_4 $

Karenanya,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $

Atau, $ F (x, y, z) = M_3. M_5. M_6. M_7 $

Karenanya,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

Gerbang Logika

Fungsi Boolean diimplementasikan dengan menggunakan gerbang logika. Berikut ini adalah gerbang logika -

BUKAN Gerbang

Gerbang NOT membalikkan satu bit masukan menjadi satu bit keluaran.

SEBUAH ~ A
0 1
1 0

DAN Gerbang

Gerbang AND adalah gerbang logika yang memberikan output tinggi hanya jika semua inputnya tinggi, jika tidak maka outputnya rendah. Titik (.) Digunakan untuk menunjukkan operasi DAN.

SEBUAH B AB
0 0 0
0 1 0
1 0 0
1 1 1

OR Gerbang

Gerbang OR adalah gerbang logika yang memberikan output tinggi jika setidaknya salah satu inputnya tinggi. Tanda plus (+) digunakan untuk menunjukkan operasi OR.

SEBUAH B A + B
0 0 0
0 1 1
1 0 1
1 1 1

Gerbang NAND

Gerbang NAND adalah gerbang logika yang memberikan output rendah hanya jika semua inputnya tinggi, jika tidak maka outputnya tinggi.

SEBUAH B ~ (AB)
0 0 1
0 1 1
1 0 1
1 1 0

Gerbang NOR

Gerbang NOR adalah gerbang logika yang memberikan output tinggi jika kedua inputnya rendah, jika tidak maka outputnya rendah.

SEBUAH B ~ (A + B)
0 0 1
0 1 0
1 0 0
1 1 0

Gerbang XOR (Exclusive OR)

Gerbang XOR adalah gerbang logika yang memberikan output tinggi jika input berbeda, jika tidak maka outputnya rendah.

SEBUAH B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Gerbang X-NOR (Exclusive NOR)

Gerbang EX-NOR adalah gerbang logika yang memberikan output tinggi jika inputnya sama, jika tidak maka outputnya rendah.

SEBUAH B A X-NOR B
0 0 1
0 1 0
1 0 0
1 1 1