Booleova logika
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Logical_connectives_Hasse_diagram.svg/400px-Logical_connectives_Hasse_diagram.svg.png)
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í
Jednovstupové
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í
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
Konjunkce
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
Párová pravidla platí i po vzájemné záměně "+" za "*", zde jsou tyto operace vzájemně symetrické.
Absorpce
- 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říjde Karel (A), nebo příjde se ženou(B)." vyplývá, že můžeme bez obav ohlásit: "Karel příjde!(A)".
Absorpce negace
- ~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říjde Karel nebo Monika. (A+B)" "Ne ne, pozor, Karel nepříjde. (~A)" "Aha, tak to příjde 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říjde Karel. (A)" a na druhém je napsáno: "Nepříjde Karel, příjde Jana. (~A*B)". Vedoucí teď neví, který lísteček je časově poslední, který platí, jestli tedy příjde nebo nepříjde 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)
Neutrálnost 0 a 1
- 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:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/B_functies_2var_versie04_eng.png/400px-B_functies_2var_versie04_eng.png)
Dvouvstupové odvozené
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
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))
Související články
- Karnaughova mapa
- Vytýkání
Externí odkazy
Média použitá na této stránce
Autor: Bob.v.R, Licence: CC BY-SA 4.0
Boolean functions of two variables - Eng - version04
The sixteen logical connectives ordered in a Hasse diagram. They are represented by:
- logical formulas
- the 16 elements of V4 = P^4({})
- Venn diagrams