Булева алгебра. Классы булевых функций. Шаблон решения контрольной работы

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
Решение: класс Кл
№
0
1
2
3
4
5
6
7
x1 x2 x3
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
6
fл(x1, x2, x3) = k0⊕k1x1⊕k2x2⊕k3x3, ki={0,1}
f
0
1
0
1
0
1 0
0 0
1 1
fл(0, 0, 0) = k0
=
fл(0, 0, 1) = k0⊕k3 =
fл(0, 1, 0) = k0⊕k2 =
fл(1, 0, 0) = k0⊕k1 =
8