Postkriterier

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. august 2022; verifikation kræver 1 redigering .

Posts kriterium er en af de centrale teoremer i teorien om boolske funktioner , der etablerer en nødvendig og tilstrækkelig betingelse for, at nogle sæt boolske funktioner har tilstrækkelig udtryksevne til at repræsentere enhver boolsk funktion. Først formuleret af den amerikanske matematiker Emil Post .

I midten af 1960'erne udkom værker næsten samtidigt i USSR og Frankrig, hvor Posts resultater blev præsenteret fra forskellige positioner og i en mere tilgængelig form. I 1980'erne lykkedes det en række forskere på én gang ved hjælp af forskellige tilgange og forskellige teknikker at få ret kompakte beviser for Posts resultater. Den algebraiske tilgang til studiet af lukkede klasser af boolske funktioner (subalgebraer af den iterative postalgebra over et sæt ) tilhører A. I. Maltsev . ${\mathsf {B}}=\{0,1\}$

Postalgebra og lukkede klasser

En boolsk funktion er en funktion af type , hvor , og er ariteten af . Antallet af forskellige aritetsfunktioner er lig med , mens det samlede antal forskellige boolske funktioner er uendeligt. Det er dog indlysende, at mange funktioner kan udtrykkes i form af andre ved hjælp af superpositionsoperatoren . For eksempel har det længe været kendt, at fra disjunktion og negation er det muligt, ved hjælp af de Morgans love , at opnå en konjunktion . Derudover kan enhver boolsk funktion repræsenteres som en DNF , det vil sige i form af konjunktion, disjunktion og negation. Et naturligt spørgsmål opstår: hvordan bestemmer man, om et givet sæt funktioner vil være tilstrækkeligt til at repræsentere en boolsk funktion? Sådanne sæt kaldes funktionelt komplette . Posts sætning besvarer dette spørgsmål. Da sætningens betingelse er nødvendig og tilstrækkelig, kaldes den også et kriterium . ${\mathsf {B}}^{n}\to {\mathsf {B}}$ ${\mathsf {B}}=\{0,1\}$ $n$ $n$ $2^{{2^{n}}}$

Ideen med sætningen er at betragte mængden af alle boolske funktioner som en algebra med hensyn til driften af superposition . Nu bærer den navnet Post algebra . Denne algebra indeholder, som dens subalgebraer, sæt af funktioner, der er lukket under superposition. De kaldes også lukkede klasser . Lad være en delmængde af . Lukningen af et sæt er den minimale subalgebra indeholdende . Med andre ord består lukningen af alle funktioner, der er superpositioner . Det vil naturligvis være funktionelt komplet, hvis og kun hvis . Spørgsmålet om, hvorvidt en given klasse er funktionelt komplet, kommer således ned til at kontrollere, om dens lukning er den samme som . ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$ $[R]$ $R$ ${\mathsf {PA}}$ $R$ $R$ $R$ $[R]={\mathsf {PA}}$ ${\mathsf {PA}}$

Operatøren er en lukningsoperatør . Med andre ord har den (blandt andre) egenskaberne: $[\_]$

$R\subseteq [R]$ ( omfang )
$R_{1}\subseteq R_{2}\Rightarrow [R_{1}]\subseteq [R_{2}]$ ( montoni )
$[[R]]=[R]$ ( idempotens )

Det siges, at et sæt funktioner genererer en lukket klasse (eller en klasse er genereret af et sæt funktioner ), hvis . Et sæt funktioner kaldes en basis for en lukket klasse, hvis og for en hvilken som helst delmængde af sættet udover . $Q$ $R$ $R$ $Q$ $[Q]=R$ $Q$ $R$ $[Q]=R$ $[Q_{1}]\neq R$ $Q_1$ $Q$ $Q$

Hvis vi tilføjer et element, der ikke hører til en subalgebra , der ikke hører til den, og danner en lukning, vil resultatet være en ny subalgebra, der indeholder den givne. Samtidig vil det falde sammen med , hvis og kun hvis der ikke er andre subalgebraer mellem den oprindelige subalgebra og , altså hvis den oprindelige subalgebra var maksimal. For at kontrollere, at et givet sæt funktioner er funktionelt komplet, er det således tilstrækkeligt at verificere, at det ikke helt tilhører nogen af de maksimale subalgebraer . Det viser sig, at der kun er fem sådanne subalgebraer, og spørgsmålet om at tilhøre dem kan løses enkelt og effektivt. ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ ${\mathsf {PA}}$ $R$ ${\mathsf {PA}}$

Dualitet, monotoni, linearitet. Fuldstændighedskriterium

Det følgende er nogle af de følger, der følger af dobbeltfunktionssætningerne .

Hvis er en lukket klasse , så er det også en lukket klasse . $R$ $R^{*}$
Sættet danner en lukket klasse . $S$
Hvis , så . Især hvis er grundlaget for klassen , så er grundlaget for klassen . $R=[Q]$ $R^{*}=[~Q^{*}]$ $Q$ $R$ $Q^{*}$ $R^{*}$

Vi vender os nu til at afklare fuldstændigheden af specifikke sæt funktioner.

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

En funktion siges at være nul -bevarende hvis . Klassen af sådanne funktioner kaldes . $f(x_{1},x_{2},\ldots,x_{n})$ $f(0,0,\ldprikker ,0)=0$ $T_{0}$
En funktion siges at være enhedsbevarende, hvis . Klassen af sådanne funktioner kaldes . $f(x_{1},x_{2},\ldots,x_{n})$ $f(1,1,\ldprikker ,1)=1$ $T_{1}$
En funktion kaldes selv-dual , hvis den tager modsatte værdier på modsatte sæt, det vil sige , at identiteten gælder for en selv-dual funktion . Klassen af sådanne funktioner kaldes . $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$
Funktionen kaldes monoton : . Klassen af sådanne funktioner kaldes . $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n })\Højrepil 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 kaldes lineær , når den kan repræsenteres af et Zhegalkin-polynomium af første grad, dvs. Klassen af sådanne funktioner kaldes . $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$

Lukkethedsteorem for hovedklasserne af funktioner

Bemærk, at ingen af de lukkede klasser er helt indeholdt i foreningen af de andre fire. Dette følger af følgende forhold: ${\displaystyle S,M,L,T_{0},T_{1))$

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

Enhver ikke-triviel (bortset fra ) lukket klasse af booleske funktioner er fuldstændig indeholdt i mindst én af klasserne . $P_2$ ${\displaystyle S,M,L,T_{0},T_{1))$

Ordlyden af kriteriet

Et system af boolske funktioner F er komplet, hvis og kun hvis det ikke helt tilhører nogen af de lukkede klasser . ${\displaystyle S,M,L,T_{0},T_{1))$

Det vil sige, når fem funktioner kan implementeres i det: ikke-selv-dual, ikke-monotone, ikke-lineær, ikke-bevarende 0 og ikke-bevarende 1.

Bevis

Beviset for Posts kriterium er baseret på, at systemet af funktioner ( OG , ELLER og IKKE ) er komplet. Ethvert system, hvori disse tre funktioner er implementeret, er således også komplet. Lad os bevise, at i et system, der opfylder Post-kriteriet, er det altid muligt at implementere konjunktion , disjunktion og negation .

Med en funktion, der ikke gemmer 0, får vi en inverter eller en konstant 1

Overvej en funktion, der ikke tilhører klassen T 0 . For hende

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

Denne funktion hører muligvis ikke til klassen T 1 .

I det første tilfælde, så har vi også en enhedskonstant. $f(1,1,...,1)=1,$ $f(x,x,...,x)=1,$
I det andet tilfælde, så har vi også en inverter. $f(1,1,...,1)=0,$ $f(x,x,...,x)={\overline {x)),$

Med en funktion, der ikke lagrer 1, får vi en inverter eller en konstant 0

Overvej en funktion, der ikke tilhører klassen T 1 . For hende

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

Denne funktion hører muligvis ikke til klassen T 0 .

I det første tilfælde, så har vi også en nulkonstant. $f(0,0,...,0)=0,$ $f(x,x,...,x)=0,$
I det andet tilfælde, så har vi også en inverter. $f(0,0,...,0)=1,$ $f(x,x,...,x)={\overline {x)),$

Med en inverter og en ikke-selv-dual funktion får vi en af konstanterne

Overvej en funktion, der ikke tilhører klassen S af selv-duale funktioner. Til det er der sådan et sæt inputvariabler X, der

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

Lad for eksempel så har vi også konstanten 1. $f(0,1,0)=f(1,0,1)=1,$ $f(x,{\overline {x)),x)=1$

På samme måde, hvis for eksempel, så har vi også konstanten 0. $f(0,0,0,1)=f(1,1,1,0)=0,$ $f(x,x,x,{\overline {x)))=0$

Under alle omstændigheder, med en inverter og en ikke-selv-dual funktion, kan vi få en af konstanterne.

Givet en inverter og en af konstanterne får vi en anden konstant

Hvis vi i et af ovenstående tilfælde fik en inverter og en af konstanterne, får vi den anden konstant ved hjælp af inverteren: eller ${\overline {0}}=1$ ${\overline {1}}=0.$

Med en ikke-monotonisk funktion og begge konstanter får vi en inverter

For en ikke-monotonisk funktion skal der være et sæt inputvariabler, således at

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

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

Lad for eksempel og . Så . $f(1,1,0)=0$ $f(1,0,0)=1$ $f(1,x,0)={\overline {x}}$

Under alle omstændigheder, med en ikke-monotonisk funktion og begge konstanter, kan vi få en inverter.

Vi har en inverter og begge konstanter

I de foregående underafsnit gennemgik vi alle mulige muligheder (se figur) og kom til den konklusion, at med funktioner, der ikke hører til klasserne T 0 , T 1 , S og M, kan vi altid få inverteren og begge konstanter i forskellige måder.

Givet en ikke-lineær funktion, en inverter og en konstant 1, får vi konjunktionen

Per definition har en ikke-lineær funktion mindst ét led i Zhegalkin-polynomiet , der indeholder en konjunktion af flere variable. Lad for eksempel være en ikke-lineæ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}.

Lad os sætte os som mål at konstruere en konjunktion på dens grundlag $c(x_{1},x_{2})=x_{1}x_{2}.$

Tildel værdierne 1 til variablerne , 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}.

Det er klart, at vi i det generelle tilfælde efter en sådan transformation får en funktion af formen

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

hvor de firkantede parenteser betyder, at det udtryk, de fremhæver, måske er til stede i det endelige udtryk.

I det enkleste tilfælde, i mangel af andre medlemmer, får vi straks en konjunktion: $f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.$

Lad os overveje andre muligheder.

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

Ethvert af disse udtryk kan ved hjælp af en inverter reduceres til en konjunktion.

Med en ikke-lineær funktion, en inverter og en konstant 1 kan du således altid få en konjunktion.

Givet en konjunktion og en inverter, får vi en disjunktion

Givet en inverter og en konjunktion, kan du altid få en disjunktion:

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

Sætningen er blevet bevist.

Konsekvens

En funktion alene er et komplet system, hvis og kun hvis: $f$

$f(0,0,...,0)=1$
$f(1,1,...,1)=0$
$f$ er ikke selv-dual

Eksempler på funktioner, der alene er et komplet system, ville være Schaeffers streg og Pierces pil . $x|y={\overline {x\operatørnavn {\&} y))$ $x\downarrow y={\overline {x\vee y))$

Sætning om det maksimale antal funktioner i en basis

Det maksimale antal funktioner i grundlaget for logikkens algebra er 4 [1] .

Bevis

1) Lad os bevise, at det fra ethvert komplet system af funktioner er muligt at udskille et komplet delsystem, der ikke består af mere end fire funktioner.

Ifølge Posts kriterium skal fem funktioner være til stede i et komplet system:

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

Lad os overveje en funktion . To tilfælde er mulige: ${\displaystyle f_{0))$

$f_{0}\in T_{1},$ derefter : og systemet er færdigt. $f_{0}\ikke \i S$ $[f_{0},f_{1},f_{M},f_{L}]$
$f_{0}\ikke \i T_{1},$ derefter : og systemet er færdigt. ${\displaystyle f_{0}\ikke \i M,T_{1))$ $[f_{0},f_{S},f_{L}]$

2) Lad os vise, at der er grundlag for fire funktioner. Overvej et system af funktioner . Dette system er komplet: ${\displaystyle \{0,1,x\cdot y,x\oplus y\oplus z\))$

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

Ingen af dens undersystemer er dog komplette:

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

Sætningen er blevet bevist.

Noter

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

Litteratur

Marchenkov S. S. Lukkede klasser af booleske funktioner. — M .: Fizmatlit, 2000.
Fujisawa T., Kasami T. Matematik for radioingeniører: teori om diskrete strukturer. - M . : Radio og kommunikation, 1984. - 240 s.
Alekseev V. B. Diskret matematik (II semester) . - M., Moscow State University, 2002. - 44 s.
Belousov A. I., Tkachev S. B. Diskret matematik. - M. : MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .
Gindikin S. G. Algebra af logik i opgaver. - M. : Nauka, 1972. - 288 s.

Postkriterier

Postalgebra og lukkede klasser

Dualitet, monotoni, linearitet. Fuldstændighedskriterium

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

Lukkethedsteorem for hovedklasserne af funktioner

Ordlyden af kriteriet

Bevis

Med en funktion, der ikke gemmer 0, får vi en inverter eller en konstant 1

Med en funktion, der ikke lagrer 1, får vi en inverter eller en konstant 0

Med en inverter og en ikke-selv-dual funktion får vi en af konstanterne

Givet en inverter og en af konstanterne får vi en anden konstant

Med en ikke-monotonisk funktion og begge konstanter får vi en inverter

Vi har en inverter og begge konstanter

Givet en ikke-lineær funktion, en inverter og en konstant 1, får vi konjunktionen

Givet en konjunktion og en inverter, får vi en disjunktion

Konsekvens

Sætning om det maksimale antal funktioner i en basis

Bevis

Noter

Litteratur

Links

Se også

Postkriterier

Postalgebra og lukkede klasser

Dualitet, monotoni, linearitet. Fuldstændighedskriterium

Hovedfunktionsklasser:

Lukkethedsteorem for hovedklasserne af funktioner

Ordlyden af ​​kriteriet

Bevis

Med en funktion, der ikke gemmer 0, får vi en inverter eller en konstant 1

Med en funktion, der ikke lagrer 1, får vi en inverter eller en konstant 0

Med en inverter og en ikke-selv-dual funktion får vi en af ​​konstanterne

Givet en inverter og en af ​​konstanterne får vi en anden konstant

Med en ikke-monotonisk funktion og begge konstanter får vi en inverter

Vi har en inverter og begge konstanter

Givet en ikke-lineær funktion, en inverter og en konstant 1, får vi konjunktionen

Givet en konjunktion og en inverter, får vi en disjunktion

Konsekvens

Sætning om det maksimale antal funktioner i en basis

Bevis

Noter

Litteratur

Links

Se også

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

Ordlyden af kriteriet

Med en inverter og en ikke-selv-dual funktion får vi en af konstanterne

Givet en inverter og en af konstanterne får vi en anden konstant