Реалізація функцій формулами

Суперпозицією функцій називається функція отримана за допомогою підстановок цих функцій друг у друга й перейменування змінних. Формулою називається вираження, що описує суперпозицію функцій.

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

Суперпозиція елементарних булевих функцій - формула.

Приклад:

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

Формули, що представляють ту саму функцію, називаються еквівалентними або рівносильними. Еквівалентність формул позначається знаком або . Стандартний метод визначення еквівалентності двох формул полягає в наступному: по кожній формулі будується таблиця істинності функції, а потім отримані дві таблиці порівнюються. Інший метод називається методом еквівалентних перетворень і складається в перетворенні однієї з формул (або обох) доти, поки не прийдемо до однакової форми.