 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Спільні системи нерівностей і рівнянь
|
|
Можна розглянути як самий загальний випадок спільну систему з
m булевих нерівностей й n булевих рівнянь:
f1(x1, x2, …, xk) £ g1(x1, x2, …, xk);
… … …
fm(x1, x2, …, xk) £ gm(x1, x2, …, xk);
fm+1(x1, x2, …, xk) = gm+1(x1, x2, …, xk);
… … …
fm+n(x1, x2, …, xk) = gm+n(x1, x2, …, xk)
Спочатку доцільно замінити всі m булевих нерівностей еквівалентними їм однорідними рівняннями
f1(x1, x2, …, xk) Ù`g1(x1, x2, …, xk) = 0
..... … …
fm(x1, x2, …, xk) Ù`gm(x1, x2, …, xk) = 0.
Далі можна зробити однорідними n булевих рівнянь, що залишилися
fm+1(x1, x2, …, xk) Å g m+1(x1, x2, …, xk) = 0
..... … …
fm+n(x1, x2, …, xk) Å g m+n(x1, x2, …, xk) = 0.
Після цього можна об'єднати всі рівняння, що вийшли, в одне єдине еквівалентне рівняння. У результаті буде отримане
f1(x1, x2, …, xk) Ù`g1(x1, x2, …, xk) Ú …
Ú fm(x1, x2, …, xk) Ù`gm(x1, x2, …, xk) Ú
Ú (fm+n(x1, x2, …, xk) Å gm+n(x1, x2, …, xk)) Ú…
Ú fm+n(x1, x2, …, xk) Å g m+n(x1, x2, …, xk) = 0.
Використовуючи заперечення й закон де-Моргана, можна праву частину замінити на 1
ù(f1(x1, x2, …, xk) Ù`g1(x1, x2, …, xk)) Ù …
Ù ù(fm(x1, x2, …, xk) Ù`gm(x1, x2, …, xk)) Ù
Ù ù((fm+n(x1, x2, …, xk) Å gm+n(x1, x2, …, xk)) Ù…
Ù ù(fm+n(x1, x2, …, xk) Å g m+n(x1, x2, …, xk)) = 1.
Фактичне визначення розв’язань рівняння хоча в принципі й просто (досить обчислити його на всіх наборах с = (x1, x2, …, xk) Î Bk), однак для великого числа змінних є трудомісткою задачею, виконання якої вимагає великої уваги. Однак саме у двійкових системах розв’язання систем булевих рівнянь і нерівностей є однією з основних задач, що зустрічаються постійно, як у аналізі, так і у синтезі логічних схем, програм і алгоритмів.
Приклад. Для розглянутих вище систем трьох рівнянь і двох нерівностей моживе спільне розв’язання
x1 Ù x2 = 0
x1 ` x2 = 0
x1 Å x2 = 0
x1 Ù x2 £ x1 / x2
x1 Å x2 £ 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)ù(`x1 Ú`x2)) Ú (((`x1 Ù x2) Ú (x1 Ù `x2))ù(`x1 Ù x2)) = 0.
Після перетворень вийде
(x1 Ù x2) Ú (`x1 Ù x2) Ú (x1 Ù `x2) Ú ((x1 Ù x2)(x1 Ù x2)) Ú (((`x1 Ù x2) Ú (x1 Ù`x2))(x1 Ú`x2)) = x1 Ú x2 Ú (x1 Ù x2) Ú (x1 Ù`x2) = x1 Ú x2 = 0.
Диз'юнкція дорівнює 0 при нульових аргументах, тобто при x1 = 0 і x2 = 0. Отже, пари з = (x1 = 0, x2 = 0) і будуть розв’язанням системи трьох рівнянь і двох нерівностей.
На закінчення можна сформулювати проблему можливості розв'язання.
Визначення. Булева функція f(x1... хk, y1(x1, x2, …, xk),....., уm(x1, x2, …, xk)) називається розв'язною по у1,..., уm, якщо є булеві функції у1(x1, x2, …, xk),....., уm(x1, x2, …, xk), такі, що
f(x1... хk, y1(x1, x2, …, xk),....., уm(x1, x2, …, xk)) = 0
Проблема полягає в знаходженні таких векторів змінних (в1,... уm), які можуть бути представлені у вигляді булевих функцій уже існуючих змінних
x1,..., хk, що задовольняють останньєму рівнянню.
Контрольні запитання
1. Що називають булевым рівнянням?
2. Яка властивість й як використовується при розв’язанні булевых рівнянь?Як використовується ця властивість?
3. Що є розв’язанням системи булевых рівнянь?
4. Як можна одержати еквівалентне рівняння для системи булевых рівнянь?
5. Що називають булевою нерівністю?
6. Яка властивість використовується при розв’язання булевых нерівностей? Як використається ця властивість?
7. Як можна одержати еквівалентне рівняння для системи булевых нерівностей?
8. Які форми можливі для еквівалентних рівнянь?
9. Як визначена спільна система булевых рівнянь і нерівностей?
10. Як виходить еквівалентне рівняння для спільної системи булевых рівнянь і нерівностей?
11. Як формулюється проблема можнасті розв'язання?
Дата публикования: 2014-11-18; Прочитано: 364 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
