- •Часть 2
- •Введение
- •1 Объем учебной программы
- •1.1 Объем теоретической части
- •1.2 Перечень вопросов по защите контрольной работы
- •1.2.1 Основные логические операции.
- •2 Теоретические основы
- •2.1 Конечный автомат
- •2.2 Основные логические операции
- •2.2.1 Операция отрицания
- •2.2.2 Операция логического умножения
- •2.2.3 Операция логического сложения
- •2.2.4 Операция эквиваленция
- •2.2.5 Операция импликация
- •2.2.6 Сумма по модулю 2
- •2.2.7 Штрих Шеффера
- •2.2.8 Стрелка Пирса
- •2.3 Функции одной переменной
- •2.4 Функции двух переменных
- •2.5 Выражение одних элементарных функций через другие
- •2.6 Законы и правила конъюнкции, дизъюнкции и отрицания
- •2.7 Аналитические формы представления лф
- •2.7.1 Представление лф в совершенной дизъюнктивной форме
- •2.7.2 Дизъюнктивная нормальная форма
- •2.7.3 Представление лф в совершенной конъюнктивной форме
- •2.8 Аналитический метод минимизации фл
- •2.9 Метод минимизации фл с помощью карт Карно
- •2 .9.1 Правила минимизации по картам Карно
- •2.9.2 Соседние клетки карт Карно
- •2.9.3 Правило объединения соседних клеток
- •2.9.4 Определение простых импликант
- •2.9.5 Не определенные логические функции в картах Карно
- •2.10 Синтез комбинационных схем
- •2.11 Построение преобразователя кодов
- •2.12 Программируемые логические матрицы
- •3.1.5 Задание 5
- •Пример решения.
- •3.2 Вариантное задание
- •3.2.1 Задание 6
- •Пример решения.
- •4 Требования к оформлению контрольной работы
- •4.1 Перечень технической литературы
2.9.4 Определение простых импликант
Каждый отдельный контур объединения соответствует минтерму, который иначе называют простой импликантой. Для определения и записи простой импликанты, прямо по карте Карно, проводится анализ переменных по тем строчкам и столбцам карты, которые пересекают контур объединенных 1 (вершин куба). Начинают анализ с первой переменной Х1.
Если переменная Х1 в любой строчке (столбце), проходящей через контур, не изменяет значения своей координаты (т.е. во всех строчках контура ее значение либо 0, либо 1), то в минтерм объединения записывается ее значение (либо 0, либо1).
Если переменная Х1 в строчках (столбцах), проходящих через контур, изменяет значение своей координаты (т.е. в одной строчке контура ее значение 0, а в другой 1, либо наоборот), то в минтерм объединения записывается, так называемая, неопределенная переменная Х на том месте, где должно записываться значение переменной Х1 (рисунок 2.10 д, е, ж). Аналогичный анализ проводится последовательно для всех переменных, в результате чего получаем минтерм объединения. На рисунке 2.10 д, е, ж они расположены на выносках.
Это первый этап записи минимальной логической функции прямо с карты Карно. На втором этапе меняем значения переменных на соответствующие им переменные по правилу: если значение переменной 0 – то пишем , если 1 – то пишем Хі. На месте неопределенной переменной Х не пишем ничего, т. е. это место пропускаем. Теперь соединив все минтермы знаком дизъюнкции, получим минимальную дизъюнктивную нормальную форму логической функции (МДНФ).
При построении минимальной формы для конъюнкции, карты Карно заполняются 0, т.е. минтермами тех наборов, на которых функция равна нулю. Объединение нулей и запись МДНФ для не функции, т.е. выполняют по тем же правилам. Затем, применив к левой и правой части равенства операцию отрицания, по правилу де-Моргана преобразуем дизъюнкцию правой части в конъюнкцию, получая минимальную конъюнктивную нормальную форму (МКНФ) ЛФ.
Отметим, минимальное покрытие выбирается интуитивным путем на основе анализа различных вариантов покрытий (контуров объединений) минимизируемой функции.
Покрытие с минимальной ценой формируется, если каждая существенная вершина будет покрыта кубом с наибольшим числом независимых переменных, а для покрытия всех существенных вершин будет использовано наименьшее число кубов.
Наилучшим считается такое покрытие, где минимум контуров объединения. В качестве примера использования карт Карно для определения минимальных ДНФ и КНФ рассмотрим функцию, представленную на рисунке 2.11.
Данной ДНФ (рисунок 2.11 а) соответствует минимальная форма вида: f= +x1 x4+x2x3.
Нулевые значения этой функции представлены на рисунке 2.11 б. Отмеченные на карте клетки определяют функцию , обратную f.
При минимизации функции , получаем:
= x2 +x1 + x3.
Используя отрицание и правило де Моргана, преобразуем в КНФ:
f= =(x1+ +x3)( +x3+x4)(x2+ ).
При пяти и более переменных строят комбинированную карту, состоящую из совокупности простых, например четырехмерных. Тогда сначала находят минимальные формы внутри четырехмерных карт, а затем, расширяя понятие соседних клеток, отыскивают минимальные термы для совокупности карт. На рисунке 2.12 показаны карты для 5 и 6 переменных.