- •«Московский технический университет связи и информатики»
- •«Минимизация логических выражений»
- •«Математическая логика и теория алгоритмов»
- •1) Составление карты карно
- •2) Склеивание
- •1) Составление карты карно
- •2) Склеивание
- •3) Считывание функции
- •Красный
- •Зеленый
- •1) Составление карты карно
- •2) Склеивание
- •3) Считывание функции
- •Фиолетовый
- •Красный
- •Зеленый
1) Составление карты карно
C D A B |
0 0 |
0 1 |
1 1 |
1 0 |
0 0 |
1 |
1 |
1 |
1 |
0 1 |
1 |
1 |
1 |
0 |
1 1 |
1 |
1 |
1 |
0 |
1 0 |
0 |
0 |
1 |
1 |
2) Склеивание
Процесс склеивания сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила;
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,...
2. Каждая клетка, входящая в группу из 2m клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни
одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным.
C D A B |
0 0 |
0 1 |
1 1 |
1 0 |
0 0 |
1 |
1 |
1 |
1 |
0 1 |
1 |
1 |
1 |
0 |
1 1 |
1 |
1 |
1 |
0 |
1 0 |
0 |
0 |
1 |
1 |
3) Считывание функции
Синий
Ячейки с координатами 0000, 0001, 0011, 0010 являются соседними, поэтому объединяются в прямоугольник, содержащий 22=4 ячейки.
Переменные C, D в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменные A, B являются неизменными и равными нулю.
Составим элементарное произведение, полученное в результате объединения ячеек:
Фиолетовый
Ячейки с координатами 0100, 0101, 1100, 1101 являются соседними, поэтому объединяются в прямоугольник, содержащий 22=4 ячейки.
Переменные A, D в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменная C является неизменной и равной нулю.
Переменная B является неизменной и равной единице.
Составим элементарное произведение, полученное в результате объединения ячеек:
Красный
Ячейки с координатами 0011, 0111, 1111, 1011 являются соседними, поэтому объединяются в прямоугольник, содержащий 22=4 ячейки.
Переменные A, B в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменные C, D являются неизменными и равными единице.
Составим элементарное произведение, полученное в результате объединения ячеек:
Зеленый
Составим сумму элементарных произведений:
F =
Построим логическую схему по минимизированному выражению:
Логическая схема
По таблице истинности построим каноническую сумму минтермов:
|
|
|
|
f |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
КСМ:
F =