Жегалкин полиномдары. Логика алгебрасының функциясының толықтығы туралы Пост теоремасы. Анықтама. Логика алгебрасының функциялар жиыны А берілсін. Егер кез келген логика алгебрасының функциясын А-да анықталған формулалар арқылы өрнектелсе, онда бұл жиынды логикалық амалдардың толық жүйесі деп атайды.
Теорема 3.6A жүйесі толық жүйе болады.
Дәлелдеуі. Егер берілген функция нөлден және бірден өзге болса, онда оның мінсіз дизъюнктивті қалыпты формасын таба аламыз. Ал функцияның МДҚФ-да тек А жүйесінен алынған амалдар ғана кездеседі. Функция нөлдік болған жағдайда ол формуласына, ал бірлік болғанда формуласына эквивалентті. Теорема дәлелденді.
Лемма 3.7 Егер А толық жүйе, ал оның кез келген функциясы басқа бір В жүйесінде анықталған формулалар арқылы өрнектелсе, онда В жүйесі де толық болады.
Дәлелдеуі. Кез келген логика алгебрасының функциясы мен екі және функциялар жүйелерін қарастырайық. жүйесі толық болғандықтан, функциясы осы жүйеде өрнектеледі. Яғни формуласы табылып, = . Теореманың шарты бойынша болатындай, формулалары табылады. Демек = . Яғни, берілген функция жүйесінде анықталған формула арқылы өрнектеледі. Осылайша барлық функцияларды жүйесінде өрнектей аламыз. Демек толық жүйе. Лемма дәлелденді.
Жегалкин полиномдары. Анықтама. айнымалылар тізбегі берілсін. Осы айнымалылардың әр көбейткіші нөлден өзге немесе 1-ге тең болатындай түріндегі көбейтінділерін берілген тізбектің монотондыконъюнкциясы деп атайды.
Анықтама. Егер кез келген үшін өрнегіндегі әрбір қосылғыш не 0, не айнымалыларына қарағанда монотонды конъюнкциялар болса, онда жоғарыдағы қосынды Жегалкин полиномы деп аталады.
Теорема 3.8 ( Жегалкин ). Логика алгебрасының кез келген функциясын айнымалыларына тәуелді бір ғана Жегалкин полиномы түрінде жазуға болады.
