Визначення 4.2.1. Елементарної кон’юнкцією називається кон’юнкція (можливо одночленна), складена зі змінних або заперечень змінних.
Приклад 4.2.1.
x, y, x & y, Ø x 1& x 2&(Ø x 3) – елементарні кон’юнкції.
x V y, x 1&Ø x 2 VØ x 1& x 2 – не елементарні кон’юнкції.
Визначення 4.2.2. Диз'юнктивною нормальною формою (ДНФ) називається формула, що має вид диз'юнкції елементарних кон’юнкцій (у вырожденном випадку це може бути одна кон’юнкція).
Приклад 4.2.2.
x, x & y, x V Ø x &(Ø y), Ø x 1& x 2&(Ø x 3) V x 1&(Ø x 2)& x 3 V x 1& x 2&(Ø x 3) – ДНФ.
(x V y)&Ø x – не ДНФ.
Визначення 4.2.3. Досконалою диз'юнктивною нормальною формою (ДДНФ) називається така диз'юнктивна нормальна форма, кожен кон’юнктивний член якої містить всі змінні, або їхнього заперечення.
Приклад 4.8.
x & y, x &Ø y V Ø x & y – ДДНФ функції двох змінних.
x VØ x & y, x V y – не ДДНФ.
Визначення 4.2.4. Елементарною диз'юнкцією називається диз'юнкція (можливо одночленна), складена зі змінних або заперечень змінних.
|
|
Приклад 4.2.3.
x, y, x V y, Ø x 1V x 2V(Ø x 3) – елементарні диз'юнкції.
x & y, (x 1VØ x 2) & (Ø x 1V x 2) – не елементарні диз'юнкції.
Визначення 4.2.5. Кон’юнктивною нормальною формою (КНФ) називається формула, що має вид кон’юнкції елементарних диз'юнкцій (у вырожденном випадку це може бути одна диз'юнкція).
Приклад 4.2.4
x, x & y, x & Ø x &(Ø y), (Ø x 1V x 2)&(Ø x 3)&(x 1VØ x 2V x 3) – КНФ.
x & y V Ø x – не КНФ.
Визначення 4.2.6 Досконалою конъюнктивной нормальною формою (ДКНФ) називається така кон’юнктивна нормальна форма, кожен диз'юнктивний член якої містить всі змінні, або їхнього заперечення.
Приклад 4.2.5
x V y, (x VØ y) &(Ø x V y) – ДКНФ функції двох змінних.
x &(Ø x V y), x & y – не ДКНФ.
Теорема 4.2.1 Для кожної формули булевої функції A є рівносильна їй диз'юнктивна нормальна форма (ДНФ) і кон’юнктивна нормальна форма (КНФ).
Доведення теореми складається просто у вказівці алгоритмів знаходження для будь-якої формули A рівносильних їй ДНФ і КНФ. Процес знаходження цих форм називається приведенням формули A відповідно до ДНФ і КНФ. Для кожної формули A є, загалом кажучи, нескінченна множина ДНФ і КНФ, але для рішення задач, у яких ці форми потрібні, потрібно, як правило, знайти принаймні одну з них.
Алгоритм 4.2.1 (Алгоритм приведення формул булевих функцій до ДНФ (КНФ)).
Крок 1. Всі підформули A виду B É C (тобто утримуючу імплікацію) заміняємо на Ø B V C або на Ø(B &Ø C).
Крок 2. Всі підформули A виду B ~ C (тобто утримуючу еквівалентність) заміняємо на ((A & B) V (Ø A &Ø B) або на (A VØ B)&(Ø A V B) (відповідно до правил 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 (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~(Ø x 1V x 2).
1. Усунувши імплікацію, одержимо:
Ø(Ø x 2 VØ x 3) ~(Ø x 1V x 2).2. Застосувавши закон де Моргана до першої дужки й знявши подвійні заперечення, одержимо:
(x 2& x 3) ~ (Ø x 1V x 2).
3. Усунувши еквівалентність, одержимо:
(x 2& x 3) & (Ø x 1V x 2) V Ø(x 2& x 3) & Ø(Ø x 1V x 2).
4. Застосувавши закон де Моргана до другого члена диз'юнкції, одержимо
(x 2& x 3) & (Ø x 1V x 2) V (Ø x 2VØ x 3) & (x 1& Ø x 2).
5. Застосувавши закон дистрибутивности 3а, одержимо
(x 2& x 3&Ø x 1 V x 2& x 3& x 2) V (Ø x 2& x 1&Ø x 2 V Ø x 3& x 1&Ø x 2).
6. Застосувавши закони идемпотентности 5а й 5б, і розташовуючи змінні по зростанню індексів, одержимо:
Ø x 1& x 2& x 3 V x 2& x 3 V x 1&Ø x 2 V x 1&Ø x 2&Ø x 3.
7. Застосувавши 2-ої закон поглинання (6б), замість Ø x 1& x 2& x 3.V x 2& x 3 запишемо x 2& x 3, а замість x 1&Ø x 2 V x 1&Ø x 2&Ø x 3 запишемо x 1&Ø x 2 й у результаті одержимо ДНФ нашої формули:
f (x 1, x 2, x 3) º x 2& x 3 V x 1&Ø x 2
При приведенні до КНФ застосуємо закон дистрибутивности 3б й одержимо:
x 2& x 3 V x 1&Ø x 2 º (x 2V x 1) & (x 2VØ x 2) & (x 3V x 1) & (x 3VØ x 2).
З огляду на, що. x 2VØ x 2 º 1 (рівносильність 11), і застосувавши властивість 9а, одержимо остаточно КНФ для f (x 1, x 2, x 3)
f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3).
Приведення деякої формули до ДНФ і КНФ не є однозначним. Кількість рівносильних ДНФ і КНФ, загалом кажучи, нескінченно. Однак, зроблені диз'юнктивні й кон’юнктивні нормальні форми (ДДНФ і ДКНФ) або не існують або єдині.
Теорема 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 (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~(Ø x 1V x 2).
1. Знайдена раніше в прикладі 4.12 ДНФ формули f (x 1, x 2, x 3) має вигляд:
x 2& x 3 V x 1&Ø x 2.
2. Кроки 2 й 3 алгоритми не потрібні (вони вже виконані), тому переходимо до кроку 4 і застосовуємо 1-ий закон розщеплення. У результаті замість кожного із двох кон’юнктивних членів одержимо дві елементарних кон’юнкції (усього їх буде чотири):
f (x 1, x 2, x 3) º x 2& x 3& x 1 V x 2& x 3&Ø x 1V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3).
3. Після застосування кроку 5 одержимо:
f (x 1, x 2, x 3) º x 1& x 2& x 3 V Ø x 1& x 2& x 3 V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3.
4. Крок 6 не потрібно. Знайдене вираження формули f (x 1, x 2, x 3) є ДДНФ цієї формули.
Алгоритм знаходження ДКНФ повністю повторює алгоритм знаходження ДДНФ, якщо зробити двоїсту заміну & на V й V на &.
Приклад 4.2.8.
Знайдемо ДКНФ формули із приклада 4.4:
f (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~(Ø x 1V x 2).
1. Знайдена в прикладі 4.12 КНФ формули f (x 1, x 2, x 3) має вигляд:
f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3).
2. Кроки 2 й 3 алгоритми не потрібні, тому переходимо до кроку 4 і застосовуємо 2-ий закон розщеплення (рівносильність 7б). Відповідно до цього закону:
x 1V x 2 º (x 1V x 2V x 3) & (x 1V x 2VØ x 3).
x 1V x 3 º (x 1V x 3V x 2)&(x 1V x 3VØ x 2).
Ø x 2 V x 3 º(Ø x 2V x 3V x 1) & (Ø x 2V x 3VØ x 1).
Тому маємо:
f (x 1, x 2, x 3)= (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 3V x 2)&(x 1V x 3VØ x 2)&(Ø x 2V x 3V x 1)&(Ø x 2 V x 3VØ x 1).
3. Застосувавши крок 5, одержимо:
f (x 1, x 2, x 3)º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 2V x 3)&(x 1VØ x 2V x 3)&(x 1VØ x 2V x 3)&(Ø x 1 VØ x 2V x 3).
4. Зауважуємо, що 1-ий й 3-ій, а також 4-ий й 5-ий диз'юнктивні члени отриманого виразу збігаються, застосовуємо крок 6 й одержимо остаточно ДКНФ формули f (x 1, x 2, x 3):
f (x 1, x 2, x 3) º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1VØ x 2V x 3)&(Ø x 1VØ x 2V x 3).