Postkriterier

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 augusti 2022; verifiering kräver 1 redigering .

Posts kriterium är en av de centrala teoremerna i teorin om booleska funktioner , som upprättar ett nödvändigt och tillräckligt villkor för att någon uppsättning booleska funktioner ska ha tillräcklig uttrycksförmåga för att representera vilken boolesk funktion som helst. Först formulerad av den amerikanske matematikern Emil Post .

I mitten av 1960-talet dök verk upp nästan samtidigt i Sovjetunionen och i Frankrike, där Posts resultat presenterades från olika positioner och i en mer tillgänglig form. På 1980-talet lyckades ett antal forskare på en gång, med olika tillvägagångssätt och olika tekniker, få ganska kompakta bevis på Posts resultat. Det algebraiska tillvägagångssättet för studiet av slutna klasser av booleska funktioner (subalgebra av den iterativa postalgebra över en uppsättning ) tillhör A. I. Maltsev . ${\mathsf {B}}=\{0,1\}$

Postalgebra och slutna klasser

En boolesk funktion är en funktion av typ , där , och är ariteten av . Antalet olika aritetsfunktioner är lika med , medan det totala antalet olika booleska funktioner är oändligt. Det är dock uppenbart att många funktioner kan uttryckas i termer av att andra använder superpositionsoperatorn . Till exempel har det länge varit känt att från disjunktion och negation är det möjligt att, med hjälp av de Morgans lagar , få en konjunktion . Dessutom kan vilken boolesk funktion som helst representeras som en DNF , det vill säga i termer av konjunktion, disjunktion och negation. En naturlig fråga uppstår: hur avgör man om en given uppsättning funktioner kommer att vara tillräcklig för att representera någon boolesk funktion? Sådana uppsättningar kallas funktionellt kompletta . Posts teorem svarar på denna fråga. Eftersom tillståndet för satsen är nödvändigt och tillräckligt, kallas det också ett kriterium . ${\mathsf {B}}^{n}\to {\mathsf {B}}$ ${\mathsf {B}}=\{0,1\}$ $n$ $n$ $2^{{2^{n}}}$

Tanken med satsen är att betrakta mängden av alla booleska funktioner som en algebra med avseende på operationen av superposition . Nu bär den namnet Postalgebra . Denna algebra innehåller, som sin subalgebra, uppsättningar av funktioner som är stängda under superposition. De kallas också för slutna klasser . Låt vara en delmängd av . Stängningen av en uppsättning är den minimala subalgebra som innehåller . Stängningen består med andra ord av alla funktioner som är superpositioner . Uppenbarligen kommer det att vara funktionellt komplett om och bara om . Frågan om huruvida en given klass är funktionellt komplett handlar alltså om att kontrollera om dess stängning är densamma som . ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$ $[R]$ $R$ ${\mathsf {PA}}$ $R$ $R$ $R$ $[R]={\mathsf {PA}}$ ${\mathsf {PA}}$

Operatören är en stängningsoperatör . Med andra ord har den (bland andra) egenskaperna: $[\_]$

$R\subseteq [R]$ ( omfattning )
$R_{1}\subseteq R_{2}\Högerpil [R_{1}]\subseteq [R_{2}]$ ( monotoni )
$[[R]]=[R]$ ( idempotens )

Det sägs att en uppsättning funktioner genererar en sluten klass (eller en klass genereras av en uppsättning funktioner ) om . En uppsättning funktioner kallas en bas för en sluten klass om och för någon annan delmängd av uppsättningen än . $F$ $R$ $R$ $F$ $[Q]=R$ $F$ $R$ $[Q]=R$ $[Q_{1}]\neq R$ $F_1$ $F$ $F$

Om vi lägger till ett element som inte tillhör en subalgebra som inte tillhör den och bildar en stängning blir resultatet en ny subalgebra som innehåller den givna. Samtidigt kommer det att sammanfalla med , om och bara om det inte finns några andra subalgebra mellan den ursprungliga subalgebra och , det vill säga om den ursprungliga subalgebra var maximal. Således, för att kontrollera att en given uppsättning funktioner är funktionellt komplett, räcker det att verifiera att den inte helt tillhör någon av de maximala subalgebrerna . Det visar sig att det bara finns fem sådana subalgebror, och frågan om att tillhöra dem kan lösas enkelt och effektivt. ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$

Dualitet, monotoni, linjäritet. Fullständighetskriterium

Följande är några av följderna som följer av dubbelfunktionssatserna .

Om är en sluten klass , då är också en sluten klass . $R$ $R^{*}$
Uppsättningen bildar en sluten klass . $S$
Om , då . I synnerhet, om är grunden för klassen , då är grunden för klassen . $R=[Q]$ $R^{*}=[~Q^{*}]$ $F$ $R$ $Q^{*}$ $R^{*}$

Vi övergår nu till att klargöra fullständigheten av specifika uppsättningar funktioner.

Huvudfunktionsklasser: ${\displaystyle S,M,L,T_{0},T_{1))$

En funktion sägs vara nollbevarande om . Klassen av sådana funktioner kallas . $f(x_{1},x_{2},\ldots,x_{n})$ $f(0,0,\ldots ,0)=0$ $T_{0}$
En funktion sägs vara enhetsbevarande om . Klassen av sådana funktioner kallas . $f(x_{1},x_{2},\ldots,x_{n})$ $f(1,1,\ldots ,1)=1$ $T_{1}$
En funktion kallas självdual om den tar motsatta värden på motsatta mängder, det vill säga identiteten gäller för en självdubbelfunktion . Klassen av sådana funktioner kallas . $f(x_{1},x_{2},\dots,x_{n})$ $f(x_{1},x_{2},\dots,x_{n})=\överlinje {f({\bar {x}}_{1},{\bar {x}}_{2}, \dots ,{\bar {x}}_{n})}$ $S$
Funktionen kallas monoton : . Klassen av sådana funktioner kallas . $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n })\Högerpil 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})$
En funktion kallas linjär när den kan representeras av ett Zhegalkinpolynom av första graden, det vill säga . Klassen av sådana funktioner kallas . $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$

Slutenhetssats för huvudklasserna av funktioner

Observera att ingen av de stängda klasserna helt och hållet ingår i föreningen av de andra fyra. Detta följer av följande relationer: ${\displaystyle S,M,L,T_{0},T_{1))$

$\{{\bar {x)),xy\oplus xz\oplus yz\}\subset S\setminus (M\kopp L\kopp T_{0}\kopp 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})$

Alla icke-triviala (annat än ) slutna klasser av booleska funktioner finns helt och hållet i minst en av klasserna . $P_2$ ${\displaystyle S,M,L,T_{0},T_{1))$

Formuleringen av kriteriet

Ett system av booleska funktioner F är komplett om och endast om det inte helt tillhör någon av de slutna klasserna . ${\displaystyle S,M,L,T_{0},T_{1))$

Det vill säga när fem funktioner kan implementeras i den: icke-självdual, icke-monotone, icke-linjära, icke-bevarande 0 och icke-bevarande 1.

Bevis

Beviset för Posts kriterium baseras på att systemet av funktioner ( OCH , ELLER och INTE ) är komplett. Således är alla system där dessa tre funktioner är implementerade också kompletta. Låt oss bevisa att i ett system som uppfyller Post-kriteriet är det alltid möjligt att implementera konjunktion , disjunktion och negation .

Med en funktion som inte lagrar 0 får vi en inverterare eller en konstant 1

Betrakta en funktion som inte tillhör klassen T 0 . För henne

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

Denna funktion kanske tillhör klassen T 1 .

I det första fallet har vi också en enhetskonstant. $f(1,1,...,1)=1,$ $f(x,x,...,x)=1,$
I det andra fallet har vi också en växelriktare. $f(1,1,...,1)=0,$ $f(x,x,...,x)={\överlinje {x)),$

Med en funktion som inte lagrar 1 får vi en inverterare eller en konstant 0

Betrakta en funktion som inte tillhör klassen T 1 . För henne

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

Denna funktion kanske tillhör klassen T 0 .

I det första fallet har vi också en nollkonstant. $f(0,0,...,0)=0,$ $f(x,x,...,x)=0,$
I det andra fallet har vi också en växelriktare. $f(0,0,...,0)=1,$ $f(x,x,...,x)={\överlinje {x)),$

Med en växelriktare och en icke-självdubbel funktion får vi en av konstanterna

Betrakta en funktion som inte tillhör klassen S av självdubbla funktioner. För det finns det en sådan uppsättning indatavariabler X att

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

Låt, till exempel, då har vi också konstanten 1. $f(0,1,0)=f(1,0,1)=1,$ $f(x,{\overline {x)),x)=1$

På liknande sätt, om, till exempel, så har vi också konstanten 0. $f(0,0,0,1)=f(1,1,1,0)=0,$ $f(x,x,x,{\overline {x)))=0$

I vilket fall som helst, med en inverterare och en icke-självdubbel funktion, kan vi få en av konstanterna.

Givet en inverterare och en av konstanterna får vi en annan konstant

Om vi i något av ovanstående fall fick en växelriktare och en av konstanterna, får vi den andra konstanten med hjälp av växelriktaren: eller ${\overline {0}}=1$ ${\overline {1}}=0.$

Med en icke-monoton funktion och båda konstanterna får vi en inverterare

För en icke-monoton funktion måste det finnas en uppsättning indatavariabler så att

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

och

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

Låt till exempel och . Sedan . $f(1,1,0)=0$ $f(1,0,0)=1$ $f(1,x,0)={\överlinje {x))$

I vilket fall som helst, med en icke-monoton funktion och båda konstanterna, kan vi få en inverterare.

Vi har en inverterare och båda konstanterna

I de föregående underavsnitten gick vi igenom alla möjliga alternativ (se figur) och kom fram till att med funktioner som inte tillhör klasserna T 0 , T 1 , S och M kan vi alltid få inverteraren och båda konstanterna i olika sätt.

Givet en icke-linjär funktion, en inverterare och en konstant 1, får vi konjunktionen

Per definition har en icke-linjär funktion minst en term i Zhegalkin-polynomet som innehåller en konjunktion av flera variabler. Låt, till exempel, det finns någon icke-linjär funktion

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

Låt oss sätta oss som mål att konstruera en konjunktion på grundval av den $c(x_{1},x_{2})=x_{1}x_{2}.$

Tilldela värdena 1 till variablerna , vi får: $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}.

Uppenbarligen, i det allmänna fallet, efter en sådan transformation, får vi en funktion av formen

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

där hakparenteserna betyder att termen de lyfter fram kan eller inte kan finnas i det slutliga uttrycket.

I det enklaste fallet, i frånvaro av andra medlemmar, får vi omedelbart en konjunktion: $f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.$

Låt oss överväga andra alternativ.

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

Vilket som helst av dessa uttryck, med hjälp av en växelriktare, kan reduceras till en konjunktion.

Med en icke-linjär funktion, en växelriktare och en konstant 1, kan du alltså alltid få en konjunktion.

Givet en konjunktion och en inverterare får vi en disjunktion

Med en växelriktare och en konjunktion kan du alltid få en disjunktion:

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

Teoremet har bevisats.

Konsekvens

Enbart en funktion är ett komplett system om och endast om: $f$

$f(0,0,...,0)=1$
$f(1,1,...,1)=0$
$f$ är inte självdual

Exempel på funktioner som ensamma är ett komplett system skulle vara Schaeffers stroke och Pierces pil . $x|y={\overline {x\operatörsnamn {\&} y))$ $x\downarrow y={\overline {x\vee y))$

Sats om det maximala antalet funktioner i en bas

Det maximala antalet funktioner i basen av logikens algebra är 4 [1] .

Bevis

1) Låt oss bevisa att det från vilket komplett system av funktioner som helst är möjligt att peka ut ett komplett delsystem som inte består av fler än fyra funktioner.

Enligt Posts kriterium ska fem funktioner finnas i ett komplett system:

f_{0}\inte \i T_{0};f_{1}\inte \i T_{1};f_{S}\inte \i S;f_{M}\inte \i M;f_ {L}\inte \i L.

Låt oss överväga en funktion . Två fall är möjliga: ${\displaystyle f_{0))$

$f_{0}\in T_{1},$ sedan : och systemet är komplett. $f_{0}\inte \in S$ $[f_{0},f_{1},f_{M},f_{L}]$
$f_{0}\inte \i T_{1},$ sedan : och systemet är komplett. ${\displaystyle f_{0}\inte \i M,T_{1))$ $[f_{0},f_{S},f_{L}]$

2) Låt oss visa att det finns en grund för fyra funktioner. Betrakta ett system av funktioner . Detta system är komplett: ${\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.

Inget av dess undersystem är dock komplett:

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

Teoremet har bevisats.

Anteckningar

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

Litteratur

Marchenkov S. S. Slutna klasser av booleska funktioner. — M .: Fizmatlit, 2000.
Fujisawa T., Kasami T. Matematik för radioingenjörer: teori om diskreta strukturer. - M . : Radio och kommunikation, 1984. - 240 sid.
Alekseev V. B. Diskret matematik (II termin) . - M., Moscow State University, 2002. - 44 sid.
Belousov A. I., Tkachev S. B. Diskret matematik. - M. : MGTU, 2006. - 744 sid. — ISBN 5-7038-2886-4 .
Gindikin S. G. Algebra av logik i uppgifter. - M. : Nauka, 1972. - 288 sid.

Länkar

Lärobok i diskret matematik. Överlagring av funktioner. Funktionsuppsättning stängning.Stängda funktionsklasser. Kompletta set. Baser , mini-soft.ru

Postkriterier

Postalgebra och slutna klasser

Dualitet, monotoni, linjäritet. Fullständighetskriterium

Huvudfunktionsklasser:

Slutenhetssats för huvudklasserna av funktioner

Formuleringen av kriteriet

Bevis

Med en funktion som inte lagrar 0 får vi en inverterare eller en konstant 1

Med en funktion som inte lagrar 1 får vi en inverterare eller en konstant 0

Med en växelriktare och en icke-självdubbel funktion får vi en av konstanterna

Givet en inverterare och en av konstanterna får vi en annan konstant

Med en icke-monoton funktion och båda konstanterna får vi en inverterare

Vi har en inverterare och båda konstanterna

Givet en icke-linjär funktion, en inverterare och en konstant 1, får vi konjunktionen

Givet en konjunktion och en inverterare får vi en disjunktion

Konsekvens

Sats om det maximala antalet funktioner i en bas

Bevis

Anteckningar

Litteratur

Länkar

Se även

Huvudfunktionsklasser: ${\displaystyle S,M,L,T_{0},T_{1))$