Формы записи логической функции.
Логическая функция может быть записана аналитически различными сочетаниями операций сложения и умножения переменных. Однако с точки зрения представления логической функции и последующего синтеза логической схемы наиболее удобны формы записи, при которых функция выражается либо в виде суммы произведений переменных, либо в виде произведения их сумм.
Запись логической функции в виде суммы произведений переменных называют дизъюнктивной нормальной формой (ДНФ):
а запись функции в виде произведения сумм — конъюнктивной нормальной формой (КНФ):
Инверсия любой функции, записанной в дизъюнктивной (конъюнктивной) нормальной форме, по правилу (1.5) дает замену записи на конъюнктивную (дизъюнктивную) нормальную форму. Например, инверсия функции
имеет вид
.
Логическую функцию, заданную любым аналитическим выражением, можно преобразовать к ДНФ или КНФ, пользуясь правилами алгебры логики. Для каждой логической функции может существовать несколько равносильных дизъюнктивных и конъюнктивных форм.
Таблица истинности
Логическая функция наиболее наглядно и полно представляется так называемой таблицей соответствия или истинности, в которой для каждой комбинации значений переменных указывается значение функции. Таким образом, таблица истинности определяет алгоритм работы создаваемой цифровой схемы.
Таблица истинности
|
|
|
| Номер комбинации | X | Y | Z | F |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 1 | 1 | 0 |
| 5 | 1 | 0 | 0 | 0 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 0 | 1 |
| 8 | 1 | 1 | 1 | 1 |
Минимизация логических функций и ее назначение.
Минимизация (упрощение формы записи) функции является важной операцией при синтезе логической схемы, так как благодаря предварительно проведенной минимизации схема реализуется с наименьшим числом элементов. Выявить и устранить избыточность в записи функции можно путем ее преобразований с использованием аксиом, законов, тождеств и теорем алгебры логики.
Метод карт Карно.
Карта Карно (рис.1.3 а - в) представляет собой графическое изображение значений всех возможных комбинаций переменных. Иными словами, карту Карно можно рассматривать как графическое представление всех минтермов заданного числа переменных.
Рис.1.3. Карта Карно функции для двух (а), трех (б) и четырех (в) переменных
Каждый минтерм изображается на карте в виде клетки. Карта образуется путем такого расположения клеток, при котором минтермы соседних клеток отличаются только значением одной переменной. В связи с указанным соседними считаются также крайние клетки каждого столбца или строки. Символ «1» характеризует прямое значение переменной, а «0» — ее инверсное значение.
|
|
|
Минтермы минимизируемой функции отмечают единицами в соответствующих клетках карты. Минтермы, не входящие в функцию, отмечают в клетках нулями или оставляют клетки пустыми. На основании распределительного закона, а также аксиом операции логического сложения два минтерма, находящиеся в соседних клетках, могут быть заменены одним логическим произведением, содержащим на одну переменную меньше. Если соседними являются две пары минтермов, то такая группа из четырех минтермов может быть заменена произведением, содержащим уже на две переменные меньше, и т. д. В общем случае наличие единиц в 2n соседних клетках позволяет исключить п переменных. В этом и заключается метод минимизации с применением карт Карно.
Рассмотрим процесс минимизации на примере четырех переменных х, у, z, v функции, заданной следующим логическим выражением:
f = yzv + xyv + yzv + хуz+ xzv + уzv + уzv.
С помощью простейших преобразований представим эту функцию в виде:
После исключения повторяющихся членов функция выражается в СДНФ:
|
|
|
Функция состоит из 11 минтермов, в связи с чем на карте Карно (рис.1.4) ее будут представлять 11 клеток, отмеченных единицами.
 |
Так, например, первый минтерм функции xyzv будет отображаться клеткой, имеющей координаты ху и zv, соответственно 11 и 11. Пять клеток карты остаются свободными.
Затем на карте Карно необходимо определить соседние минтермы (клетки) и объединить их в минимальное количество групп соседних минтермов (клеток). Для наглядности выделенные группы соседних клеток показывают сплошными линиями. Минимальное количество групп соседних минтермов для рассматриваемой функции будет равно трем.
В первую группу входят две нижние клетки второго столбца слева с минтермами xyzv и xyzv. В соответствии с аксиомой дизъюнкции имеем
т.е. переменная 
из этой группы может быть исключена.
Вторая группа состоит из двух пар верхних клеток крайних столбцов, определяющих минтермы xyzv, xyzv и xyzv, xyzv. Сумма этих минтермов дает
т.е. из группы исключаются две переменные: x и 
.
Третья группа состоит из восьми клеток второй и третьей строк, для которых v = 1, а переменные х, у, z входят с прямыми и инверсными значениями, в связи с чем переменные х, у, z из этой группы могут быть исключены. Сумма минтермов обеих строк будет равна v.
|
|
|
На основании проведенных операций получаем минимальную функцию, выраженную в ДНФ: 
Карта Карно позволяет также провести минимизацию той же функции в КНФ по нулевым значениям минтермов, находящихся в пустых клетках карты (рис. 1.5) и определяющих нулевое значение функции, т. е. ее инверсное значение F. Порядок проведения минимизации сохраняется прежним. Минимизирующие контуры, охватывающие соседние клетки с нулевым значением минтермов рассматриваемой функции, показаны на рис.6 пунктиром. Из карты Карно находим F= хуz + уzv + xzv + xyv.
Воспользовавшись инверсным преобразованием (1.8), находим минимальную функцию, выраженную в КНФ. равносильную ДНФ:
F = (x+y+z+v)(y+z+v)(x+z+v)(x+y+v).
Минимизация функции в ДНФ или КНФ равноправна. Представление результата минимизации в ДНФ или КНФ зависит от вида функции и состава используемых логических элементов. Реализация функции в ДНФ требует преимущественного использования логических элементов И (И—НЕ), а в КНФ — логических элементов ИЛИ (ИЛИ—НЕ) При использовании логических элементов И (И—НЕ) логическую функцию целесообразно представить в виде произведения переменных, а логических элементов ИЛИ (ИЛИ—НЕ) — в виде суммы переменных. Задачу решают, воспользовавшись правилом двойной инверсии и теоремой де Моргана. Для рассматриваемой функции соответственно имеем:
F = xyzyzv, Р = х+у+z+v+у+z+v+x+z+v+x+y+v.
В качестве примеров определим минимальные функции в ДНФ и КНФ, представленные в виде карт Карно для трех переменных (5) и четырех переменных (рис.1. 6).
Дата добавления: 2018-02-15; просмотров: 2046; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!