Forudfyldte klasser

En prækomplet klasse i teorien om boolske funktioner er en lukket klasse af boolske funktioner , der har følgende egenskab: lukningen af foreningen af denne klasse med enhver boolsk funktion , der ikke tilhører den, genererer alle . Sættet af prækomplette klasser af boolske funktioner er udtømt af listen: $P_2$

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 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\}$
Klassen af lineære funktioner — repræsenteret ved Zhegalkin-polynomiet af første grad: . $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\}$

Man taler også om forfuldstændigheden af en lukket klasse i en anden. En klasse A er besat i klasse B, hvis lukningen af klasse A med en funktion, der hører til B, men ikke hører til A, genererer klasse B. For eksempel er klassen besat i klasserne og . $M\cap T_{0}$ $T_{0}$ $M$

I flerværdilogik defineres prækomplette klasser på samme måde som lukkede klasser, der har den egenskab , at lukningen af foreningen af denne klasse med enhver funktion fra , der ikke tilhører den, genererer alle . Men i tilfælde af k>2 er der i øjeblikket ingen generel beskrivelse af strukturen af prækomplette klasser, i modsætning til to-værdi logik. $P_{k}$ $P_{k}$

Litteratur

Yablonsky SV Introduktion til diskret matematik. — M.: Nauka. – 1986