Zárt logikai függvényosztályok

A Boole-függvények elméletében egy zárt osztály a logikai algebra függvényeinek halmaza , amelynek lezárása a szuperpozíció műveletére nézve önmagával egybeesik: . Más szóval, minden függvény, amely egy képlettel kifejezhető halmazfüggvényekkel , ismét benne van ugyanabban a halmazban. $P$ $[P]=P$ $P$

1941-ben Emil Post bemutatta a zárt osztályrendszer teljes leírását, amelyet Posta rácsnak is neveznek .

Függvényzárási tulajdonságok változókkal

Bármely halmaz a lezárásának egy részhalmaza : . $A\subseteq [A]$
A részhalmaz lezárása a lezárás részhalmaza: . Meg kell jegyezni, hogy a halmazok szigorú beágyazása csak a lezárásaik nem szigorú beágyazását jelenti: . $A\subseteq B\Jobbra [A]\alseteq [B]$
$A\alkészlet B\Jobbra [A]\alkészlet [B]$
A záróművelet többszöri alkalmazása egyetlen alkalmazásnak felel meg: . $[[A]]=[A]$

Példák zárt osztályokra

Az összes lehetséges logikai függvény halmaza zárva van. $P_2$

A Boole-függvények elmélete szempontjából különösen fontosak a következő zárt osztályok, amelyeket prekomplett osztályoknak neveznek :

A 0 állandót megőrző függvényosztály: . $T_{0}$
$T_{0}=\left\{f(x_{1},\pontok ,x_{n})|f(0,\pontok ,0)=0\jobbra\}$
Az 1 állandót megőrző függvényosztály: . $T_{1}$
$T_{1}=\left\{f(x_{1},\pontok ,x_{n})|f(1,\pontok ,1)=1\jobbra\}$
Az ön-kettős függvények osztálya : . $S$
$S=\left\{f(x_{1},\dots ,x_{n})|f(\overline {x_{1}},\dots ,\overline {x_{n}})=\overline {f (x_{1},\pontok ,x_{n})}\jobbra\}$
A monoton Boole-függvények osztálya : . $M$
$M=\left\{f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Jobbra f(a_{1},\dots ,a_ {n})\leq f(b_{1},\pontok ,b_{n})\jobbra\}$
Lineáris logikai függvényosztály : . $L$
$L=\left\{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}\in \{0,1\}\right\}$

A , kivételével a logikai függvények bármely zárt osztálya teljes egészében benne van az öt előre befejezett osztály legalább egyikében . $P_2$

További fontos zárt órák:

A K kötőszók osztálya, amely a halmaz lezárása . Ez az űrlap függvényeinek halmaza . $\{\ék ,0,1\}$ $c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})$
D diszjunkciós osztály, amely a halmaz lezárása . Ez az űrlap függvényeinek halmaza . $\{\vee ,0,1\}$ $c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})$
Egy U változó függvényosztálya, amely csak konstansokat, negációt és egy szelektort tartalmaz (egy függvény, amely megegyezik az egyik argumentumával minden értékhalmazon).
Függvényosztály ( m egynél nagyobb természetes szám), amely teljesíti a következő feltételt: minden m halmazhoz, amelyen a függvény nulla értéket vesz fel, van egy változó, amely szintén nulla értéket vesz fel ezeken a halmazokon. $O^{m}$
A függvényosztály, amelyre a feltétel teljesül , ahol a függvényváltozók egyike. $O^{\infty }$ $f(x_{1},\ldots ,x_{n})\geq x_{i}$ $x_{i}$
A függvényosztály (m egynél nagyobb természetes szám), amely eleget tesz a következő feltételnek: minden m halmazhoz, amelyen a függvény egységértéket vesz fel, van olyan változó, amely az összes ilyen halmaz egységértékét is felveszi. $én^{m}$
A függvényosztály, amelyre a feltétel teljesül , ahol a függvényváltozók egyike. $én^{\infty }$ $f(x_{1},\ldots ,x_{n})\leq x_{i}$ $x_{i}$

1941-ben Emil Post kimutatta, hogy a Boole-függvények bármely zárt osztálya a fent leírt osztályok véges számú metszéspontja, teljes leírást adva a kétértékű logika zárt osztályainak szerkezetéről. Post azt is megállapította, hogy véges bázissal bármilyen zárt osztály generálható.

A zárt osztályok néhány tulajdonsága

A zárt osztályok nem üres metszéspontja ismét zárt osztály.
A zárt osztályok szövetsége nem lehet zárt osztály.
A nem csak konstansokat tartalmazó Boole-függvények zárt osztálya szükségszerűen tartalmaz egy azonos függvényt.
A Boole-függvények zárt osztályának kiegészítése az összes Boole-függvény halmazával nem zárt osztály. $P_2$

Komplett funkciórendszerek

A logikai algebra függvényhalmazát teljes rendszernek nevezzük, ha ennek a halmaznak a lezárása egybeesik az összes függvény halmazával. (Különösen a kétértékű logikára .) Más szóval, a logikai algebra bármely függvényét ki lehet fejezni halmazfüggvényeket használó képlettel . $A$ $[A]=P_{2}$ $A$

Post kritériuma egy szükséges és elégséges feltételt fogalmaz meg egy logikai függvényrendszer
teljességéhez: A Boole-függvények rendszere akkor és csak akkor teljes, ha nem tartalmazza teljes egészében a , , , osztályok egyikében sem . $T_{0}$ $T_{1}$ $S$ $M$ $L$
Különösen, ha egy függvény nem szerepel a Post egyik osztályában sem, akkor önmagában egy teljes rendszert alkot. Példa erre a Schaeffer-függvény (a konjunkció tagadása ).

A Boole-függvények alábbi teljes rendszerei széles körben ismertek:

$\left\{\land ,\lor ,\neg \right\}$ ( kötőszó , diszjunkció , tagadás );
$\left\{\land ,\oplus ,1\right\}$ (kötőszó, modulo 2 összeadás , konstans 1);
$\left\{\land ,\neg \right\}$ ( kötőszó , tagadás );
$\left\{\vagy ,\neg \jobbra\}$ ( diszjunkció , tagadás );
$\left\{\downarrow \right\}$ ( Pierce nyíl );
$\left\{|\right\}$ ( Scheffer stroke ).

Az első rendszert például a függvények diszjunktív és konjunktív normálalak formájában való ábrázolására használják, a másodikat pedig Zhegalkin polinomok formájában .

Kevésbé ismert egyéb teljes logikai függvényrendszerek:

$\left\{\jobbra nyíl ,\neg \jobbra\}$ ( implikáció , tagadás );
$\left\{\rightarrow ,\oplus \right\}$ ( implikáció , modulo 2 összeadás );
$\left\{\jobbra ,0\jobbra\}$ ( implikáció , konstans 0);

A teljes függvényrendszert bázisnak nevezzük, ha megszűnik teljesnek lenni, amikor bármely elemet kizárunk belőle. A fent említett teljes rendszerek közül az első nem alap, hiszen de Morgan törvényei szerint akár a diszjunkció, akár a konjunkció kizárható a rendszerből, és a maradék két függvény segítségével visszaállítható. A második rendszer az alap – mindhárom eleme szükséges a teljességhez. A Boole-függvények maximális száma a bázisban 4 lehet.

Néha olyan függvényrendszerről beszélünk, amely valamely zárt osztályban teljes, és ennek megfelelően ennek az osztálynak az alapjáról. Például a rendszert nevezhetjük egy lineáris függvényosztály alapjának. $\left\{\oplus ,1\right\}$

Jegyzetek

Irodalom

Yablonsky SV Bevezetés a diszkrét matematikába. - M .: Nauka, 1986.
Marchenkov S. S. Boole-függvények zárt osztályai. - M .: Fizmatlit, 2000.
Gavrilov G. P., Sapozhenko A. A. Feladatgyűjtemény a diszkrét matematikában. — M.: Nauka. – 1969
Alekseev V. B. Diszkrét matematika (előadások kurzusa, II. félév). Összeg. A. D. Poszpelov
Akhmetova N.A., Usmanova Z.M. Diszkrét matematika, a logikai algebra függvényei.