Приведення формул булевих функцій до диз’юнктивної досконалої нормальної форми
Визначення 4.2.1. Елементарної кон’юнкцією називається кон’юнкція (можливо одночленна), складена зі змінних або заперечень змінних.
Приклад 4.2.1.
x, y, x&y, Øx1&x2&(Øx3) – елементарні кон’юнкції.
xVy, x1&Øx2 VØx1&x2 – не елементарні кон’юнкції.
Визначення 4.2.2. Диз'юнктивною нормальною формою (ДНФ) називається формула, що має вид диз'юнкції елементарних кон’юнкцій (у вырожденном випадку це може бути одна кон’юнкція).
Приклад 4.2.2.
x, x&y, x V Øx&(Øy), Øx1&x2&(Øx3) V x1&(Øx2)&x3 V x1&x2&(Øx3) – ДНФ.
(xVy)&Øx – не ДНФ.
Визначення 4.2.3. Досконалою диз'юнктивною нормальною формою (ДДНФ) називається така диз'юнктивна нормальна форма, кожен кон’юнктивний член якої містить всі змінні, або їхнього заперечення.
Приклад 4.8.
x&y, x&Øy V Øx&y – ДДНФ функції двох змінних.
xVØx&y, xVy – не ДДНФ.
Визначення 4.2.4. Елементарною диз'юнкцією називається диз'юнкція (можливо одночленна), складена зі змінних або заперечень змінних.
Приклад 4.2.3.
x, y, xVy, Øx1Vx2V(Øx3) – елементарні диз'юнкції.
x&y, (x1VØx2) & (Øx1Vx2) – не елементарні диз'юнкції.
Визначення 4.2.5. Кон’юнктивною нормальною формою (КНФ) називається формула, що має вид кон’юнкції елементарних диз'юнкцій (у вырожденном випадку це може бути одна диз'юнкція).
Приклад 4.2.4
x, x&y, x & Øx&(Øy), (Øx1Vx2)&(Øx3)&(x1VØx2Vx3) – КНФ.
x&y V Øx – не КНФ.
Визначення 4.2.6 Досконалою конъюнктивной нормальною формою (ДКНФ) називається така кон’юнктивна нормальна форма, кожен диз'юнктивний член якої містить всі змінні, або їхнього заперечення.
Приклад 4.2.5
xVy, (xVØy) &(ØxVy) – ДКНФ функції двох змінних.
x &(ØxVy), x&y – не ДКНФ.
Теорема 4.2.1Для кожної формули булевої функції A є рівносильна їй диз'юнктивна нормальна форма (ДНФ) і кон’юнктивна нормальна форма (КНФ).
Доведення теореми складається просто у вказівці алгоритмів знаходження для будь-якої формули A рівносильних їй ДНФ і КНФ. Процес знаходження цих форм називається приведенням формули A відповідно до ДНФ і КНФ. Для кожної формули A є, загалом кажучи, нескінченна множина ДНФ і КНФ, але для рішення задач, у яких ці форми потрібні, потрібно, як правило, знайти принаймні одну з них.
Алгоритм 4.2.1 (Алгоритм приведення формул булевих функцій до ДНФ (КНФ)).
Крок 1. Всі підформули A виду B É C (тобто утримуючу імплікацію) заміняємо на ØBVC або на Ø(B&ØC).
Крок 2. Всі підформули A виду B ~ C (тобто утримуючу еквівалентність) заміняємо на ((A&B) V (ØA&ØB) або на (AVØB)&(ØAVB) (відповідно до правил 13).
Крок 3. Всі заперечення, що стоять над складними підформулами, опускаємо за законами де Моргана (відповідно до правил 4, 19, 20).
Крок 4. Усуваємо всі подвійні заперечення над формулами (відповідно до правил 8).
Крок 5. Здійснюємо розкриття всіх дужок за законом дистрибутивності кон’юнкції щодо диз'юнкції для ДНФ (відповідно до правил 3а і 17) або за законом дистрибутивності диз'юнкції відносно кон’юнкції для КНФ (відповідно до правил 3б й 18).
Крок 6. для одержання більш простої формули доцільно використати правил 5, 6, 7, 9, 10, 11.
Очевидно, що в результаті всіх зазначених операцій формула має вигляд ДНФ або КНФ. Зазначені операції, загалом кажучи, можуть здійснюватися в будь-якому порядку, однак доцільно дотримуватися викладеного вище, за винятком зняття подвійних заперечень (крок 4), від яких варто позбуватися в міру їхньої появи.
Приклад 4.2.6
Приведемо до ДНФ і КНФ розглянутого раніше в прикладі 4.2.5 формулу f(x1, x2, x3) = Ø(x2 
Øx3) ~(Øx1Vx2).
1. Усунувши імплікацію, одержимо:
Ø(Øx2 VØx3) ~(Øx1Vx2).2. Застосувавши закон де Моргана до першої дужки й знявши подвійні заперечення, одержимо:
(x2&x3) ~ (Øx1Vx2).
3. Усунувши еквівалентність, одержимо:
(x2&x3) & (Øx1Vx2) V Ø(x2&x3) & Ø(Øx1Vx2).
4. Застосувавши закон де Моргана до другого члена диз'юнкції, одержимо
(x2&x3) & (Øx1Vx2) V (Øx2VØx3) & (x1& Øx2).
5. Застосувавши закон дистрибутивности 3а, одержимо
(x2&x3&Øx1 V x2&x3&x2) V (Øx2&x1&Øx2 V Øx3&x1&Øx2).
6. Застосувавши закони идемпотентности 5а й 5б, і розташовуючи змінні по зростанню індексів, одержимо:
Øx1&x2&x3 V x2&x3 V x1&Øx2 V x1&Øx2&Øx3.
7. Застосувавши 2-ої закон поглинання (6б), замість Øx1&x2&x3.V x2&x3 запишемо x2&x3, а замість x1&Øx2 V x1&Øx2&Øx3 запишемо x1&Øx2 й у результаті одержимо ДНФ нашої формули:
f(x1, x2, x3) º x2&x3 V x1&Øx2
При приведенні до КНФ застосуємо закон дистрибутивности 3б й одержимо:
x2&x3 V x1&Øx2 º ( x2Vx1) & (x2VØx2) & (x3Vx1) & (x3VØx2).
З огляду на, що. x2VØx2 º 1 (рівносильність 11), і застосувавши властивість 9а, одержимо остаточно КНФ для f(x1, x2, x3)
f(x1, x2, x3) º ( x1Vx2) & (x1Vx3) & (Øx2Vx3).
Приведення деякої формули до ДНФ і КНФ не є однозначним. Кількість рівносильних ДНФ і КНФ, загалом кажучи, нескінченно. Однак, зроблені диз'юнктивні й кон’юнктивні нормальні форми (ДДНФ і ДКНФ) або не існують або єдині.
Теорема 4.2.2.Кожна формула A, не рівна тотожно нулю, може бути приведена до ДДНФ, що є єдиною з точністю до перестановки диз'юнктивних членів.
Теорема 4.2.3.Кожна формула A, не рівна тотожно одиниці, може бути приведена до ДКНФ, що є єдиною з точністю до перестановки кон’юнктивних членів.
Доведення цих теорем складається у вказівці алгоритму приведення формули А к ДДНФ і ДКНФ.
Алгоритм 4.2.2. (Алгоритм приведення формули булевої функції до ДДНФ)
Крок 1. Використовуючи алгоритм побудови ДНФ, знаходимо формулу В, що є ДНФ формули А.
Крок 2. Викреслюємо в B всі елементарні кон’юнкції, у яких одночасно входять яка-небудь змінна і її заперечення. Це обґрунтовується рівносильністями:
A&ØA º 0, B&0 º 0, СV0 º С.
Крок 3. Якщо в елементарної кон’юнкції формули B деяка змінна або її заперечення зустрічається кілька разів, то залишаємо тільки одне її входження. Це обґрунтовується законом идемпотентности для кон’юнкції: A&A º A.
Крок 4. Якщо в елементарну кон’юнкцію З формули В не входить ні змінна x, ні її заперечення Øx, те на підставі 1- го закону розщеплення (рівносильність 7а) заміняємо С на (С&x) V (C&Øx).
Крок 5. У кожної елементарної кон’юнкції формули B переставляємо кон’юнктивні члени так, щоб для кожного i (i = 1, ..., n) на i-ом місці була або змінна xi, або її заперечення Øxi..
Крок 6. Усуваємо можливі повторення кон’юнктивних членів відповідно до закону ідемпотентності для диз'юнкції: СVС º С.
Приклад 4.2.7.
Знайдемо ДДНФ формули із приклада 4.4:
f(x1, x2, x3) = Ø(x2 Øx3) ~(Øx1Vx2).
1. Знайдена раніше в прикладі 4.12 ДНФ формули f(x1, x2, x3) має вигляд:
x2&x3 V x1&Øx2.
2. Кроки 2 й 3 алгоритми не потрібні (вони вже виконані), тому переходимо до кроку 4 і застосовуємо 1-ий закон розщеплення. У результаті замість кожного із двох кон’юнктивних членів одержимо дві елементарних кон’юнкції (усього їх буде чотири):
f(x1, x2, x3) º x2&x3&x1 V x2&x3&Øx1V x1&Øx2&x3 V x1&Øx2&Øx3).
3. Після застосування кроку 5 одержимо:
f(x1, x2, x3) º x1&x2&x3 V Øx1&x2&x3 V x1&Øx2&x3 V x1&Øx2&Øx3.
4. Крок 6 не потрібно. Знайдене вираження формули f(x1, x2, x3) є ДДНФ цієї формули.
Алгоритм знаходження ДКНФ повністю повторює алгоритм знаходження ДДНФ, якщо зробити двоїсту заміну & на V й V на &.
Приклад 4.2.8.
Знайдемо ДКНФ формули із приклада 4.4:
f(x1, x2, x3) = Ø(x2 Øx3) ~(Øx1Vx2).
1. Знайдена в прикладі 4.12 КНФ формули f(x1, x2, x3) має вигляд:
f(x1, x2, x3) º (x1Vx2) & (x1Vx3) & (Øx2Vx3).
2. Кроки 2 й 3 алгоритми не потрібні, тому переходимо до кроку 4 і застосовуємо 2-ий закон розщеплення (рівносильність 7б). Відповідно до цього закону:
x1Vx2 º ( x1Vx2Vx3) & (x1Vx2VØx3).
x1Vx3 º (x1Vx3Vx2)&(x1Vx3VØx2).
Øx2 Vx3 º(Øx2Vx3Vx1) & (Øx2Vx3VØx1).
Тому маємо:
f(x1,x2,x3)= (x1Vx2Vx3)&(x1Vx2VØx3)&(x1Vx3Vx2)&(x1Vx3VØx2)&(Øx2Vx3Vx1)&(Øx2 V x3VØx1).
3. Застосувавши крок 5, одержимо:
f(x1,x2,x3)º (x1Vx2Vx3)&(x1Vx2VØx3)&(x1Vx2Vx3)&(x1VØx2Vx3)&(x1VØx2Vx3)&(Øx1 VØx2Vx3).
4. Зауважуємо, що 1-ий й 3-ій, а також 4-ий й 5-ий диз'юнктивні члени отриманого виразу збігаються, застосовуємо крок 6 й одержимо остаточно ДКНФ формули f(x1, x2, x3):
f(x1, x2, x3) º (x1Vx2Vx3)&(x1Vx2VØx3)&(x1VØx2Vx3)&(Øx1VØx2Vx3).
Дата добавления: 2014-12-22; просмотров: 2941;