За́мкнений клас фу́нкцій а́лгебри ло́гіки — така множина P функцій алгебри логіки, замикання якої відносно операції суперпозиції збігається з ним самим, тобто [P] = P.
Тобто, довільна функція, яку можна представити формулою з використанням функцій множини P, також входить в цю множину:
- (замкнутість щодо заміни змінних);
- (замкнутість щодо суперпозиції).
Замкненим класом функцій алгебри логіки є, наприклад, клас всіх функцій алгебри логіки.
В 1941 році Еміль Пост надав повний опис замкнених класів, який назвали решіткою Поста.
Приклади
Особливо важливими замкнутими класами є так звані передповні класи:
- клас функцій, що зберігають константу 0:
. - клас функцій, що зберігають константу 1:
. - клас самодвоїстих функцій:
. - клас монотоних функцій:
. - клас лінійних функцій:
.
Ні один з передповних класів не міститься повністю в об'єднанні чотирьох інших класів; довільний замкнутий клас, відмінний від , повністю міститься в хоча б в одному з п'яти передповних класів.
Іншими важливими замкнутими класами є:
- Клас кон'юнкцій K, що є замиканням множини операцій . Він являє собою множину функцій виду .
- Класс диз'юнкцій D, що є замиканням множини операцій . Він являє собою множину функцій виду .
- Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).
- Клас функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.
- Класс функцій, для яких виконується умова .
- Класс функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.
- Класс функцій, для яких виконується умова .
В 1941 році Еміль Пост показав, що довільний замкнутий клас є перетином скінченної кількості вищеописаних класів. Також Пост встановив, що довільний замкнутий клас може бути порождений скінченним базисом.
Властивості
- Перетин замкнутих класів є замкнутим класом.
- Об'єднання замкнутих класів може не бути замкнутим класом.
- Доповнення замкнутого класа булевих функцій до множини всіх булевих функцій не є замкнутим класом.
Повні класи
Множина A функцій алгебри логіки називається повною системою, якщо її замикання збігається з множиною всіх функцій (для двозначної логіки [A] = P2).
Критерій Поста формулює необхідну і достатнью умову повноти для системи функцій.
- Система булевих функцій є повною тоді і тільки тоді, коли вона не міститься повністю ні в одному із передповних класів, тобто , , , , .
Повна система називається базисом, якщо вона перестає бути повною при виключенні з неї довільної функції.
Прикладами повних систем із однієї функції є штрих Шефера та стрілка Пірса.
Широко відомими є такі повні системи булевих функцій:
- (кон'юнкція, диз'юнкція, заперечення) — відповідно до законів де Моргана не є базисом (кон'юнкцію чи диз'юнкцію можна виключити);
- (кон'юнкція, виключна диз'юнкція, константа 1) — є базисом.
Перша система використовується для представлення булевих функцій у вигляді диз'юнктивних та кон'юнктивних нормальных форм, друга — для представлення у вигляді поліномів Жегалкіна.
Максимальна кількість булевих функцій в базисі — 4.
Деколи говорять про систему функцій повну в деякому класі, а також про базис цього класу. Наприклад, систему можна назвати базисом класа лінійних функцій.
Література
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Za mknenij klas fu nkcij a lgebri lo giki taka mnozhina P funkcij algebri logiki zamikannya yakoyi vidnosno operaciyi superpoziciyi zbigayetsya z nim samim tobto P P Tobto dovilna funkciya yaku mozhna predstaviti formuloyu z vikoristannyam funkcij mnozhini P takozh vhodit v cyu mnozhinu f x1 xn P f xi1 xin P displaystyle forall f x 1 ldots x n in P f x i 1 ldots x i n in P zamknutist shodo zamini zminnih f x1 xn gi x1 xn P f x1 gi x1 xn xn P displaystyle forall f x 1 ldots x n g i x 1 ldots x n in P f x 1 ldots g i x 1 ldots x n ldots x n in P zamknutist shodo superpoziciyi Zamknenim klasom funkcij algebri logiki ye napriklad klas P2 displaystyle P 2 vsih funkcij algebri logiki V 1941 roci Emil Post nadav povnij opis zamknenih klasiv yakij nazvali reshitkoyu Posta PrikladiOsoblivo vazhlivimi zamknutimi klasami ye tak zvani peredpovni klasi klas funkcij sho zberigayut konstantu 0 T0 f x1 xn f 0 0 0 displaystyle T 0 left f x 1 dots x n f 0 dots 0 0 right klas funkcij sho zberigayut konstantu 1 T1 f x1 xn f 1 1 1 displaystyle T 1 left f x 1 dots x n f 1 dots 1 1 right klas samodvoyistih funkcij S f x1 xn f x1 xn f x1 xn displaystyle S left f x 1 dots x n f overline x 1 dots overline x n overline f x 1 dots x n right klas monotonih funkcij M f x1 xn i ai bi f a1 an f b1 bn displaystyle M left f x 1 dots x n forall i a i leq b i Rightarrow f a 1 dots a n leq f b 1 dots b n right klas linijnih funkcij L f x1 xn f x1 xn a0 a1x1 anxn ai 0 1 displaystyle 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 Ni odin z peredpovnih klasiv ne mistitsya povnistyu v ob yednanni chotiroh inshih klasiv dovilnij zamknutij klas vidminnij vid P2 displaystyle P 2 povnistyu mistitsya v hocha b v odnomu z p yati peredpovnih klasiv Inshimi vazhlivimi zamknutimi klasami ye Klas kon yunkcij K sho ye zamikannyam mnozhini operacij 0 1 displaystyle wedge 0 1 Vin yavlyaye soboyu mnozhinu funkcij vidu c0 c1 x1 cn xn displaystyle c 0 wedge c 1 vee x 1 wedge ldots wedge c n vee x n Klass diz yunkcij D sho ye zamikannyam mnozhini operacij 0 1 displaystyle vee 0 1 Vin yavlyaye soboyu mnozhinu funkcij vidu c0 c1 x1 cn xn displaystyle c 0 vee c 1 wedge x 1 vee ldots vee c n wedge x n Klas U funkcij odnoyi zminnoyi sho mistit tilki konstanti zaperechennya ta selektor funkciyu sho totozhna odnij zi svoyih zminnih Klas Om displaystyle O m funkcij m naturalne chislo bilshe odinici v yakih dlya dovilnih m naboriv na yakih funkciya rivna nulyu znajdetsya zminna yaka tezh rivna nulyu na vsih cih naborah Klass O displaystyle O infty funkcij dlya yakih vikonuyetsya umova f x1 xn xi displaystyle f x 1 ldots x n geq x i Klass Im displaystyle I m funkcij m naturalne chislo bilshe odinici v yakih dlya dovilnih m naboriv na yakih funkciya rivna 1 znajdetsya zminna yaka tezh rivna 1 na vsih cih naborah Klass I displaystyle I infty funkcij dlya yakih vikonuyetsya umova f x1 xn xi displaystyle f x 1 ldots x n leq x i V 1941 roci Emil Post pokazav sho dovilnij zamknutij klas ye peretinom skinchennoyi kilkosti visheopisanih klasiv Takozh Post vstanoviv sho dovilnij zamknutij klas mozhe buti porozhdenij skinchennim bazisom VlastivostiPeretin zamknutih klasiv ye zamknutim klasom Ob yednannya zamknutih klasiv mozhe ne buti zamknutim klasom Dopovnennya zamknutogo klasa bulevih funkcij do mnozhini vsih bulevih funkcij P2 displaystyle P 2 ne ye zamknutim klasom Povni klasiMnozhina A funkcij algebri logiki nazivayetsya povnoyu sistemoyu yaksho yiyi zamikannya zbigayetsya z mnozhinoyu vsih funkcij dlya dvoznachnoyi logiki A P2 Kriterij Posta formulyuye neobhidnu i dostatnyu umovu povnoti dlya sistemi funkcij Sistema bulevih funkcij ye povnoyu todi i tilki todi koli vona ne mistitsya povnistyu ni v odnomu iz peredpovnih klasiv tobto T0 displaystyle T 0 T1 displaystyle T 1 S displaystyle S M displaystyle M L displaystyle L Povna sistema nazivayetsya bazisom yaksho vona perestaye buti povnoyu pri viklyuchenni z neyi dovilnoyi funkciyi Prikladami povnih sistem iz odniyeyi funkciyi ye shtrih Shefera ta strilka Pirsa Shiroko vidomimi ye taki povni sistemi bulevih funkcij displaystyle left land lor neg right kon yunkciya diz yunkciya zaperechennya vidpovidno do zakoniv de Morgana ne ye bazisom kon yunkciyu chi diz yunkciyu mozhna viklyuchiti 1 displaystyle left land oplus 1 right kon yunkciya viklyuchna diz yunkciya konstanta 1 ye bazisom Persha sistema vikoristovuyetsya dlya predstavlennya bulevih funkcij u viglyadi diz yunktivnih ta kon yunktivnih normalnyh form druga dlya predstavlennya u viglyadi polinomiv Zhegalkina Maksimalna kilkist bulevih funkcij v bazisi 4 Dekoli govoryat pro sistemu funkcij povnu v deyakomu klasi a takozh pro bazis cogo klasu Napriklad sistemu 1 displaystyle left oplus 1 right mozhna nazvati bazisom klasa linijnih funkcij Literatura Enciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973