- •«Московский технический университет связи и информатики»
- •«Минимизация логических выражений»
- •«Математическая логика и теория алгоритмов»
- •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 |
0 |
1 |
0 1 |
1 |
1 |
1 |
1 |
1 1 |
1 |
1 |
1 |
1 |
1 0 |
1 |
1 |
0 |
0 |
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 |
0 |
1 |
0 1 |
1 |
1 |
1 |
1 |
1 1 |
1 |
1 |
1 |
1 |
1 0 |
1 |
1 |
0 |
0 |
3) Считывание функции
Красный
Ячейки с координатами 0000, 0001, 0100, 0101, 1100, 1101, 1000, 1001 являются соседними, поэтому объединяются в прямоугольник, содержащий 23=8 ячеек.
Переменные A, B, D в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменная С является неизменной и равной нулю.
Составим элементарное произведение:
Синий
Ячейки с координатами 0100, 0101, 0111, 0110, 1100, 1101, 1111, 1110 являются соседними, поэтому объединяются в прямоугольник, содержащий 23=8 ячеек.
Переменные A, C, D в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменная B является неизменной и равной единице.
Составим элементарное произведение:
Зеленый
Ячейки с координатами 0000, 0100, 0010, 0110 являются соседними, поэтому объединяются в прямоугольник, содержащий 22=4 ячейки.
Переменные C, B в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения.
Переменные A, D являются неизменными и равными нулю.
Составим элементарное произведение, полученное в результате объединения ячеек:
Составим сумму элементарных произведений:
F =
Построим логическую схему по минимизированному выражению:
Логическая схема
Задание 3. Минимизировать заданную логическую схему и написать соответствующую каноническую сумму минтермов.
Составим логическое выражение по данной логической схеме:
F =
По полученному логическому выражению построим таблицу истинности:
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
f |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
По таблице истинности составим минимальное выражение с помощью карты Карно: