Розкладання булевої функції по змінним

Нехай s приймає значення 0 або 1, тобто s {0, 1}.

Уведемопозначення:

x^s = Ø x, якщо s = 0, x^s = x, якщо s = 1.

Т. е. x ⁰ =Ø x, x ¹ = x.

Очевидно, що x^s = 1, якщо x = s й x^s = 0, якщо x s.

Теорема 4.2.4 (про розкладання булевої функції по змінним).

Кожна булева функція f (x ₁, x ₂,..., x_n) може бути представлена у вигляді:

f (x ₁, x ₂,..., x_n) = f (x ₁, x ₂,..., x_m, x_{m +1},..., x_n) = V x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_m^sm &

f (s ₁, s ₂,... s_m, x_{m +1},..., x_n), (4.1)

m n, де диз'юнкція береться по всіх наборах (s ₁, s ₂,..., s_m) (їх 2 ^m).

Наприклад, для m = 2, n = 4 розкладання (4.1) містить у собі чотири (2 ^m = 2² =4) кон’юнкції й має вигляд:

f (x ₁, x ₂, x ₃, x ₄) = x & x & f (0, 0, x ₃, x ₄) V x & x & f (0, 1, x ₃, x ₄) V x & x & f (1, 0, x ₃, x ₄) V x & x & f (1, 1, x ₃, x ₄) = Ø x ₁&Ø x ₂& f (0, 0, x ₃, x ₄) V Ø x ₁& x ₂& f (0, 1, x ₃, x ₄) V x ₁&Ø x ₂& f (1, 0, x ₃, x ₄) V x ₁& x ₂& f (1, 1, x ₃, x ₄).

Доведення теореми 4.5.

Теорема буде доведена, якщо показати, що рівність (4.1) виконується для довільного набору змінних (y _1, y ₂,..., y_m, y_{m +1},..., y_n).

Підставимо цей довільний набір змінних у ліву й праву частини рівності (4.1).

У лівій частині одержимо f (y _1, y ₂,..., y_n).

Т. к. y^s = 1 тільки, коли y = s, те серед 2 ^m кон’юнкцій y ₁ ^{s 1}& y ₂ ^{s 2}&...& y_m^sm у правій частині (4.1) тільки одна звернеться в 1 – та, у якій y ₁ = s ₁,…, y_m = s_m... Всі інші кон’юнкції рівні 0. Тому в правій частині (4.1) одержимо:

y ₁ ^{y 1}& y ₂ ^{y 2}&...& y_m^ym & f (y _1, y ₂,..., y_m, y_{m +1},..., y_n) = f (y _1, y ₂,..., y_n).

Теорема 4.5 доведена.

Теорема 4.6 (про подання булевої функції формулою в ДДНФ),

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

Доведення.

При m = n одержимо важливий наслідок теореми 4.5:

f (x ₁, x ₂,..., x_n)=V x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_n^sn, (4.2)

f (s ₁, s ₂,..., s_n) = 1

де диз'юнкція береться по всіх наборах (s ₁, s ₂,..., s_n), на яких f = 1.

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

Очевидно також, що для булевої функції f (x ₁, x ₂,..., x_n), тотожно рівної 0, розкладання (2) не існує.

У силу викладеного для одержання формули булевої функції f (x ₁, x ₂,..., x_n) у ДДНФ можна скористатися наступним алгоритмом.

Алгоритм 4.3. (Алгоритм подання булевої функції, заданою таблицею, формулою в ДДНФ).

Крок 1. Вибираємо в таблиці всі набори змінних s ₁, s ₂,..., s_n, для яких значення f дорівнює 1, тобто f (s ₁, s ₂,..., s_n) = 1.

Крок 2. Для кожного такого набору (рядка таблиці) становимо кон’юнкцію x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_n^sn, де x_i^si = x_i, якщо s_i = 1 й x_i^si =Ø x_i, якщо s_i = 0, i = 1, 2,..., n.

Крок 3. Становимо диз'юнкцію всіх отриманих кон’юнкцій. У результаті вийде формула даної функції в ДДНФ.

Приклад 4.15.

Знайдемо формулу в ДДНФ для функції f (x ₁, x ₂, x ₃), заданою таблицею 4.4.

1. Виберемо в таблиці рядка, де f (x ₁, x ₂, x ₃) =1. Це 4-а, 5-а. 6-а й 8-а рядка.

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

x ₁⁰& x ₂¹& x ₃¹ = Ø x ₁ & x ₂& x ₃.

x ₁¹& x ₂⁰& x ₃⁰ = x ₁&Ø x ₂&Ø x ₃.

x ₁¹& x ₂⁰& x ₃¹ = x ₁&Ø x ₂& x ₃ .

x ₁¹& x ₂¹& x ₃¹ = x ₁& x ₂& x ₃ .

3. Становимо диз'юнкцію всіх отриманих кон’юнкцій і знаходимо ДДНФ:

f (x ₁, x ₂, x ₃) = Ø x ₁& x ₂& x ₃V x ₁&Ø x ₂&Ø x ₃ V x ₁&Ø x ₂& x ₃ V x ₁& x ₂& x ₃.

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

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

Теорема 4.7 (про подання булевої функції формулою в ДКНФ),

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

Доведення.

Розглянемо функцію Ø f (x ₁, x ₂,..., x_n). Відповідно до теореми 4.6, якщо вона не дорівнює тотожно 0, існує її формула в ДДНФ. Позначимо цю формулу F ₁. Очевидно, умова, що функція Ø f (x ₁, x ₂,..., x_n) не дорівнює тотожно 0, рівносильно умові, що функція f (x ₁, x ₂,..., x_n) не дорівнює тотожно 1. Крім того, за законом де Моргана формула F ₂ º Ø F ₁ перебуває в ДКНФ (заперечення кон’юнкції є диз'юнкція заперечень). За законом подвійного заперечення

F ₂ º Ø F ₁ º ØØ f (x ₁, x ₂,..., x_n) º f (x ₁, x ₂,..., x_n),

що й доводить теорему.

Для одержання формули булевої функції f (x ₁, x ₂,..., x_n) у ДКНФ варто скористатися наступним алгоритмом.

Алгоритм 4.4. (Алгоритм подання булевої функції, заданою таблицею, формулою в ДКНФ)

Крок 1. Вибираємо в таблиці всі набори змінних s ₁, s ₂,..., s_n, для яких значення f (s ₁, s ₂,..., s_n) = 0.

Крок 2. Для кожного такого набору (рядка таблиці) становимо диз'юнкцію

x ₁ ^{Ø s 1}V x ₂^{Ø s 2}V...V x_n ^{Ø sn}, де x_i ^{Ø si} = x_i, якщо s_i = 0 і x_i ^{Ø si} = Ø x_i, якщо s_i = 1, i = 1, 2,..., n.

Крок 3. Становимо кон’юнкцію всіх отриманих диз'юнкцій. У результаті вийде ДКНФ.

Приклад 4.16.

Знайдемо формулу в ДКНФ для функції f (x ₁, x ₂, x ₃), заданою таблицею 4.4.

1. Виберемо в таблиці рядки, де f (x ₁, x ₂, x ₃) = 0. Це 1-ий, 2-ий, 3-ий і 7-ий рядки.

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

x ₁¹V x ₂¹V x ₃¹ = x ₁V x ₂V x ₃.

x ₁¹V x ₂¹V x ₃⁰ = x ₁V x ₂VØ x ₃.

x ₁¹V x ₂⁰V x ₃¹ = x ₁VØ x ₂V x ₃.

x ₁⁰V x ₂⁰V x ₃¹ = Ø x ₁VØ x ₂V x ₃.

3. Становимо кон’юнкцію всіх отриманих диз'юнкцій і знаходимо ДКНФ:

f (x ₁, x ₂, x ₃) = (x ₁V x ₂V x ₃)&(x ₁V x ₂VØ x ₃)&(x ₁VØ x ₂V x ₃)&(Ø x ₁VØ x ₂V x ₃).

Це вираження збігається з отриманим раніше в прикладі 4.14 поданням нашої формули в ДКНФ.

Зауваження. Т. к. усього рядків у таблиці функції 2 ⁿ, те, якщо число диз'юнктивних членів у ДДНФ дорівнює p, а число конъюнктивных членів у ДКНФ дорівнює q, те p + q =2 ⁿ.

Так, для функції, розглянутої в прикладах 4.15 й 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2³.

ЛІТЕРАТУРА

1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцькиц Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.6-15.

2. Кужель О.В. Елементи теорії множин і математичної логіки. – К.: Рад. школа, 1977. – С. 4-24.

3. Новиков Ф.А. Дискретная математика для програмистов. – СПб.: Питер, 2002. – С.19-32.

4. Федосеева Л.И. Дискретная математика: Учеб.-практич. пособие. – Пенза: Изд-во Пенз. технол. ин-та, 1998. – С. 3-30.

Дата добавления: 2014-10-17