Logické funkce n-proměnných
- Logická funkce f:\{0,1\}^n \to \{0,1\} přiřazuje každé kombinaci (x_1,\dots,x_n) právě jednu výstupní hodnotu 0/1.
- Arita (stupeň) = počet vstupních proměnných n.
- Počet funkcí
- Pro n vstupů existuje 2^n různých vstupních kombinací (vektorů)
- Každé kombinaci přiřadíme výstup 0/1 nezávisle
- Laicky: Pro každou vstupní kombinaci vytvoříme všechny možné výstupní kombinace
- Celkem 2^{\,2^n} funkcí pro n proměnných, např.:
- pro 1 vstup existuje 2^{2^1}=2^2=4 funkcí,
- pro 2 vstupy existuje 2^{2^2}=2^4=16 funkcí,
- pro 3 vstupy existuje 2^{2^3}=2^8=256 funkcí.
- Indexové značení \mathrm{F}_k odpovídá pořadí funkce v tabulce.
- Toto číslo se shoduje s binární hodnotou čísla vzniklého spojením výstupních hodnot ve sloupcích
(např. \{0, 1, 1, 0\} = 0110_{(2)}=6)
- Toto číslo se shoduje s binární hodnotou čísla vzniklého spojením výstupních hodnot ve sloupcích
Poznámky k tabulkám:
Normální forma je matematický zápis v minimální podobě jen z operátorů logického součtu (OR) a součinu (AND). Zde konkrétně se jedná o disjunktní normální formu, kterou budeme probírat později.
Zvýrazněné řádky označují nejpoužívanější funkce pro návrh logických obvodů, které existují i ve formě logických členů (součástek):
- Unární
- NOT = „opačná hodnota vstupu“
- Binární
- AND = „oba vstupy zároveň“
- OR = „alespoň jeden vstup“
- XOR = „vstupy se nerovnají“, „přesně jeden vstup“, „lichý počet vstupů“
- XNOR = „vstupy se rovnají“, „sudý počet vstupů“
- NAND = „maximálně jeden vstup“, „nejsou oba vstupy zároveň“
- NOR = „žádný vstup“
Funkce jedné proměnné – unární (n=1)
Index | Vstup a | Operátor | Normální forma | Název | |
|---|---|---|---|---|---|
| 0 | 1 | ||||
| \mathrm{F}_{0} | 0 | 0 | 0 | 0 | nulová konstanta |
| \mathrm{F}_{1} | 0 | 1 | a | a | identita |
| \mathrm{F}_{2} | 1 | 0 | \lnot a | \overline{a} | negace / NOT |
| \mathrm{F}_{3} | 1 | 1 | 1 | 1 | jednotková konstanta |
Funkce dvou proměnných – binární (n=2)
| Index | Vstupní hodnoty | Operátor | Normální forma | Název | ||||
|---|---|---|---|---|---|---|---|---|
a b |
0 0 |
0 1 |
1 0 |
1 1 |
||||
| \mathrm{F}_{0} | 0 | 0 | 0 | 0 | 0 | 0 | nulová konstanta | |
| \mathrm{F}_{1} | 0 | 0 | 0 | 1 | a \land b | a\cdot b | konjunkce / logický součin / AND | |
| \mathrm{F}_{2} | 0 | 0 | 1 | 0 | a \nRightarrow b | a\cdot \overline{b} | přímá inhibice | |
| \mathrm{F}_{3} | 0 | 0 | 1 | 1 | a | a | projekce na a / identita a | |
| \mathrm{F}_{4} | 0 | 1 | 0 | 0 | b \nRightarrow a | \overline{a}\cdot b | zpětná inhibice | |
| \mathrm{F}_{5} | 0 | 1 | 0 | 1 | b | b | projekce na b / identita b | |
| \mathrm{F}_{6} | 0 | 1 | 1 | 0 | a \oplus b | \overline{a}b+a\overline{b} | neekvivalence / exkluzivní součet / XOR | |
| \mathrm{F}_{7} | 0 | 1 | 1 | 1 | a \lor b | a+b | disjunkce / logický součet / OR | |
| \mathrm{F}_{8} | 1 | 0 | 0 | 0 | a \downarrow b | \overline{a+b} | NOR / Piercova funkce | |
| \mathrm{F}_{9} | 1 | 0 | 0 | 1 | a \Leftrightarrow b | \overline{a}\,\overline{b}+ab | ekvivalence / XNOR | |
| \mathrm{F}_{10} | 1 | 0 | 1 | 0 | \lnot a | \overline{a} | negace a | |
| \mathrm{F}_{11} | 1 | 0 | 1 | 1 | b \Rightarrow a | \overline{b}+a | zpětná implikace | |
| \mathrm{F}_{12} | 1 | 1 | 0 | 0 | \lnot b | \overline{b} | negace b | |
| \mathrm{F}_{13} | 1 | 1 | 0 | 1 | a \Rightarrow b | \overline{a}+b | přímá implikace | |
| \mathrm{F}_{14} | 1 | 1 | 1 | 0 | a \uparrow b | \overline{a \cdot b} | NAND / Shefferova funkce | |
| \mathrm{F}_{15} | 1 | 1 | 1 | 1 | 1 | 1 | jednotková konstanta | |
Funkce tří proměnných – ternární (n=3)
Funkcí tří proměnných existuje celkem 256. Taková pravdivostní tabulka by byla značně nepraktická a tak je výhodné ji nějakým způsobem zjednodušit. K tomu lze využít zákonů booleovy algebry (které budeme probírat zanedlouho).
Myšlenka je snadná – namísto funkce tří proměnných f(x, y, z) můžeme chytře rozdělit situaci na dva případy:
- x = 0 – vytvoříme tabulku funkcí f(0, y, z)
- x = 1– vytvoříme tabulku funkcí f(1, y, z)
V obou případech nám zůstanou dvě proměnné tak můžeme situaci vyřešit pomocí funkcí dvou proměnných, kterých je jen 16.
Dostaneme tedy dvě tabulky po 16 funkcích – celkem 32 funkcí. Matematicky tyto případy spojíme následovně:
Zdůvodnění: Násobení je spojka AND – musí tedy platit současně správná hodnota x a výsledek funkce dvou proměnných. Jednotlivé případy sečteme (spojka OR) – stačí aby platil jeden z případů. Zamyslíme-li se nad tím, nemůžou platit oba současně, protože x nemůže být současně 0 a 1.
Tento postup lze použít i pro funkce více proměnných.