Suljetut Boolen funktioluokat

Suljettu luokka Boolen funktioiden teoriassa on joukko logiikan algebran funktioita , joiden sulkeutuminen superpositioon nähden osuu yhteen itsensä kanssa: . Toisin sanoen mikä tahansa funktio, joka voidaan ilmaista kaavalla joukkofunktioita käyttämällä, sisältyy jälleen samaan joukkoon. $P$ $[P]=P$ $P$

Vuonna 1941 Emil Post esitti täydellisen kuvauksen suljetusta luokkajärjestelmästä, jota kutsutaan myös Postihilaksi .

Toiminnon sulkemisominaisuudet muuttujilla

Mikä tahansa joukko on sen sulkemisen osajoukko : . $A\subseteq [A]$
Osajoukon sulkeminen on sulkemisen osajoukko: . On huomattava, että sarjojen tiukka upottaminen tarkoittaa vain niiden sulkujen ei-tiukkaa upottamista: . $A\subseteq B\Oikeanuoli [A]\subseteq [B]$
$A\osajoukko B\oikeanuoli [A]\alaryhmä [B]$
Useita sulkemisoperaatioita vastaa yhtä sovellusta: . $[[A]]=[A]$

Esimerkkejä suljetuista luokista

Kaikkien mahdollisten Boolen funktioiden joukko on suljettu. $P_2$

Erityisen tärkeitä Boolen funktioiden teorialle ovat seuraavat suljetut luokat, joita kutsutaan esitäydellisiksi luokiksi :

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\}$
Yksiäänisten Boolen funktioiden 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\}$
Lineaarinen boolen funktioluokka : . $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\}$

Mikä tahansa suljettu Boolen funktioiden luokka, lukuun ottamatta , sisältyy kokonaan vähintään yhteen viidestä esitäydellisestä luokasta . $P_2$

Muita tärkeitä suljettuja kursseja ovat:

Konjunktioiden luokka K, joka on joukon sulkeminen . Se on joukko lomakkeen toimintoja . $\{\kiila ,0,1\}$ $c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})$
Disjunktioluokka D, joka on joukon sulkeminen . Se on joukko lomakkeen toimintoja . $\{\vee ,0,1\}$ $c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})$
Yhden muuttujan U funktioiden luokka, joka sisältää vain vakiot, negatiivisen ja valitsimen (funktio, joka on yhtä suuri kuin jokin sen argumenteista kaikissa niiden arvojoukoissa).
Funktioiden luokka (m on mikä tahansa luonnollinen luku, joka on suurempi kuin yksi), joka täyttää seuraavan ehdon: jokaiselle m joukolle, jossa funktio saa nolla-arvon, on muuttuja, joka saa myös nolla-arvon kaikissa näissä joukoissa. $O^{m}$
Funktioiden luokka , jolle ehto täyttyy , jossa on yksi funktion muuttujista. $O^{\infty }$ $f(x_{1},\ldots ,x_{n})\geq x_{i}$ $x_{i}$
Funktioiden luokka (m on mikä tahansa luonnollinen luku, joka on suurempi kuin yksi), joka täyttää seuraavan ehdon: jokaiselle m joukolle, jossa funktio ottaa yksikköarvon, on muuttuja, joka ottaa myös yksikköarvon kaikista näistä joukoista. $minä^{m}$
Funktioiden luokka , jolle ehto täyttyy , jossa on yksi funktion muuttujista. $minä^{\infty }$ $f(x_{1},\ldots ,x_{n})\leq x_{i}$ $x_{i}$

Vuonna 1941 Emil Post osoitti, että mikä tahansa suljettu Boolen funktioiden luokka on rajallisen joukon edellä kuvattujen luokkien leikkauspiste, mikä antaa täydellisen kuvauksen kaksiarvoisen logiikan suljettujen luokkien rakenteesta. Post totesi myös, että mikä tahansa suljettu luokka voidaan generoida äärellisellä perusteella.

Jotkut suljettujen luokkien ominaisuudet

Suljettujen luokkien ei- tyhjä leikkauspiste on jälleen suljettu luokka.
Suljettujen luokkien liitto ei voi olla suljettu luokka.
Boolen funktioiden suljettu luokka, joka ei sisällä vain vakioita, sisältää välttämättä identtisen funktion.
Boolen funktioiden suljetun luokan komplementti kaikkien Boolen funktioiden joukkoon ei ole suljettu luokka. $P_2$

Täydelliset toimintojärjestelmät

Joukkoa logiikan algebran funktioita kutsutaan täydelliseksi järjestelmäksi, jos tämän joukon sulkeminen osuu yhteen kaikkien funktioiden joukon kanssa. (Erityisesti kaksiarvoiselle logiikalle .) Toisin sanoen mikä tahansa logiikan algebran funktio pitäisi olla mahdollista ilmaista kaavalla käyttäen joukkofunktioita . $A$ $[A]=P_{2}$ $A$

Postin kriteeri muodostaa välttämättömän ja riittävän ehdon Boolen funktiojärjestelmän täydellisyydelle:
Boolen funktiojärjestelmä on täydellinen silloin ja vain, jos se ei sisälly kokonaan mihinkään luokkiin , , , , . $T_{0}$ $T_{1}$ $S$ $M$ $L$
Erityisesti, jos funktio ei sisälly mihinkään Postin luokkiin, se muodostaa täydellisen järjestelmän sellaisenaan. Esimerkki on Schaeffer-funktio ( konjunktion negaatio ).

Seuraavat täydelliset Boolen funktioiden järjestelmät tunnetaan laajalti:

$\vasen\{\maa ,\tai ,\neg \oikea\}$ ( konjunktio , disjunktio , negaatio );
$\vasen\{\maa ,\oplus ,1\oikea\}$ (konjunktio, modulo 2 lisäys , vakio 1);
$\vasen\{\maa ,\neg \oikea\}$ ( konjunktio , negaatio );
$\vasen\{\tai ,\neg \oikea\}$ ( disjunktio , negaatio );
$\vasen\{\alaspäin \oikea\}$ ( Pierce nuoli );
$\left\{|\right\}$ ( Schefferin aivohalvaus ).

Ensimmäistä järjestelmää käytetään esimerkiksi esittämään funktioita disjunktiivisten ja konjunktiivisten normaalimuotojen muodossa , toista käytetään esittämään niitä Zhegalkin-polynomien muodossa .

Vähemmän tunnetut muut täydelliset loogisten funktioiden järjestelmät:

$\left\{\rightarrow ,\neg \right\}$ ( implikaatio , negaatio );
$\left\{\rightarrow ,\oplus \right\}$ ( implikaatio , modulo 2 lisäys );
$\left\{\rightarrow ,0\right\}$ ( implikaatio , vakio 0);

Täydellistä funktiojärjestelmää kutsutaan perustaksi, jos se lakkaa olemasta täydellinen, kun jokin elementti suljetaan pois siitä. Ensimmäinen edellä mainituista kokonaisista järjestelmistä ei ole perusta, koska de Morganin lakien mukaan joko disjunktio tai konjunktio voidaan sulkea pois järjestelmästä ja palauttaa käyttämällä kahta muuta funktiota. Toinen järjestelmä on perusta - sen kaikki kolme elementtiä ovat välttämättömiä täydellisyyden kannalta. Boolen funktioiden enimmäismäärä pohjassa on 4.

Joskus puhutaan funktiojärjestelmästä, joka on täydellinen jossain suljetussa luokassa, ja vastaavasti tämän luokan perustasta. Järjestelmää voidaan kutsua esimerkiksi lineaaristen funktioiden luokan perustaksi. $\vasen\{\oplus ,1\oikea\}$

Muistiinpanot

Kirjallisuus

Yablonsky SV Johdatus diskreettiin matematiikkaan. - M .: Nauka, 1986.
Marchenkov S. S. Boolen funktioiden suljetut luokat. - M .: Fizmatlit, 2000.
Gavrilov G. P., Sapozhenko A. A. Diskreetin matematiikan tehtäväkokoelma. - M.: Nauka. – 1969
Alekseev V. B. Diskreetti matematiikka (luentokurssi, II lukukausi). Comp. A. D. Pospelov
Akhmetova N.A., Usmanova Z.M. Diskreetti matematiikka, logiikan algebran funktiot.