МЛИТА_Лаб№4
.docxМИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ
Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра «Информатика»
Лабораторная работа №4
«Минимизация логических выражений»
по дисциплине
«Математическая логика и теория алгоритмов»
Выполнил: студент гр. БСТ2106
Вариант №3
Проверил: Семин В.Г.
Москва, 2022 г.
Задание №1: Написать минимальное выражение для заданной таблицы истинности и нарисовать по нему логическую схему.
I(3:0) |
F |
||||
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
|
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 |
0 |
|
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
|
Решение задания №1:
Чтобы написать минимальное выражение данной функции, используем способ «Карты Карно».
Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор.
Ниже приведена разметка карты Карно для n=4 переменных (I3, I2, I1, I0).
I0 I1 |
I2 I3 |
||||
|
00 |
01 |
11 |
10 |
|
00 |
0000 |
0001 |
0011 |
0010 |
|
01 |
0100 |
0101 |
0111 |
0110 |
|
11 |
1100 |
1101 |
1111 |
1110 |
|
10 |
1000 |
1001 |
1011 |
1010 |
|
5
I0 I1 |
I2 I3 |
||||
|
00 |
01 |
11 |
10 |
|
00 |
|
|
0 |
|
|
01 |
1 |
1 |
|
3 |
|
11 |
|
2 |
4 |
0 |
|
10 |
6 |
0 |
|
1 |
|
1
1
1
1
1
1
Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной.
Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила:
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,...
2. Каждая клетка, входящая в группу из 2m клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным
Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.
Результат считывания:
Первый контур охватывает 2 единицы, в которой не изменяется только I0I1I2
Второй контур охватывает 2 единицы, в которой не изменяется только I0I2I3
Третий контур охватывает 2 единицы, в которой не изменяется только I0I2I3
Четвертый контур охватывает 2 единицы, в которой не изменяется только I0I1I2
Пятый контур охватывает 2 единицы, в которой не изменяется только I0I1I2
Шестой контур охватывает 1 единицу, содержащую I0I1I2I3
Получаем минимизированное выражение:
+
Построим логическую схему:
&
&
&
F
1
&
&
&
Задание №2: Для заданного логического выражения написать каноническую сумму минтермов и нарисовать минимальную логическую схему.
Указание: логическое выражение записывается по следующему принципу. Знаку "+" в строке варианта соответствует указанное в шапке таблицы полное логическое произведение. В это произведение переменные входят в инверсном или прямом виде в соответствии с указанным кодом. Например для варианта 1 первому в этой строке знаку "+" соответствует 0 для кода ab cd , поэтому первым слагаемым в логическом выражении является произведение всех переменных, взятых с инверсией, так как код нуля в четырехразрядном формате записывается как 0000 и т.д.
Код abcd |
|||||||||||||||
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
- |
- |
- |
- |
- |
- |
+ |
- |
+ |
- |
+ |
- |
+ |
- |
+ |
- |
Код bcd |
Код abd |
Код ab |
|||||||||||||||||||
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
||
- |
- |
- |
- |
- |
- |
- |
+ |
- |
- |
- |
- |
+ |
- |
- |
- |
- |
+ |
- |
- |
||
Код bc |
Код abc |
Код acd |
||||||||||||||||||
0 |
1 |
2 |
3 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
f = abcd + abcd + abcd + abcd + bcd + abd + ab
Чтобы для выражения нарисовать минимальную логическую схему, необходимо минимизировать функцию через Карты Карно.
Но для этого построим таблицу истинности по канонической сумме минтермов, полученной выше.
-
a
b
c
d
F
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
a,b |
c, d |
||||
|
00 |
01 |
11 |
10 |
|
00 |
0 |
0 |
0 |
0 |
|
01 |
|
1 |
1 |
1 |
|
11 |
|
0 |
0 |
|
|
10 |
1 |
0 |
|
1 |
|
1
1
1
1
Минимизированная функция по результату считывания:
f = ab + acd + acd + abc
Схема по минимизированной функции:
1
&
&
&
f
&
Задание №3:
Минимизировать заданную логическую схему и написать соответствующую каноническую сумму минтермов.
Решение задания №3:
Каноническая сумма минтермов:
f = abc + acd + ab + acd + abcd + abc
Минимизация по карте Карно:
3
a, b |
c, d |
||||
|
00 |
01 |
|
10 |
|
00 |
1 |
|
|
0 |
|
01 |
1 |
1 |
1 |
|
|
11 |
1 |
1 |
1 |
4 |
|
10 |
2 |
0 |
1 |
0 |
|
11
1
1
1
Результат считывания:
Первая область охватывает четыре единицы с координатами 0000, 0001, 0100, 0100. Ему соответствует abcd+abcd+abcd+abcd в которой не изменяет своих значений только переменная ac, которая войдет в МСДНФ
Вторая область охватывает четыре единицы c координатами 0100, 0101, 1100, 1101. Ему соответствует abcd+abcd+abcd+abcd в которой не изменяет своих значений только переменная bc, которая войдет в МСДНФ
Третья область охватывает четыре единицы c координатами 0011, 0111, 1111, 1011. Ему соответствует abcd+abcd+abcd+abcd в которой не изменяет своих значений только переменная cd, которая войдет в МСДНФ
Четвертая область охватывает четыре единицы с координатами 0100, 0101, 0111, 0110. Ему соответствует abcd+abcd+abcd+abcd в которой не изменяет своих значений только переменная ab, которая войдет в МСДНФ
По результатам считывания записываем минимизированную функцию:
f = aс + bс + cd + ab
Минимизированная логическая схема:
&
1
&
&
&
f