Booleova algebra

Logické obvody realizují logické funkce , které jsou definovány Booleovou algebrou , což je binární algebra, v níž jsou použity tyto logické funkce: AND (logický součin), OR (logický součet), NAND (negovaný logický součin), NOR (negovaný logický součet) a negace. Všechny operace jsou prováděny nad dvouprvkovou množinou hodnot { 0, 1 }.

Tuto algebru zavedl v 19. století George Boole jako zjednodušení zápisu matematických vět a důkazů. V roce 1937 tuto algebru použil Claude Elwood Shannon k popisu zapojení sítí relé a spínačů.

Dvojková soustava

Dvojková číselná soustava začala mít praktický význam, až v době prvních počítačů. Jsou v ní povolené dva znaky, 0 a 1.

Převod z desítkové soustavy do dvojkové

Postup je relativně jednoduchý, číslo dělíme dvěma, zapisujeme si zbytky po dělení a nakonec získané číslo otočíme. Příkladem může být převod čísla 60:

60 : 2 = 30 zbytek 0
30 : 2 = 15 zbytek 0
15 : 2 = 7 zbytek 1
7 : 2 = 3 zbytek 1
3 : 2 = 1 zbytek 1
1 : 2 = 0 zbytek 1

Takže desítkové číslo 60 je ve dvojkové soustavě 111100.

Převod z dvojkové soustavy do desítkové

Převod opačným směrem je také poměrně jednoduché, ukážeme si to na stejném příkladu, tzn. převedeme číslo 111100 do desítkové soustavy. Číslo si rozložíme na jednotlivé číslici, a provedeme součet součinu číslice a členu 2n, kde n je rovno pozici číslice, pozici značíme zprava a číslujeme od 0.

(111100)2 = 1.25 + 1.24 + 1.23 + 1.22 + 0.21 + 0.20 = (60)10

Pravdivostní tabulky základních logických funkcí

Pravdivostní tabulky základních logických funkcí
A B AND OR NAND NOR neg. A neg. B
0 0 0 0 1 1 1 1
0 1 0 1 1 0 1 0
1 0 0 1 1 0 0 1
1 1 1 1 0 0 0 0

Základní pravidla Booleovy algebry

Zákony agresivnosti hodnot 0 a 1
a + 1 = 1 a . 0 = 0
Zákony neutrálnosti hodnot 0 a 1
a + 0 = a a . 1 = a
Zákony komutativní
a + b = b + a ab = ba
Zákony asociativní
a + (b + c) = (a + b) + c a(bc) = (ab)c
Zákony distributivní
a(b + c) = ab + ac a + bc = (a + b)(a + c)
Zákon dvojité negace
Zákon o vyloučeném třetím
Zákony absorpce
a + a = a
a + ab = a
a(a + b) = a
aa = a
Zákony absorpce negace
Zákony o vytvoření negace (zákony de Morganovy)

Příklady logických funkcí

Příklady logických funkcí
Funkce Vstupní proměnné a 0 1 0 1
b 0 0 1 1
Název funkce Logický člen Algebraický výraz
f 0 0 0 0 0 konstanta 0
f 1 0 1 1 1 logický součet OR a + b
f 2 1 0 1 1 implikace
f 3 1 1 0 1 implikace
f 4 1 1 1 0 Shefferova funkce NAND
f 5 0 0 0 1 logický součin AND ab
f 6 0 0 1 0 inhibice
f 7 0 1 0 0 inhibice
f 8 1 0 0 0 Pieceova funkce NOR
f 9 0 1 0 1 identita a
f 10 0 0 1 1 identita b
f 11 1 0 0 1 ekvivalence
f 12 0 1 1 0 neekvivalence Exclusive-OR
f 13 1 0 1 0 negace NOT
f 14 1 1 0 0 negace NOT
f 15 1 1 1 1 konstanta 1

Literatura

  1. Introduction to Boolean Algebra

Napsat komentář