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

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
0
1
0
1
0
1
0
1
f(x1, x2, x3) =
1
0
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
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
1
1
СДНФ
___
xyz
__
xyz
0
1
_
xyz
СКНФ
_
x \/ y \/ z
0
_
x_\/ y \/ z _
0
x \/ y \/ z
1
_
xyz
1
zyz
4

5.

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

7.

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

8.

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