Нормальні форми

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

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

Приклад. у=(х₁`х<sub>2</sub>)Ú(х<sub>2</sub>х<sub>3</sub>`х₄) ДНФ, у=(х₁Ú`х<sub>2</sub>)×(х<sub>2</sub>Ú`х₃Úх₄) КНФ, у=х₁×`х₂Úх₂×ù (х₃×х₄) не ДНФ і не КНФ.

Визначення. Члени ДНФ, що являють собою елементарні кон'юнкції з ²k² букв, називаються мінтермами к-го рангу. Члени КНФ, що являють собою елементарні диз'юнкції з ²k² букв, називаються макстермами к-го рангу.

Приклад. х₁×`х<sub>2</sub> - мінтерм 2-го рангу, х<sub>2</sub>×х<sub>3</sub>×`х₄ - мінтерм 3-го рангу, (х₁Ú`х<sub>2</sub>) – макстерм 2-го рангу, (х<sub>1</sub>Ú`х₂) і (х₂Ú`х₃Úх₄) – макстерм 3-го рангу.

Визначення. Якщо в кожнім члені нормальної диз'юнктивної чи кон'юнктивної форми представлені всі ²n² змінних (у прямому чи інверсному вигляд), від яких залежить булева функція, то така форма називається досконалою диз'юнктивною чи кон'юнктивною нормальною формою (СДНФ чи СКНФ – як термін).

Лема: Будь-яка булева функція, яка не є такою, що тотожно дорівнює нулю, має одну і тільки одну СДНФ. Будь-яка булева функція, яка не є такою, що тотожно дорівнює одиниці, має одну і тільки одну СКНФ.

Мінтерми СДНФ називають конституентами ²1². Макстерми СКНФ називають конституентами ²0². Конституента ²1² перетворюється в одиницю тільки при одному відповідному їй наборі значень змінних, котрий виходить, якщо всі змінні конституенти прийняти такими, що дорівнюють одиниці, а для всіх інверсій конституенти змінні прийняти такими, що дорівнюють нулю. Конституента ²0² перетворюється в нуль тільки при одному відповідному їй наборі значень змінних, котрий виходить, якщо всі змінні конституенти прийняти такими, що дорівнюють нулю, а для всіх інверсій конституенти змінні прийняти такими, що дорівнюють одиниці.

Приклад. х₁`х<sub>2</sub>х<sub>3</sub>`х₄=1×`0×1×`0=1, `х<sub>1</sub>Úх<sub>2</sub>Úх<sub>3</sub>Ú`х₄=`1Ú0Ú0Ú`1=0

СДНФ є диз'юнкцією конституент ²1², булева функція f(x₁, x₂,..., x_n), що її представляє, перетворюється в одиницю тільки при наборах значень змінних, відповідних хоча б одній одиниці цих конституент. На інших наборах ця функція перетворюється в нуль. СКНФ є кон'юнкціей конституент ²0², її булева функція f(x₁, x₂,..., x_n) перетворюється в нуль тільки при наборах значень змінних, відповідних хоча б одному нулю цих конституент. На інших наборах ця функція перетворюється в одиницю.

Для завдання булевой функції у вигляді СДНФ записують диз'юнкцію конституент “1” для всіх наборів змінних, на яких функція приймає значення одиниці.

Для завдання булевой функції у вигляді СКНФ записують кон'юнкцію конституент ²0² для всіх наборів змінних, на яких функція приймає значення нуля.

Такі представлення булевої функції називають аналітичним представленням у вигляді СДНФ чи СКНФ.

Приклад. Таблиця істинності, СДНФ і СКНФ функції від 3-х змінних

Таблиця 23.2

X1	X2	X3	Y

 

у=(`х<sub>1</sub>`х₂`х<sub>3</sub>)Ú(`х₁х₂`х<sub>3</sub>)Ú(`х₁х₂х₃)Ú(х₁`х<sub>2</sub>`х₃) – СДНФ,

у=(х₁Úх₂Ú`х<sub>3</sub>)(`х₁Úх₂Ú`х<sub>3</sub>)(`х₁Ú`х<sub>2</sub>Úх<sub>3</sub>)(`х₁Ú`х<sub>2</sub>Ú`х₃) - СКНФ

Для скрізь визначеної булевої функції СДНФ і СКНФ рівносильні. Аналітичне завдання можливе й у ДНФ, КНФ, тупикових та інших формах.

23.1.3. Геометричний спосіб

Областю визначення булевих функцій від ²n² змінних є множина потужністю 2ⁿ n-вимірних векторів. Якщо поставити у відповідність кожному вектору вершину n-вимірного куба, то область визначення булевої функції представляється у вигляді n-вимірної геометричної фігури.

Булева функція задається на n-вимірному кубі виділенням вершин, що відповідають векторам <х₁, х₂,..., х_n>, на яких функція дорівнює одиниці чи нулю. Кожної з n змінних виділяється своя вісь координат, на якій відкладається одиничний вектор. Початок вектора змінної відповідає значенню «0», кінець вектора – значенню «1».

Приклад.

- n = 1, потужність множини вершин дорівнює 2, приклад функції - у =`х (див. рис.13.1,а);

- n = 2, потужність множини вершин дорівнює 4, фігура виглядає як квадрат з відзначеними для конституент вершинами, приклад функції – y = x₁ `x₂ Ú x₁ x₂
(див. рис.13.1,б);

- n = 3, потужність множини вершин дорівнює 8, фігура виглядає як куб з відзначеними для конституент вершинами, приклад функції – y = x₃ Ú x₁`x<sub>2</sub> Ú`x₁ x₂.(див. рис.13.1,с).

При n ³ 4 графічний спосіб утрачає наочність.

Рис. 23.1. Одномірний а); двовимірний б); тривимірний с) куби для
функцій відповідно від однієї, двох і трьох змінних

23.1.4. Чисельний спосіб

У чисельному вигляді булева функція задається перерахуванням номерів наборів, на яких функція приймає нульові чи одиничні значення.

Приклад. Таблиця істинності і чисельне завдання СДНФ і СКНФ функції від трьох змінних

Таблиця 23.3

№	X1	X2	X3	Y

у=Ú¹ (0, 3, 4, 7) СДНФ, у=Ù⁰ (1, 2, 5, 6) СКНФ

23.2. Приведення формул булевої алгебри до досконалої форми

Якщо якій-небудь член j_j ДНФ не містить змінної х_і, то ця змінна вводиться тотожним перетворенням:

j_j=j_jÙ1=j_jÙ(x_iÚ`x<sub>i</sub>)=(j<sub>j</sub>Ùx<sub>i</sub>)Ú(j<sub>j</sub>Ù`x_i).

Якщо якій-небудь член j_j КНФ не містить змінної х_і, то ця змінна вводиться тотожним перетворенням:

j_j=j_jÚ0=j_jÚ(x_iÙ`x<sub>i</sub>)=(j<sub>j</sub>Úx<sub>i</sub>)Ù(j<sub>j</sub>Ú`x_i).

Приклад.

у=х₁х₂Úх₃=х₁х₂х₃Úх₁х₂`х<sub>3</sub>Úх<sub>1</sub>х<sub>3</sub>Ú`х₁х₃=х₁х₂х₃Úх₁х₂`х<sub>3</sub>Úх<sub>1</sub>х<sub>2</sub>х<sub>3</sub>Úх<sub>1</sub>`х₂х₃Ú`х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>Ú`х₁`х₂х₃

у=(х₁Úх₂)х₃=((х₁Úх₂)Úх₃`х<sub>3</sub>)((х<sub>3</sub>Úх<sub>1</sub>`х₁)Úх₂`х<sub>2</sub>)=(х<sub>1</sub>Úх<sub>2</sub>)Úх<sub>3</sub>)×((х<sub>1</sub>Úх<sub>2</sub>)Ú`х₃)×(((х₃Úх₁)(х₃Ú`х<sub>1</sub>))Úх<sub>2</sub>)×(((х<sub>3</sub>Úх<sub>1</sub>)(х<sub>3</sub>Ú`х₁))Ú`х<sub>2</sub>)=(х<sub>1</sub>Úх<sub>2</sub>Úх<sub>3</sub>)(х<sub>1</sub>Úх<sub>2</sub>Ú
Ú`х₃)×(х₃Úх₁)Úх₂)×((х₃Ú`х<sub>1)</sub>Úх<sub>2</sub>)×((х<sub>3</sub>Úх<sub>1</sub>)Ú`х₂)×((х₃Ú`х<sub>1</sub>)Ú`х₂)=(х₁Úх₂Úх₃)(х₁Úх₂Ú`х<sub>3</sub>)(х<sub>1</sub>Úх<sub>2</sub>Úх<sub>3</sub>)(`х₁Úх₂Úх₃)×(х₁Ú`х<sub>2</sub>Úх<sub>3</sub>)×(`х₁Ú`х₂Úх₃).