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

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

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

Приклад. у=(х₁ ` х<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>)×(` х₁Ú ` х₂Úх₃).

Контрольні запитання

1. Що є табличним способом завдання булевих функцій?

2. Що таке ДНФ і КНФ, СДНФ і СКНФ?

3. Яка різниця між мінтермом і макстермом?

4. Що є “констітуентою одиниці” і “конституентою нуля”?

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

6. Що є чисельним способом завдання булевих функцій?

7. Як ввести відсутню перемінну в який-небудь член ДНФ або КНФ?

8. Що є приведенням формули до досконалої форми?