Минимизация логических функций

1.

ВОЕННАЯ АКАДЕМИЯ СВЯЗИ
ТЕМА № 4
«Основы алгебры логики»
ЗАНЯТИЕ № 9 ЛЕКЦИЯ
«Минимизация логических функций»
Руководитель занятия – доцент 2 кафедры
Полковник Грецев В. П.

2.

УЧЕБНЫЕ ВОПРОСЫ
2
Цель занятия:
Изучить способы минимизации логических функций и преобразование их к
виду удобному для реализации в заданном базисе.
1. Минимизация с помощью алгебраических преобразований.
2. Минимизация с помощью карт Карно .
3. Преобразование логических функций к виду, удобному для
реализации в заданном базисе.
ЛИТЕРАТУРА
1. Вычислительная техника и информационные технологии. /Под общ. ред. Н. П.
Грачева. – СПб.: Военная академия связи. 2014. С. 19-29
2. Вычислительная техника и информационные технологии. /Под общ. ред. Н. П.
Грачева. Электронное учебное пособие. – СПб.:– ВАС, 2016

3. Реализация логической функции на логических элементах: а) И и ИЛИ; б) ИЛИ-НЕ; в) И-НЕ.

1. Минимизация с помощью алгебраических
преобразований
3
Минимизация с помощью алгебраических преобразований
Под минимизацией логической (булевой) функции понимается нахождение
более простой формы записи заданной функции. Если это удается сделать, то
функциональная схема, реализующая эту функцию, будет более простой –
сократится число логических элементов (Э), уменьшится число входов
логических элементов (Вх), уменьшится глубина схемы (Г). А чем меньше
сложность функциональной схемы, тем ниже стоимость цифрового
устройства, выше надежность и быстродействие, меньше габариты и
энергопотребление.
Реализация логической функции на логических элементах: а) И и ИЛИ; б)
ИЛИ-НЕ; в) И-НЕ.
в)
а)
б)
x1 x2 x3
x1 x2 x3
&
&
&
&
x1 x2 x3
1
f
&
&
1
f
f
1
1
1
1

4. Карта Карно для трех переменных

2. Минимизация с помощью карт Карно
Карта Карно для трех переменных
х2
x1x2 x3
0
x1x2x3
1
х3
x1x2 x3
2
x1x2 x3
x1x2 x3
6
4
x1x2 x3 x1x2 x3
x1x2x3
5
3
7
х1
4

5. Карта Карно для 4-х переменных

2. Минимизация с помощью карт Карно
Карта Карно для 4-х переменных
х2
х1
x1x 2x3x 4
0
12
8
x1x2x3x4 x1x2x3x4 x1x 2x3x4
5
13
9
x1x 2x3x4
x1x 2x3x4
x1x2x3x4
x1x 2x3x4
3
7
15
11
x1x 2x3x 4
x1x2x3x 4
2
х3
4
x1x2x3x 4 x1x2x3x 4
x1x 2x3x4
1
х4
x1x2x3x 4
6
x1x2x3x 4 x1x 2x3x 4
14
10
5

6. Варианты склеивания

2. Минимизация с помощью карт Карно
6
Варианты склеивания
a)
б)
x2
x1
1
1
1
Ф
1
1
1
1
1
1
1
Ф
1
1
1
Ф
1
1
1
1
Ф
1
x4
1
x2
1
Ф
1
1
Ф
Ф
1
1
1
Ф
1
1
1
Ф
x4
x2
x1
Ф
1
1
1
Ф
Ф
x4
1
x3
а) –
f ( x1, x 2, x3, x 4) x3 x 4;
б) –
f ( x1, x 2, x3, x 4) x1 x 2;
1
1
Ф
10
1
4
0
1
5
1
0
1
3
x4
1
1
1
1
1
Ф
1
1
1
Ф
x3
x2
x1
x3
Ф
1
Ф
1
x3
Ф
1
x1
1
1
x4
г)
x2
x1
x3
в)
x4
1
Ф
x3
е)
x2
x1
Ф
x4
д)
x2
0
2
x3
в) –
f ( x1, x 2, x3, x 4) x 2 x 4;
г) –
f ( x1, x 2, x3, x 4) x 2 x 4 x 2 x 4;
д) –
f ( x1, x 2, x3, x 4) x 2 x 4 x 2 x 4;
е) –
f ( x1, x 2, x3, x 4) x1x 2 x3x 4 x 2 x3 x1x 2 x 3 x 2 x 3x 4.
Ф 12
Ф8
1
0
1
4
Ф 12
Ф8
0
0
0
1
1
5
0
0
13
0
7
0
6
x2
x1
15
Ф
9
0
0
11
x4
1
14
1
3
10
x3
0
2
0
13
0
9
0
7
15
6
Ф 14
11
1
10
x1

7. Варианты реализации функции 3-х переменных

3. Преобразование логических функций к виду,
удобному для реализации в заданном базисе
7
Варианты реализации функции 3-х переменных
F AB BC AC AB BC AC (2)
F = AB + BC + AC (1)
A
A
&
&
B
B
F
&
1
F
&
&
C
C
&
&
При построении логической схемы на элементах И-НЕ на основе булевой функции в
первой нормальной форме (ДНФ) необходимо всюду вместо элементов И и ИЛИ
ставить элемент И-НЕ.

8.

3. Преобразование логических функций к виду,
удобному для реализации в заданном базисе
8
F ( A B)( B C )( A C )
После преобразования по теореме де Моргана получим:
F ( A B )( B C )( A C ) ( A B ) ( B C ) ( A C )
A
1
B
F
1
1
C
1
При построении логической схемы на элементах ИЛИ-НЕ на основе булевой
функции во второй нормальной форме (КНФ) необходимо всюду вместо элементов
И и ИЛИ ставить элемент ИЛИ-НЕ

9.

ЗАДАНИЕ НА САМОСТОЯТЕЛЬНУЮ РАБОТУ
9
1. Вычислительная техника и информационные технологии. /Под
общ. ред. Н. П. Грачева. – СПб.: Военная академия связи. 2014
2. Вычислительная техника и информационные технологии. /Под
общ. ред. Н. П. Грачева. Электронное учебное пособие. – СПб.:–
ВАС, 2016
Дополнить конспекты