1_Algebra_logiki
.pdf
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Закон |
Закон |
Законы идемпотентности |
|
противоречия |
исключения третьего |
15. x1 |
_ x1 = x1 |
13. x1 x1 = 0 |
14. x1 _ x1 = 1 |
16. x1 |
x1 = x1 |
Закон поглощения
17. x1 x2 _x1 = x1 (x1 x2 _x1 = x1)
Правило простого склеивания 18. x1 x2 _ x1 x2 = x1
Обобщенное склеивание 19. x1 x2 _ x3 x2 = x1 x2 _ x3 x2 _ x1 x3
x1 x2 _x1 = x1 x2 _x1 1 = x1 (x2 _1) = x1 1 = x1
x1 x2 _x1 x2 = x1 (x2 _x2) = x1 1 = x1
x1 x2 _ x3 x2 = x1 x2 _ x1 x2 x3 _ x3 x2 _ x1 x3 x2 = x1 x2 _ x3 x2 _ x1 x3 (x2 _ x2) = x1x2 _ x3x2 _ x1x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
12 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
20.x1 ! x2 = x1 _ x2.
21.x1 x2 = x1x2 _ x1x2.
22.x1 x2 = x1x2 _ x1x2.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
13 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
20. |
x1 |
! x2 = x1 _ x2. |
|
|
|
|
|
_ |
|
23. |
x1 |
=x2 = x1x2 = x1 |
x2. |
||||||
21. |
x1 x2 = x1x2 _ x1x2. |
|
|
|
|
|
|
||
|
24. |
x1 |
# x2 = x1 _ x2 = x1x2. |
||||||
22. |
x1 |
x2 = x1x2 _ x1x2. |
|||||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
13 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Введем обозначение x = x _ x , 2 f0; 1g.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
14 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Введем обозначение x = x _ x , 2 f0; 1g.
(
x = x; ïðè = 1; x; ïðè = 0.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
14 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Введем обозначение x = x _ x , 2 f0; 1g.
(
x = x; ïðè = 1; x; ïðè = 0.
Элементарная конъюнкция Формула вида:
x 1 x m
i1 im
где все переменные попарно различны, называется элементарной конъюнкцией.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
14 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Введем обозначение x = x _ x , 2 f0; 1g.
(
x = x; ïðè = 1; x; ïðè = 0.
Элементарная конъюнкция Формула вида:
x 1 x m
i1 im
где все переменные попарно различны, называется элементарной конъюнкцией.
Число ее сомножителей m , m > 1, называется ее рангом.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
14 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Введем обозначение x = x _ x , 2 f0; 1g.
(
x = x; ïðè = 1; x; ïðè = 0.
Элементарная конъюнкция Формула вида:
x 1 x m
i1 im
где все переменные попарно различны, называется элементарной конъюнкцией.
Число ее сомножителей m , m > 1, называется ее рангом.
Число всевозможных элементарных конъюнкций, составленных из m переменных, равно 2m.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
14 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Теорема
Любая булева функция f(x1; : : : ; xn) может быть разложена по m переменным, m 2 f1; : : : ng, следующим образом:
( 1 |
_ m |
x11 xmm f( 1; : : : ; m; xm+1; : : : ; xn) |
f(x1; : : : ; xn) = |
|
|
|
;:::; |
) |
f( 1; : : : ; m; xm+1; : : : ; xn) функция f с фиксацией m первых переменных константами 1; : : : ; m.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
15 / 50 |
Нормальные формы |
Разложение булевой функции по подмножеству переменных |
Разложение булевой функции по подмножеству переменных
Доказательство
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
16 / 50 |