13.1. Booleova Algebra

13.1. Booleova Algebra
	Kapitola 13. Kombinační obvody

Odkazy:

Číslicové počítače. Jan Blatný, Karel Krištoufek, Zdeněk Pokorný, Ján Kolenička. SNTL 1982. Strana 62.
Booleova algebra na Wikipedii

Booleova algebra je množina B o alespoň svou prvcích (O a I), nad níž jsou definovány dvě binární (∧ a ∨) a jedna unární operace (¬), splňující následující axiómy. Nejdříve si ale povíme něco více o použitých pojmech.

Je zvykem označovat prvky množiny B znaky

První prvek: 0, O, L
Druhý prvek: 1, I, H

Označení číslicemi 0 a 1 je obvyklé v matematice a výpočetní technice. Označení písmeny L a H je obvyklé v číslicové technice. Použití písmene O místo 0 a písmene I místo 1 je z historických důvodů kdy se pro tyto číslice častou používali písmena abecedy jim podobná.

Dvě binární operace nazývané jako sčítání a násobení jsou pojmenovávány a značeny jako

logický součet, ∨, ∧, +, OR
logický součin, ∧, ⋅, ., ⋆, AND

Unární operace je nazývána negace a označována znaky ¬, -, /, !, NOT, nebo tak, že se nad výrazem udělá vodorovná čára přes celý výraz.

Axiomy

1. výsledkem všech tří operací ∨ , ∧ a ¬ jsou prvky množiny B
2.
3. komutativita: a∨b = b∨a, a∧b = b∧a
4. asociativita: a + (b ⋅ c) = (a + b) ⋅ (a + c), a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)
2a: ∃ prvek 0, pro který platí a + 0 = a
2b: ∃ prvek 1, pro který platí a ⋅ 1 = a
4a: a + (b ⋅ c) = (a + b) ⋅ (a + c)
4b: a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)
5: Jsou-li prvky 0,1 z axiómu 2 jediné, pak pro každý prvek a existuje prvek ¬a ∊ B, který splňuje rovnice a ⋅ ¬a = 0, a + ¬a = 1
6: Množina B obsahuje alespoň dva navzájem různé prvky a, b.
REMOVE: 1a: a + b ∊ B
REMOVE: 1b: a ⋅ b ∊ B
REMOVE: 3a: a + b = b + a
REMOVE: 3b: a ⋅ b = b ⋅ a

Věty:

1a: Prvek 0 v axiómu 2a je jediný.
1b: Prvek 1 v axiómu 2b je jediný.
2a: a + a = a
2b: a ⋅ a = a
3a: a + 1 = 1
3b: a ⋅ 0 = 0
4a: a + a ⋅ b = a
4b: a ⋅ (a + b) = a
5: ¬a je určen jednoznačně
6: ¬(¬a) = a
7a: ¬(a + b) = ¬a ⋅ ¬b
7b: ¬(a ⋅ b) = ¬a + ¬b
8a: (a + b) + c = a + (b + c)
8b: (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)
9a: a + ¬a ⋅ b = a + b
9b: a ⋅ (¬a + b) = a ⋅ b
10: (a + b) ⋅ (¬a + c) = a ⋅ c + ¬a ⋅ b
11a: ¬(a ⋅ c + b ⋅ ¬c) = ¬a ⋅ c + ¬b ⋅ ¬c
11b: ¬((a + c) ⋅ (b + ¬c)) = (¬a + c) ⋅ (¬b + ¬c)

Elementy: exist ∃, forall ∀, isin ∊, ni ∍, notin ∉, sdot ⋅

Chyba je v TeX souboru v řádku: {bold}}1a:\endSeq{}\endNode{} a + b \Character{8714} B\endSeq{}\endNode{}\endPar{}\endDisplayGroup{}\endNode{}\Node%

znak isin je podle ISOTECH unicode 02208_HEX, Popis znaku: "/in R: =set membership"

element &element; nefunguje

Tabulka 13.1. Pravdivostní tabulka některých binárních operací

a	b	a∧b	a∨b	¬a
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

Tabulka 13.2. Pravdivostní tabulka některých binárních operací

a	b	a∧b	a∨b	¬a
O	O	O	O	I
O	I	O	I	I
I	O	O	I	O
I	I	I	I	O