Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

В роботі розглянуто поняття функціональної повноти системи функцій алгебри логіки, спеціальних класів функцій алгебри логіки, а також досліджено умови виконання теорема Поста.

Засади алгебри логіки були сформульовані британцем Джорджем Булем у 1847 році. Пізніше її розвивали Чарлз Пірс, Генрі Шеффер, П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.

Відтоді ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання алгебри логіки для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).

Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. Тобто, представлення логіки у вигляді алгебраїчної структури.

Проте із закінченням формування теорії множин, що відбулось в 70-тих роках 19 століття, яка включила в себе алгебру множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.

Булевою функцією називається функція в якій всі аргументи є незалежними, і сама функція є логічними змінними, що приймають лише два значення 0 та 1. Ці функції можуть бути задані аналітично, геометрично або за допомогою таблиць істинності. Всі елементарні булеві функції двох змінних представлені таблицею істинності.