У таблиці Ai, j - константи 0 або 1, що визначають значення аргументів; Fj - константи 0 або 1, що визначають значення функції для даної комбінації аргументів; M = 2 N - кількість усіх можливих комбінацій.
Визначимо функції від 1 аргументу:
Тоді вихідна функція може бути представлена у вигляді:
Як бачите, це знаходить свій вираз тільки через функції,
і . Кожен рядок в нашому правилі (*) відповідає рядку таблиці.
Залишилося довести, що ліва частина (*) дійсно дорівнює вихідної функції. Візьмемо довільну n -ю рядок таблиці. Переконаємося, що значення функції Fn дійсно дорівнює значенню лівої частини (*) коли значення аргументів рівні значень, зазначених у цьому рядку: xi = Ai, n для i = 1, 2, 3. N.
Тобто, для вибраного n і для будь-якого i вірно:
Беремо в (*) n -ю рядок, підставляємо в неї (1) і застосовуємо закон поглинання x 1 = x.
Тепер беремо в (*) будь-яку іншу рядок, крім n -й. Нехай вона має номер m. Оскільки всі рядки таблиці містять різні набори Ai, j. то хоча б в одному стовпці буде відмінність. Нехай відмінність міститься в k -му стовпці:
Тобто, для обраних k і m вірно:
Беремо в (*) m -ю рядок, підставляємо в неї (2) і застосовуємо закони поглинання x 0 = 0 і 0 x = 0.
Таким чином, значення всіх рядків СДНФ, крім n -й дорівнює 0 за рахунок нуля, який дає хоча б одна відмінність в наборах аргументів. І лише n -а рядок дорівнює Fn.
В результаті отримуємо:
І за законами поглинання x 0 = x і 0 x = x отримуємо:
Ми розглядали довільну n -ю рядок таблиці і переконалися, що для набору аргументів, записаного в цьому рядку, значення функції збігається зі значенням лівій частині (*). Точно таке ж міркування можна повторити для всіх інших рядків, скільки б їх не було. Таким чином, значення функції збігається з лівою частиною (*) для всіх можливих наборів аргументів. Що й потрібно було довести.
У формулі (*) рядки, в яких Fj = 0 можна опустити, завдяки законам поглинання: x 0 = 0, x 0 = x і 0 x = x. А в рядках, в яких Fj = 1 можна опустити Fj. завдяки закону поглинання: x 1 = x.
Після цих скорочень виходить запис, яка і називається досконалою диз'юнктивній нормальною формою (СДНФ).
Приклад складання СДНФ.
Складемо СДНФ для функції, яка наводилася раніше в якості прикладу.
Складаємо СДНФ таким чином: для кожного рядка з одиницею в крайньому правому стовпчику утворюємо дужки і об'єднуємо їх операцією. У кожну дужку вставляємо послідовність з простих елементів, об'єднаних операцією : Для комірки таблиці, де проставлена 1, пишемо змінну-аргумент, а для кожного осередку, де проставлено 0, пишемо змінну-аргумент зі знаком
СДНФ можна спрощувати і далі, для чого існують різні методи, в тому числі метод під назвою "карти Карно", побудований на наочних зорових образах. Всі ці методи засновані на правилах спрощення:
b c) = a c
(a b) (a
Тобто, якщо в СДНФ виявляються дві дужки, які відрізняються тільки знаком
перед одним з елементів, їх можна замінити на одну дужку, в якому цього елемента немає. Наприклад, отриману вище формулу можна спростити за цим правилом, об'єднавши дві останні дужки в одну: