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)

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

ZA	b	do	Semestr	Minterm
0	0	0	x'y'z '	m ₀
0	0	1	x'y'z	m ₁
0	1	0	x'yz '	m ₂
0	1	1	x'yz	m ₃
1	0	0	xy'z '	m ₄
1	0	1	xy'z	m ₅
1	1	0	xyz ”	m ₆
1	1	1	xyz	m ₇

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).

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

ZA	b	do	Semestr	Maxterm
0	0	0	x + y + z	M ₀
0	0	1	x + y + z '	M ₁
0	1	0	x + y '+ z	M ₂
0	1	1	x + y '+ z'	M ₃
1	0	0	x '+ y + z	M ₄
1	0	1	x '+ y + z'	M ₅
1	1	0	x '+ y' + z	M ₆
1	1	1	x '+ y' + z '	M ₇

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