Авторы: Богомазова Елена Викторовна, Елена Викторовна Богомазова
Должность: преподаватель
Учебное заведение: Колледж ФГБОУ ВО "ЛГУ им. В. Даля"
Населённый пункт: город Луганск
Наименование материала: методическая разработка
Тема: Минимизация. Карты Карно, Вейча
Раздел: среднее профессиональное
Колледж Луганского государственного университета
имени Владимира Даля
МЕТОДИЧЕСКАЯ РАЗРАБОТКА
занятия
на тему: «Минимизация. Карты Вейча»
План занятия
1.
Организационная часть
2. Сообщение темы, цели и основных задач
3. Вопросы занятия
3.1. Актуализация опорных знаний и мотивация учебной деятельности (вопросы)
1.
Что такое ДНФ?
2.
Что такое КНФ?
3.
Что такое СДНФ?
4.
Что такое СКНФ?
5.
Как перейти от ДНФ к СДНФ?
6.
Как перейти от КНФ к СКНФ?
7.
Как строится схема по СДНФ функции?
8.
Как строится схема по СКНФ функции?
3.2. Вопросы лекции
1.
Минимизация логических функций методом карт Вейча.
Для логических функций, содержащих не более 5-ти аргументов, целесообразнее проводить
минимизацию логических функций с помощью карт Вейча.
При использовании карт Вейча логическую функцию предварительно следует привести к
совершенной дизъюнктивной нормальной форме (СДНФ). Карты Вейча представляют
собой прямоугольные таблицы истинности для двух, трёх и четырёх аргументов (рисунок
1)
Рисунок 1 – Таблицы истинности для двух, трёх и четырёх аргументов
Число клеток карты равно числу всех возможных наборов значений аргументов
2
𝑛
(n –
число аргументов функций). При заполнении карты в определённые клетки записываются
логические 1, соответствующие значениям минтермов логической функции (минтерм –
комбинация переменных при которых функция равна 1). Остальные клетки карты, для
которых отсутствуют минтермы, заполняются нулями.
Процесс
получения
минимальной
дизъюнктивной
нормальной
формы
(МДНФ)
функций с помощью карт Вейча сводится к следующему алгоритму:
1.
Для разрабатываемого устройства составляется функция СДНФ.
2.
Заполнить логические 1, в те клетки карты (таблицы) Вейча, которым соответствуют
минтермы функции СДНФ.
3.
Объединить все клетки, содержащие логические 1 замкнутыми областями.
4.
Каждая область должна представлять собой прямоугольник с числом клеток
2
𝑘
, где k
= 0, 1, 2,.... Значит допустимое число клеток в области 1, 2, 4, 8,….
5.
Области могут пересекаться и одни и те же клетки могут входить в разные области.
6.
Самая нижняя и самая верхняя строки таблицы (а также крайний левый и правый
столбцы)
считаются
исходными
при
построении
области
(т.е.
как
поверхность
цилиндра).
7.
При охвате клеток замкнутыми областями следует стремиться, чтобы число областей
было минимальными (при этом минимальным будет число членов в МДНФ функции),
а каждая область содержала как можно большее число клеток (при этом минимальным
будет число букв в членах МДНФ функции).
8.
Проводится запись выражения МДНФ функции. Каждый член МДНФ составляется
лишь
из
тех
аргументов,
которые
для
клеток
соответствующей
области
имеют
одинаковое значение (без инверсии либо с инверсией)
Пример 1. Записать МДНФ функции по заданной таблице (рисунок 2)
Рисунок 2
Решение:
МДНФ функции
𝑓
=
𝑥
1
𝑥
2
v
𝑥
1
𝑥
3
(рисунок 2)
Пример 2. Минимизировать функцию, принимающую единичные значения на наборах 1,
4, 5, 7 (таблица 1).
Таблица 1
№
строки
𝑥
1
𝑥
2
𝑥
3
𝑓
0
0
0
0
0
1
0
0
1
1
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
0
7
1
1
1
1
Решение:
Запишем по таблице истинности функцию СДНФ
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
Функция содержит три аргумента (n=3) и четыре минтерма, т.е. каждая конъюнкция
представлена всеми аргументами и равна логической 1.
Вписываем в соответствующие клетки карты Вейча значения минтермов (логические 1):
для 1-й конъюнкции
𝑥
1
𝑥
2
𝑥
3
=1 (
𝑥
1
= 1;
𝑥
2
= 1;
𝑥
3
= 1)
вписываем логические 1 в третью
клетку нижней строки (переменные конъюнкции выступают как координаты минтермы) и
так для каждого минтерма (рисунок 3)
Рисунок 3
Записываем конъюнкции:
- для I области –
𝑥
1
𝑥
3
(
𝑥
2
– входит с разными значениями; поэтому эта переменная
исключается);
- для II области -
𝑥
2
𝑥
3
(
𝑥
1
– входит с разными значениями; поэтому эта переменная
исключается);
- для III области -
𝑥
1
𝑥
2
(
𝑥
3
– входит с разными значениями; поэтому эта переменная
исключается).
Сводя
эти
конъюнкции
в
дизъюнкцию,
получим
минимальную
дизъюнктивную
нормальную форму МДНФ:
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
𝑥
3
v
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
Пример 3. Минимизировать функцию, принимающую единичные значения на наборах 0, 4,
5, 6. (таблица 2,
𝑓
1
)
Таблица 2
№
строки
𝑥
1
𝑥
2
𝑥
3
𝑓
1
𝑓
2
𝑓
3
0
0
0
0
1
0
0
1
0
0
1
0
0
1
2
0
1
0
0
1
0
3
0
1
1
0
0
1
4
1
0
0
1
1
0
5
1
0
1
1
1
1
6
1
1
0
1
1
1
7
1
1
1
0
1
1
Решение:
Запишем СДНФ функции по таблице истинности
𝑓
1
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
∙
𝑥
2
∙
𝑥
3
v
𝑥
1
∙
𝑥
2
∙
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
Заполним карту Вейча (рисунок 4)
Рисунок 4
МДНФ функции по карте Вейча
𝑓
1
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
𝑥
3
v
𝑥
1
𝑥
2
v
𝑥
2
∙
𝑥
3
Пример 4. Минимизировать функцию, принимающую единичные значения на наборах 2, 4,
5, 6, 7 таблицы истинности (таблица 2,
𝑓
2
)
Решение
СДНФ функции по таблице истинности
𝑓
2
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
∙
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
МДНФ функции по карте Вейча (рисунок 5)
𝑓
2
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
2
𝑥
3
v
𝑥
1
Рисунок 5
Пример 5. Минимизировать функцию, принимающую единичные значения на наборах 1, 3,
5, 6, 7 таблицы истинности (таблица 2,
𝑓
3
)
Решение
Нарисуем таблицу истинности и по ней запишем СДНФ функции
𝑓
3
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
v
𝑥
1
𝑥
2
𝑥
3
МДНФ функции по карте Вейча (рисунок 6)
𝑓
3
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
𝑥
3
v
𝑥
1
𝑥
2
Рисунок 6
Пример 6. Минимизировать функцию
4
х
аргументов на наборах 0, 1, 2, 4, 5, 6, 7, 10, 14 по
таблице истинности (таблица 3)
Таблица 3
№
строки
𝑥
1
𝑥
2
𝑥
3
𝑥
4
f
0
0
0
0
0
1
1
0
0
0
1
1
2
0
0
1
0
1
3
0
0
1
1
0
4
0
1
0
0
1
5
0
1
0
1
1
6
0
1
1
0
1
7
0
1
1
1
1
8
1
0
0
0
0
9
1
0
0
1
0
10
1
0
1
0
1
11
1
0
1
1
0
12
1
1
0
0
0
13
1
1
0
1
0
14
1
1
1
0
1
15
1
1
1
1
0
СДНФ функции
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
,
𝑥
4
)=
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
v
𝑥
1
𝑥
2
𝑥
3
𝑥
4
Рисунок 7
МДНФ функции запишем по карте Вейча (рисунок 7)
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
,
𝑥
4
)=
𝑥
1
𝑥
2
v
𝑥
1
𝑥
3
v
𝑥
3
𝑥
4
Для получения МКНФ функции замкнутыми областями охватываются клетки с нулевыми
значениями функции и при записи членов логического выражения берутся инверсии
аргументов на пересечении которых находятся области, при этом аргументы складываются,
а области умножаются.
Пример 7. Минимизировать функцию
3
𝑥
аргументов, принимающую нулевые значения на
наборах 1, 2, 3, 5, 6. (таблица 4) Найти её МКНФ.
Таблица 4
№
строки
𝑥
1
𝑥
2
𝑥
3
f
0
0
0
0
1
1
0
0
1
0
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
0
6
1
1
0
0
7
1
1
1
1
Решение
По таблице истинности (таблица 4) запишем СКНФ функции
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
(
𝑥
1
v
𝑥
2
v
𝑥
3
)
∗
(
𝑥
1
v
𝑥
2
v
𝑥
3
)
∗
(
𝑥
1
v
𝑥
2
v
𝑥
3
)
* (
𝑥
1
v
𝑥
2
v
𝑥
3
)
∗ ∗
(
𝑥
1
v
𝑥
2
v
𝑥
3
)
В таблице (рисунок 8) представим с помощью карт Вейча функцию трёх аргументов
Рисунок 8
МКНФ функции
𝑓
(
𝑥
1
,
𝑥
2
,
𝑥
3
) =
(
𝑥
1
v
𝑥
2
)
∗
(
𝑥
2
v
𝑥
3
)
(
∗
𝑥
2
v
𝑥
3
)
Для минимизации функции с числом аргументов, большим пяти, карты Вейча оказываются
неудобными. Минимизация таких функций может быть выполнена методом Квайна.
2.
Решение примеров.
Минимизировать функцию трех аргументов, принимает единичные значения на наборах:
А) 0,1,3,4,5
Б) 1,2,5,6,7
Минимизировать функцию четырех аргументов, принимает единичные значения на
наборах:
А) 2,7,5,9,15,5,10,12,8
3.3. Вопросы для взаимосвязи
1.
Опишите алгоритм минимизации функции с помощью карт Вейча.
2.
Чему равна число клеток карты?
3.
Сформулируйте правила получения МДНФ функций с помощью карт Вейча.
4.
Как определить клетки, которые заполняются 1 или 0?
5.
Что должна представлять собой каждая область?
6.
Сколько клеточек может быть в области?
7.
Как определить, сколько клеточек будет МДНФ или МКНФ?
8.
Как определить, сколько аргументов будет в каждом члене МДНФ или МКНФ?
4. Выдача заданий для самостоятельной работы обучающихся.
1) Минимизировать с помощью карт Вейча функции трех аргументов, принимающие
единичные значения на наборах: а) 1, 3, 6, 7; б) 0, 2, 4, 6;
Минимизировать с помощью карт Вейча функциию четырех аргументов, , принимающую
единичные значения на наборах 0, 1, 2, 3, 4, 8, 9, 10, 11, 12
2) Минимизировать с помощью карт Вейча функцию, принимающую нулевые значения на
наборах 0, 1, 2, 4, 6, 10, 11, 14, 15
4)
Минимизировать
функцию
3
х
аргументов
принимающую
единичные
значения
на
наборах 1, 4, 5, 6, 7. Начертить структурную схему устройства.
5. Подведение итогов занятия