Criterii de postare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 august 2022; verificarea necesită 1 editare .

Criteriul lui Post este una dintre teoremele centrale în teoria funcțiilor booleene , stabilind o condiție necesară și suficientă pentru ca un set de funcții booleene să aibă suficientă expresivitate pentru a reprezenta orice funcție booleană. Formulat pentru prima dată de matematicianul american Emil Post .

La mijlocul anilor 1960, lucrările au apărut aproape simultan în URSS și în Franța, unde rezultatele Post au fost prezentate din diferite poziții și într-o formă mai accesibilă. În anii 1980, un număr de cercetători simultan, folosind diverse abordări și tehnici diferite, au reușit să obțină dovezi destul de compacte ale rezultatelor lui Post. Abordarea algebrică a studiului claselor închise de funcții booleene (subalgebre ale algebrei iterative Post peste o mulțime ) îi aparține lui A. I. Maltsev . ${\mathsf {B}}=\{0,1\}$

Post algebră și clase închise

O funcție booleană este o funcție de tip , unde și este aritatea lui . Numărul de funcții de aritate diferite este egal cu , în timp ce numărul total de funcții booleene diferite este infinit. Cu toate acestea, este evident că multe funcții pot fi exprimate în termenii altora folosind operatorul de suprapunere . De exemplu, se știe de mult că din disjuncție și negație este posibil, folosind legile lui de Morgan , să se obțină o conjuncție . În plus, orice funcție booleană poate fi reprezentată ca un DNF , adică în termeni de conjuncție, disjuncție și negație. Apare o întrebare firească: cum să determinați dacă un anumit set de funcții va fi suficient pentru a reprezenta orice funcție booleană? Astfel de seturi sunt numite complet funcțional . Teorema lui Post răspunde la această întrebare. Deoarece condiția teoremei este necesară și suficientă, se mai numește și criteriu . ${\mathsf {B}}^{n}\la {\mathsf {B}}$ ${\mathsf {B}}=\{0,1\}$ $n$ $n$ $2^{{2^{n}}}$

Ideea teoremei este de a considera mulțimea tuturor funcțiilor booleene ca o algebră în ceea ce privește operația de suprapunere . Acum poartă numele Post algebră . Această algebră conține, ca subalgebrele sale, seturi de funcții care sunt închise sub suprapunere. Se mai numesc si clase inchise . Să fie un subset de . Închiderea unei mulțimi este subalgebra minimă care conține . Cu alte cuvinte, închiderea constă din toate funcțiile care sunt suprapoziții . Evident, va fi complet funcțional dacă și numai dacă . Astfel, întrebarea dacă o anumită clasă este completă funcțional se rezumă la verificarea dacă închiderea ei este aceeași cu . ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$ $[R]$ $R$ ${\mathsf {PA}}$ $R$ $R$ $R$ $[R]={\mathsf {PA}}$ ${\mathsf {PA}}$

Operatorul este un operator de închidere . Cu alte cuvinte, are (printre altele) proprietățile: $[\_]$

$R\subseteq [R]$ ( extensiune )
$R_{1}\subseteq R_{2}\Rightarrow [R_{1}]\subseteq [R_{2}]$ ( monotonitate )
$[[R]]=[R]$ ( idempotenta )

Se spune că un set de funcții generează o clasă închisă (sau o clasă este generată de un set de funcții ) dacă . Un set de funcții se numește o bază a unei clase închise dacă și pentru orice submulțime a mulțimii , altul decât . $Q$ $R$ $R$ $Q$ $[Q]=R$ $Q$ $R$ $[Q]=R$ $[Q_{1}]\neq R$ $Q_1$ $Q$ $Q$

Dacă adăugăm un element care nu aparține unei subalgebre care nu îi aparține și formăm o închidere, rezultatul va fi o nouă subalgebră care conține cea dată. În același timp, va coincide cu , dacă și numai dacă nu există alte subalgebre între subalgebra originală și , adică dacă subalgebra originală a fost maximă. Astfel, pentru a verifica dacă un anumit set de funcții este complet funcțional, este suficient să verificăm că nu aparține în totalitate niciunei dintre subalgebrele maxime . Se pare că există doar cinci astfel de subalgebre, iar problema apartenenței lor poate fi rezolvată simplu și eficient. ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$

Dualitate, monotonitate, liniaritate. Criteriul de completitudine

Următoarele sunt câteva dintre corolarele care decurg din teoremele funcției duale .

Dacă este o clasă închisă , atunci este și o clasă închisă . $R$ $R^{*}$
Mulțimea formează o clasă închisă . $S$
Dacă , atunci . În special, dacă este baza clasei , atunci este baza clasei . $R=[Q]$ $R^{*}=[~Q^{*}]$ $Q$ $R$ $Q^{*}$ $R^{*}$

Ne întoarcem acum la clarificarea caracterului complet al unor seturi specifice de funcții.

Clase de funcții principale: $S,M,L,T_{0},T_{1)$

Se spune că o funcție este zero - conservare dacă . Clasa unor astfel de funcții se numește . $f(x_{1},x_{2},\ldots,x_{n})$ $f(0,0,\ldots ,0)=0$ $T_{0}$
Se spune că o funcție păstrează unitatea dacă . Clasa unor astfel de funcții se numește . $f(x_{1},x_{2},\ldots,x_{n})$ $f(1,1,\ldots ,1)=1$ $T_{1}$
O funcție se numește auto-duală dacă ia valori opuse pe mulțimi opuse, adică identitatea este valabilă pentru o funcție auto-duală . Clasa unor astfel de funcții se numește . $f(x_{1},x_{2},\dots ,x_{n})$ $f(x_{1},x_{2},\dots ,x_{n})=\overline {f({\bar {x}}_{1},{\bar {x}}_{2}, \dots ,{\bar {x}}_{n})}$ $S$
Funcția se numește monotonă : . Clasa unor astfel de funcții se numește . $(\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})$
O funcție se numește liniară atunci când poate fi reprezentată printr-un polinom Zhegalkin de gradul I, adică . Clasa unor astfel de funcții se numește . $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$

Teorema de închidere pentru principalele clase de funcții

Rețineți că niciuna dintre clasele închise nu este cuprinsă în întregime în uniunea celorlalte patru. Aceasta rezultă din următoarele relații: $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})$

Orice clasă închisă non-trivială (altele decât ) de funcții booleene este conținută în întregime în cel puțin una dintre clase . $P_2$ $S,M,L,T_{0},T_{1)$

Formularea criteriului

Un sistem de funcții booleene F este complet dacă și numai dacă nu aparține în întregime nici uneia dintre clasele închise . $S,M,L,T_{0},T_{1)$

Adică, atunci când în el pot fi implementate cinci funcții: non-auto-dual, nemonoton, neliniar, neconservator 0 și non-conservator 1.

Dovada

Dovada criteriului Post se bazează pe faptul că sistemul de funcții ( ȘI , SAU și NU ) este complet. Astfel, orice sistem în care sunt implementate aceste trei funcții este și el complet. Să demonstrăm că într-un sistem care satisface criteriul Post, este întotdeauna posibil să se implementeze conjuncția , disjuncția și negația .

Având o funcție care nu stochează 0, obținem un invertor sau o constantă 1

Se consideră o funcție care nu aparține clasei T 0 . Pentru ea

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

Această funcție poate aparține sau nu clasei T 1 .

În primul caz, atunci avem și o constantă unitară. $f(1,1,...,1)=1,$ $f(x,x,...,x)=1,$
În al doilea caz, atunci avem și un invertor. $f(1,1,...,1)=0,$ $f(x,x,...,x)={\overline {x)),$

Având o funcție care nu stochează 1, obținem un invertor sau o constantă 0

Se consideră o funcție care nu aparține clasei T 1 . Pentru ea

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

Această funcție poate aparține sau nu clasei T 0 .

În primul caz, atunci avem și o constantă zero. $f(0,0,...,0)=0,$ $f(x,x,...,x)=0,$
În al doilea caz, atunci avem și un invertor. $f(0,0,...,0)=1,$ $f(x,x,...,x)={\overline {x)),$

Având un invertor și o funcție non-duală, obținem una dintre constantele

Să considerăm o funcție care nu aparține clasei S de funcții autoduale. Pentru aceasta, există un astfel de set de variabile de intrare X care

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

Să fie, de exemplu, atunci avem și constanta 1. $f(0,1,0)=f(1,0,1)=1,$ $f(x,{\overline {x)),x)=1$

În mod similar, dacă, de exemplu, atunci avem și constanta 0. $f(0,0,0,1)=f(1,1,1,0)=0,$ $f(x,x,x,{\overline {x)))=0$

În orice caz, având un invertor și o funcție non-auto-duală, putem obține una dintre constante.

Având în vedere un invertor și una dintre constante, obținem o altă constantă

Dacă într-unul din cazurile de mai sus avem un invertor și una dintre constante, obținem a doua constantă folosind invertorul: sau ${\overline {0}}=1$ ${\overline {1}}=0.$

Având o funcție nemonotonă și ambele constante, obținem un invertor

Pentru o funcție nemonotonă, trebuie să existe un set de variabile de intrare astfel încât

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

și

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

Să fie, de exemplu, și . Apoi . $f(1,1,0)=0$ $f(1,0,0)=1$ $f(1,x,0)={\overline {x}}$

În orice caz, având o funcție nemonotonă și ambele constante, putem obține un invertor.

Avem un invertor și ambele constante

În subsecțiunile anterioare, am trecut prin toate opțiunile posibile (vezi figura) și am ajuns la concluzia că având funcții care nu aparțin claselor T 0 , T 1 , S și M, putem obține întotdeauna invertorul și ambele constante în diferite căi.

Având în vedere o funcție neliniară, un invertor și o constantă 1, obținem conjuncția

Prin definiție, o funcție neliniară are cel puțin un termen în polinomul Zhegalkin care conține o conjuncție de mai multe variabile. Să fie, de exemplu, o funcție neliniară

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}.

Să ne stabilim scopul de a construi o conjuncție pe baza ei $c(x_{1},x_{2})=x_{1}x_{2}.$

Atribuiți valorile 1 variabilelor , obținem: $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}.

Evident, în cazul general, după o astfel de transformare, obținem o funcție a formei

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

unde parantezele pătrate înseamnă că termenul pe care îl evidențiază poate fi prezent sau nu în expresia finală.

În cel mai simplu caz, în absența altor membri, obținem imediat o conjuncție: $f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.$

Să luăm în considerare și alte opțiuni.

$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}.$

Oricare dintre aceste expresii, folosind un invertor, poate fi redusă la o conjuncție.

Astfel, având o funcție neliniară, un invertor și o constantă 1, puteți obține întotdeauna o conjuncție.

Având în vedere o conjuncție și un invertor, obținem o disjuncție

Având în vedere un invertor și o conjuncție, puteți obține întotdeauna o disjuncție:

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

Teorema a fost demonstrată.

Consecință

O singură funcție este un sistem complet dacă și numai dacă: $f$

$f(0,0,...,0)=1$
$f(1,1,...,1)=0$
$f$ nu este auto-dual

Exemple de caracteristici care sunt singure un sistem complet ar fi lovitura lui Schaeffer și săgeata lui Pierce . $x|y={\overline {x\operatorname {\&} y)}$ $x\downarrow y={\overline {x\vee y)}$

Teoremă privind numărul maxim de funcții dintr-o bază

Numărul maxim de funcții în baza algebrei logicii este 4 [1] .

Dovada

1) Să demonstrăm că din orice sistem complet de funcții este posibil să evidențiem un subsistem complet format din nu mai mult de patru funcții.

Conform criteriului Post, cinci funcții ar trebui să fie prezente într-un sistem complet:

f_{0}\nu \in T_{0};f_{1}\nu \in T_{1};f_{S}\nu \in S;f_{M}\nu \in M;f_ {L}\nu \în L.

Să luăm în considerare o funcție . Sunt posibile două cazuri: $f_{0}$

$f_{0}\in T_{1},$ apoi : iar sistemul este complet. $f_{0}\nu \în S$ $[f_{0},f_{1},f_{M},f_{L}]$
$f_{0}\nu \in T_{1},$ apoi : iar sistemul este complet. $f_{0}\nu \în M,T_{1)$ $[f_{0},f_{S},f_{L}]$

2) Să arătăm că există o bază a patru funcții. Luați în considerare un sistem de funcții . Acest sistem este complet: $\{0,1,x\cdot y,x\oplus y\oplus z\)$

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

Cu toate acestea, niciunul dintre subsistemele sale nu este complet:

$\{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}.$

Teorema a fost demonstrată.

Note

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

Literatură

Marchenkov S. S. Clase închise de funcții booleene. — M .: Fizmatlit, 2000.
Fujisawa T., Kasami T. Matematică pentru ingineri radio: teoria structurilor discrete. - M . : Radio şi comunicare, 1984. - 240 p.
Alekseev V. B. Matematică discretă (semestrul II) . - M., Universitatea de Stat din Moscova, 2002. - 44 p.
Belousov A. I., Tkachev S. B. Matematică discretă. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .
Gindikin S. G. Algebra logicii în sarcini. - M. : Nauka, 1972. - 288 p.

Link -uri

Manual de matematică discretă. Suprapunerea functiilor. Închidere set de funcții Clase de funcții închise. Seturi complete. Baze , mini-soft.ru

Criterii de postare

Post algebră și clase închise

Dualitate, monotonitate, liniaritate. Criteriul de completitudine

Clase de funcții principale:

Teorema de închidere pentru principalele clase de funcții

Formularea criteriului

Dovada

Având o funcție care nu stochează 0, obținem un invertor sau o constantă 1

Având o funcție care nu stochează 1, obținem un invertor sau o constantă 0

Având un invertor și o funcție non-duală, obținem una dintre constantele

Având în vedere un invertor și una dintre constante, obținem o altă constantă

Având o funcție nemonotonă și ambele constante, obținem un invertor

Avem un invertor și ambele constante

Având în vedere o funcție neliniară, un invertor și o constantă 1, obținem conjuncția

Având în vedere o conjuncție și un invertor, obținem o disjuncție

Consecință

Teoremă privind numărul maxim de funcții dintr-o bază

Dovada

Note

Literatură

Link -uri

Vezi și

Clase de funcții principale: $S,M,L,T_{0},T_{1)$