Booleova logika
Booleova logika se zabývá logickými operacemi konjunkce (značená též "*", AND, "&" nebo ), disjunkce (značena též "+", OR, "|", "." nebo ) a negace (značena též pruhem nad částí výrazu, NOT) na množině hodnot { 0, 1 }. Jejím rozšířením je pak Booleova algebra.
Definice logických funkcí
[editovat | editovat zdroj]Jednovstupové
[editovat | editovat zdroj]| A | ID | NOT | |
|---|---|---|---|
| 0 | 0 | 1 | |
| 1 | 1 | 0 |
ID – vrací stejnou hodnotu, jako měl vstup. Platí:
- A = ID(A)
- ID( 0 ) = 0
- ID( 1 ) = 1
NOT – vrací opačnou hodnotu, než měl vstup. Platí:
- NOT( 0 ) = 1, komplement
- NOT( 1 ) = 0, komplement
- A = NOT ( NOT(A) ), involuce
Dvouvstupové základní
[editovat | editovat zdroj]| A | B | OR | NOR | AND | NAND | XOR | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | ||||
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | ||||
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | ||||
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
OR – vrací součet hodnot vstupů. Platí:
- 0 + 1 = 1
- 1 + A = 1, agresivita, omezenost
- 0 + A = A, neutralita, omezenost
- A + A = A, idempotence
- A + B = B + A, komutativita
- A + NOT(A) = 1, komplement
AND – vrací součin hodnot vstupů. Platí:
- 0 * 1 = 0
- 1 * A = A, neutralita, omezenost
- 0 * A = 0, agresivita, omezenost
- A * A = A, idempotence
- A * B = B * A, komutativita
- A * NOT(A) = 0, komplement
Základní pravidla
[editovat | editovat zdroj]Párová pravidla platí i po vzájemné záměně "+" za "*", zde jsou tyto operace vzájemně symetrické.
- A*(A+B) = A
Ve výrazu (A+B) jeho část +B už nemůže rozšířit limitující A, proto je zbytečné.
- A+(A*B) = A
Dodatečné (A*B) nemůže zúžit šíři faktu A, proto je zbytečné.
Obě tato pravidla se dají na sebe vzájemně převést:
A*(A+B) = A*A + A*B = A + (A*B).
Z věty "Přijde Karel (A), nebo přijde se ženou(B)." vyplývá, že můžeme bez obav ohlásit: "Karel přijde!(A)".
Absorpce negace
[editovat | editovat zdroj]- ~A*(A+B)=~A×B
Odvození je poměrně snadné: ~A*(A+B) = ~A*A + ~A*B = ~A*B. Výraz B v závorce je rozšiřován o A, ale množina daná výrokem ~A*A je prázdná.
"Zítra přijde Karel nebo Monika. (A+B)" "Ne ne, pozor, Karel nepřijde. (~A)" "Aha, tak to přijde jen Monika. (~A*B)"
- A+(~A*B)=A+B
Odvození je zajímavé, protože Booleova algebra jinak roznásobovává závorky než běžná aritmetika:
A+(~A*B)=(A+~A)*(A+B)=(A+B)
Vedoucí přemýšlí: "Kdo zítra maže turbínu?" Na stole mu podřízení nechali dva lístečky: "Přijde Karel. (A)" a na druhém je napsáno: "Nepřijde Karel, přijde Jana. (~A*B)". Vedoucí teď neví, který lísteček je časově poslední, který platí, jestli tedy přijde nebo nepřijde Karel, pak si řekne: "To je jedno. Prostě jeden z nich přijde (A+B)."
- (A+B)+C = A+(B+C)
- (A*B)*C = A*(B*C)
- A*(B+C) = AB+AC
- A+(B*C) = (A+B)*(A+C), protože A+AB+AC+BC = A+A*(B+C)+BC = (A+A*D)+E = A+E, (substituce, pak absorpce závorky)
- A+0 = A
- A*1 = A
- A+A = A
- A*A = A
Logický součet a součin lze vyjádřit jeden pomocí druhého, při použití negace.
De Morganovy zákony tedy definují negace logického součtu a součinu:
Dvouvstupové odvozené
[editovat | editovat zdroj]NOR – negace součtu vstupů:
- A NOR B = NOT (A+B)
- A NOR B = NOT(A) * NOT(B)
NAND – negace součinu vstupů:
- A NAND B = NOT(A) + NOT(B)
- A NAND B = NOT (A*B)
NOR – Buď při splněném předpokladu A vrací B, nebo z nesplněného předpokladu vyplývá cokoli a vrací 1:
- A B = NOT(A) + B = NOT( A*NOT(B) )
EQ – porovnává shodnost hodnot všech vstupů:
- A B = A*B + NOT(A)*NOT(B) = (A+NOT(B)) * (NOT(A)+B)
XOR – porovnává unikátnost hodnoty každého vstupu:
- A XOR B = A*NOT(B) + B*NOT(A)
XOR versus NEQ
[editovat | editovat zdroj]Obecně jsou XOR a nonekvivalence rozdílné funkce, ale pro dvě dvouhodnotové proměnné dále platí:
- ( A XOR B ) = NOT( A B )
nebo jinak,
- XOR(A,B) = NOT(EQ(A,B))
