Suorita luokat valmiiksi

Esitäydellinen luokka Boolen funktioiden teoriassa on Boolen funktioiden suljettu luokka , jolla on seuraava ominaisuus: tämän luokan liiton sulkeminen minkä tahansa siihen kuulumattoman Boolen funktion kanssa generoi kaikki . Esitäydellisten Boolen funktioiden luokkien joukko on käytetty loppuun luettelossa: $P_2$

Funktioiden luokka , jotka säilyttävät vakion 0: . $T_{0}$
$T_{0}=\vasen\{f(x_{1},\pisteet ,x_{n})|f(0,\pisteet ,0)=0\oikea\}$
Funktioiden luokka , jotka säilyttävät vakion 1: . $T_{1}$
$T_{1}=\vasen\{f(x_{1},\pisteet ,x_{n})|f(1,\pisteet ,1)=1\oikea\}$
Itsenäisten kaksoistoimintojen luokka : . $S$
$S=\left\{f(x_{1},\dots ,x_{n})|f(\overline {x_{1}},\dots ,\overline {x_{n}})=\overline {f (x_{1},\pisteet ,x_{n})}\oikea\}$
Monotonisten toimintojen luokka : . $M$
$M=\left\{f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_ {n})\leq f(b_{1},\dots ,b_{n})\right\}$
Lineaaristen funktioiden luokka , jota edustaa ensimmäisen asteen Zhegalkin-polynomi : . $L$
$L=\left\{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\}$

Puhutaan myös yhden suljetun luokan esitäydellisyydestä toisessa. Luokka A on prepositoitu luokassa B, jos luokan A sulkeminen millä tahansa funktiolla, joka kuuluu B:hen mutta ei kuulu A:han, tuottaa luokan B. Esimerkiksi luokka on prepositoitu luokissa ja . $M\cap T_{0}$ $T_{0}$ $M$

Moniarvologiikassa esitäydelliset luokat määritellään samalla tavalla suljetuiksi luokiksi, joilla on ominaisuus , että tämän luokan liiton sulkeminen minkään funktion kanssa, joka ei kuulu siihen, tuottaa kaikki . Mutta k>2:n tapauksessa esitäydellisten luokkien rakenteesta ei tällä hetkellä ole yleistä kuvausta, toisin kuin kaksiarvoisessa logiikassa. $P_{k}$ $P_{k}$

Kirjallisuus

Yablonsky SV Johdatus diskreettiin matematiikkaan. - M.: Nauka. – 1986