Wyrażenia i funkcje boolowskie

Algebra Boole'a jest algebrą logiki. Zajmuje się zmiennymi, które mogą mieć dwie dyskretne wartości, 0 (fałsz) i 1 (prawda); i operacje, które mają znaczenie logiczne. Najwcześniejsza metoda manipulowania logiką symboliczną została wymyślona przez George'a Boole'a, a następnie stała się znana jako algebra Boole'a.

Algebra Boole'a stała się obecnie nieodzownym narzędziem w informatyce ze względu na jej szerokie zastosowanie w teorii przełączania, budowie podstawowych obwodów elektronicznych i projektowaniu komputerów cyfrowych.

Funkcje boolowskie

A Boolean functionjest specjalnym rodzajem funkcji matematycznej $ f: X ^ n \ rightarrow X $ stopnia n, gdzie $ X = \ lbrace {0, 1} \ rbrace $ jest domeną boolowską, a n jest nieujemną liczbą całkowitą. Opisuje sposób, w jaki sposób wyprowadzić dane wyjściowe typu Boolean z danych wejściowych typu Boolean.

Example- Niech, $ F (A, B) = A'B '$. Jest to funkcja stopnia 2 ze zbioru uporządkowanych par zmiennych boolowskich do zbioru $ \ lbrace {0, 1} \ rbrace $, gdzie $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ i $ F (1, 1) = 0 $

Wyrażenia logiczne

A Boolean expressionzawsze daje wartość logiczną. Wyrażenie logiczne składa się z kombinacji stałych boolowskich (prawda lub fałsz), zmiennych boolowskich i łączników logicznych. Każde wyrażenie logiczne reprezentuje funkcję boolowską.

Example - $ AB'C $ jest wyrażeniem logicznym.

Tożsamości logiczne

Prawo podwójnego dopełniacza

$ \ sim (\ sim A) = A $

Prawo uzupełniające

$ A + \ sim A = 1 $ (formularz OR)

$ A. \ sim A = 0 $ (ORAZ formularz)

Idempotentne prawo

$ A + A = A $ (formularz OR)

$ A. A = A $ (ORAZ formularz)

Prawo tożsamości

$ A + 0 = A $ (formularz OR)

$ A. 1 = A $ (ORAZ formularz)

Prawo dominacji

$ A + 1 = 1 $ (formularz OR)

$ A. 0 = 0 $ (ORAZ formularz)

Prawo przemienne

$ A + B = B + A $ (formularz OR)

$ A. B = B. A $ (AND Form)

Prawo stowarzyszeniowe

$ A + (B + C) = (A + B) + C $ (OR Form)

$ A. (B. C) = (A. B). C $ (ORAZ formularz)

Prawo absorpcji

$ A. (A + B) = A $

$ A + (A. B) = A $

Prawo dotyczące uproszczenia

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

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

Prawo dystrybucyjne

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

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

Prawo De-Morgana

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

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

Formy kanoniczne

W przypadku wyrażenia logicznego istnieją dwa rodzaje form kanonicznych -

  • Suma form minterms (SOM)
  • Iloczyn postaci maxterms (POM)

Formularz Suma Minterms (SOM) lub Sum of Products (SOP)

Minterm jest iloczynem wszystkich zmiennych w postaci bezpośredniej lub uzupełnionej. Dowolna funkcja logiczna może być wyrażona jako suma jej 1-minterminów, a odwrotność funkcji może być wyrażona jako suma jej 0-mintermów. W związku z tym,

F (lista zmiennych) = ∑ (lista 1-minutowych indeksów)

i

F '(lista zmiennych) = ∑ (lista indeksów 0-minterm)

ZA b do Semestr 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

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

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

W związku z tym,

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

Teraz znajdziemy dopełnienie $ F (x, y, z) $

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

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

W związku z tym,

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

Formularz Product of Maxterms (POM) lub Product of Sums (POS)

Maksymalny termin to dodanie wszystkich zmiennych w postaci bezpośredniej lub uzupełnionej. Dowolna funkcja logiczna może być wyrażona jako iloczyn jej 0-maksymalnych terminów, a odwrotność funkcji może być wyrażona jako iloczyn jej 1-maksymalnych terminów. W związku z tym,

F (lista zmiennych) = $ \ pi $ (lista indeksów 0-maxterm).

i

F '(lista zmiennych) = $ \ pi $ (lista maksymalnie 1-terminowych indeksów).

ZA b do Semestr 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

Przykład

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

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

W związku z tym,

$ 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 ') $

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

W związku z tym,

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

Bramki logiczne

Funkcje boolowskie są implementowane przy użyciu bramek logicznych. Oto bramki logiczne -

NIE Brama

Bramka NOT zamienia pojedynczy bit wejściowy na pojedynczy bit wyjściowy.

ZA ~ A
0 1
1 0

Brama AND

Bramka AND jest bramką logiczną, która daje wysoki sygnał wyjściowy tylko wtedy, gdy wszystkie jej wejścia są wysokie, w przeciwnym razie daje niski sygnał wyjściowy. Kropka (.) Służy do pokazania operacji AND.

ZA b AB
0 0 0
0 1 0
1 0 0
1 1 1

LUB Brama

Bramka OR to bramka logiczna, która daje wysoki sygnał wyjściowy, jeśli przynajmniej jedno z wejść jest wysokie. Znak plus (+) służy do pokazania operacji LUB.

ZA b A + B
0 0 0
0 1 1
1 0 1
1 1 1

Brama NAND

Bramka NAND to bramka logiczna, która daje niski poziom wyjściowy tylko wtedy, gdy wszystkie jej wejścia są wysokie, w przeciwnym razie zapewnia wysoką wydajność.

ZA b ~ (AB)
0 0 1
0 1 1
1 0 1
1 1 0

Brama NOR

Bramka NOR jest bramką logiczną, która daje wysoki sygnał wyjściowy, jeśli oba wejścia są niskie, w przeciwnym razie daje niski poziom wyjściowy.

ZA b ~ (A + B)
0 0 1
0 1 0
1 0 0
1 1 0

Brama XOR (ekskluzywna OR)

Bramka XOR to bramka logiczna, która daje wysoką moc wyjściową, jeśli wejścia są różne, w przeciwnym razie daje niski poziom wyjściowy.

ZA b A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Brama X-NOR (ekskluzywna NOR)

Bramka EX-NOR jest bramką logiczną, która daje wysoki sygnał wyjściowy, jeśli wejścia są takie same, w przeciwnym razie daje niski poziom wyjściowy.

ZA b A X-NOR B
0 0 1
0 1 0
1 0 0
1 1 1