Booleovské funkce, funkčně úplné systémy

Booleovské funkce

• Booleovská funkce s $n$ argumenty ($n$-ární booleovská funkce) je libovolné zobrazení, které uspořádané $n$-tici hodnot $0$ nebo $1$ přiřadí hodnotu $0$ nebo $1$.

• Každou booleovskou funkci $f$ s $n$ argumenty lze zapsat v tabulce

• Předpokládejme, že argumenty funkce $f$ označíme $x_1,...,x_n$, pak píšeme také $f(x_1,...,x_n)$

• Existuje právě $2^{2^n}$ booleovských funkcí s $n$ argumenty

Všechny booleovské funkce jedné proměnné

x₁| f₁  f₂  f₃  f₄ 
------------------
0 | 0   0   1   1
1 | 0   1   0   1

• Vidíme, že $f_3$ je pravdivostní funkce spojky negace, tj. $f_3(0)=1$ a $f_3(1)=0$.

Všechny booleovské funkce dvou proměnných

x₁  x₂ | f₁  f₂  f₃  f₄  f₅  f₆  f₇  f₈  f₉  f₁₀ f₁₁ f₁₂ f₁₃ f₁₄ f₁₅ f₁₆
--------------------------------------------------------------------------
1   1  | 1   1   1   1   1   1   1   1   0    0   0   0   0   0   0   0                            
1   0  | 1   1   1   1   0   0   0   0   1    1   1   1   0   0   0   0                           
0   1  | 1   1   0   0   1   1   0   0   1    1   0   0   1   1   0   0                      
0   0  | 1   0   1   0   1   0   1   0   1    0   1   0   1   0   1   0                             

• Vidíme, že
  • $f_2$ je pravdivostní funkce spojky disjunkce,
  • $f_5$ je pravidvostní funkce spojky implikace,
  • $f_7$ je pravdivostní funkce spojky ekvivalence,
  • $f_8$ je pravidovostní funkce spojky konjunkce.

Funkčně úplný systém

• Množina booleovských funkcí $\{f_1,...,f_k\}$ je funkčně úplná, pokud každou booleovskou funkci $f:\{0,1{\}}^n\to \{0,1\}$ lze vyjádřit jako složení některých funkcí z $\{f_1,...,f_k\}$.

  • Jinými slovy, pokud máme sadu logických operací, a pomocí této sady můžeme sestavit jakýkoli možný logický výraz, je tato sada považována za funkčně úplnou.

• Řekneme, že množina výrokových spojek je úplná (tvoří úplný systém spojek), jestli je funkčně úplná množina jim odpovídajících booleovských funkcí.

• Každý úplný minimální systém spojek VL nazveme bází.

• Funkčně úplné množiny logických funkcí: $\{\neg ,\wedge \},\{\neg ,\vee \},\{\neg ,\to \},\{\uparrow \},\{\downarrow \}$

  Důkaz

  • Pomocí $\uparrow$ (resp. $\downarrow$) lze vyjádřit $\neg ,\wedge ,\vee$: Zřejmě $(a\uparrow b)\leftrightarrow \neg (a\wedge b).$ Odsud:
    1. $\neg a\leftrightarrow \neg (a\wedge a)\leftrightarrow (a\uparrow a);$
    2. $(a\wedge b)\leftrightarrow \neg \neg (a\wedge b)\leftrightarrow \neg (a\uparrow b)\leftrightarrow ((a\uparrow b)\uparrow (a\uparrow b));$
    3. $(a\vee b)\leftrightarrow \neg \neg (a\vee b)\leftrightarrow \neg (\neg a\wedge \neg b)\leftrightarrow (\neg a\uparrow \neg b)\leftrightarrow ((a\uparrow a)\uparrow (b\uparrow b)).$

  Podobně pro $\downarrow$.

Navíc z internetu

• Funkčně úplné systémy se používají pro:
  1. Návrh digitálních obvovů
     • V návrhu digitálních obvodů je efektivní používat omezený počet základních operací.
     • Funkčně úplné systémy nám umožní realizovat všechny potřebné logické funkce pouze s těmito operacemi.
  2. Teoretickou informatiku
     • Funkčně úplné systémy jsou důležité při studiu výpočetní složitosti a logických teorií. Mohou být použity k analýze, jak složité je realizovat určité funkce pomocí omezených prostředků.
  3. Optimalizaci a minimalizaci logických obvodů
     • S použitím funkčně úplných systémů lze logické obvody optimalizovat a minimalizovat tím, že se redukuje počet různých typů logických operací a brán potřebných k realizaci složitějších operací.

Navigace

Předchozí: Výroková logika, formule, pravdivost, vyplývání Následující: Úplné konjunktivní a disjunktivní normální formy Celý okruh: Výroková logika, formule, pravdivost, vyplývání