Розглянемо приклад знаходження досконалої диз'юнктивної нормальної форми (ДДНФ) для формули .

ЛАБОРАТОРНА РОБОТА 2

Тема: Основні положення та означення комп`ютерної логіки. Частина 2. Досконалі диз'юнктивні та кон'юнктивні нормальні форми перемикальних функцій булевої алгебри, алгебра Жегалкіна.

Мета роботи:

- вивчення технологій знаходження диз’юнктивних нормальних форм (ДНФ), кон’юнктивних нормальних форм (КНФ), досконалих диз’юнктивних нормальних форм (ДДНФ) і досконалих кон’юнктивних нормальних форм (ДКНФ) для довільних виразів булевої алгебри;

- опановування методів подання булевих функцій у вигляді поліномів Жегалкіна;

 

Базові поняття:

‒ методи знаходження диз’юнктивних нормальних форм (ДНФ) і кон’юктивних нормальних форм (КНФ) довільних виразів булевої алгебри, досконалі диз’юнктивні нормальні форми (ДДНФ) і досконалі кон’юнктивні нормальні форми (ДКНФ), ДДНФ і ДКНФ заданих булевих функцій;

‒теорема про розкладання булевої функції по змінній, залишкові функції;

‒ методи знаходження ДДНФ і ДКНФ для булевих функцій, які задані аналітично та таблично;

- поняття алгебри Жегалкіна, основні тотожності алгебри Жегалкіна та способи їх доведення, зв'язок операцій булевої алгебри й алгебри Жегалкіна, подання виразів булевої алгебри в алгебрі Жегалкіна та виконання зворотної операції.

 

ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Поняття безінверсної форми виразу в булевiй алгебрi, елементарної кон’юнкції, диз’юнктивної нормальної форми (ДНФ), досконалої диз’юнктивної нормальної форми (ДДНФ), констітуенти одиниці, визначення ДДНФ на основі констітуент одиниці

 

Безінверсною формою виразу А=А(х1…xn) булевої алгебри називають

вираз В, побудований зi змінних х1…xn та їх заперечень за допомогою кон’юнкцій i диз’юнкцій.

Будь-який вираз булевої алгебри за допомогою тотожних співвідношень даної алгебри може бути приведений до безінверсної форми.

 

Елементарна кон’юнкція - вираз, що являє собою кон’юнкцію кінцевого числа попарно різних булевих змінних або їх заперечень.

За визначенням, до елементарних кон'юнкцій також відносять:

- вирази, що складаються з однієї змінної (з запереченням або без заперечення);

- константи 0 i 1.

Елементарні кон’юнкції, що відрізняються лише порядком розташування змінних, як правило, не розрізняють у силу комутативності кон’юнкції.

Елементарну кон'юнкцію задає наступна формула:

, , i = 1, 2, ..., n,

 

Прикладами елементарних кон'юнкцій є вирази 1, x, , xy, , .

Не є елементарними кон’юнкціями вирази , y*y, .

Диз’юнктивною нормальною формою (ДНФ) називають диз'юнкцію кінцевого числа попарно різних елементарних кон’юнкцій.

Прикладом ДНФ є f(x1, x2, x3) = x1 2 Úx2x3 Ú x3.

Розглянемо приклад знаходження диз'юнктивної нормальної форми (ДНФ) для формули :

 

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

Алгоритм приведення виразу до ДНФ наведено нижче.

Крок 1. Якщо заданий вираз вже є ДНФ, то завершуємо роботу, інакше переходимо до кроку 2.

Крок 2. Приводимо початковий вираз до безінверсної форми.

Крок 3. Відповідно до першого дистрибутивного закону, розкриваємо всі дужки.

Крок 4. Виключаємо всі нулi на основі тотожності xÚ0 = x та об’єднуємо всi рівні диз’юнктивні компоненти на основі тотожності xÚx=x.

 

Розглянемо приклад приведення виразу до ДНФ:

 

f(x,y,z,w) = (xyÚ z) = (xyÚ z)( Ú ) =

= (xyÚ z)(xÚ ) = xyÚx zÚxy Ú z = xyÚx zÚ z .

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

Повна правильна елементарна кон'юнкція щодо змінних x1, x2, ..., xnвирізняється тим, що кожна зі змінних входить до неї один раз (можливо, зі знаком заперечення).

Досконалою диз'юнктивною нормальною формою (ДДНФ) щодо змінних x1, x2, ..., xn називається диз'юнктивна нормальна форма, в якій усі елементарні кон’юнкції не співпадають, є правильними та повними щодо змінних x1, x2, ..., xn.

Будь-яку булеву функцію f(x1, x2, ..., xn), яка тотожно не дорівнює нулю, можна подати за допомогою досконалої диз'юнктивної нормальної форми:

(1)

 

Розглянемо приклад знаходження досконалої диз'юнктивної нормальної форми (ДДНФ) для формули .

Розглянемо розв'язок завдання прикладу 2 табличним методом, який спирається на наведене вище подання булевої функції у вигляді ДДНФ.

Етап 1. Для заданої формули складається таблиця істинності.

Етап 2. У таблиці істинності виділяються ті набори , для яких значення формули є істинним (тотожно дорівнює одиниці).

Етап 3. Для кожного виділеного набору, складаються елементарні кон’юнкції.

Етап 4. Формується диз'юнкція побудованих елементарних кон’юнкцій.

 

 

У підсумку, буде отримано наступний результат:

Також можливо отримати розв'язок завдання аналітичним методом.

ДДНФ називають ДДНФ булевої функції f=f(x1…xn), якщо:

– ДДНФ тотожно дорівнює данiй булевiй функції (приймає ті самі значення на тих самих наборах значень змінних);

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

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

Разом iз тим, важливу роль вiдiграє властивість існування й єдиності ДДНФ заданої булевої функції, а саме: для будь-якої булевої функцiї f(x1,…,xn) існує тільки одна ДДНФ, яка тотожно дорівнює їй.

 

Нехай зафіксовано множину М={х1, …, хn} булевих змінних (аргументів булевої функції).

Констітуентами одиниці називають елементарні кон’юнкції, що містять в прямому або інверсному вигляді всі змінні заданої множини М.

Для множини М={x1, …, xn} довільну констітуенту одиницi можна подати у вигляді 1 Ù 2 Ù… Ù n, де і дорівнює хі, або , і=1, 2, ..., n.

Визначальною властивістю констітуент одиницi є те, що для будь-якої констітуенти одиницi К = 1 Ù 2 Ù… Ù n існує один і тільки один набір a=(a1,…,an) значень змінних, які входять до К, на якому дана констітуента приймає значення 1 (указаний набiр a та констітуента одиниці K, яка на даному наборі приймає значення одиницi, називаються відповідними один одному).

Наприклад, констітуентами одиниці для множини M={x1, x2, x3} будуть елементарні кон’юнкції x1* 2 *x3, 1*x2*x3, x1*x2* 3, які будуть приймати значення 1 на наступних наборах:

– x1* 2 *x3 – на наборі (1,0,1);

– 1*x2*x3 – на наборі (0,1,1);

– x1*x2* 3 – на наборi (1,1,0).

Досконалою ДНФ (ДДНФ) є така ДНФ, у якої всі елементарні кон’юнкції, з яких вона складається, є констітуентами одиницi для заданої множини змінних М.

Наприклад, для M={ x1, x2, x3}:

- вираз x1 2x3Ú 1x2x3Úx1x2 3 є ДДНФ;

- вираз x1 2x3 x2 3 1x2 x3 є лише ДНФ, але не ДДНФ:

Алгоритм знаходження ДДНФ для булевої функцiї, що задана таблицею, полягає в наведених нижче дiях.

Крок 1.Обираємо з таблиці ті набори значень двійкових змінних, на яких задана булева функцiя приймає значення 1.

Крок 2. Записуємо відповідні вказаним наборам констітуенти 1.

Крок 3. Об’єднуємо отримані констітуенти 1 знаками диз’юнкції.

Наведемо пояснювальний приклад.

Нехай булеву функцiю задано наступною таблицею істинності:

Х Y Z F(х, y, z)

 

Знайдемо ДДНФ, яка дорiвнює заданiй булевiй функцiї:

f(x,y,z)= yz x xy xyz

Існує також алгоритм знаходження тотожно рiвної ДДНФ для визначеної булевої функцiї, що задана аналітично.

Алгоритм, який дозволяє для будь-якого виразу булевої алгебри знайти ДДНФ, яка тотожно дорiвнює йому, наведено нижче.

Етап 1. Приводимо довільний вираз булевої алгебри до ДНФ.

Етап 2. Доки не всі елементарні кон’юнкції, що входять до ДНФ, є констітуентами одиницi, здiйснюємо наведенi нижче дії.

Крок 2_1. Обираємо елементарну кон’юнкцію p, яка входить до ДНФ, та яка не містить в собі деякої зi змінних хi (i= 1,…,n), від яких залежить булева функцiя.

Крок 2_2. У ДНФ замінюємо кон’юнкцію p виразом, який дорівнює їй у силу наступних тотожностей: p = р(xiÚ i) = pxiÚp i ,

Наведемо пояснювальний приклад, в якому потрібно привести до ДДНФ вираз f(x, y, z) = (x Ú z):

f(x, y, z)= (x Ú z)= ( )(x Ú z) = ( Ú )(x Ú z) =

=( Ú )(x Ú z) ( Ú z) = Ú (y Ú )z =

= Ú y z Ú z

Поняття елементарної диз'юнкції, кон’юнктивної нормальної форми (КНФ) і досконалої кон`юнктивної нормальної форми (ДКНФ), констітуенти нуля, визначення ДКНФ на основі констітуент нуля

Елементарна диз'юнкція - вираз, що являє собою диз'юнкцію кінцевого числа попарно різних булевих змінних або їх заперечень.

За визначенням, до елементарних диз'юнкцій також відносять:

- вирази, що складаються з однієї змінної (з запереченням або без нього);

- константи 0 i 1.

Елементарні диз'юнкції, що відрізняються лише порядком розташування змінних, як правило, не розрізняють через комутативнiсть диз'юнкції.

Елементарну диз'юнкцію задає формула наступного виду:

.

Прикладами елементарних диз'юнкцій є вирази 0, х, , , Ú .

Не є елементарними диз'юнкціями вирази x1Úx2Úx1, aÚbÚ .

Кон’юнктивною нормальною формою (КНФ) називають кон’юнкцію кінцевого числа попарно різних елементарних диз'юнкцій.

Приклад КНФ: f(x1, x2, x3)=(x1Ú 2)( Ú 2Ú 3) 3.