Booleova logika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Booleova logika se zabývá logickými operacemi "+", "*" a "NOT()" na množině hodnot { 0, 1 }. Jejím rozšířením je pak Booleova algebra.

Definice logických funkcí[editovat | editovat zdroj]

jeden argument
A ID NOT
0 0 1
1 1 0
dva argumenty
A B OR NOR AND NAND \Rightarrow \Leftrightarrow 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

Jednovstupové[editovat | editovat zdroj]

Identita[editovat | editovat zdroj]

ID – vrací stejnou hodnotu, jako měl vstup. Platí:

  • A = ID(A)
  • ID( 0 ) = 0
  • ID( 1 ) = 1

Negace[editovat | editovat zdroj]

NOT – vrací opačnou hodnotu, než měl vstup. Platí:

Dvouvstupové základní[editovat | editovat zdroj]

Disjunkce[editovat | editovat zdroj]

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

Konjunkce[editovat | editovat zdroj]

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

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é.

Absorbce[editovat | editovat zdroj]

  • A*(A+B) = A, protože (A+B) jen rozšiřuje už platný a užší fakt A, takže zbytečné.
  • A+(A*B) = A, protože (A*B) jen zužuje už platný a širší fakt A, takže zbytečné.

Asociativita[editovat | editovat zdroj]

  • (A+B)+C = A+(B+C)
  • (A*B)*C = A*(B*C)

Distributivita[editovat | editovat zdroj]

  • 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 absorbce závorky)

Neutrálnost 0 a 1[editovat | editovat zdroj]

  • A+0 = A
  • A*1 = A

Idempotence[editovat | editovat zdroj]

  • A+A = A
  • A*A = A

De Morganovy zákony[editovat | editovat zdroj]

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 Morganových 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}

Dvouvstupové odvozené[editovat | editovat zdroj]

NOR[editovat | editovat zdroj]

NOR – negace součtu vstupů:

  • A NOR B = NOT (A+B)
  • A NOR B = NOT(A) * NOT(B)

NAND[editovat | editovat zdroj]

NAND – negace součinu vstupů:

  • A NAND B = NOT(A) + NOT(B)
  • A NAND B = NOT (A*B)

Implikace[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 \Leftrightarrow B )

nebo jinak,

  • XOR(A,B) = NOT(EQ(A,B))

Související články[editovat | editovat zdroj]