Способи задання булевих функцій.
Булеві функції можуть задаватися наступними способами:
1) За допомогою таблиці істинності (значення якої беруться з
інтерпретацій).
2) Порядковим номер, який має ця функція.
3) Аналітично (у вигляді формули).
Таблиця, в якій кожній інтерпретації функції поставлена у відповідність
її значення, називається таблицею істинностібулевої функції.
Кількість булевих функцій двох змінних f(x, y) дорівнює
222 =16.
Більшість з 16-ти булевих функцій f(x, y) часто застосовують на практиці,
мають різні значення.
Двоїстість.
Поняття двоїстості є однією з тих концепцій, які з успіхом використовуються у
найрізноманітніших галузях математики. Ми розглянемо двоїстість на простішому прикладі
булевих функцій.
Означення 10.1. Нехай f(x1,…,xn)IPn – булева функція. Тоді функція
f *(x1,…,xn) = ( ,..., ) 1 n f x x
називається двоїстою функцієюдо f.
З означення випливає, що двоїста функція інволютивна: f ** = f, а відношення “бути
двоїстою до” на множині булевих функцій симетричне, тобто якщо f * = g, то g * = f.
Якщо в таблиці істинності булевої функції f інвертувати всі значення, то отримана
таблиця буде таблицею істинності двоїстої функції f *.
Наприклад
| x y xUy |
| 0 0 0 |
| 0 1 0 |
| 1 0 0 |
| 1 1 1 |
| x y (xUy)* |
| 1 1 1 |
| 1 0 1 = |
| 0 1 1 |
| 0 0 0 |
| x y (xUy)* |
| 0 0 0 |
| 0 1 1 |
| 1 0 1 |
| 1 1 1 |
Таким чином можна визначити двоїсту функцію до будь-якої булевої функції.
|
|
|
Наведемо приклади інших двоїстих функцій:
_ функція 0 двоїста 1;
_ функція 1 двоїста 0;
_ функція кон’юнкції xUy двоїста диз’юнкції xUy;
_ функція диз’юнкції xUy двоїста кон’юнкції xUy.
Закони булевої алгебри.
Бу́лева а́лгебра — це алгебраїчна структура, що є доповненою дистрибутивнною ґраткою, та частина математики яка вивчає подібні структури.
Закони булевої алгебри
1) Комутативність кон’юнкції та диз’юнкції
2) x y= y x, x y = y x
3) Асоціативність кон’юнкції та диз’юнкції
4) x (y z) = (x y) z, x (y z) = (x y) z
5) Дистрибутивність кон’юнкції та диз’юнкції відносно один одного
6) x (y z) = (x y) (x z), x (y z) = (x y) (x z)
7) Ідемпотентність кон’юнкції та диз’юнкції
8) x x = x, x x = x
9) Закон виключного третього
4
10) x x = 1
11) Закон протиріччя
12) x x = 0
13) Тотожність с константами
14) x 0 = x, x 1 = x, x 1 = 1, x 0 = 0
15) Закони елімінації
16) x (x y) = x; x (x y) = x
17) Закон подвійного заперечення
18) x = x
19) Закони де Моргана
20) ( x y ) = x y , ( x y ) = x y
1. Множини. Способи задання множин.
|
|
|
2. Основні поняття теорії множин.
3. Геометрична інтерпретація множин.
4. Операції на множинах.
5. Алгебра множин.
6. Нескінченні множини.
7. Поняття відношення. Задання відношень.
8. Операції над відношеннями.
9. Властивості бінарних відношень.
10. Відношення еквівалентності.
11. Відношення порядку.
12. Відношення толерантності.
13. Функціональні відношення.
14. Реляційна модель даних.
15. Алгебраїчні операції та їх властивості.
16. Поняття алгебраїчної структури.
17. Кільця і поля.
18. Гратки.
19. Булеві змінні і функції.
20. Способи задання булевих функцій.
21. Двоїстість.
22. Закони булевої алгебри.
Дата добавления: 2018-08-06; просмотров: 509; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!