Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Функции, сохраняющие константу
Если в функции f(x1,x2,…,xn) вместо всех переменных поставить одну переменную х, то возможно 4 различных варианта: · a-функция, если f = x; · b-функция, если f = 1; · c-функция, если f = 0; · d-функция, если f =`x; Рассмотрим множество a- и b - функций. Для них f(1,1,…,1) = 1, поэтому эти функции называют функциями, сохраняющими 1. Можно показать, что суперпозиция этих функций будет снова сохранять константу 1. Значит, множество этих функций замкнуто и образует класс функций, сохраняющих единицу. Этот класс обозначают как С1. Аналогично можно показать, что множество a- и c-функций образуют класс функций, сохраняющих константу 0, так как для них f(0,0,…,0) = 0. Этот класс принято обозначать как С0. Функциональная полнота
Мы выделили 5 классов функций алгебры логики. Различных классов функций гораздо больше: так, a-функции образуют свой класс, пересечение классов снова будет классом. Американский математик Э.Пост установил, что классы М, D, L, C1 и C0 являются предполными, и других предполных классов в С нет. Решение задачи формулируется как теорема Э.Поста. Теорема. Для того чтобы множество функций F порождало класс всех функций С, необходимо и достаточно, чтобы это множество содержало, по крайней мере, одну немонотонную, одну несамодвойственную, одну нелинейную, одну несохраняющую константу ноль и одну несохраняющую константу единица функцию. Необходимые условия формулируются из результатов Поста о предполных классах. Необходимо, чтобы в F по отношению к любому из этих классов была функция, не принадлежащая классу. Действительно, если в рассматриваемом множестве нет, например, несамодвойственной функции, то в результате суперпозиций будут реализовываться только самодвойственные функции, то есть нельзя получить, например, конъюнкцию, которая не является самодвойственной. Достаточность доказывается конструктивно. Покажем, как из функций, удовлетворяющих условиям теоремы Поста, получить инверсию и конъюнкцию или дизъюнкцию, составляющие функционально полный базис. Пусть множество содержит функцию f0, не сохраняющую константу ноль, f1, не сохраняющую константу единица, f2 – немонотонную, f3 – несамодвойственную и f4 – нелинейную функцию (все функции не обязательно различные). f0(0,0,…,0) = 1. Для этой функции возможны два варианта значений f0(1, 1,…,1). Если f0 (1, 1,…,1) = 1, то функция является b-функцией, и при подстановке вместо всех аргументов произвольного одного аргумента она превращается в константу 1. Имея константу 1, из функции f1 получаем константу 0, так как f1(1, 1,…,1) = 0. Если f0 (1, 1,…,1) = 0, то функция является d-функцией и при подстановке вместо всех аргументов произвольного одного аргумента она превращается в инверсию. В этом случае рассмотрим функцию f3. Для неё найдется набор значений аргументов <a1, a2,…, a n>, такой, что f(a1, a2,…, an) = f(`a1, `a2,…, `an). В функцию f3 поставим произвольную переменную в прямой форме, если компонента набора ai равна 1, и в инверсной форме, если равна 0, то получим константу, равную f(a1, a2,…, an). Из неё с помощью инверсии получается вторая константа. С помощью констант из функции f2 можно получить инверсию. Для неё найдется два соседних набора, таких, что на меньшем наборе функция равна единице, а на большем – нулю. Если подставим в f2 константы этого набора, где они совпадают, и произвольную перемен-ную, где наборы отличаются, получим инверсию этой переменной. Константы и инверсия позволяют получить конъюнкцию перемен-ных из функции f4. Запишем эту функцию в виде полинома Жегалкина, выделим в нём первое вхождение переменных в конъюнкцию, и все пе-ременные, кроме переменных конъюнкции, заменим константой 0, а переменные в конъюнкции заменим произвольно на два различных аргумента, например на x и y. В результате возможны, с точностью до инверсии (константы С0 в полиноме), следующие варианты: 1) xy; 2) xyÅx; 3) xyÅy; 4) xyÅxÅy.
В первом случае получаем конъюнкцию, что и необходимо получить, во втором варианте полученная функция равна функции `xy, из которой с помощью инверсии получим конъюнкцию. То же самое можно сказать и о третьем варианте, где функция равна `yx. Для последнего варианта функция равна дизъюнкции. Теорема доказана. В табл. 3.3 показана при-надлежность простейших функций к предполным классам. Здесь + озна-чает, что функция принадлежит, а Из таблицы видно, что функциональной полнотой обладают множества {` x , x Ú y }, {` x , x × y }, { x × y , x Å y , 1}. { x ® y, 1}. Особый интерес представляют 2 последние функции, составляющие монофункциональ-ный базис. Такие функции, отве-чающие всем условиям теоремы Поста, получили название функций шефферовского типа. Теорема позволяет определить, является ли заданное множество функционально полным, если нет, то какой функции в нём не хватает. Можно решать задачу построения функции шефферовского типа от более чем двух переменных. Это должна быть d-функция, так как она не сохраняет константы. Как d-функция она немонотонна, и дальше нужно распределить единицы и нули в таблице так, чтобы функция была нелинейной и несамодвойственной.
|
Последнее изменение этой страницы: 2019-03-31; Просмотров: 399; Нарушение авторского права страницы