Algebra Boole'a
Fundamentem teoretycznym dla techniki cyfrowej jest algebra Boole'a. Jej podstawy przedstawił matematyk angielski George Boole w opracowaniu pt. "An Investigation of the Laws of Thought" z 1854 roku. Dzieło to przeleżało na półkach ponad pół wieku, zanim znalazło zastosowanie w technice do analizy i syntezy układów przełączających. Jest to nie pierwszy przykład w historii nauki, że dopiero po wielu latach niektóre teorie abstrakcyjne stają się teoriami o wyraźnie zaznaczonym aplikacyjnym charakterze. Teoria układów logicznych wykorzystuje również pewne wyniki osiągnięte w XIX wieku w dziedzinie logiki teoretycznej przez takich matematyków jak de'Morgan czy też Polak Łukasiewicz, który jest twórcą znanego i stosowanego do dziś sposobu zapisu algorytmu, określanego jako tzw. odwrotna notacja polska.
Algebrą Boole'a B = <B, +, ∗, ¬, 0, 1> nazywamy zbiór B zawierający przynajmniej dwa elementy i spełniający następujące aksjomaty (dla x, y, z ∈B):
A1: x + 0 = x A2: x ∗ 1 = x element neutralny
A3: x + (¬x) = 1 A4: x ∗ (¬x) = 0 uzupełnienie
A5: x + y = y + x A6: x ∗ y = y ∗ x przemienność
A7: (x + y) + z = x + (y + z) łączność
A8: (x ∗ y) ∗ z = x ∗ (y ∗ z) łączność
A9: x ∗ (y + z) = x ∗ y + x ∗ z rozdzielność
A10: x + y ∗ z = (x + y) ∗ (x + z) rozdzielność
Twierdzenia
T1: x + x = x T2: x ∗ x = x idempotentność
T3: x + 1 = 1 T4: x ∗ 0 = 0 własności „zera” i „jedynki”
T5: ¬(x + y) = (¬x) ∗ (¬y) dualność (prawa d'Morgana)
T6: ¬(x ∗ y) = (¬x) + (¬y) dualność (prawa d'Morgana)
T7: x + (x ∗ y) = x T8 x ∗ (x + y) = x absorpcja
T9: ¬(¬x) = x inwolucja
Przykłady
B = <B, ∨, ∧, ¬, 0, 1>, gdzie B = {0, 1}
B = <B, ∨, ∧, ¬, F, T>, gdzie B = {T, F}
B = <B, ∨, ∧, ¬, 0, 1>, gdzie B = {Fn} oraz Fn - zbiór funkcji boolowskich