Пять классов булевых функций

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

Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булефых функций (f₁, f₂, ... f_k), что произвольная булева функция f может быть записана в виде формулы через функции этой совокупности.

Исходя оз определения СДНФ, СПНФ, СКНФ и ФПСБФ следует отнести системы: (/\, \/, не),(/\, , не).
Это обуславливает целесообразность постановки задачи определения свойств, которыми должны обладать функции, составляющие ФПСБФ.
Решение этой задачи основано на понятии замкнутого относительно операции суперпозиции класса функций. Класс булевых функций, функционально замкнутый по операции суперпозиции, есть множество функций, любая суперпозиция которых дает функцию, также принадлежащую этому множеству. Среди функционально замкнутых классов выделяют классы обычного типа, называемые предполными, которые обладают следующими свойствами. Предполный класс S не совпадает с множеством Р₂ всех возможных булевых функций, однако, если в него включить любую, не входящую в S, булеву функцию, то новый функционально замкнутый класс будет совпадать с множеством Р₂. Проведенные исследования показали, что преднолных классов пять, а для построения ФПСБФ необходимо и достаточно, чтобы ее функции не содержались полностью ни в одном из пяти предполных классов.
Перечислим предполные классы булевых функций:

1. булевы функции, сохраняющие константу 0;
2. булевы функции, сохраняющие константу 1;
3. самодвойственные булевы функции;
4. линейные булевы функции;
5. монотонные булевы функции;

К булевым функциям сохраняющим константу 0, относят такие булеы функции f(x₁,...,x_n), для которых справедливо соотношение f(0,...,0)=0.

Примерами булевых функций, сохраняющих константу 0, являются функции f₀, f₁,..., f₇ (табл 3.1). Поскольку таблица истинности для функций, сохраняющих константу 0, в первой строке значений функций содержит 0, то имеется ровно 2^{2(^n)-1} таких функций.

К булевым функциям сохраняющим константу 1, относят такие булеы функции f(x₁,...,x_n), для которых справедливо соотношение f(1,...,1)=1.

Примерами булевых функций, сохраняющих константу 1, являются функции f₁, f₃, f₅, f₇, f₉, f₁₁, f₁₃, f₁₅ (табл 3.1). Поскольку таблица истинности для функций, сохраняющих константу 1, в последней строке значений функций содержит 1, то имеется ровно 2^{2(^n)-1} таких функций.
Прежде чем ввести понятие класса самодвойстенных функций, дадим следующее определение.

Булевы функции f₁(x₁,...,x_n) и f₂(x₁,...,x_n) называются двойственными друг другу, если выполняется соотношение

f₁(x₁,...,x_n)=/(f₂(/x₁,...,/x_n))

Двойственными являются функции f₀ и f₁₅, f₁ и f₇, f₂ и f₁₁ и т.д. (табл 3.1).

К самодвойственным булевым функциям относят такие булеы функции, которые двойственны по отнощению к самим себе, т.е. справедливо соотношение f(x₁,...,x_n)=/(f(/x₁,...,/x_n)). Если условия назвать противоположными наборами, набор <y₁,y₂,...,y_n> и набор </y₁,/y₂,...,/y_n>, то определение самодвойственных функций дадим следующее.

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

Самодвойственными являются функции f₃, f₅, f₁₀, f₁₂ (табл 3.1). Из определения самодвойственной функции следует, что она полностью определяется своими значениями на первой половине строк таблицы истинности. Поэтому число всех самодвойственных булевых функций f(x₁,...,x_n) равно

К линейным булевым функциям относят такие булевы функции, которые представимы в виде

f(x₁,...,x_n)=с₀ + c₁x₁ + ... + c_nx_n,

где c_i E {0,1}, а + операция "сумма по mod 2".

Линейными являются булевы функции f₀, f₃, f₅, f₆, f₉, f₁₀, f₁₂, f₁₅, (табл 3.1), ибо
f₀ = 0, f₃ = x₁, f₅ = x₂, f₆ = x₁ + x₂, f₉ = x₁ + x₂ + 1, f₁₀ = /x₂ = 1 + x₂, f₁₂ = /x₁ = 1 + x₁, f₁₅ = 1.
Примечание + = .
Поскольку линейная функция однозначно определяется заданием коэффициентов с₀,...,с_n, то число линейных функций равно 2⁽ⁿ⁺¹⁾.
Прежде чем ввести понятие класса монотонных булевых функций, дадим следующее определение.

Двоичный набор Y = <y₁,y₂,...,y_n> не меньше двоичного набора B = <b₁,b₂,...,b_n> , если для каждой пары (Y_i,B_i) i = 1...n справедливо соотношение Y_i >= B_i.

Так, набор 1011 >= 1010. Вместе с тем наборы 1011 и 0100 несравнимы в том смысле, что для них не выполняется ни соотношение Y >= B, ни Y <= B.

Булева функция f(x₁,...,x_n) называется монотонной, если для любых двух наборов Y = <y₁,y₂,...,y_n> и B = <b₁,b₂,...,b_n> таких, что Y >= B имеет место неравенство f(y₁,...,y_n)>=f(b₁,...,b_n).

Монотонными являются булевы функции f₀, f₁, f₃, f₅, f₇, f₁₅ (табл. 3.1). Вместе с тем функция f₂ из табл. 3.1 не является монотонной, так как f₂(1,0) > f₂(1,1), хотя набор <1,0> меньше, чем набор <1,1>.
Приведем без доказательства две формулировки теоремы о функциональной полноте.
Теорема.

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

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

Рассмотрим примеры ФПСБФ. Для удобства изложения материала сведем элементарные булевы функциидвух переменных и некоторые функции одной переменной в таблицу, класифицируя каждую из них по признакам принадлежности к предполным классам.

Из таблицы видно, что каждая из функций f₈ и f₁₄ являются ФПСБФ. Иными словами, используя, например, только булеву функцию f₁₄ - "штрих Шеффера", можно записать в виде формулы любую булеву функцию. f₁₄ = х₁ / х₂ = /х₁ v /х₂. Признаком функциональной полноты, очевидно, является наличие плюса в каждом столбце таблицы, хотя бы для одной из составляющих систему булевых функций. К таким ФСПБФ, наиболее распостраненным в практике построения цифровых автоматов, следует отнести:

Иногда удобно строить ФПСБФ при наличии констант, т.е. булевых функций "константа 0", "константа 1". Как следует из таблицы, функция "константа 0" несамодвойственна и не сохраняет 1; функция "константа 1" несамодвойственна и не сохраняет 0. Вместе с тем константы являютя линейными и монотонными функциями. Отсюда непосредственно (на основании теоремы о функциональной полноте) вытекает следующее: система булевых функций является ослабленно функционально полной, если она содержит хотя бы одну нелинейную и хотя бы одну нелинейную и хотя бы одну немонотонную булеву функцию.
Примерами ослабленых ФПСБФ могут служить следующие системы:

Введенное понятие двойственных булевых функций позволяет сформулировать принцып двойственности, заключающийся в следующем: если формула U=c[f₁,...,f_s] реализует булеву фунуцию f(x₁,...,x_n), то формула U*=c[f*₁,...,f*_n], полученная из U заменой функций f₁,...,f_s на двойственные функции f*₁,...,f*_s, соответтвенно реализует функцию f*=f*(x₁,...,x_n), двойственную функции f. Формулу U называют двойственной U. Для формул над множеством {0, 1, /x, x₁x₂, x₁ v x₂} принцип двойственности может быть сформулирован так: для получения формулы U* двойственной формуле U достаточно в формуле U всюду заменить 0 на 1, 1 на 0, & на \/, \/ на &. "

9. Понятие о риске в комбинационных схемах и о гонке сигналов в конечных автоматах.

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

Проектирование цифровой аппаратуры с использованием принципов комплексной миниатюризации на основе достижений микроэлектроники в качестве основной из своих задач выдвигает проблему обеспечения устойчивости ее функционирования при влиянии коструктивно-технологических факторов и дестабилизирующих воздействий внешней среды [1– 4].

Функциональная устойчивость определяется стабильностью реализации цифровым устройством заданного алгоритма работы при наличии разброса задержек выполнения операций в логических элементах, задержек сигналов в линиях связи и электромагнитных наводок паразитных сигналов. Термин “функциональная устойчивость” можно рассматривать также как синоним алгоритмической устойчивости.

В схемотехническом плане проблема функциональной устойчивости может быть сведена к устранению опасных состязаний (гонок) сигналов устройства. Эффект состязаний сигналов, приводящий к неустойчивой работе цифрового устройства, известен давно. Наиболее наглядный пример - эффект “дребезга” контактов реле, кнопок и других электромагнитных устройств. Проблема гонок в цифровой схемотехнике является очень серьезной. Большинство труднообнаруживаемых и удивительно разнообразно проявляющихся ошибок в цифровых схемах связано именно с гонками, возможность появления которых разработчик не предвидел или не заметил.

Состязаниями (гонками) сигналов называется процесс их распространения в различных цепях цифрового устройства при существовании разбросов временных задержек этих цепей. Цепь - совокупность логических и других элементов и линий связи между ними. Алгоритмическим переходом называется изменение сигнала на выходе какой-либо схемы, предусмотренное алгоритмом ее работы. Неалгоритмическим переходом называется изменение выходного сигнала, не предусмотренное алгоритмом ее работы. Опасными называются такие состязания, которые могут привести к неалгоритмическому переходу в цифровой схеме при заданных условиях ее работы, а неопасными называются такие состязания, которые не могут привести к неалгоритмическому переходу. Схемой, свободной от влияния опасных состязаний, называется такая цифровая структура, в которой неалгоритмический переход, возникший в части схемы из-за опасных состязаний, не изменяет алгоритма работы схемы в целом при заданных условиях ее работы.

Задержка логической схемы слагается из задержек срабатывания логических элементов и задержек распространения сигналов по цепям связи между ними. Важнейшим параметром, характеризующим инерционность логического элемента, является среднее время задержки выходного сигнала по отношению к входному t_зд.ср.. Трудоемкость учета задержек зависит от соотношения значений задержек самих логических элементов и задержек в цепи связи t_св.. Если эти значения близки, то задержки различных трактов схемы можно определить лишь после размещения элементов на поверхности печатной платы или кристалла БИС, когда станут известны фактические длины связей. В сверхбыстродействующих ИС и БИС, построенных на ТТЛШ- и ЭСЛ- элементах, время задержки выполнения логической операции в вентиле (логическом элементе) оценивается единицами или десятыми долями наносекунды. В этом случае не считаться с t_св. нельзя.

Ситуации, когда задержки t_св. превышают t_зд.ср., возникают и при использовании не очень быстродействующих элементов, когда сигналы передаются между блоками на достаточно большое расстояние. Однако доля подобных связей невелика, поэтому их можно выделить особо и учесть t_св. в линии связи. Тем не менее для большинства микроэлектронных устройств сейчас (90-е годы) выполняется соотношение t_св.< t_зд.ср..

Задержки различных экземпляров элементов какой-либо серии имеют технологический разброс, который обычно описывают некоторым статистическим законом. Дестабилизирующие воздействия внешней среды, в основном выражающиеся в изменении температуры, напряжения питания и в воздействии радиационного излучения, приводят к расширению диапазона вариации задержки выполнения операции в логических элементах и поэтому могут быть сведены к эквивалентному расширению влияния конструктивно-технологических факторов. Задержка каждого конкретного элемента зависит от количества и типа нагрузок, от паразитной емкости монтажа, числа лет с момента выпуска и ряда других факторов. Точное значение величины t_зд.ср. для конкретного случая не известно, так как в технических условиях изготовитель указывает значение t_{зд.ср.max} для наихудших условий применения. Разработчику часто полезно знать кроме максимальной еще и минимально возможную величину t_зд.ср.. К сожалению, для большинства серийно выпускаемых микросхем значение минимальной задержки в технических условиях не указано и, следовательно, изготовителем не гарантируется. Поэтому если разработчик аппаратуры, предназначеннойдля серийного выпуска, использует микросхемы, в паспорте которых не оговорено минимальное значение задержки, то он вынужден полагать его равным нулю. Никаких юридических оснований считать, что это значение больше нуля у него нет [4].

---

<== предыдущая страница	|	следующая страница ==>
Синтез схем в базисе функции Пирса	|	Состязания и гонки конечных автоматов

---

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

---

Поделиться с ДРУЗЬЯМИ:

Мы поможем в написании ваших работ!