Lukkede booleske funktionsklasser

En lukket klasse i teorien om boolske funktioner er et sæt funktioner af logikkens algebra , hvis lukning med hensyn til driften af superposition falder sammen med sig selv: . Med andre ord er enhver funktion, der kan udtrykkes med en formel ved hjælp af sætfunktioner, igen inkluderet i det samme sæt. $P$ $[P]=P$ $P$

I 1941 præsenterede Emil Post en komplet beskrivelse af det lukkede klassesystem, også kaldet Postgitteret .

Funktionslukningsegenskaber med variabler

Ethvert sæt er en delmængde af dets lukning: . $A\subseteq [A]$
En delmængdelukning er en delmængde af en lukning: . Det skal bemærkes, at den strenge indlejring af sæt kun indebærer en ikke-streng indlejring af deres lukninger: . $A\subseteq B\Højrepil [A]\subseteq [B]$
$A\undersæt B\Højrepil [A]\undersæt [B]$
Flere påføringer af lukkeoperationen svarer til en enkelt påføring: . $[[A]]=[A]$

Eksempler på lukkede klasser

Sættet af alle mulige booleske funktioner er lukket. $P_2$

Af særlig betydning for teorien om boolske funktioner er følgende lukkede klasser, kaldet prækomplette klasser :

Klassen af funktioner, der bevarer konstanten 0: . $T_{0}$
$T_{0}=\venstre\{f(x_{1},\dots ,x_{n})|f(0,\dots ,0)=0\right\}$
Klassen af funktioner, der bevarer konstanten 1: . $T_{1}$
$T_{1}=\venstre\{f(x_{1},\dots ,x_{n})|f(1,\dots ,1)=1\right\}$
Klassen af selvdobbelte funktioner : . $S$
$S=\venstre\{f(x_{1},\dots,x_{n})|f(\overline {x_{1}},\dots,\overline {x_{n}})=\overline {f (x_{1},\dots,x_{n})}\right\}$
Klasse af monotone booleske funktioner :. $M$
$M=\venstre\{f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Højrepil f(a_{1},\dots ,a_ {n})\leq f(b_{1},\dots ,b_{n})\right\}$
Lineær boolesk funktionsklasse :. $L$
$L=\venstre\{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}\i \{0,1\}\right\}$

Enhver lukket klasse af boolske funktioner bortset fra , er fuldstændig indeholdt i mindst én af de fem prækomplette klasser . $P_2$

Andre vigtige lukkede klasser er:

Klassen af konjunktioner K, som er slutningen af sættet . Det er et sæt funktioner i formen . $\{\kile ,0,1\}$ $c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})$
Disjunction klasse D, som er lukningen af sættet . Det er et sæt funktioner i formen . $\{\vee ,0,1\}$ $c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})$
Klasse af funktioner af en variabel U, der kun indeholder konstanter, negation og en selektor (en funktion svarende til et af dens argumenter på alle sæt af deres værdier).
En klasse af funktioner (m er ethvert naturligt tal større end én), der opfylder følgende betingelse: for ethvert m sæt, hvor funktionen har en nulværdi, er der en variabel, der også har en nulværdi på alle disse sæt. $O^{m}$
Klassen af funktioner, for hvilken betingelsen er opfyldt , hvor er en af funktionsvariablerne. $O^{\infty }$ $f(x_{1},\ldots,x_{n})\geq x_{i}$ $x_{i}$
Klassen af funktioner (m er ethvert naturligt tal større end én), der opfylder følgende betingelse: for alle m sæt, hvor funktionen tager enhedsværdien, er der en variabel, der også tager enhedsværdien på alle disse mængder. $I^{m}$
Klassen af funktioner, for hvilken betingelsen er opfyldt , hvor er en af funktionsvariablerne. $I^{\infty }$ $f(x_{1},\ldots,x_{n})\leq x_{i}$ $x_{i}$

I 1941 viste Emil Post , at enhver lukket klasse af boolske funktioner er skæringspunktet mellem et endeligt antal af klasserne beskrevet ovenfor, hvilket giver en fuldstændig beskrivelse af strukturen af de lukkede klasser af to-værdi logik. Post fastslog også, at enhver lukket klasse kan genereres på en endelig basis.

Nogle egenskaber for lukkede klasser

Et ikke- tomt kryds af lukkede klasser er igen en lukket klasse.
Sammenslutningen af lukkede klasser må ikke være en lukket klasse.
En lukket klasse af booleske funktioner, der ikke kun indeholder konstanter, indeholder nødvendigvis en identisk funktion.
Komplementet af en lukket klasse af boolske funktioner til sættet af alle boolske funktioner er ikke en lukket klasse. $P_2$

Komplet systemer af funktioner

Et sæt funktioner i logikkens algebra kaldes et komplet system, hvis lukningen af dette sæt falder sammen med sættet af alle funktioner. (Især for logik med to værdier .) Med andre ord bør det være muligt at udtrykke enhver funktion af logikkens algebra ved hjælp af en formel ved hjælp af sætfunktioner . $EN$ $[A]=P_{2}$ $EN$

Posts kriterium formulerer en nødvendig og tilstrækkelig betingelse for fuldstændigheden af et system af boolske funktioner:
Systemet af boolske funktioner er komplet, hvis og kun hvis det ikke er helt indeholdt i nogen af klasserne , , , , . $T_{0}$ $T_{1}$ $S$ $M$ $L$
Især hvis en funktion ikke er inkluderet i nogen af Posts klasser, danner den et komplet system i sig selv. Et eksempel er Schaeffer-funktionen (negation af konjunktion ).

Følgende komplette systemer med booleske funktioner er almindeligt kendte:

$\left\{\land ,\lor ,\neg \right\}$ ( konjunktion , disjunktion , negation );
$\left\{\land ,\oplus ,1\right\}$ (sammenhæng, modulo 2 addition , konstant 1);
$\left\{\land ,\neg \right\}$ ( konjunktion , negation );
$\left\{\lor ,\neg \right\}$ ( disjunktion , negation );
$\venstre\{\pil ned \højre\}$ ( Prince pil );
$\venstre\{|\højre\}$ ( Scheffer slagtilfælde ).

Det første system bruges for eksempel til at repræsentere funktioner i form af disjunktive og konjunktive normale former , det andet bruges til at repræsentere dem i form af Zhegalkin polynomier .

Mindre kendte andre komplette systemer med booleske funktioner:

$\left\{\rightarrow ,\neg \right\}$ ( implikation , negation );
$\left\{\rightarrow ,\oplus \right\}$ ( implikation , modulo 2-addition );
$\venstre\{\højrepil ,0\højre\}$ ( implikation , konstant 0);

Et komplet system af funktioner kaldes et grundlag, hvis det ophører med at være komplet, når ethvert element er udelukket fra det. Det første af de komplette systemer, der er nævnt ovenfor, er ikke et grundlag, da enten disjunktion eller konjunktion ifølge de Morgans love kan udelukkes fra systemet og gendannes ved hjælp af de resterende to funktioner. Det andet system er grundlaget - alle dets tre elementer er nødvendige for fuldstændigheden. Det maksimalt mulige antal booleske funktioner i basis er 4.

Nogle gange taler man om et system af funktioner, der er komplet i en lukket klasse, og følgelig om grundlaget for denne klasse. For eksempel kan systemet kaldes grundlaget for en klasse af lineære funktioner. $\left\{\oplus ,1\right\}$

Noter

Litteratur

Yablonsky SV Introduktion til diskret matematik. — M .: Nauka, 1986.
Marchenkov S. S. Lukkede klasser af booleske funktioner. — M .: Fizmatlit, 2000.
Gavrilov G. P., Sapozhenko A. A. Samling af problemer i diskret matematik. — M.: Nauka. - 1969
Alekseev V. B. Diskret matematik (forelæsningsforløb, II semester). Comp. A. D. Pospelov
Akhmetova N.A., Usmanova Z.M. Diskret matematik, funktioner i logikkens algebra.