Булева алгебра. ДМ 3

1. Дискретная математика

2.

Булева алгебра
Формулы, представляющие одну и ту же
функцию называются равносильными
(эквивалентными).
Булевы операции – это конъюнкция ( ),
дизъюнкция ( ) и отрицание (¬).
Булева алгебра – это множество
логических функций с введенными на
нем булевыми операциями.
А P2 , , , .

3. Основные свойства булевых операций

Закон коммутативности
1 x y y x , 2 x y y x ,
Закон ассоциативности
3 x y z x y z ,
4 x y z x y z ,

4. Основные свойства булевых операций

Закон дистрибутивности
5 x y z x z y z ,
6 x y z x z y z ,
Закон де Моргана
7 x y x y ,
8 x y x y

5. Основные свойства булевых операций

Закон уничтожения кратности
9 x x x ,
10 x x x ,
Закон исключенного третьего
11 x x 1,
Закон противоречия
12 x x 0,

6. Основные свойства булевых операций

Закон поглощения
13 x xy x ,
14 x x y x ,
Закон двойного отрицания
15 x x ,

7. Основные свойства булевых операций

Свойства констант
16 x 0 x ,
17 x 0 0,
18 x 1 1,
19 x 1 x ,
20 0 1 1,
21 0 1 0.

8.

Основные эквивалентности
Закон простого склеивания
22 xy xy x
23 x y x y x
Закон расщепления
24 x xy xy
25 x x y x y

9.

Основные эквивалентности
Первый закон обобщенного склеивания
26 xz yz xy xz yz ,
Второй закон обобщенного склеивания
27 x xy x y.

10. Основные эквивалентности

Эквивалентность
28 x ~ x 1,
29 x ~ x 0,
30 x ~ 1 x ,
31 x ~ 0 x .

11. Основные эквивалентности

Сложение по модулю 2
32 x x 0,
33 x x 1,
34 x 1 x ,
35 x 0 x.

12. Основные эквивалентности

Импликация
36 x x 1, 39 x 0 x ,
37 x x x , 40 x 1 1,
38 x x x , 41 0 x 1,
42 1 x x.

13. Утверждение о единственности СДНФ логической функции

СДНФ любой логической функции
единственна с точностью до порядка
элементарных конъюнкций и порядка
элементов в конъюнкциях.
Единственная логическая функция, не
имеющая СДНФ, функция –константа 0.

14. Теорема о преобразовании равносильных формул друг в друга

Пусть F1 и
формулы.
F2
равносильные
Тогда существует последовательность
эквивалентных преобразований,
переводящих одну эквивалентную
формулу в другую.

15. Теорема о преобразовании равносильных формул друг в друга

Доказательство:
Так как формулы F1 и F2
равносильны, то они представляю
одну функцию f .
У каждой функции единственна
СДНФ.
Приведем F1 и F2 к СДНФ.
F1 СДНФ ; F2 СДНФ .

16. Теорема о преобразовании равносильных формул друг в друга

Доказательство:
Обратим второе преобразование.
F1 СДНФ F2
Получим последовательность
преобразований, переводящих
F1
в
F2

17. Теорема о представимости логической функции булевой формулой

Любая логическая функция
представима булевой формулой.
Доказательство: У каждой функции
существует СДНФ – булева
формула. Функция константа 0
может быть выражена булевой
формулой вида: x x 0.