Основні припущення

Метод використовує наступні основні факти.

Відомо, що будь-яку булеву функцію можна зобразити в диз’юнктивній нормальній формі. Для функції від трьох змінних загальний вигляд ДНФ можна записати так:

(16.1)

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

При визначенні ДНФ ураховують властивість: диз’юнкція деякого числа змінних дорівнює нулю, якщо всі вхідні в неї змінні дорівнюють нулю; дорівнює одиниці, якщо хоча б одна змінна дорівнює одиниці:

(16.2)

Оскільки функція від трьох змінних визначена на стандартних
8-двійкових наборах, праву частину формули (16.1) можна перетворити на кожному наборі змінних, у результаті чого виходить система рівнянь:

(16.3)

Якщо функція приймає нульові значення на відповідному наборі змінних , то, згідно з (16.2), всі коефіцієнти, що входять у дане рівняння, дорівнюють нулю. Тоді в інших рівняннях системи (16.3), де , варто також покласти рівними нулю ці коефіцієнти.

Систему (16.3) зручно зобразити у вигляді таблиці (табл. 16.1).

Нижні індекси коефіцієнтів кожного стовпця визначають номер змінних, верхні – відповідають стовпцю значень ціх змінних. В останньому стовпці таблиці вказуються значення функції на відповідному наборі змінних, які визначаються за умовою задачі. Передбачається також, що всі коефіцієнти в довільному рядку пов’язані символами диз'юнкції.

Таблиця 16.1 – Подання системи рівнянь (16.3) за допомогою таблиці

№				Коефіцієнти системи