Далее эти компоненты логически суммируют. В итоге выражение для функции будет иметь вид, соответствующий СДНФ . Проверка правильности полученного результата может быть произведена простым перебором значений переменных и вычислением функции. Первое слагаемое, а значит и вся функция обращается в единицу, когда Х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	*

Пусть для функции Z от трех переменных комбинации Х1=1, Х2=0, Х3=1 и Х1=1, Х2=1, Х3=1 никогда не появляются. В этом случае сказать о том, какие значения будут у функции на этих наборах переменных нельзя, так как она на них не задана (не определена). Формально в таблице определяющей функцию, это отмечается записью в соответствующие клетки каких-либо значков, к примеру звездочек

---

Смотрите также файлы

• ВолковЭТНОПЕДАГОГИКА.doc

• В47 Мировое образовательное пространство.docx

• синтаксис.pdf

• Основные направления деятельности психолога и виды психологической помощи.docx

• 2012_MATEMATIKA-2_GiMU Tovarovedenie NULEVOJ.doc