Booleova logika

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
AIDNOT
001
110

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í:

Dvouvstupové základní

dva argumenty
ABORNORANDNANDXOR
000101110
011001101
101001001
111010110

OR – vrací součet hodnot vstupů. Platí:

Konjunkce

AND – vrací součin hodnot vstupů. Platí:

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:

16 booleovských funkcí dvou proměnných

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

Externí odkazy

Média použitá na této stránce

B functies 2var versie04 eng.png
Autor: Bob.v.R, Licence: CC BY-SA 4.0
Boolean functions of two variables - Eng - version04
Logical connectives Hasse diagram.svg
The sixteen logical connectives ordered in a Hasse diagram. They are represented by: The nodes are connected like the vertices of a 4 dimensional cube. The light blue edges form a rhombic dodecahedron - the convex hull of the tesseract's vertex-first shadow in 3 dimensions.