Кукон давлат педагогика институти

Таъриф: f (x,x...x) функция чизикли дейилади, агар куйдагича Жигалкин купхадлиги деб аталувчи даражаси бирдан катта булмаган купхад оркали ифодалаш мумкин булса, яъни f (x,x...x)= а₀+а₁x+а₂x+...+а_nx. Бу ерда а₀,а₁,а₂,...,а_n ноль ёки бирдан иборат булган доимийликдир. Барча чизикли функциялар синфини L оркали ифодалаймиз. Юкоридаги аникланган P₀,P,S,M,L системалар тула Буль функциясини ифодалашда мухим роль уйнайди. Дастлаб биз бу системаларни мухим булган хусусиятларини курстиб утамиз.

Таъриф: Буль функциялари системаси хос система дейилади, агар у буш булмаса, хамда барча Буль функциялари системаси билан хам усма-уст тушмаса.

Таъриф: Буль функциялар синфи ёпик синф ёки пост синф дейилади, агар бу синф унга кирувчи ихтиёрий функция билан унинг хар кандай суперпозициясини уз ичига олса.

Теорема: P₀, P, S, M, L синфлар хос булган ёпик Буль функциялари синфидир.

Шуни таъкидлаб утиш керакки, баъзи бир Буль функциялари курсатиб утилган синфларнинг бир нечтасига тегишли булиши мумкин. Баъзи бирлари эса умуман бирортасига хам тегишли булмаслиги мумкин.

Масалан: f(х)=х функция P₀, P, S, M, L ларнинг хар бирига тегишли.

Энди биз тула Буль системалари хакидаги куйдаги теоремаларни келтирамиз. Бу теорема 1921 йили Америкалик математик Э. Пост томонидан исботланган.

Теорема: {f₀ ,f₁ ,...,f_n} Буль функциялари системаси тула система булиши учун куйдаги шартларни бажарилиши зарур ва етарли.

Бу система ичида Р₀ синфга тегишли булмаган функция мавжуд:

Бу система ичида Р₁ синфга тегишли булмаган функция мавжуд:

Бу система ичида S синфга тегишли булмаган функция мавжуд:

Бу система ичида M синфга тегишли булмаган функция мавжуд:

Бу система ичида L синфга тегишли булмаган функция мавжуд.