Числовой способ задания фал

Способы задания функций алгебры логики.

Дата добавления: 2015-08-31 ; просмотров: 9977 ; Нарушение авторских прав

При сопоставлении функций АЛ с дискретными автоматами аргументы функций, сопоставляются с входами, а сами функции с выходами дискретного автомата.

Поскольку дискретный автомат имеет конечное число входов, то мы будем иметь дело с функцией конечного числа аргументов. Если автомат имеет m входов, то количество входных переменных тоже m и число возможных комбинаций наборов значений этих входных аргументов (переменных) К=2 m .

Поскольку автомат имеет конечное число входов, его состояние описывается конечным числом значений функций выходов. Существует несколько способов задания функций АЛ и дискретного автомата.

1. Табличный способ. При этом способе функция задается в виде таблицы истинности, представляющей собой совокупность всех наборов переменных и соответствующих им значений функции.

Таблица истинности содержит 2 m строк, m столбцов (по количеству входов) и один столбец для записи значения функции.

Например: пусть требуется задать функцию трех переменных F1(Х1,Х2,Х3) (рис. 1.4), т.е. автомат на три входа и на один выход, следовательно, M=3, К=8.

Следующий способ задания дискретного автомата – числовой. В Этом случае функция задается в виде десятичных эквивалентов номеров наборов аргументов, при которых функция принимает единичное значение. Например, для рассмотренного выше примера функция F1 принимает единичные значения на наборах переменных со следующими номерами: 1, 2, 5, тогда числовой способ задания будет иметь вид

.

Координатный способ. При этом способе дискретный автомат задается с помощью карты его состояния, которая известна как карта Карно.

Карта Карно содержит 2 m клеток по числу наборов значений переменных. Каждая клетка определяется координатами строк и столбцов, соответствующими определенному набору переменных. Все входные переменные разбиваются на 2 группы так, что одна группа определяет координаты строк, а другая — координаты столбцов. В каждой клетке карты Карно проставляется соответствующее значение функции на заданном наборе. Пример задания функции трех переменных приведен на рис. 1.5. Числовое выражение этой функции выглядит так:

Пример построения карты Карно для функции 4-х переменных. Пусть функция задана в числовой форме и имеет вид:

,

следовательно, К=16, m=4.

Сначала проводим разметку координат карты Карно без указания значений функции. Для удобства воспользуемся указанием «шапки» в виде прямых линий, “под” которыми переменные входят в значение координат без отрицания (рис.1.6). Таким образом, по столбцам и по строкам переменные входят без отрицания в пределах линии-шапки.

Для наглядности координаты клеток карты Карно указаны в трех формах: в виде наборов переменных; в виде двоичного числа, соответствующего порядковому номеру набора переменных; в десятичном эквиваленте номеров наборов переменных. На практике координаты внутри клеток не записывают (рис. 1.7), в клетках указываются единичные значения функции, соответствующие “координатным” наборам переменных. Нулевые значения функции в клетки можно не записывать, т.е. клетки, координаты которых определяются наборами переменных с нулевыми значениями функции, можно оставить пустыми.

Следует отметить, что перестановка местами переменных Х1 и Х2, а так же переменных Х3 и Х4 допускается, допускается также перестановка местами переменных Х1Х2 и Х4Х3. При построении карты Карно, т.е. при задании логической функции, указывают лишь внешние элементы разметки координат (рис. 1.7).

Аналитический способ задания функции алгебры логики. При этом способе функция задается в виде аналитического выражения, полученного путем применения каких-либо логических операций.

Например: .

Совершенная нормальная дизъюнктивная форма (СНДФ). По таблице истинности можно составить логическое выражение, содержащее наборы переменных, в которые входят все переменные с отрицанием или без. Одна из его форм называется СНДФ.

В качестве примера получения СНДФ рассмотрим случай задания логической функции в виде таблицы истинности. Пусть задана функция трех переменных. Таблица истинности этой функции показана на рис. 1.8. (очевидно, что значения функции взяты произвольно и могут быть любыми).

Из таблицы истинности видно, что функция принимает значение логической единицы только на трех наборах переменных, т.е. на 2, 4 и 5-м наборах. Для второй строки (второго набора переменных) можно записать: Х1=0, Х2=1, Х3=0, следовательно, функция f(0,1,0)=1. Принято (по умолчанию) считать, что если переменная в «нормальном» состоянии имеет значение логической единицы, а в инверсном — логического нуля, тогда функцию для второй строки можно представить в виде `X<sub>1</sub>Х<sub>2</sub>X<sub>3</sub> = 1. Для четвертой строки — `X₁X₂Х₃ = 1 и для пятой строки — Х₁X₂Х₃ = 1. Аналитическое выражение функции выглядит как

.

Каждое произведение содержит все три переменные с отрицанием или без отрицания и соответствует только одной строке набора переменных, на котором функция принимает значение логической единицы. Произведения, в которых содержатся все переменные с отрицанием или без, называются конституентами единицы илиминтермами. Функция будет представлять логическую сумму всех произведений, равных логической единице. В нашем примере вся сумма (дизъюнкция) соответствует совокупности произведений переменных для трех строк.

СНДФ любой функции записывается по таблице истинности согласно следующему правилу.

Для каждого набора переменных, на которых функция принимает значение логической 1, записываются конституенты, и все эти конституенты объединяются дизъюнктивно.

Переменные каждой строки, имеющие значение логического 0, в конституенты входят с отрицанием (записываются в произведение в инвертированном виде), а переменные, имеющие значения логической 1 — без отрицания.

Любую логическую (булеву) функцию можно представить дизъюнкцией конституент. Если одно из произведений не содержит хотя бы одной переменной, то такая форма называется нормальной дизъюнктивной формой (НДФ).

Например: .

Совершенная нормальная конъюнктивная форма (СНКФ). СНКФ можно построить по таблице истинности также как СНДФ. Для чего все значения функции представляют в инверсном виде и записывают СНДФ для инверсной функции. Далее, используя закон де Моргана, получают конъюнкцию всех дизъюнкций. В каждую дизъюнкцию входят все переменные строки таблицы, для которой функция до инвертирования принимала значение логической 1.

Если (хотя бы одна) дизъюнкции, которые называются также макстермами (конституентами нуля), не содержат отдельные переменные, то такая форма записи функции называется нормальной конъюнктивной формой (НКФ).

Пример записи СНКФ. Пусть функция представлена в виде таблицы истинности (рис. 1.9).

Элементарные функции алгебры-логики.Среди всех функций алгебры логики особое место занимают функции одной и двух переменных, называемые элементарными. В качестве логических операций над переменными, эти функции позволяют реализовать различные функции от любого числа переменных.

Общее количество функций АЛ отm переменных R=2 k , где k=2 m . Рассмотрим элементарные функции от двух переменных

Источник

Задание и минимизация

2.2 Графический способ

Д анный способ задания ФАЛ основан на сопоставлении наборам значений переменных ФАЛ точек n -мерного пространства. При этом множество наборов 2 n определяет число вершин n -мерного единичного квадрата или куба, которым приписаны значения функции на этих наборах. Куб или квадрат называют единичным, так как каждое их ребро соединяет вершины, наборы которых различаются только одной переменной.

ФАЛ задается единичным квадратом, если она зависит от двух переменных. Так, например, для таблицы 2.1 ФАЛ можно задать в виде квадрата, показанного на рисунке 2.1.

ФАЛ задается единичным кубом, если она зависит от трех аргументов. Так для таблицы 2.2 ФАЛ будет задана кубом, показанным на рисунке 2.2.

Графический способ задания ФАЛ является достаточно наглядным, однако он может быть использован при двух и трех аргументах, реже четырех или пяти. Как правило, если число аргументов функции более трех, то используют другие способы задания ФАЛ.

2.3 Координатный способ

При координатном способе ФАЛ задается в виде координатной карты состояний (карты Карно). Карта состояний представляет собой прямоугольную таблицу, разделенную на клетки. Общее число клеток карты равно числу наборов функции k = 2 n , а все переменные ФАЛ разделяются на определяющие строки и определяющие столбцы карты.

На пересечении строки и столбца расположена клетка, в которую записываются значения ФАЛ на выбранном наборе переменных. Разделение переменных на группы выполняется таким образом, чтобы в соседних клетках наборы различались значением лишь одной переменной.

П риведем примеры карт Карно, соответствующих таблицам 2.1, 2.2 и 2.3. Для таблицы 2.1 карта Карно имеет k = 2 2 = 4 клетки. Она представлена на рисунке 2.3.

Как видно из рисунка 2.3 для каждого аргумента карта состояний разбивается на две части. Одна половина карты соответствует прямому значению аргумента (под прямой чертой), а другая – инверсному его значению (под фигурной скобкой).

Для таблицы 2.2 карта состояний должна иметь k = 2 3 = 8 клеток. Она представлена на рисунке 2.4. Карта увеличивается в два раза при увеличении количества аргументов на единицу.

При четырех переменных карта Карно имеет k = 2 4 = 16 клеток. Для таблицы 2.3 она имеет вид, показанный на рисунке 2.5.

Карта для пяти переменных содержит 2 5 = 32 клетки. При этом общая карта состоит как бы из двух четырехмерных подкарт, расположенных одна над другой. Практически такой вариант неприемлем, поэтому подкарты располагают в одной плоскости (рисунок 2.6). Подкарта 1 располагается под прямым значением переменной х 5 , а подкарта 2 – под инверсным значением этой переменной.

Координатный способ задания ФАЛ, наряду с табличным, находит очень широкое применение. Однако он имеет недостаток, связанный с ограничением числа переменных. Обычно координатный способ используется при числе переменных до четырех, реже – до пяти, шести.

2.4 Числовой способ

При числовом способе задания ФАЛ каждому набору переменных ставится в соответствие определенное число в двоичной системе исчисления и присваивается ему соответствующий десятичный номер. Функция задается в виде десятичных номеров, на которых она принимает единичные (первый вариант числового задания) или нулевые (второй вариант числового задания) значения.

Так, например, для таблицы 2.1 по первому варианту ФАЛ будет записана следующим образом: f = <1, 2>x 1 x 2 , а по второму варианту – f =  <0, 3>x 1 x 2 . Для таблицы 2.2 числовая запись ФАЛ по первому варианту имеет вид f = <1, 2, 3, 6>x 1 x 2 x 3 , по второму варианту – f =  <0, 4, 5, 7>x 1 x 2 x 3 , а для таблицы 2.3 (первый вариант) f = <1, 2, 3, 5, 6, 8, 9, 12, 13, 15>x 1 x 2 x 3 x 4 и f =  <0, 4, 7, 10, 11, 14>x 1 x 2 x 3 x 4 (второй вариант). Знак «» во втором варианте записи указывает на то, что используются наборы нулевых значений функции.

В приведенных выражениях в фигурных скобках через запятую записаны в порядке возрастания номера наборов, на которых ФАЛ равна «1» (счет ведется с нуля). Сразу же за фигурными скобками проставляются в виде индексов аргументы ФАЛ, начиная со старшего разряда.

Данный способ задания ФАЛ является одним из наиболее простых, однако, его недостаток – слабая наглядность.

2.5 Аналитический способ

При данном способе ФАЛ задается в виде алгебраического выражения, получаемого при применении каких-либо логических операций к переменным.

Алгебраическое выражение показывает, какие логические операции должны выполняться над аргументами функции, и какова должна быть их последовательность.

Например, применяя операции инверсии, конъюнкции и дизъюнкции можно задать функцию или функцию .

Недостаток данного способа в отсутствии наглядности, а преимущество – в возможности применения математического аппарата для операций с переменными.

2.6 Задание ФАЛ с использованием диаграмм двоичного решения

Диаграмма двоичного решения является разновидностью корневого ориентированного графа. Она обеспечивает полное, краткое и простое описание сложных цифровых функций. На рисунке 2.7 приведена диаграмма двоичного решения для функции .

На рисунке 2.7 прямоугольники с цифрами 0 и 1 соответствуют окончательным значениям ФАЛ. Узлы, обозначенные кружками, соответствуют переменным, от которых зависит ФАЛ, а цифры у ветвей – значениям этих переменных. Диаграммы двоичного решения широко используются для анализа сложных функций, формирования тестов, задач верификации и т.д.

2.7 Задание ФАЛ при помощи диаграмм Венна

Диаграммы Венна, названные по имени священника Джона Венна [3], применявшего их в исследованиях по логике, являются графическим представлением, демонстрирующим соотношения между множествами. На основе соответствия между теорией булевой алгебры и теорией множеств диаграммы Венна очень полезны для визуального представления аксиом и законов булевой алгебры, однако их не следует использовать для построения доказательств тождеств, поскольку большинство общих положений эти диаграммы показать не могут. На рисунке 2.8 приведены диаграммы Венна для констант «0», «1» и элементарных функций логического умножения, сложения и инверсии. Область, ограниченная кружком на рисунке, соответствует одной переменной. На рисунке 2.9 представлена диаграмма Венна для функции .

2.8 Задание ФАЛ с использованием контактных схем

Контактная схема может рассматриваться как техническая модель логических выражений. Одну из первых моделей предложил в 1910 году физик П.С. Эренфест [3], в которой использована аналогия между высказываниями и электрическими контактами, поскольку и те и другие имеют двоичную природу. На рисунке 2.10 приведены контактные модели для констант 0, 1 и элементарных функций логического умножения, сложения и инверсии. Обозначение U ип на рисунках указывает на положительный полюс источника питания.

На рисунке 2.11 представлена реализация на контактах функции .

3 КАНОНИЧЕСКИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ФАЛ

При минимизации ФАЛ часто приходится представлять исходные выражения в нормальном (каноническом) виде, т.е. пользоваться так называемыми каноническими формами ФАЛ [1]. Рассмотрим их подробнее.

К каноническим (общепринятым) формам представления ФАЛ относятся:

ДНФ (дизъюнктивная нормальная форма);

СДНФ (совершенная дизъюнктивная нормальная форма);

КНФ (конъюнктивная нормальная форма);

СКНФ (совершенная конъюнктивная нормальная форма).

Определение. Элементарной конъюнкцией называется конъюнкция (логическое умножение) любого числа различных независимых переменных, входящих в данную конъюнкцию с инверсией или без нее не более одного раза. Например,

Определение. Элементарной дизъюнкцией называется дизъюнкция (логическое сложение) любого числа различных независимых переменных, входящих в данную дизъюнкцию с инверсией или без нее не более одного раза. Например,

Определение. Дизъюнктивной нормальной формой называется дизъюнкция любого числа элементарных конъюнкций. Например,

Совершенная ДНФ содержит в каждом члене все аргументы или инверсии заданной функции.

Определение. Конъюнктивной нормальной формой называется конъюнкция любого числа элементарных дизъюнкций. Например,

Совершенная КНФ содержит в каждой скобке все аргументы или их инверсии.

Формы СДНФ и СКНФ используются в процессе синтеза ДУ для перехода от табличной формы представления функций алгебры логики к аналитической, а также являются базовыми для различных методов минимизации, особенно связанных с применением персональных компьютеров.

Для получения СДНФ по ТИ необходимо проанализировать значение функции на всех наборах аргументов. Каждое единичное значение функции дает один член (одну конъюнкцию) в формуле СДНФ. Все члены (все конъюнкции) соединяются между собой знаками дизъюнкции. Таким образом, число конъюнкций равно числу единиц в значении функции в ТИ.

Каждая конъюнкция состоит из произведения аргументов функции, а каждый аргумент в формуле записывается без инверсии, если в ТИ он равен единице, или с инверсией, если в ТИ он равен нулю.

Например для таблицы 3.1, СДНФ будет иметь следующий вид: Для перехода от ДНФ к СДНФ необходимо добавить к каждому члену (конъюнкции) недостающие аргументы, используя закон дополнительности до единицы. Например,

Ф орма ДНФ является упрощенной, т.е. позволяет построить схему с меньшим числом элементов, чем при форме СДНФ.

При переходе от СДНФ к ДНФ можно использовать для упрощения формулы законы АЛ или любые другие способы минимизации функций.

Форма СКНФ также получается по ТИ. В СКНФ присутствует столько скобок, сколько нулей имеет функция в ТИ. Каждая скобка соединяется знаком конъюнкции.

Для получения аргументов в скобках используются следующие правила.

Если значение аргументов в ТИ равно нулю, то в формуле этот аргумент записывается без инверсии.

Если же в ТИ значение аргумента равно единице, то он записывается в формулу с инверсией.

Все аргументы в скобке соединяются между собой знаками дизъюнкции. Для таблицы 3.1 СКНФ будет иметь следующий вид:

Для перехода от КНФ к СКНФ необходимо, используя законы и правила АЛ (в основном закон дополнительности до нуля), добавить к каждому члену (в каждой скобке) недостающий аргумент.

Большая часть методов минимизации ориентирована на получение минимальной дизъюнктивной нормальной формы (МДНФ).

Определение. Число переменных, входящих в конъюнкцию дизъюнктивной нормальной формы, называется рангом конъюнкции. Для СДНФ ранг конъюнкции равен числу аргументов функции.

Определение. Две конъюнкции называются соседними, если они различаются значением только одной переменной. Например,

Определение Конъюнкция ( n – 1) переменной, полученная в результате склеивания соседних конъюнкций (конституентов) по закону склеивания называется минтермом ( n – 1) ранга; конъюнкция ( n – i ) переменных, полученная склеиванием соседних минтермов [ n – ( i – 1)]-го ранга, называется минтермом ( n – i )-го ранга.

Например, в выражении после применения закона склеивания получатся следующие минтермы 2-го ранга: и функция после первой итерации применения закона склеивания будет состоять из дизъюнкции минтермов 2-го ранга Применив закон склеивания к полученной функции второй раз, получим минтерм 1-го ранга x 2 . Причем, этот минтерм будет реализовывать ту же ТИ, что и исходная функция, т.е.

Определение. Конституенты (минтермы) функции, к которым не применима операция склеивания, называются простыми или первичными импликантами.

Определение. Простой импликант называется существенным, если он образован склеиванием таких конституентов, что по крайней мере для одного из них эта операция была единственной.

Определение. ДНФ ФАЛ, составленная из простых импликантов, некоторые члены которой могут быть избыточными и удалены без нарушения эквивалентности исходной функции, называется сокращенной.

Определение. ДНФ ФАЛ называется тупиковой, если ни один ее член не может быть удален без нарушения эквивалентности исходной функции. К минтермам тупиковой ДНФ (ТДНФ) операция склеивания неприменима.

Определение. ТДНФ называется минимальной, если она содержит наименьшее число вхождений переменных по сравнению с другими ТДНФ. Минимальная форма функции обязательно содержит существенные импликанты.

Можно выделить два направления в решении задачи минимизации.

Первое состоит в отыскании простых импликантов, построении из них тупиковых форм и определении путем перебора минимальной ДНФ.

Второе направление заключается в нахождении всех существенных импликантов, отыскании недостающих для реализации заданной функции простых импликантов и построении ТДНФ.

Каждое из обоих направлений включает целый ряд методов. Рассмотрим некоторые из них.

4 МИНИМИЗАЦИЯ ФАЛ

4.1 Общие положения

При разработке ДУ обычно возникает задача оптимизации их структуры, т.е. получения экономичной и надежной технической реализации [2, 3]. Это означает, что из двух схем ДУ, выполняющих одинаковые функции, следует выбирать ту, которая содержит меньшее число элементов, а при одинаковом числе элементов – ту, суммарное число входов используемых элементов которой будет наименьшим.

Решение этой задачи связано с проблемой минимизации (упрощения, сокращения) ФАЛ, реализующих данное ДУ.

Минимизация – это процесс нахождения такого эквивалентного выражения ФАЛ, которое содержит минимальное число вхождений переменных. При минимизации могут быть различные варианты: получение выражений с минимальным числом инверсных переменных либо с минимальным числом вхождений какой-либо одной переменной и т.д.

Для минимизации функций и поиска наиболее экономичной схемы, реализующей заданное выражение, до сих пор не найдено эффективных алгоритмов, позволяющих решать эти задачи целенаправленно и быстро. Гарантированно найти минимальное выражение для произвольной функции можно лишь методом полного перебора вариантов различных способов группировки в процессе минимизации, а это реально осуществимо лишь при небольшом числе аргументов. С ростом их числа сложность минимизации и поиска экономичной схемы растет экспоненциально и очень скоро становится не под силу ни человеку, ни ЭВМ.

С точки зрения подходов к упрощению логических выражений функции, с которыми имеет дело схемотехник, удобно разделить на три группы: функции малого числа аргументов; «объективные» функции многих аргументов и «субъективные» функции многих аргументов.

К первой группе можно отнести функции двух–пяти аргументов. Статистический анализ реальных схем цифровой аппаратуры показывает, что разработчики в подавляющем большинстве случаев сталкиваются именно с необходимостью реализовывать именно такие функции. Благодаря малому числу переменных таблицы таких функций короткие, вариантов группировки при минимизации не слишком много, хорошо работает наиболее наглядное геометрическое представление, и в общем, минимизация таких функций любым способом серьезных проблем не вызывает.

Ко второй группе – громоздких «объективных» функций – относятся функции более пяти переменных, которые были получены не человеком, а отражают некую объективную природную зависимость. Для этих функций характерно следующее. Во-первых, в них не заложено какой-либо простой логической закономерности, которую можно угадать и использовать для минимизации, т.е. таблица такой функции это просто некая случайная последовательность единиц и нулей. Во-вторых, в силу значительного числа переменных полный перебор вариантов при любом способе поиска минимальной или любой другой экономичной формы практически неосуществим. И, в-третьих, что самое важное, из теоремы О.Б. Лупанова об оценке сложности функций следует, что с ростом числа аргументов доля экономичных по оборудованию функций стремится к нулю, т.е. почти все функции оказываются неупрощаемыми. Следовательно, задача поиска минимальных форм «объективных» функций многих аргументов не только сложна и громоздка, но и с большой вероятностью безнадежна. Это учитывают изготовители элементов, выпуская для реализации функций многих переменных специальные микросхемы – программируемые логические матрицы (ПЛМ) и постоянные запоминающие устройства (ПЗУ). При использовании наиболее распространенных простых вариантов ПЛМ реализация функций будет самой экономичной по затратам аппаратуры, если функция приведена не к минимальной, а к кратчайшей форме. Если же при минимизации ДНФ самую короткую форму получить не удалось, то проигрыш оказывается небольшим, поскольку стоимость реализации на ПЛМ каждой элементарной конъюнкции ДНФ невелика – 1/50 стоимости корпуса. Одной из целей освоения промышленностью ПЛМ как раз и была экономия труда разработчиков схем.

При использовании ПЗУ на них реализуется непосредственно ТИ функции, т.е. ни записи ФАЛ, ни тем более ее минимизации не требуется вообще.

К третьей группе – «субъективных» функций многих аргументов относятся функции, составленные человеком. Особенность их связана с понятием декомпозиции. Это значит, что сложная ФАЛ разбивается на более простые составляющие, из минимальных форм которых в конечном итоге строится аппаратная реализация ДУ. Однако декомпозиция может быть выполнена неудачно, и устройство в результате будет неэффективным. Для того чтобы избежать этого существуют специальные методы декомпозиции, которые позволяют получать приемлемый результат.

Рассмотрим методы минимизации в применении к первой группе функций как наиболее часто и повсеместно встречающихся.

Если значение ФАЛ однозначно определено на всех возможных наборах значений ее аргументов, то она называется полностью определенной (заданной). Если же на некоторых наборах значение функции является безразличным и однозначно не определено, то такая функция называется неполностью или частично заданной.

В соответствии с этим разделим и методы минимизации (упрощения) ФАЛ на две группы: методы минимизации полностью заданных ФАЛ и методы минимизации неполностью заданных ФАЛ.

Источник