Booleova logika

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í

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é

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, 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

(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}}$

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

Externí odkazy

Booleova logika v České terminologické databázi knihovnictví a informační vědy (TDKIV)