Минимизация классических функций в классе ДНФ

1.

Будем рассматривать классический базис (И, ИЛИ, НЕ) в
классе ДНФ.
ДНФ, содержащая минимальное число букв, называется
минимальной (МДНФ). Минимизация булевых функций –
это получение МДНФ.

2.

Элементарное склеивание:
a b a b a
Элементарное поглощение:
a a b a
Если к ДНФ применять эти операции, то в конце концов
дальнейшие преобразования будут невозможны: получится
тупиковая ДНФ. Среди всех тупиковых ДНФ будет МДНФ.

3.

Множество переменных разбивается на группы в таблице по
строкам и столбцам. При составлении карты Карно строки
нумеруются всеми возможными комбинациями переменных
первой группы, чтобы расстояние между ними было равно 1.
Это означает, что единицам, расположенным в соседних по
вертикали или горизонтали клетках соответствуют
конъюнкции, которые можно склеить.
Склеивание двух единиц соответствует 1 переменной, четырех
единиц – двум переменным.

4.

Провести
минимизацию
функции
методом склеивания и поглощения и
методом Карно.
f x1 x2 x3 x1 x2 x3 x1 x2 x3
x1 x2 x3 x1 x2 x3 x1 x2 x3
Метод склеивания и поглощения.
x1 x2 x3
x1 x2 x3
x1 x2 x3
x1 x2 x3
x1 x2 x3
x1 x2 x3
f x1 x2 x1 x3 x1 x3 x1 x2 x2 x3
x2 x3 x1 x2 x1 x1 x2 x1 x2 x1 x2

5.

Метод Карно.
f x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3
1
2
3
X1Х2\Х3
0
1
00
11
12
01
13
14
11
15
16
4
11 ,12 ,13 ,14 x1
13 ,14 ,15 ,16 x2
10
f x1 x2
5
7