Booleova logika

16 booleovských funkcí dvou proměnných Booleova logika se zabývá logickými operacemi konjunkce (značená též "*", AND, "&" nebo \wedge), disjunkce (značena též "+", OR, "|", "." nebo \vee) 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é

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í

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ří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ázná.

"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. +more (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). ".

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. * A + B = \overline{\overline{A} \cdot \overline{B}} * A \cdot B = \overline{\overline{A} + \overline{B}}

De Morganovy zákony tedy definují negace logického součtu a součinu: * \overline{A + B}=\overline{A} \cdot \overline{B} * \overline{A \cdot B}=\overline{A} + \overline{B}

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 \Rightarrow B = NOT(A) + B = NOT( A*NOT(B) )

Ekvivalence

EQ - porovnává shodnost hodnot všech vstupů: * A \Leftrightarrow 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 \Leftrightarrow B ) nebo jinak, * XOR(A,B) = NOT(EQ(A,B))

Související články

Karnaughova mapa * Vytýkání

Externí odkazy

Kategorie:Logika