Булева алгебра. Классы булевых функций

1. КЛАССЫ БУЛЕВЫХ ФУНКЦИЙ

Классы булевых функций
2020
Высшая математика (специальные разделы)
БУЛЕВА АЛГЕБРА
КЛАССЫ БУЛЕВЫХ ФУНКЦИЙ
Шаблон решения контрольной работы
Факультет компьютерной инженерии и управления,
кафедра АПВТ, ХНУРЭ
Харьковский национальный университет радиоэлектроники,
кафедра АПВТ, тел. 7021 326, е-mail: [email protected]
1

2.

Классы булевых функций
2020
Вариант №
• Дано: f(x1, x2, x3) =
• Найти:
1) Составить таблицу истинности (ТИ);
2) Восстановить СДНФ, СКНФ по ТИ;
3) Упростить СДНФ, СКНФ до ДНФ, КНФ;
4) Установить принадлежность f классам К0, К1, Кс, Км, Кл
2

3.

Классы булевых функций
2020
Решение: ТИ
1
№ x1 x2 x3
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
f(x1, x2, x3) =
0
1
0
1
0
1
0
1
3

4.

Классы булевых функций
2020
Решение: СДНФ, СКНФ
2
№ x1 x2 x3 f
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
СДНФ
СКНФ
0
1
0
1
0
1
0
1
4

5.

Классы булевых функций
2020
Решение: ДНФ, КНФ
№ x1 x2 x3
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
f
2
fСДНФ(x1, x2, x3) = x1x2x3 ∨ … ∨ x1x2x3 =
fСКНФ(x1, x2, x3) =(x1∨x2∨x3) … (x1∨x2∨x3)=
5

6.

Классы булевых функций
2020
Решение: классы К0, К1, Кс
№ x1 x2 x3
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
4
f
0
1
0
1
0
1
0
1
6

7.

Классы булевых функций
2020
Решение: класс Км
№ x1 x2 x3
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
5
f
111(7)
101
(5)
011
(3)
001
(1)
010
(2)
110
(6)
100
(4)
000(0)
7

8.

Классы булевых функций
2020
Решение: класс Кл
№ x1 x2 x3
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
6
fл(x1, x2, x3) = k0⊕k1x1⊕k2x2⊕k3x3, ki={0,1}
f
fл(0, 0, 0) = k0
=
fл(0, 0, 1) = k0⊕k3 =
fл(0, 1, 0) = k0⊕k2 =
fл(1, 0, 0) = k0⊕k1 =
8