Förklara klasser

En förkomplett klass i teorin om booleska funktioner är en sluten klass av booleska funktioner som har följande egenskap: stängningen av föreningen av denna klass med valfri boolesk funktion som inte tillhör den genererar alla . Uppsättningen av förfullständiga klasser av booleska funktioner är uttömd av listan: $P_2$

Klassen av funktioner som bevarar konstanten 0: . $T_{0}$
$T_{0}=\left\{f(x_{1},\dots,x_{n})|f(0,\dots,0)=0\right\}$
Klassen av funktioner som bevarar konstanten 1: . $T_{1}$
$T_{1}=\vänster\{f(x_{1},\dots ,x_{n})|f(1,\dots ,1)=1\right\}$
Klassen av självdubbla funktioner : . $S$
$S=\left\{f(x_{1},\dots,x_{n})|f(\overline {x_{1}},\dots ,\overline {x_{n}})=\overline {f (x_{1},\dots,x_{n})}\right\}$
Klass av monotona funktioner : . $M$
$M=\left\{f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Högerpil f(a_{1},\dots ,a_ {n})\leq f(b_{1},\dots ,b_{n})\right\}$
Klassen av linjära funktioner — representeras av Zhegalkinpolynomet av första graden: . $L$
$L=\vänster\{f(x_{1},\dots ,x_{n})|f(x_{1},\dots ,x_{n})=a_{0}\oplus a_{1}x_{ 1}\oplus \dots \oplus a_{n}x_{n},a_{i}\in \{0,1\}\right\}$

Man talar också om förfullständigheten av en sluten klass i en annan. En klass A är besatt i klass B om stängningen av klass A med någon funktion som tillhör B men som inte tillhör A genererar klass B. Till exempel är klassen besatt i klasserna och . $M\cap T_{0}$ $T_{0}$ $M$

I flervärdslogik definieras förfullständiga klasser på liknande sätt som slutna klasser som har egenskapen att stängningen av föreningen av denna klass med någon funktion från som inte tillhör den genererar alla . Men i fallet med k>2 finns det för närvarande ingen allmän beskrivning av strukturen för förfullständiga klasser, i motsats till tvåvärdig logik. $P_{k}$ $P_{k}$

Litteratur

Yablonsky SV Introduktion till diskret matematik. — M.: Nauka. — 1986