náhled|vpravo|400px|16 booleovských funkcí dvou proměnných 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é + jeden argument A ID NOT 0 0 1 1 1 0
Identita ID – vrací stejnou hodnotu, jako měl vstup. Platí: A = ID(A) ID( 0 ) = 0 ID( 1 ) = 1
Negace 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í + dva argumenty 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
Disjunkce 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řijde Karel (A), nebo přijde se ženou(B)." vyplývá, že můžeme bez obav ohlásit: "Karel přijde!(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ř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)."
Asociativita (A+B)+C = A+(B+C) (A*B)*C = A*(B*C)
Distributivita 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
Idempotence A+A = A A*A = A
De Morganovy zákony 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:
náhled|400px|16 booleovských funkcí dvou proměnných
Dvouvstupové odvozené
NOR NOR – negace součtu vstupů: A NOR B = NOT (A+B) A NOR B = NOT(A) * NOT(B)
NAND NAND – negace součinu vstupů: A NAND B = NOT(A) + NOT(B) A NAND B = NOT (A*B)
Implikace 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) )
Ekvivalence EQ – porovnává shodnost hodnot všech vstupů: A B = A*B + NOT(A)*NOT(B) = (A+NOT(B)) * (NOT(A)+B)
Exkluzivní disjunkce 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
Kategorie:Logika