Hozzászólás kritériumai

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. augusztus 20-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Post-kritérium a Boole-függvények elméletének egyik központi tétele , amely szükséges és elégséges feltételt teremt ahhoz, hogy néhány Boole-függvényhalmaz elegendő kifejezőképességgel rendelkezzen bármely Boole-függvény ábrázolásához. Először Emil Post amerikai matematikus fogalmazta meg .

Az 1960-as évek közepén szinte egyszerre jelentek meg művek a Szovjetunióban és Franciaországban, ahol Post eredményeit különböző pozíciókból és elérhetőbb formában mutatták be. Az 1980-as években számos kutatónak egyszerre, különféle megközelítésekkel és különféle technikákkal sikerült meglehetősen tömör bizonyítékot szereznie Post eredményeiről. A Boole-függvények zárt osztályainak (az iteratív Post algebra egy halmaz feletti részalgebrái) vizsgálatának algebrai megközelítése A. I. Malcevhez tartozik . ${\mathsf {B}}=\{0,1\}$

Hozzászólás algebra és zárt osztályok

A logikai függvény a típus függvénye , ahol , és az aritása . A különböző aritásfüggvények száma egyenlő , míg a különböző Boole-függvények száma végtelen. Nyilvánvaló azonban, hogy sok függvény másokkal is kifejezhető a szuperpozíciós operátor használatával . Például régóta ismert, hogy a diszjunkcióból és tagadásból de Morgan törvényei segítségével kötőszót kaphatunk . Ezenkívül bármely Boole-függvény ábrázolható DNF -ként , azaz konjunkció, diszjunkció és negáció szempontjából. Felmerül a természetes kérdés: hogyan határozható meg, hogy egy adott függvényhalmaz elegendő lesz-e bármely Boole-függvény ábrázolásához? Az ilyen halmazokat funkcionálisan teljesnek nevezzük . Post tétele válaszol erre a kérdésre. Mivel a tétel feltétele szükséges és elégséges, ezért kritériumnak is nevezik . ${\mathsf {B}}^{n}\ to {\mathsf {B}}$ ${\mathsf {B}}=\{0,1\}$ $n$ $n$ $2^{{2^{n}}}$

A tétel gondolata az, hogy az összes Boole-függvény halmazát algebraként tekintsük a szuperpozíció műveletére vonatkozóan . Most a Post algebra nevet viseli . Ez az algebra részalgebraként olyan függvényhalmazokat tartalmaz, amelyek szuperpozíció alatt záródnak . Zárt osztályoknak is nevezik őket . Legyen valamilyen részhalmaza . Egy halmaz lezárása a -t tartalmazó minimális részalgebra . Más szóval, a lezárás minden olyan függvényből áll, amely szuperpozíció . Nyilvánvalóan akkor és csak akkor lesz funkcionálisan teljes, ha . Így az a kérdés, hogy egy adott osztály funkcionálisan teljes-e, annak ellenőrzésére vezethető vissza, hogy a lezárása megegyezik-e a -val . ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$ $[R]$ $R$ ${\mathsf {PA}}$ $R$ $R$ $R$ $[R]={\mathsf {PA}}$ ${\mathsf {PA}}$

Az üzemeltető egy záráskezelő . Más szavakkal, a következő tulajdonságokkal rendelkezik (többek között): $[\_]$

$R\subseteq [R]$ ( kiterjedtség )
$R_{1}\subseteq R_{2}\Jobbra [R_{1}]\subseteq [R_{2}]$ ( monotonitás )
$[[R]]=[R]$ ( idempotencia )

Azt mondják, hogy egy függvényhalmaz zárt osztályt generál (vagy egy osztályt függvénykészlet generál ), ha . Egy függvényhalmazt akkor nevezünk egy zárt osztály bázisának , ha a halmaz bármely részhalmazára , kivéve a . $K$ $R$ $R$ $K$ $[Q]=R$ $K$ $R$ $[Q]=R$ $[Q_{1}]\neq R$ $Q_1$ $K$ $K$

Ha hozzáadunk egy olyan elemet, amely nem tartozik hozzá nem tartozó részalgebrához , és lezárást alkotunk, akkor az eredmény egy új részalgebra lesz, amely az adott elemet tartalmazza. Ugyanakkor akkor és csak akkor esik egybe a -val, ha az eredeti részalgebra és a között nincs más részalgebra, vagyis ha az eredeti részalgebra maximális volt. Így annak ellenőrzéséhez, hogy egy adott függvénykészlet funkcionálisan teljes-e, elegendő ellenőrizni, hogy nem tartozik-e teljesen a maximális részalgebrák egyikéhez sem . Kiderült, hogy csak öt ilyen algebra létezik, és a hozzájuk tartozás kérdése egyszerűen és hatékonyan megoldható. ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$

Kettősség, monotonitás, linearitás. Teljességi kritérium

Az alábbiakban felsorolunk néhány következményt, amelyek a kettős függvénytételekből következnek .

Ha zárt osztály , akkor zárt osztály is . $R$ $R^{*}$
A készlet egy zárt osztályt alkot . $S$
Ha , akkor . Különösen, ha az osztály alapja , akkor az osztály alapja . $R=[Q]$ $R^{*}=[~Q^{*}]$ $K$ $R$ $Q^{*}$ $R^{*}$

Most rátérünk az egyes függvénykészletek teljességének tisztázására.

Fő funkcióosztályok: ${\displaystyle S,M,L,T_{0},T_{1))$

Egy függvényt nulla megőrzőnek mondunk, ha . Az ilyen függvények osztályát . $f(x_{1},x_{2},\ldots ,x_{n})$ $f(0,0,\ldots ,0)=0$ $T_{0}$
Egy függvényt egységmegőrzőnek mondunk , ha . Az ilyen függvények osztályát . $f(x_{1},x_{2},\ldots ,x_{n})$ $f(1,1,\ldots ,1)=1$ $T_{1}$
Egy függvényt önduálisnak nevezünk, ha ellentétes értékeket vesz fel ellentétes halmazokon, vagyis az azonosság érvényes egy önduális függvényre . Az ilyen függvények osztályát . $f(x_{1},x_{2},\pontok,x_{n})$ $f(x_{1},x_{2},\dots ,x_{n})=\overline {f({\bar {x}}_{1},{\bar {x}}_{2}, \dots ,{\bar {x}}_{n})}$ $S$
A függvényt monotonnak nevezzük : . Az ilyen függvények osztályát . $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n })\Rightarrow f(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq f(\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})$ $M$
- $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n })\Leftrightarrow \forall i(\beta _{i}\geq \alpha _{i})$
Egy függvényt lineárisnak nevezünk , ha egy elsőfokú Zhegalkin-polinommal reprezentálható , azaz . Az ilyen függvények osztályát . $f(x_{1},x_{2},\ldots ,x_{n})=\alpha _{0}\oplus \alpha _{1}x_{{1}}\oplus \alpha _{2}x_ {{2}}\oplus \ldots \oplus \alpha _{n}x_{{n}};$ $\alpha _{0},\alpha _{i}\in {0,1}(i\in \overline {1,n})$ $L$

Zártsági tétel a fő függvényosztályokhoz

Megjegyzendő, hogy a zárt osztályok egyike sem tartozik teljes egészében a másik négy uniójába. Ez a következő összefüggésekből következik: ${\displaystyle S,M,L,T_{0},T_{1))$

$\{{\bar {x)),xy\oplus xz\oplus yz\}\subset S\setminus (M\cup L\cup T_{0}\cup T_{1})$
$\{0,1,x\lor y\}\subset M\setminus (S\cup L\cup T_{0}\cup T_{1})$
$\{1,x\oplus y\}\subset L\setminus (S\cup M\cup T_{0}\cup T_{1})$
$\{x\oplus y,xy\}\subset T_{0}\setminus (S\cup M\cup L\cup T_{1})$
$\{x\oplus y\oplus 1,x\lor y\}\subset T_{1}\setminus (S\cup M\cup L\cup T_{0})$

A logikai függvények bármely nem triviális (kivéve ) zárt osztálya teljes egészében benne van az osztályok legalább egyikében . $P_2$ ${\displaystyle S,M,L,T_{0},T_{1))$

A kritérium megfogalmazása

Egy F logikai függvényrendszer akkor és csak akkor teljes, ha nem tartozik teljes egészében egyik zárt osztályhoz sem . ${\displaystyle S,M,L,T_{0},T_{1))$

Vagyis amikor öt függvény implementálható benne: nem önkettős, nem monoton, nemlineáris, nem megőrző 0 és nem megőrző 1.

Bizonyítás

A Post kritériumának bizonyítása azon alapul, hogy a függvényrendszer ( ÉS , VAGY és NEM ) teljes. Így minden olyan rendszer is teljes, amelyben ez a három funkció megvalósul. Bizonyítsuk be, hogy a Post-kritériumot kielégítő rendszerben mindig lehetséges a konjunkció , a diszjunkció és a negáció megvalósítása .

Ha van egy függvény, ami nem tárol 0-t, akkor egy invertert vagy egy konstans 1-et kapunk

Tekintsünk egy függvényt, amely nem tartozik a T 0 osztályba . Neki

f(0,0,...,0)=1.

Ez a függvény tartozhat a T 1 osztályba, de lehet, hogy nem .

Az első esetben akkor van egy egységállandónk is. $f(1,1,...,1)=1,$ $f(x,x,...,x)=1,$
A második esetben akkor van inverterünk is. $f(1,1,...,1)=0,$ $f(x,x,...,x)={\overline {x)),$

Ha van egy függvény, ami nem tárol 1-et, akkor egy invertert vagy egy konstans 0-t kapunk

Tekintsünk egy függvényt, amely nem tartozik a T 1 osztályba . Neki

f(1,1,...,1)=0.

Ez a függvény tartozhat a T 0 osztályba, de lehet, hogy nem .

Az első esetben akkor is van egy nulla állandó. $f(0,0,...,0)=0,$ $f(x,x,...,x)=0,$
A második esetben akkor van inverterünk is. $f(0,0,...,0)=1,$ $f(x,x,...,x)={\overline {x)),$

Egy inverterrel és egy nem ön-kettős funkcióval kapjuk az egyik állandót

Tekintsünk egy olyan függvényt, amely nem tartozik az önduális függvények S osztályába. Ehhez létezik egy olyan X bemeneti változókészlet, amely

f(x_{1},x_{2},...,x_{n})=f({\overline {x}}_{1},{\overline {x}}_{2} ,...,{\overline {x}}_{n}).

Legyen például akkor az 1-es konstans is. $f(0,1,0)=f(1,0,1)=1,$ $f(x,{\overline {x)),x)=1$

Hasonlóképpen, ha például akkor is megvan a 0 konstans. $f(0,0,0,1)=f(1,1,1,0)=0,$ $f(x,x,x,{\overline {x)))=0$

Mindenesetre egy inverterrel és egy nem önduális funkcióval megkaphatjuk az egyik állandót.

Adott egy invertert és az egyik állandót, egy másik állandót kapunk

Ha a fenti esetek egyikében kaptunk egy invertert és az egyik állandót, akkor az inverter segítségével megkapjuk a második állandót: ill . ${\overline {0}}=1$ ${\overline {1}}=0.$

Nem monoton függvény és mindkét konstans birtokában egy invertert kapunk

Egy nem monoton függvényhez olyan bemeneti változók halmazának kell lennie, hogy

f(x_{1},x_{2},...,0,...,x_{n})=1

és

f(x_{1},x_{2},...,1,...,x_{n})=0.

Legyen például és . Akkor . $f(1,1,0)=0$ $f(1,0,0)=1$ $f(1,x,0)={\overline {x}}$

Mindenesetre nem monoton függvény és mindkét konstans birtokában kaphatunk invertert.

Van egy inverterünk és mindkét konstans

Az előző alfejezetekben az összes lehetséges opciót végigjártuk (lásd az ábrát), és arra a következtetésre jutottunk, hogy olyan függvényekkel, amelyek nem tartoznak a T 0 , T 1 , S és M osztályokba, mindig megkaphatjuk az invertert és mindkét állandót különböző módokon.

Adott egy nemlineáris függvény, egy inverter és egy konstans 1, megkapjuk a

Definíció szerint egy nemlineáris függvénynek legalább egy olyan tagja van a Zhegalkin-polinomban , amely több változó konjunkcióját tartalmazza. Legyen például néhány nemlineáris függvény

f(x_{1},x_{2},x_{3},x_{4},x_{5})=1\oplus x_{1}\oplus x_{1}x_{2}x_{ 3}\oplus x_{2}x_{3}x_{4}\oplus x_{2}x_{3}x_{5}\oplus x_{2}x_{3}x_{4}x_{5}.

Tűzzük ki magunknak azt a célt, hogy ennek alapján alkossunk egy kötőszót $c(x_{1},x_{2})=x_{1}x_{2}.$

Adjuk hozzá az 1-es értékeket a változókhoz , így kapjuk: $x_{3},x_{4},x_{5}$

f(x_{1},x_{2},1,1,1)=1\oplus x_{1}\oplus x_{1}x_{2}\oplus x_{2}\oplus x_{2 }\oplus x_{2}=1\oplus x_{1}\oplus x_{1}x_{2}\oplus x_{2}.

Nyilván általános esetben egy ilyen átalakítás után az alak függvényét kapjuk

f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}[\oplus x_{1}][\oplus x_{2}] [\oplus 1],

ahol a szögletes zárójelek azt jelentik, hogy az általuk kiemelt kifejezés szerepelhet a végső kifejezésben, vagy nem.

A legegyszerűbb esetben más tagok hiányában azonnal kötőszót kapunk: $f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.$

Tekintsünk más lehetőségeket.

$x_{1}x_{2}\oplus x_{1}=x_{1}{\overline {x}}_{2};$
$x_{1}x_{2}\oplus x_{2}={\overline {x}}_{1}x_{2};$
$x_{1}x_{2}\oplus x_{1}\oplus x_{2}={\overline ({\overline {x))_{1}{\overline {x))))_{ 2}.$
$x_{1}x_{2}\oplus 1={\overline {x_{1}x}}_{2};$ .
$x_{1}x_{2}\oplus x_{1}\oplus 1={\overline {x_{1}{\overline {x))))_{2};$
$x_{1}x_{2}\oplus x_{2}\oplus 1={\overline ((\overline {x))_{1}x))_{2};$
$x_{1}x_{2}\oplus x_{1}\oplus x_{2}\oplus 1={\overline {x}}_{1}{\overline {x}}_{2}.$

Ezen kifejezések bármelyike inverter segítségével konjunkcióvá redukálható.

Így egy nemlineáris függvény, egy inverter és egy állandó 1 birtokában mindig kaphat konjunkciót.

Adott egy konjunkció és egy inverter, diszjunkciót kapunk

Adott egy inverter és egy konjunkció, mindig kaphat diszjunkciót:

x_{1}+x_{2}={\overline ({\overline {x}}_{1}{\overline {x}}}}_{2}.

A tétel bizonyítást nyert.

Következmény

Egy függvény önmagában akkor és csak akkor teljes rendszer, ha: $f$

$f(0,0,...,0)=1$
$f(1,1,...,1)=0$
$f$ nem önkettős

Példák olyan jellemzőkre, amelyek önmagukban egy teljes rendszert alkotnak, lehet Schaeffer vonása és Pierce nyila . $x|y={\overline {x\operatorname {\&} y))$ $x\downarrow y={\overline {x\vee y))$

Tétel a függvények maximális számáról egy bázisban

A logikai algebra alapján a függvények maximális száma 4 [1] .

Bizonyítás

1) Bizonyítsuk be, hogy bármely teljes függvényrendszerből ki lehet választani egy teljes alrendszert, amely legfeljebb négy függvényből áll.

A Post kritériuma szerint egy teljes rendszerben öt funkciónak kell jelen lennie:

f_{0}\not \in T_{0};f_{1}\not \in T_{1};f_{S}\not \in S;f_{M}\not \in M;f_ {L}\nem \in L.

Tekintsünk egy függvényt . Két eset lehetséges: $f_{0}$

$f_{0}\in T_{1},$ majd : és a rendszer kész. $f_{0}\not \in S$ $[f_{0},f_{1},f_{M},f_{L}]$
$f_{0}\not \in T_{1},$ majd : és a rendszer kész. ${\displaystyle f_{0}\not \in M,T_{1))$ $[f_{0},f_{S},f_{L}]$

2) Mutassuk meg, hogy négy függvénynek van alapja. Tekintsünk egy függvényrendszert . Ez a rendszer kész: ${\displaystyle \{0,1,x\cdot y,x\oplus y\oplus z\))$

0\not \in T_{1},S;1\not \in T_{0};x\cdot y\not \in L;x\oplus y\oplus z\not \in M.

Azonban egyik alrendszere sem teljes:

$\{0,1,x\cdot y\}\subseteq M;$
$\{0,1,x\oplus y\oplus z\}\subseteq L;$
$\{0,x\cdot y,x\oplus y\oplus z\}\subseteq T_{0};$
$\{1,x\cdot y,x\oplus y\oplus z\}\subseteq T_{1}.$

A tétel bizonyítást nyert.

Jegyzetek

↑ Alekszejev V.B. (2002), p. 12.

Irodalom

Marchenkov S. S. Boole-függvények zárt osztályai. - M .: Fizmatlit, 2000.
Fujisawa T., Kasami T. Matematika rádiómérnökök számára: diszkrét szerkezetek elmélete. - M . : Rádió és kommunikáció, 1984. - 240 p.
Alekseev V. B. Diszkrét matematika (II félév) . - M., Moszkvai Állami Egyetem, 2002. - 44 p.
Belousov A. I., Tkachev S. B. Diszkrét matematika. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .
Gindikin S. G. Logikai algebra feladatokban. - M. : Nauka, 1972. - 288 p.

Linkek

Tankönyv a diszkrét matematikáról. Funkciók szuperpozíciója. Függvénykészlet lezárása Zárt funkcióosztályok. Komplett készletek. Alapok , mini-soft.ru

Hozzászólás kritériumai

Hozzászólás algebra és zárt osztályok

Kettősség, monotonitás, linearitás. Teljességi kritérium

Fő funkcióosztályok:

Zártsági tétel a fő függvényosztályokhoz

A kritérium megfogalmazása

Bizonyítás

Ha van egy függvény, ami nem tárol 0-t, akkor egy invertert vagy egy konstans 1-et kapunk

Ha van egy függvény, ami nem tárol 1-et, akkor egy invertert vagy egy konstans 0-t kapunk

Egy inverterrel és egy nem ön-kettős funkcióval kapjuk az egyik állandót

Adott egy invertert és az egyik állandót, egy másik állandót kapunk

Nem monoton függvény és mindkét konstans birtokában egy invertert kapunk

Van egy inverterünk és mindkét konstans

Adott egy nemlineáris függvény, egy inverter és egy konstans 1, megkapjuk a

Adott egy konjunkció és egy inverter, diszjunkciót kapunk

Következmény

Tétel a függvények maximális számáról egy bázisban

Bizonyítás

Jegyzetek

Irodalom

Linkek

Lásd még

Fő funkcióosztályok: ${\displaystyle S,M,L,T_{0},T_{1))$