• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

ІІІ. Бульова алгебра

8. Означення бульової алгебри

Запишемо основні тотожності бульової алгебри.

1. xy=yx

2. xy=yx

3. x(yz)=(xy) z

4. x(yz)=(xy) z

5. x(yz)=(xy) (xz)

6. x(yz)=(xy) (xz)

7. =

8. =

9. xx=x

10. xx=x

11. x0=x

12. x1=x

13. x=1

14. x=0

15. x1=1

16. x0=0

17. =x

Тотожності 1 – 6 виражають комутативний (переставний), асоціативний (сполучний), дистрибутивний (розподільний) закони відповідно для диз’юнкції та кон’юнкції. Тотожності 7- 8 мають назву правил Де Моргана. Тотожністі 13 та 14 називають відповідно законами виключеного третього та суперечності. Звичайно, всі тотожності виконуються в алгебрі висловлень.

Означення. Бульовою алгеброю називають числення висловлень, в якому операції заперечення, кон’юнкція та диз’юнкція (¯ , , ) визначаються тотожностями 1 -- 17.

9. Доведеня тотожностей в бульовій алгебрі

Якщо в алгебрі висловлень два основних питання (рівносильність і тотожня істинність) вирішуються таблицями істинності, то в бульовій алгебрі ці ж питання вирішуються за допомогою тотожних перетворень. Доведемо наступні дві тотожності:

18. xxy=x

19. x(xy)=x

Спочатку доведемо, що ці тотожності еквівалентні, тобто, якщо виконується одна з них, то інша теж виконується.

xxy =⁶ ( xx ) ( xy )=⁹ x( xy ).

Ми довели, що ліві частини обох тотожностей є рівносильні формули, з чого і випливає еквівалентність обох тотожностей. Тепер доведемо одну з цих тотожностей.

xxy =¹² (x1) (xy)=⁵ x(1y)=¹ x(y1)=¹⁵ x1=¹² x.

Як бачимо, дослідження формул за допомогою тотожних перетворень значно складніше, ніж за допомогою таблиць. Такими тотожними перетвореннями не можна дослідити нерівносильні формули. Тому в бульовій алгебрі вводять формули у досконалих формах, які відіграють таку ж роль, що й таблиці істинності алгебри висловлень.

10. Елементарні добутки

Починаємо вивчати формули у досконалих формах. Цих форм є дві:

Д Д Н Ф – досконала диз’юнктивна нормальна форма.

Д К Н Ф – досконала кон’юнктивна нормальна форма.

Означення. Елементарним добутком для n-місної бульової функції називають формулу, що являє собою логічний добуток n різних змінних, взятих із запереченням або без нього.

Наприклад: _.

Розглянемо властивості елементарних добутків.

Властивість 1. Бульова функція, що виражається елементарним добутком, приймає значення 1 і тільки на одному наборі.

Випливає з означення елементарного добутку і означення кон’юнкції.

Приклади: _. Ці елементарні добутки приймають значення 1 відповідно на наборах 1 0 1, 1 1 1, 0 1 0, 1 0 1 0.

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

Випливає з означення елементарного добутку і означення кон’юнкції.

11. Означення формули у ДДНФ. Перехід від таблиці до формули

ДДНФ – досконала диз’юнктивна нормальна форма.

Означення. Формулою у ДДНФ для n-місної бульової функції називають логічну суму різних n-місних елементарних добутків.

Приклади: , _, .

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

Ця властивість випливає з 2-ої властивості елементарних добутків і означення логічної операції диз’юнкція.

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

Приклад. Бульові функції та задані таблицями своїх значень. Побудувати для них формули у Д Д Н Ф.

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Для кращого розуміння побудови формул, в таблиці наведені значення функцій для відповідних елементарних добутків.

_=, =.

12. Теорема про представлення бульової функції формулою у ДДНФ

Теорема. Довільну бульову функцію, що не дорівнює тотожно нулю, можна представити формулою у Д Д Н Ф.

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

x1 x2 ... xn-1 xn					...
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 ....................... 1 1 1 0 1 1 1 1	...	...	...	...	... ... ... ... ... ... ...	...

Для функції будуємо допоміжні функції _{, , ,} ..., так, щоб кожній одиниці функції відповідала одна і тільки допоміжна функція яка приймає значення 1 на тому ж наборі, що і функція . Запишемо допоміжні функції формулами в формі елементарних добутків.

=_, =_, =_{, ...,} =.

Хвилясті лінії над змінними означають, що заперечення може бути, а може і не бути. Ці формули допоміжних функцій відрізняються одна від одної розташуванням заперечень. Доведемо рівність =... .

Доведення: ...=.

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

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

13. Алгоритм зведення формули до ДДНФ

Алгоритм зведення формули до Д Д Н Ф полягає у виконанні тотожних перетворень за формулами наступних п’яти пунктів.

1.

2. ,

3.

4. , де - добуток змінних без х

5. =, де - елементарний n – місний добуток

В разі потреби для спрощення формул використовують тотожності 1 - 17

Приклад. №34(4), стор. 15, [3]. Звести до Д Д Н Ф формулу .

=¹=²=³

=³=⁴=⁵=⁶

=⁶=⁷=⁸

=⁸.

Пояснення.

1) Позбавляємось від імплікації, використовуючи тотожність1-го пункту алгоритму.

2) Використовуємо правило Де Моргана 2-го пункту алгоритму.

3) Використовуємо тотожність з тотожностей 1 – 17 та тотожність з 3–го пункту алгоритму.

4) Використовуємо тотожність з тотожностей 1 – 17.

5) Використовуємо тотожність 4–го пункту алгоритму.

6) Використовуємо тотожність з тотожностей 1 – 17.

7) Використовуємо тотожність 4–го пункту алгоритму.

8) Використовуємо тотожність = 5–го пункту алгоритму.

14. Елементарні суми

Означення. Елементарною сумою для n-місної бульової функції називають формулу, що являє собою логічний суму n різних змінних, взятих із запереченням або без нього.

Наприклад: _.

Розглянемо властивості елементарних сум.

Властивість 1. Бульова функція, що виражається елементарною сумою, приймає значення 0 і тільки на одному наборі.

Випливає з означення елементарного суми і означення диз’юнкції.

Приклади: _. Ці елементарні суми приймають значення 0 відповідно на наборах 0 1 0, 0 0 0, 1 0 1, 0 1 0 1.

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

Випливає з означення елементарного суми і означення диз’юнкції.

15. Означення формули у ДКНФ. Перехід від таблиці до формули

ДКНФ – досконала кон’юнктивна нормальна форма.

Означення. Формулою у ДКНФ для n-місної бульової функції називають логічний добуток різних n-місних елементарних сум.

Приклади: , .

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

Ця властивість випливає з 2-ої властивості елементарних сум і означення логічної операції кон’юнкція.

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

Приклад. Бульові функції та задані таблицями своїх значень. Побудувати для них формули у Д К Н Ф.

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Для кращого розуміння побудови формул, в таблиці наведені значення функцій для відповідних елементарних сум.

,.

16. Теорема про представлення бульової функції формулою у ДКНФ

Теорема. Довільну бульову функцію, що не дорівнює тотожно одиниці, можна представити формулою у Д К Н Ф.

Доведення. Нехай бульова функція задана таблицею значень. В цій таблиці повинен бути хоч один нулик, бо тотожно істина формула в Д К Н Ф не представляється.

x1 x2 ... xn-1 xn					...
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 ....................... 1 1 1 0 1 1 1 1	...	...	...	...	... ... ... ... ... ... ...	...

Для функції будуємо допоміжні функції _{, , ,} ..., так, щоб кожному нулю функції відповідала одна і тільки допоміжна функція яка приймає значення 0 на тому ж наборі, що і функція . Запишемо допоміжні функції формулами в формі елементарних сум.

=_, =_, =_{, ...,} =.

Хвилясті лінії над змінними означають, що заперечення може бути, а може і не бути. Ці формули допоміжних функцій відрізняються одна від одної розташуванням заперечень. Доведемо рівність

=... .

Доведення: 0 0...= 0.

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

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

17. Алгоритм зведення формули до ДКНФ

Алгоритм зведення формули до Д К Н Ф полягає у виконанні тотожних перетворень за формулами наступних п’яти пунктів.

1.

2. ,

3.

4. , де - логічна сума змінних без х

5. =, де - елементарна n – місна сума

В разі потреби для спрощення формул використовують тотожності 1 - 17

Приклад. №34(4), стор. 15, [3]. Звести до Д К Н Ф формулу .

=¹=²=³

=³=⁴.

Пояснення.

1) Позбавляємось від імплікації, використовуючи тотожність1-го пункту алгоритму.

2) Використовуємо правило Де Моргана 2-го пункту алгоритму.

3) Використовуємо тотожність з тотожностей 1 – 17 та тотожність з 3–го пункту алгоритму.

4) Використовуємо тотожність та з тотожностей 1 – 17.

18. Рівносильні та тотожно істинні формули в бульовій алгебри

З теорем про представлення бульової функції формулою у досконалих формах випливає, що такі представлення єдині. Тому, щоб перевірити дві формули на рівносильність, достатньо звести їх до однієї із досконалих форм і порівняти.

Тотожно істинна формула в Д Д Н Ф містить доданків, а в Д К Н Ф не містить жодної елементарної суми. Тому при дослідженні формули на тотожну істинність зведенням її до Д Д Н Ф слід перевірити присутність всіх доданків. А при зведенні тотожно істинної формули до Д К Н Ф вираз спрощується і одержуємо константу 1.

Тотожно хибна формула в Д К Н Ф містить множників, а в Д Д Н Ф не містить жодного елементарного добутку. Тому при дослідженні формули на тотожну хибність зведенням її до Д К Н Ф слід перевірити присутність всіх множників. А при зведенні тотожно хибної формули до Д Д Н Ф вираз спрощується і одержуємо константу 0.

Приклад. Перевірити, чи рівносильні формули: , .

Бачимо, що перша формула відразу ж зводиться до Д К Н Ф. ==.

Зведемо і другу формулу до Д К Н Ф. =====.

Висновок: , формули не рівносильні, нульові набори 0 0 1 та 1 0 1 відповідно.

19. Зв’язок між рівносильними і тотожно істинними формулами

Теорема. Для того, щоб формули та були рівносильні, необхідно і досить щоб формула була тотожно істинною.

Необхідність. .

Доведення. .

Достатність. .

Доведемо твердження обернене до протилежного: .

.

Читайте також:

1. Алгебра випадкових подій
2. Алгебра множин
3. Алгебра подій
4. Алгебраїчний спосіб визначення точки беззбитковості
5. Алгебраїчні критерії стійкості
6. Алгебраїчні операції
7. Алгебраїчні системи
8. ІІ. Алгебра висловлень
9. Мінори та алгебраїчні доповнення.
10. Однорідні системи лінійних алгебраїчних рівнянь.
11. Основні алгебраїчні структури

Переглядів: 1374