Теория дискретных устройств
Российская
Открытая
Академия
Транспорта
Способы задания логических
функций и методы их
минимизации
Лунев Сергей Александрович
2
Цель работы: Научиться по цифровой
записи функции строить таблицу
истинности, временную диаграмму,
совершенные дизъюнктивную и
конъюнктивную нормальные формы,
применять свойства, тождества и
законы алгебры логики и карты Карно
для минимизации логических функций
трех переменных.
Российская Открытая Академия Транспорта
Порядок выполнения задания
- 1. Получить индивидуальное задание на практическое занятие.
3
-
2. По индивидуальному заданию составить таблицу истинности, доопределить безразличия (при
их наличии) и построить временную диаграмму. -
3. Построить СДНФ на основе следующего алгоритма
- 3.1. Выделить комбинации в таблице истинности, на которых функция равна 1.
-
3.2. Для каждой выделенной комбинации составить логическое произведение независимых
переменных, из которых она образована, причем если в комбинации значение переменных равно
0, то в логическое произведение эта переменная входит с инверсией, если в комбинации значение
переменной равно 1, то в логическое произведение эта переменная входит без инверсии. -
3.3. Формула функции образуется путем логического сложения полученных логических
произведений.
-
4. Минимизировать полученную СДНФ с помощью изученных свойств, тождеств и законов
алгебры логики (см. Приложения 1, 2, 3). - 5. Составить карту Карно в дизъюнктивной форме для логической функции заданной в
индивидуальном задании. Выполнить минимизацию дизъюнктивной формы логической функции
(получить МДНФ) по карте Карно.
4
-
6. Построить СКНФ на основе следующего алгоритма
- 6.1. Выделить комбинации в таблице истинности, на которых функция равна 0.
-
6.2. Для каждой выделенной комбинации составить логическое сложение независимых
переменных, из которых она образована, причем если в комбинации значение переменных равно
0, то в логическое сложение эта переменная входит без инверсии, если в комбинации значение
переменной равно 1, то в логическое произведение эта переменная входит с инверсией. -
6.3. Формула функции образуется путем логического умножения полученных логических
сложений.
-
7. Минимизировать полученную СКНФ с помощью изученных свойств, тождеств и законов
алгебры логики (см. Приложения 1, 2, 3). -
8. Составить карту Карно в конъюнктивной форме для логической функции заданной в
индивидуальном задании. Выполнить минимизацию конъюнктивной формы логической функции
(получить МКНФ) по карте Карно.
Российская Открытая Академия Транспорта
Пример выполнения работы
Исходные данные: f={1, 4, 5, 7 (2)}x,y,z
Составим таблицу истинности заданной функции:
5
|
Номер комбинации |
X |
J | ||
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
2 |
0 |
1 |
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, 4, 5, 7
функция f принимает значения 1. На
наборе 2 функция не определена,
следовательно, на наборах 0, 3, 6
функция принимает значения 0.
^ Российская Открытая Академия Транспорта
Представление логической функции
временной диаграммой
W Российская Открытая Академия Транспорта Построение СДНФ заданной логической функции
001 100 101 111
7
имизация логиче
алгебраическимЗ
нкции
Идемпотентный закон
Теория
дискретны
х
устройств
МДНФ
^ Российская Открытая Академия Транспорта Минимизация логических функций с помощью карт
л огической функции методом Карно
Минимизация СДНФ зад
МДНФ
8
х | у | Z | f | ||
0 | 0 | 0 | 0 | 0 | A = х-у z |
1 | 0 | 0 | 1 | 1 | |
2 | 0 | 1 | 0 | ||
3 | 0 | 1 | 1 | 0 | |
4 | 1 | 0 | 0 | 1 | f4 = X-yZ. |
5 | 1 | 0 | 1 | 1 | |
6 | 1 | 1 | 0 | 0 | |
7 | 1 | 1 | 1 | 1 | = X ’ V ’ Z |
ДФ
Построение СКНФ заданной логической функции
9
Теория дискретных
сигналов
Отсутствуют в
анты склеивания
нкция не минимизируется
На
ором наборе значе
функции не определено (безразлично)
Рассмотрим вариант минимизации функции при принятии
значения функции на наборе номер 2 равным нулю
Открытая Академия Транспорта Построение СКНФ заданной логической функции
000 010 011
110
10
ции
еивания
закон
МКНФ
Минимизация СКНФ логических функций методом Карно
11
х | у | Z | f | ||
\ 0 | 0 | 0 | 0 | 0 | fO = X + Y + Z |
1 | 0 | 0 | 1 | 1 | |
2 | 0 | 1 | 0 | 0 | J2= X + Y + Z |
3 | 0 | 1 | 1 | 0 | f3 = X + Y + Z |
4 | 1 | 0 | 0 | 1 | |
5 | 1 | 0 | 1 | 1 | |
6 | 1 | 1 | 0 | 0 | -f6 = X + Y + Z- |
7 | 1 | 1 | 1 | 1 |
МКНФ f
КФ
12
Свойства
и отношения эквивалентности
Принцип подстановки
Если x = y, то в любом выражении содержащем
переменную x, его можно заменить на переменную y
Симметричность
Если x = y, то и y = x
Транзитивность
Если x = y и y = z, то x = z
Тождества алгебры логики
14
Коммутативный (переместительный)
х-у = у-х\ х+у = у+х;
Ассоциативный (сочетательный)
(x-y)-z = x-(y-z); (x+y}+z = x+(y+z)‘,
Дистрибутивный (распределительный)
x-(y+z) = x-y+x-z;
x+(y-z) = (x+y)\x+z)\
Идемпотентный
Закон поглощения
Закон склеивания
Закон двойственности (закон де Моргана)
Комментарии (0)