Нормальні форми зображення булевих функцій

Система булевих функцій V називається функціонально повною, якщо для будь-якого булевого виразу знайдеться булевий вираз, який дорівнює даному, і містить лише функції з V. Іншими словами, система булевих функцій називається функціонально повною, якщо будь-яку булеву функцію можна виразити за допомогою функцій, які входять до складу цієї системи. Відомо досить багато функціонально повних систем булевих функцій. Фундаментальна теорема Поста, яка вивчається в курсі дискретної математики, встановлює необхідні і достатні умови функціональної повноти.
Найбільш відомою і вживаною функціонально повною системою є система, що складається з трьох функцій: кон'юнкції, диз'юнкції та заперечення. Особливе місце цього набору пов'язано з тим, що існує простий стандартний алгоритм вираження будь-якої булевої функції за допомогою цих трьох функцій; алгоритм полягає у побудові на основі таблиці істинності досконалої диз'юнктивної нормальної форми.
Можна навести інші приклади функціонально повних систем, такі як:

* кон'юнкція та заперечення;
* диз'юнкція та заперечення;
* тотожний нуль, тотожна одиниця, кон'юнкція, додавання за модулем 2;
* імплікація та тотожний нуль.

Існують функціонально повні набори, кожний з яких містить єдину функцію. Такими функціями є штрих Шефера та стрілка Пірса.

Вираження довільного булевого виразу через кон'юнкцію, диз'юнкцію та заперечення

Cистема булевих функцій, яка містить кон'юнкцію, диз'юнкцію та заперечення, є функціонально повною, і існує загальновживаний (хоч і не завжди оптимальний з точки зору часу виконання) алгоритм представлення будь-якого булевого виразу через ці функції. Алгоритм складається з двох частин:

* побудова таблиці істинності для заданого виразу;
* побудова за таблицею істинності досконалої диз'юнктивної нормальної форми.