2015-06-28
406
Визначення. Нехай f(x1, x2, …, xk) і g(x1, x2, …, xk) — дві булеві функції від
k змінних, представлені, наприклад, за допомогою двох яких-небудь відповідних булевих форм. Тоді
f(x1, x2, …, xk) = g (x1, x2, …, xk)
є найбільш загальною формою булева рівняння. Розв’язаннями є всі такі вектори наборів вигляду с = (x’1, x’2, …, x’k) Î Bk, де В = {0, 1}, для яких справедливо f(с) = g(с).
Повинні виконуватися такі відношення
f(с) = g (с) = 0 або f(с) = g (с) = 1
Приклад. Розв’язанням булева рівняння x1 Å x2 = x1 Ú x2 будуть:
набір c1 = (x1,= 0, x2 = 0), на якому x1 Å x2 = x1 Ú x2 = 0;
набори c2 = (x1,= 0, x2 = 1) і c3 = (x1,= 1, x2 = 0), на яких x1 Å x2 = x1 Ú x2 = 1.
Для булевих рівнянь досить розглядати форми f(x1, x2, …, xk) = 0 і відповідно f(x1, x2, …, xk) = 1, оскільки
f(x1, x2, …, xk) = g(x1, x2, …, xk) Û
Û f(x1, x2, …, xk) Å g(x1, x2, …, xk) = 0
Ці рівняння еквівалентні однє одному в тому розумінні, що вони мають однакові множини розв’язань. Умова f(x1, x2, …, xk) Å g (x1, x2, …, xk) = 0 саме й означає рівність значень функцій.
Якщо прийняти g(x1, x2, …, xk) = 1, то звідси треба
f(x1, x2, …, xk) = 1 Û `f(x1, x2, …, xk) = 0,
якщо прийняти g(x1, x2, …, xk) = 0, то треба
f(x1, x2, …, xk) = 0 Û `f(x1, x2, …, xk) = 1
Якщо задано систему n рівнянь
f1(x1, x2, …, xk) = 0
… … …
fn(x1, x2, …, xk) = 0,
тоді вектор с = (x1, x2, …, xk) Î Bk є розв’язанням цієї системи, тільки якщо він задовольняє кожному її рівнянню.
Ця система рівнянь може бути замінена еквівалентним їй рівнянням.
Якщо всі ліві частини булевих рівнянь, що входять у систему, об'єднати диз’юнктивно, то вийде рівняння
f1(x1, x2, …, xk) Ú f2(x1, x2, …, xk) Ú … Ú fn(x1, x2, …, xk) = 0,
рівносильне вихідній системі булевих рівнянь, оскільки диз'юнкція дорівнює 0 тільки тоді, коли кожна присутня в ній змінна (тут кожна булева функція) приймає значення 0.
Приклад. Нехай задана система трьох найпростіших рівнянь:
x1 Ù x2 = 0
x1 ` x2 = 0
x1 Å x2 = 0
Тоді при диз'юнктивному об'єднанні всіх лівих частин одержимо
(x1 Ù x2) Ú (x1 ` x2) Ú (x1 Å x2) = 0.
Приведення до булевого базису дасть
(x1 Ù x2) Ú (`x1 Ù x2) Ú ((`x1 Ù x2) Ú (x1 Ù `x2)) = 0.
Після перетворень вийде
(x1 Ù x2) Ú (`x1 Ù x2) Ú (x1 Ù `x2) = x1 Ú x2 = 0.
Як відомо, диз'юнкція дорівнює 0 при нульових аргументах, тобто при x1 = 0 і x2 = 0. Отже, пара (x1 = 0, x2 = 0) і буде розв’язанням системи трьох рівнянь.
Якщо всі ліві частини рівнянь, що входять у систему, об'єднати кон’юнктивно, то вийде рівняння
`f1(x1, x2, …, xk) Ù `f2(x1, x2, …, xk) Ù … Ù `fn(x1, x2, …, xk) = 1,
рівносильне вихідній системі булевих рівнянь, оскільки кон’юнкція дорівнює 1 тільки тоді, коли кожна присутня в ній змінна (у рівнянні - інверсія кожної булевой функції) приймає значення 1.
Приклад. Нехай задана система трьох найпростіших рівнянь
x1 ¯ x2 = 1
x1 ~ x2 = 1
x1 ® x2 = 1
Тоді при кон ’ юнктивному об'єднанні всіх лівих частин вийде
(x1 ¯ x2) Ù (x1 ~ x2) Ù (x1 ® x2) = 1.
Приведення до булевого базису дасть
(`x1 Ù`x2) Ù ((`x1 Ú x2) Ù (x1 Ú `x2)) Ù (`x1 Ú x2) = 1.
Після перетворень вийде
`x1 Ù`x2 Ù (`x1 Ú x2) Ù (x1 Ú `x2) Ù (`x1 Ú x2) = `x1 Ù`x2 = 1.
Як відомо, кон ’ юнкція дорівнює 1 при одиничних аргументах, тобто при x1 = 0 і x2 = 0. Отже, у цьому прикладі, як і у попередньому, пара (x1 = 0, x2 = 0) і буде розв’язанням системи трьох рівнянь.
