Сделай Сам Свою Работу на 5

Класс монотонных функций М





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

Два булевых вектора и находятся в отношении предшествования тогда и только тогда, когда одноименные координаты этих векторов находятся в отношении £: . например, в случае трех переменных наборы их значений имеют номера от 0 до 7. Соответственно отношение предшествования на этих наборах определяется так:

Отношение предшествования на множестве вершин единичного n-мерного куба при является частичным порядком.

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

Очевидно, константы 0 и 1 монотонны. Функция не монотонна, если на нулевом наборе значений переменных ее значение равно 1, но функция не является константой 1, или а функция не является константой 0.

Монотонными являются элементарные функции: . Тогда как .

Мажоритарная функция в соответствии с определением является монотонной, а трехместная функция XOR – нет, , так как, например, , а . Можно также указать и на другие нарушения монотонности этой функции.



Множество всех монотонных функций определим как

Теорема. Класс М замкнут и неполон, т.е. [M]=M¹P2.

ª Так как тождественная функция монотонна, для доказательства замкнутости достаточно показать, что суперпозиция монотонных функций монотонна. Пусть - m-местная монотонная функция и

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

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

и, следовательно,

А так как то монотонность доказана, а значит, доказана и замкнутость класса М. Неполнота М следует из существования немонотонных функций. ¨

Лемма о немонотонной функции: из произвольной немонотонной функции с помощью подстановки констант и отождествления переменных можно получить функцию отрицания.

ª Пусть Это означает, что существуют такие наборы значений переменных, находящихся в отношении предшествования, что а Последнее означает, что Из того, что значения функции на выбранных наборах не равны, следует, что сами наборы также не равны. Пусть расстояние Хемминга между наборами равно 1 и обусловлено различием значений переменной Образуем функцию Тогда Так как функция не монотонна, то



.

Соотношение определяет одноместную функцию отрицания.

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

Пример применения леммы о немонотонной функции.

Рассмотрим элементарную булеву функцию ®, вектор значений которой имеет вид: . Это двуместная функция, нулевой набор предшествует второму, расстояние Хемминга между ними равно 1 по первой переменной и . Вторая переменная в обоих наборах равна 0, а первая принимает оба возможных значения (мелькает). «Работа» леммы над этой функцией представлена ниже:

.

В формуле, которая задает рассматриваемую булеву функцию, тем переменным, которые не меняют значение в сравниваемых соседних наборах, на которых происходит нарушение монотонности, присваиваются значения этих переменных. Единственная переменная, изменяющая значение на рассматриваемой паре соседних векторов, получает значение x.

В соответствии с леммой о немонотонной функции при этом будет получена одноместная функция отрицания.

¨

Класс линейных функций L

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



где коэффициенты . Такая функция называется симметрической.

Множество всех линейных функций обозначается

Терема. Класс L замкнут и неполон, т.е. [L]=L¹P2.

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

Неполнота L следует из существования нелинейных функций. ¨

Очевидно, что мощность класса n-местных линейных функций равна .

Лемма о нелинейной функции. Из произвольной нелинейной функции с помощью подстановки констант, тождественной функции и функции отрицания и, возможно, навешиванием отрицания на всю функцию, можно получить конъюнкцию и дизъюнкцию.

Пусть . Тогда ее полином по mod2 содержит монотонные элементарные конъюнкции ранга выше 1. Выберем среди этих элементарных конъюнкций конъюнкцию минимального ранга (>1). Для удобства рассуждений положим, что выбранная конъюнкция содержит переменные x1 и x2. Выполним следующие подстановки: всем переменным, участвующим в выбранной конъюнкции, кроме переменных x1 и x2, присвоим значение1. А всем переменным, не вошедшим в выбранную конъюнкцию, присвоим значение 0. В силу единственности полинома, представляющего данную функцию, после выполнения равносильных преобразований полином примет вид:

.

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

a0 a1 a2 Полином Функция
x1x2 F(x1x2)=x1x2
x2Åx1x2=

Доказано, что из нелинейной функции могут быть получены конъюнкция и дизъюнкция.

Теорема Поста

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

Следствие 1. В любом полном множестве существует полное подмножество, состоящее не более, чем из пяти функций.

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

Для доказательства функциональной полноты системы булевых функций по критерию Поста необходимо построить таблицу Поста, строки которой именуются функциями исследуемой системы, а столбцам присваиваются имена предполных классов. На пересечении i-й строки и j-го столбца таблицы ставится 1, если i-я функция принадлежит j-му классу, и 0 – в противном случае. Система функций полна, если в каждом столбце таблицы имеется хотя бы один 0. В противном случае система не является функционально полной в Р2, так как входит целиком в один из предполных классов.

Пусть имеется система функций D={(x1Å x2Åx3 ), (x1®x2), (x1&`x2), 1}. Таблица Поста для нее будет иметь вид:

  T0 T1 S M L
f1={(x1Å x2Åx3 )
f2=(x1®x2)
f3=(x1&`x2)
f4=1

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

Другой вопрос, связанный с использованием теоремы Поста, состоит в определении минимально необходимого набора функций из множества D, образующих функционально полную систему. Система функций D ÍР2 называется базисом в Р2, если она функционально полна в Р2, но при исключении из нее любой функции, она перестает быть функционально полной, т.е. [D]=P2, и "f:((fÎD)®([D\{f}]ÌP2)). Для определения базиса, соответствующего данной системе D, используют метод Петрика, состоящий в следующем. Рассматривая функции системы D как переменные, строим из них конъюнктивную нормальную форму, содержащую пять (по числу предполных классов) элементарных дизъюнкций, включая в каждую элементарную дизъюнкцию только те функции системы, которые принадлежат данному предполному классу, соединяя полученные дизъюнкции связкой &. Затем преобразуем полученное выражение к ДНФ, использую аксиомы и тождества логики высказываний. Каждая из конъюнкций в полученной ДНФ содержит все функции, образующие базис. Длина ДНФ соответствует числу базисов, соответствующих данной системе. Для рассмотренного примера применение метода Петрика состоит в следующем:

(f2Úf4)&f3&(f2Úf3Úf4)&(f1Úf2Úf3)&(f2Úf3)=(f2Úf4)&f3=f2f3 Ú f3f4.

Таким образом, данная система содержит два базиса: D1= {f2,f3 }, D2={f3, f4}.

Список литературы

1. А.Я. Савельев. Прикладная теория цифровых автоматов. М.: Высшая школа, 1987.

2. С.П. Плеханов. Симметричные карты - мощное средство минимизации булевых функций при проектировании цифровых устройств больших размерностей.// Электронная техника. Сер. 10. Микроэлектронные устройства. Вып. 4(88), 1991

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.