2015-06-28
377
Визначення. Нехай f(x1, x2, …, xk) і g(x1, x2, …, xk) — дві булеві функції від k змінних, представлені за допомогою двох булевих форм. Тоді
f(x1, x2, …, xk) £ g (x1, x2, …, xk)
є самою загальною формою булевої нерівності. Розв’язаннями є всі такі вектори наборів з = (x1, x2, …, xk) Î Bk, для яких справедливо f(с) (g (с).
У цьому випадку повинне виконуватися
f(с) = g (с) = 0 або f(с) = 0, g(с) = 1 або f(с) = g (с) = 1.
Приклад. Розв’язанням булевої нерівності x1 Å x2 £ x1 Ù x2 буде набір c = (x1,= 1, x2 = 1), на якому x1 Å x2 =0, 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 = 1, g = 0.
Якщо прийняти g(x1, x2, …, xk) = 1, тобто `g(x1, x2, …, xk) = 0 як частка випадку, то із цього треба
f(x1, x2, …, xk) = 0,
або
f(x1, x2, …, xk) = 1;
якщо прийняти g(x1, x2, …, xk) = 0, то треба
f(x1, x2, …, xk) = 0...
Нехай задана система m булевих нерівностей
f1(x1, x2, …, xk) £ g1(x1, x2, …, xk);
… … …
fm(x1, x2, …, xk) £ gm(x1, x2, …, xk).
Тоді вектор з = (x1, x2, …, xk) Î Bk є розв’язанням цієї системи, тільки якщо він задовольняє кожну її нерівність.
Ця система булевих нерівностей може бути замінена еквівалентним їй рівнянням за допомогою диз'юнктивного об'єднання
(f1(x1, x2, …, xk) Ù`g1(x1, x2, …, xk)) Ú
Ú (f2(x1, x2, …, xk) Ù`g2(x1, x2, …, xk)) Ú
… … …
Ú (fn(x1, x2, …, xk) Ù`gn(x1, x2, …, xk)) = 0...
Це рівняння рівносильне вихідній системі булевих нерівностей, оскільки диз'юнкція дорівнює 0 тільки тоді, коли кожна зустрічна змінна (тут рівняння, еквівалентне кожной булевой нерівності) приймає значення 0.
Приклад. Нехай задана система двох нерівностей
x1 Ù x2 £ x1 / x2`
x1 Å x2 £ x1` x2.
Тоді при диз'юнктивному об'єднанні всіх еквівалентних рівнянь вийде
((x1 Ù x2) ù (x1 / x2)) Ú ((x1 Å x2)ù (x1` x2)) = 0.
Приведення до булевого базису дасть
((x1 Ù x2)ù(`x1 Ú`x2)) Ú (((`x1 Ù x2) Ú (x1 Ù `x2))ù(`x1 Ù x2)) = 0.
Після перетворень вийде
((x1 Ù x2)(x1 Ù x2)) Ú (((`x1 Ù x2) Ú (x1 Ù`x2))(x1 Ú`x2)) =
= (x1 Ù x2) Ú (x1 Ù`x2) = 0.
Диз'юнкція дорівнює 0 при нульових аргументах, отже,
пари з1 = (x1 = 0, x2 = 0) і з2 = (x1 = 0, x2 = 1) будуть розв’язаннями системи двох нерівностей.
Якщо еквівалентні рівняння всіх булевих нерівностей, що входять у систему, об'єднати конъюнктивно, то вийде рівняння
ù(f1(x1, x2, …, xk)`g1(x1, x2, …, xk)) Ù
Ùù(f2(x1, x2, …, xk)`g2(x1, x2, …, xk)) Ù
… … …
Ùù(fn(x1, x2, …, xk)`gn(x1, x2, …, xk)) = 1
рівносильне вихідній системі булевих нерівностей, оскільки кон’юнкція дорівнює 1 тоді і тільки тоді, коли кожна зустрічна змінна (у загальному рівнянні - інверсія еквівалентного рівняння кожної булевої нерівності) приймає значення 1.
Приклад. Нехай задана система двох нерівностей
x1 ~ x2 £ x1 / x2
x1 ® x2 £ x1 Å x2
Тоді при кон ’ юнктивному об'єднанні всіх еквівалентних рівнянь вийде
ù ((x1 ~ x2) ù (x1 / x2)) Ù ù ((x1 ® x2)ù (x1 Å x2)) = 1.
Приведення до булевого базису дасть
ù (((x1Ùx2)Ú(`x1Ù`x2))Ù(x1Ù x2))Ùù((`x1Ú x2)Ù((x1Ù x2)Ú(`x1 Ù`x2)))=1.
Після перетворень вийде
(`x1 Ú`x2) Ù ((`x1 Ù x2) Ú (x1 Ù`x2)) = (`x1 Ù x2) Ú (x1 Ù`x2) = 1.
Кон ’ юнкція дорівнює 1 при одиничних аргументах, отже,
пари з1 = (x1 = 0, x2 = 1) і з2 = (x1 = 1, x2 = 0) будуть розв’язаннями системи двох нерівностей.
