Uzavřené třídy booleovských funkcí

Uzavřená třída v teorii booleovských funkcí je množina funkcí algebry logiky , jejíž uzavření s ohledem na operaci superpozice se shoduje se sebou samým: . Jinými slovy, jakákoli funkce, kterou lze vyjádřit vzorcem pomocí množinových funkcí , je opět zahrnuta do stejné množiny. $P$ $[P] = P$ $P$

V roce 1941 předložil Emil Post úplný popis systému uzavřených tříd, nazývaného také Postova mřížka .

Vlastnosti uzavření funkce s proměnnými

Libovolná množina je podmnožinou svého uzávěru: . $A\subseteq [A]$
Podmnožina uzávěru je podmnožinou uzávěru: . Je třeba poznamenat, že přísné vkládání sad znamená pouze nepřísné vkládání jejich uzávěrů: . $A\subseteq B\Šipka doprava [A]\subseteq [B]$
$A\podmnožina B\šipka doprava [A]\podmnožina [B]$
Vícenásobné použití operace uzavření je ekvivalentní jedné aplikaci: . $[[A]]=[A]$

Příklady uzavřených tříd

Množina všech možných booleovských funkcí je uzavřena. $P_2$

Zvláštní význam pro teorii booleovských funkcí mají následující uzavřené třídy, nazývané předkompletní třídy :

Třída funkcí, které zachovávají konstantu 0: . $T_{0}$
$T_{0}=\left\{f(x_{1},\tečky ,x_{n})|f(0,\tečky ,0)=0\vpravo\}$
Třída funkcí, které zachovávají konstantu 1: . $T_{1}$
$T_{1}=\left\{f(x_{1},\tečky ,x_{n})|f(1,\tečky,1)=1\vpravo\}$
Třída sebeduálních funkcí : . $S$
$S=\left\{f(x_{1},\tečky ,x_{n})|f(\overline {x_{1}},\tečky ,\overline {x_{n}})=\overline {f (x_{1},\tečky ,x_{n})}\vpravo\}$
Třída monotónních booleovských funkcí : . $M$
$M=\left\{f(x_{1},\tečky ,x_{n})|\forall i(a_{i}\leq b_{i})\Šipka doprava f(a_{1},\tečky ,a_ {n})\leq f(b_{1},\tečky ,b_{n})\vpravo\}$
Třída lineární booleovské funkce : . $L$
$L=\left\{f(x_{1},\tečky ,x_{n})|f(x_{1},\tečky ,x_{n})=a_{0}\oplus a_{1}x_{ 1}\oplus \tečky \oplus a_{n}x_{n},a_{i}\v \{0,1\}\vpravo\}$

Jakákoli uzavřená třída booleovských funkcí jiná než , je zcela obsažena v alespoň jedné z pěti předkompletních tříd . $P_2$

Další důležité uzavřené třídy jsou:

Třída spojek K, která je uzávěrem množiny . Je to soubor funkcí formuláře . $\{\wedge ,0,1\}$ $c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})$
Disjunkce třídy D, která je uzávěrem množiny . Je to soubor funkcí formuláře . $\{\vee ,0,1\}$ $c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})$
Třída funkcí jedné proměnné U obsahující pouze konstanty, negaci a selektor (funkce rovna jednomu z jejích argumentů na všech množinách jejich hodnot).
Třída funkcí (m je libovolné přirozené číslo větší než jedna) splňující následující podmínku: pro libovolných m množin, na kterých funkce nabývá nulové hodnoty, existuje proměnná, která rovněž nabývá nulové hodnoty na všech těchto množinách. $O^{m}$
Třída funkcí, pro které je splněna podmínka , kde je jedna z funkčních proměnných. $O^{\infty }$ $f(x_{1},\ldots ,x_{n})\geq x_{i}$ $x_{i}$
Třída funkcí (m je libovolné přirozené číslo větší než jedna) splňující následující podmínku: pro libovolných m množin, na kterých funkce nabývá jednotkové hodnoty, existuje proměnná, která také nabývá jednotkovou hodnotu na všech těchto množinách. $já^{m}$
Třída funkcí, pro které je splněna podmínka , kde je jedna z funkčních proměnných. $I^{\infty }$ $f(x_{1},\ldots ,x_{n})\leq x_{i}$ $x_{i}$

V roce 1941 Emil Post ukázal, že jakákoli uzavřená třída booleovských funkcí je průsečíkem konečného počtu výše popsaných tříd, čímž poskytl úplný popis struktury uzavřených tříd dvouhodnotové logiky. Post také stanovil, že jakákoli uzavřená třída může být generována na konečné bázi.

Některé vlastnosti uzavřených tříd

Neprázdný průnik uzavřených tříd je opět uzavřená třída.
Spojení uzavřených tříd nemusí být uzavřenou třídou.
Uzavřená třída booleovských funkcí obsahující nejen konstanty nutně obsahuje identickou funkci.
Doplněk uzavřené třídy booleovských funkcí k množině všech booleovských funkcí není uzavřená třída. $P_2$

Kompletní systémy funkcí

Soubor funkcí algebry logiky se nazývá úplný systém, pokud se uzávěr této množiny shoduje s množinou všech funkcí. (Zejména pro dvouhodnotovou logiku .) Jinými slovy, mělo by být možné vyjádřit jakoukoli funkci algebry logiky vzorcem pomocí množinových funkcí . $A$ $[A]=P_{2}$ $A$

Postovo kritérium formuluje nezbytnou a postačující podmínku úplnosti systému booleovských funkcí:
Systém booleovských funkcí je úplný právě tehdy, není-li zcela obsažen v žádné z tříd , , , , . $T_{0}$ $T_{1}$ $S$ $M$ $L$
Zejména, pokud funkce není zahrnuta v žádné z Postových tříd, tvoří sama o sobě kompletní systém. Příkladem je Schaefferova funkce (negace konjunkce ).

Následující kompletní systémy booleovských funkcí jsou široce známé:

$\left\{\land ,\lor ,\neg \right\}$ ( konjunkce , disjunkce , negace ) ;
$\left\{\land ,\oplus ,1\right\}$ (konjunkce, modulo 2 sčítání , konstanta 1);
$\left\{\land ,\neg \right\}$ ( konjunkce , negace );
$\left\{\lor ,\neg \right\}$ ( disjunkce , negace );
$\left\{\downarrow \right\}$ ( propíchněte šíp );
$\left\{|\right\}$ ( Schefferův zdvih ).

První systém se používá například k reprezentaci funkcí ve formě disjunktivních a konjunktivních normálních forem , druhý se používá k jejich reprezentaci ve formě Zhegalkinových polynomů .

Méně známé další kompletní systémy booleovských funkcí:

$\left\{\rightarrow ,\neg \right\}$ ( implikace , negace );
$\left\{\rightarrow ,\oplus \right\}$ ( implikace , sčítání modulo 2 );
$\left\{\rightarrow ,0\right\}$ ( implikace , konstanta 0);

Kompletní systém funkcí se nazývá základ , pokud přestane být úplný, když je z něj vyloučen jakýkoli prvek. První z výše zmíněných úplných systémů není základem, protože podle de Morganových zákonů lze ze systému vyloučit disjunkci nebo konjunkci a obnovit pomocí zbývajících dvou funkcí. Druhý systém je základem – pro úplnost jsou nezbytné všechny jeho tři prvky. Maximální možný počet booleovských funkcí v základu je 4.

Někdy se mluví o systému funkcí, který je v nějaké uzavřené třídě úplný, a tedy o základu této třídy. Systém lze například nazvat základem třídy lineárních funkcí. $\left\{\oplus ,1\right\}$

Poznámky

Literatura

Yablonsky SV Úvod do diskrétní matematiky. — M .: Nauka, 1986.
Marchenkov S. S. Uzavřené třídy booleovských funkcí. — M .: Fizmatlit, 2000.
Gavrilov G. P., Sapozhenko A. A. Sbírka problémů v diskrétní matematice. — M.: Nauka. — 1969
Alekseev V. B. Diskrétní matematika (průběh přednášek, II semestr). Comp. A. D. Pospelov
Akhmetova N.A., Usmanova Z.M. Diskrétní matematika, funkce algebry logiky.