Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра Информатики
Лабораторная работа №4
«Минимизация логических выражений»
Вариант №2
Проверил:
Семин В.Г.
Москва 2021
Задание 1.
Написать минимальное выражение для заданной таблицы истинности и нарисовать по нему логическую схему.
Выполнение: 1)Разработка СДНФ:
-x1-x2-x3x4 + -x1x2x3-x4 + x1-x2x3x4
2)Составление карты Карно
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
1 |
0 |
3)Сцепление единиц:
Первая область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
1 |
0 |
Вторая область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
1 |
0 |
Третья область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
1 |
0 |
4) Считывание МСДНФ:
Считывание функции по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания (Например, для 4-ой группы по вертикали x1 и x2 сохраняют свои значения 1 и 0, соответственно, по горизонтали x3 сохраняет своё значение (0-0), а х4 – нет, так как оно меняется с нуля на единицу (0-1), соответственно)
-x1-x2-x3x4 + -x1x2x3-x4 + x1-x2x3x4
5)Построение логической схемы получившегося выражения
Задание 2. Для заданного логического выражения написать каноническую сумму минтермов и нарисовать минимальную логическую схему. Указание: логическое выражение записывается по следующему принципу. Знаку "+" в строке варианта соответствует указанное в шапке таблицы полное логическое произведение. В это произведение переменные входят в инверсном или прямом виде в соответствии с указанным кодом. Например для варианта 1 первому в этой строке знаку "+" соответствует 0 для кода ab cd , поэтому первым слагаемым в логическом выражении является произведение всех переменных, взятых с инверсией, так как код нуля в четырехразрядном формате записывается как 0000 и т.д.
1)Запись логического выражения:
Таблица истинности по получившемуся выражению:
a |
b |
c |
d |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
F |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
2)Разработка СДНФ
3)Составление карты Карно:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
1 |
1 |
01 |
0 |
1 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
4)Сцепление единиц:
Используемые правила для склеивания единиц:
Каждая клетка, входящая в группу из 2𝑚 клеток, должна иметь m соседних в группе (для 1-ой группы – m=2, для 2-ой – m=1, для 3-ей – m=1, для 4-ой – m=1).
Каждая клетка должна входить хотя бы в одну группу (Выполняется).
В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе (Например, для второй группы задействовано свойство, что карта Карно является сферой и могут быть соединены клетки на противоположных частях карты).
Число групп должно быть минимальным (4 группы – минимальное количество).
Первая область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
1 |
1 |
01 |
0 |
1 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
Вторая область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
1 |
1 |
01 |
0 |
1 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
Третья область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
1 |
1 |
01 |
0 |
1 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
Четвертая область:
|
00 |
01 |
11 |
10 |
00 |
0 |
1 |
1 |
1 |
01 |
0 |
1 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
5)Считывание мсднф:
Считывание функции по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания (Например, для 4-ой группы по вертикали x1 и x2 сохраняют свои значения 1 и 0, соответственно, по горизонтали x3 сохраняет своё значение (0-0), а х4 – нет, так как оно меняется с нуля на единицу (0-1), соответственно)
6)Логическая схема данной функции:
a b c d -a -b -c -d
Задание 3: Минимизировать заданную логическую схему и написать соответствующую каноническую сумму минтермов.
1)Запись СДНФ:
