Добавлен: 10.02.2019
Просмотров: 7422
Скачиваний: 53
Далее
эти компоненты логически суммируют. В
итоге выражение для функции будет иметь
вид, соответствующий СДНФ
.
Проверка правильности полученного
результата может быть произведена
простым перебором значений переменных
и вычислением функции. Первое слагаемое,
а значит и вся функция обращается в
единицу, когда Х1=1,
Х2=0, Х3=0.
Поэтому Х2,
Х3
и входят в него с инверсиями, так как
только в таком случае
.
Аналогичным образом выглядит ситуация для последних двух строк таблицы. На остальных наборах ни одна из компонент формулы в единицу не обращается, следовательно функция будет равна нулю.
Рассмотренную
функцию можно представить и в конъюнктивной
нормальной форме. В этом случае для
каждого набора переменных, на котором
она обращается в нуль, записывают
логическую сумму всех переменных. Если,
значения переменных равны единице, то
они должны входить туда с инверсией, а
если нулю – то в прямом виде. Полученные
суммы называются конституентами нуля.
Далее их логически перемножают. Для
приведенной ранее функции
запись в виде КНФ имеет вид, который
одновременно представляет собой и СКНФ
.
Такое представление абсолютно эквивалентно предыдущему, но сложнее по структуре из-за того, что на восьми наборах переменных функция лишь три раза обращается в единицу и пять раз принимает нулевое значение. При ее записи в виде СДНФ в выражении войдет три компоненты, а в форме СКНФ – пять. Поэтому на практике часто используют ту форму представления, которая позволяет получить выражение минимальной сложности.
|
Х1 |
Х2 |
Х3 |
||
|
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
Единичных
значений у нее будет меньше, чем нулевых,
и СДНФ окажется проще. Для функции,
представленной в данной таблице при
использовании обычного подхода получим
а
для инверсной функции выражение примет
вид
.
Чтобы
вернуться к исходной функции достаточно
проинвертировать обе части данного
равенства
.
Хотя это и не СДНФ, но данное выражение
гораздо проще, предыдущего, что в ряде
случаев важнее канонической формы
представления.
Последнее связано с тем, что при разработке устройств, работающих с цифровыми сигналами, их функционирование описывают в виде совокупности логических функций, а затем реализуют с помощью электронных узлов. Чем компактнее удается получить выражение для функции, тем проще аппаратно реализовать соответствующую ей процедуру обработки.
В алгебре логики применяются специальные процедуры минимизации логических функций, позволяющие в ряде случаев представить их с использованием минимального количества логических операций. Некоторые функции минимизировать, то есть сократить количество, входящих в их состав компонент нельзя, а для других это возможно и разными способами.
Пусть
исходная функция представлена в ДНФ и
имеет вид
.
Для ее преобразования можно воспользоваться
правилами и основными законами алгебры
логики. Если из первых двух слагаемых
за скобки вынести произведение Х1·Х2,
то функция
примет вид.
.
Так как сумма прямого и инверсного
значений одной и той же переменной Х3
равна единице, а умножение на единицу
оставляет результат неизменным, то
.
В
оставшемся выражении за скобки можно
вынести Х1,
выражение в скобках опять будет равно
единице и в итоге
.
То есть данная конкретная функция от
трех переменных, ранее содержащая три
компоненты будет равна Х1.
В ходе выполнения процедуры минимизации часть переменных исчезает. Это происходит при обработке пар слагаемых, отличающихся тем, что какая-либо переменная входит в одно из них в прямом, а в другое - в инверсном виде, причем все остальные компоненты слагаемых совпадают. В этом случае из двух слагаемых получается одно с уменьшенным на единицу количеством переменных.
Отсюда
следует, что выражение
минимизировать можно, а -
нет. Если за скобки вынести Х1,
то в выражении
число переменных не уменьшится.
Таким образом, для минимизации требуется просмотреть все компоненты, входящие в состав функции и попарно сгруппировать слагаемые, отличающиеся значениями лишь одной переменной. Затем вместо них записать выражение с уменьшенным на единицу числом переменных,. Эта процедура может повторяться несколько раз. В итоге форма представления исходной функции будет содержать минимальное количество слагаемых и переменных.
Аналогичным образом проводится минимизация функций, представленных в конъюнктивной форме. Формализовать этот процесс можно используя так называемые карты Карно. Данный прием особенно удобен, если число аргументов логической функции не превышает четырех-пяти.
|
Х1 |
Х2 |
Х3 |
F1 |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
Пусть имеется таблица некоторой функции F1 от трех переменных. В виде СДНФ функция содержит пять слагаемых и выглядит следующим образом. Ее можно минимизировать аналитически, так как в данном выражении существуют пары слагаемых, в которых меняется значение лишь одной переменной. Это первое и третье, четвертое и пятое. Проделав необходимые действия, получим
Однако для рассматриваемой функции процесс минимизации можно продолжить дальше. Если в исходном выражении рассмотреть первое и второе слагаемые, то можно сделать вывод, что обрабатывая их, удалось бы сократить переменную (Х2), но в преобразованном выражении первое слагаемое уже изменено и данная процедура формально не выполнима.
В
то же время в соответствии с законами
алгебры логики, в частности Х+Х=Х, в любое
выражение можно без изменения результата
логически прибавлять любые имеющиеся
там слагаемые. Следовательно, если в
первоначальную форму представления
функции прибавить
,
то после обработки этой компоненты со
вторым слагаемым, получится
.
Выражение для F1
примет вид
,
соответствующий минимальной дизъюнктивной
форме представления рассматриваемой
функции.
Объединение слагаемых с одновременным уменьшением числа входящих в их состав переменных, часто называется склеиванием. В целом аналитическая процедура минимизации оказывается достаточно длительной даже простых функций.
Карта
Карно представляет собой таблицу,
количество клеток или ячеек в которой
равно числу значений принимаемых
функцией, которое связано с количеством
переменных
соотношением
.
Для функции от трех переменных их будет
восемь. Ячейкам карты приписываются
все возможные значения комбинаций
аргументов. Совокупность аргументов в
каждой комбинации разбивается на две
группы. У функции F1
в качестве одного из возможных вариантов
разбиения в одну группу можно объединить
Х1,
Х2,
и отдельно рассматривать Х3,
либо сгруппировать Х1,
Х3, а Х2
представлять отдельно. Возможны и иные
варианты.
Столбцы
обозначаются комбинациями логических
произведений прямых и инверсных значений
соответствующих переменных группы. Для
первого случая разбиения они будут
такими
.
Комбинации
аргументов, используемые в обозначении
соседних столбцов должны отличаться
лишь в одном разряде. То есть
и
но не
и
,
так как здесь меняют значения сразу обе
переменные. Верхнюю строку можно
обозначить Х3, а нижнюю
,
однако возможен и вариант
.
В итоге таблица будет иметь следующий
вид.
Д
алее
карту Карно заполняют значениями
функции, которые она принимает на
соответствующих наборах переменных.
Если аргумент в наборе равен единице,
то в обозначение строки или столбца он
входит без инверсии, а если нулю – то с
инверсией. Таким образом, для рассматриваемой
функции
,
и т.д. Процедура минимизации заключается
в том, что расположенные рядом единицы
охватываются так называемыми контурами
склейки, причем некоторые из единиц
могут входить сразу в несколько контуров,
а некоторые ни в один. Количество ячеек
в контуре должно быть равно одному из
чисел ряда
.
Из
приведенной ранее таблицы следует, что
функция
принимает единичное значение когда
Х1=Х2=Х3=1,
то есть на наборе Х1Х2Х3,
а также при Х1=Х3=1,
Х2=0. Таким
образом, в выражение для функции будут
входить компоненты
и при их склеивании исчезнет переменная
Х2.
Процедура
минимизации с использованием карт Карно
проводится следующим образом. Проверяются
переменные в контурах склейки и если
они меняют свое значение, то их не вносят
в запись соответствующей компоненты
функции. Рассмотрение верхнего контура
дает произведение Х1Х3,
так как Х2
меняет свое
значение. Из следующего контура получится
выражение
.
Оставшаяся
единица соответствует комбинации
переменных
.
Таким образом минимизированное выражение
для функции будет иметь вид
совпадающий с полученным в ходе первого
этапа ее минимизации аналитическим
способом. Однако там добавление
вспомогательной компоненты, которая
не изменила значения функции, позволило
устранить еще одну переменную и
окончательное выражение получилось
проще.
А
налогичный
подход возможен и при использовании
карт Карно. Для этого вводятся
дополнительные контура, охватывающие
уже склеенные единицы. Если ввести такой
контур для нижней строки то вместо
получится
и функция примет вид,
полностью совпадающий с результатом
аналитической минимизации.
Контура
склейки можно выбрать и по другому. В
этом случае выражение для функции станет
таким
.
Оно не совпадает с предыдущим, но также
является минимальной дизъюнктивной
формой представления той же функции.
Отсюда следует, что минимальных форм
может быть несколько.
Е
сли,
как показано штриховой линией, охватить
дополнительным контуром уже склеенные
единицы, то структура выражения
,
описывающего функцию, усложнится, хотя
сама функция не изменится. Поэтому число
контуров обычно стремятся выбрать
минимальным.
Д
ля
некоторой функции
картина распределения ее значений может
выглядеть следующим образом. В этом
случае формируются два горизонтальных,
контура склейки, а нижняя правая единица
остается одна. Выражение для функции
примет вид.
.
В нем первые два слагаемых отличаются
значением переменной Х3
и полученное соотношение можно
аналитически минимизировать до
.
Эта же процедура реализуется и с использованием карты Карно, для чего потребуется образовать контур склейки, включающий в себя четыре рядом расположенных единицы и, проанализировав какие из аргументов не меняются, оставить только их в выражении для функции. В данном случае неизменной остается лишь переменная Х1, которая и войдет в окончательное выражение.
К
ак
уже отмечалось, склеивать расположенные
соответствующим образом единицы
допускается, если их количество кратно
степени двойки, то есть 2,4,8,16 и т.д.
Если
сравнить комбинации аргументов для
крайних клеток одной строки карты Карно,
то можно убедиться, что они также
отличаются значением лишь одного из
них. Для левой нижней клетки комбинация
имеет вид
,
а для правой -
.
Так как эти компоненты входят в выражение
описывающее ДНФ функции, то в ходе
дальнейшей минимизации должно остаться
произведение
.
Таким образом, форма представления
рассматриваемой функции может быть
дополнительно упрощена до вида
.
Карта
Карно является как бы разверткой объемной
фигуры, поэтому ее крайние клетки на
самом деле располагаются рядом и
комбинации соответствующих переменных
отличаются значением лишь одной из них.
Это позволяет вводить контура склейки,
охватывающие и крайние группы ячеек.
На карте такой контур условно представляется
как разорванный. Его введение для
приведенного примера трансформирует
компоненту
в
.
К
ак
уже отмечалось, рассмотренная картина
чередования переменных для обозначения
строк и столбцов не является единственно
возможной. Альтернативный вариант карты
Карно для рассматриваемой функции
выглядит следующим образом. Единицы и
нули здесь будут располагаться по
другому, иными станут контура склейки,
но результат минимизации окажется тем
же
.
П
усть
имеется некоторая функция Y
от четырех переменных и карта Карно для
нее выглядит следующим образом. Здесь
одним контуром можно охватить восемь
единиц, находящихся в нижней части
карты, а вторым четыре единицы в правом
столбце.
Единицу,
расположенную в ячейке
можно объединить с одной из единиц
нижней группы, образовав контур из двух
клеток. Склеить эту пару с единицами
правого крайнего столбца нельзя, так
как они расположены не рядом и при
переходе от одного столбца к другому
меняются сразу две переменных.
Левую
верхнюю единицу можно объединить с
правой верхней, либо с левой нижней,
однако целесообразнее создать контур
из четырех единиц. Такая склейка краевых
клеток возможна, так как карта Карно
данной конфигурации формально представляет
собой сферу, то есть у нее все края
состыкованы и крайние четыре клетки на
самом деле располагаются рядом. Отсюда
следует, что минимизированное выражение
для функции будет иметь вид
Для функции от пяти переменных, получится карта с 32 клетками, а если переменных шесть, то карта Карно будет содержать 64 ячейки. При этом простота и наглядность рассмотренного способа минимизации теряются, и поэтому используются иные подходы.
В ряде случаев работа некоторых устройств с двумя возможными состояниями описывается так называемыми неполностью заданными или недоопределенными функциями. Они отличаются от ранее рассмотренных тем, что некоторые наборы переменных не могут реализовываться.
|
Х3 |
Х2 |
Х1 |
Z |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
* |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
* |