Для того, чтобы доказать является ли функция полной мы рисуем табличку и смотрим, если среди всех столбиков нету тех, в которых были бы только +, то функция полная. Один из этих столбиков (классов) L отвечает за линейность функции, другой S за монотонность. У меня такой вопрос : как эти 2 параметра определить для любой функции и в частноcти для моей ( в моём случае это x | y ).

Tan а раздел какой? Дискретная математика? И еще что именно тебе надо доказать, и что означает |?

да, дискретка, пардон, что не упомянул! А | черта Шефера

1. линейность по Жегалкину определяется
2. монотонность(имхо он она М а не S, S-самодвойственность) сравниванием следущего и предыдущего значения функции. т.е. берем фун-ю в значении 1, и если она меньше следущего знач ф., которое также находится в 1, то она не монотонна

ой М, извинясь, не так написал а С у нас называют самодуальностью =), что такое по Жегалкину ?

Монотонность доказывается так.
Берем первый элемент a=(0, 0) и b=(0, 1) как второй элемент, тогда Tm:={f| a=<b => f(a)=<f(b)}, := значит по определению. Tm означает класс монотонных функций. Значит сравниваем при следующих наборах:



На счет линейности, то должно удовлетворить TL:={f | f= c0 +c1x1+...+cnxn}, где + это сложение по модулю 2, а c1x1 обозначет конъюнкцию с1 на х1

Добавлено через 5 мин.


Разговор о полиноме Жегалкина. Представление булевой функции над базисом {0, 1, И, +}, где И конъюнкция и + сложение по модулю два.

Добавлено через 7 мин.
Но реально если надо доказать полноту Штриха Шеффера, то это довольно просто, достаточно через него задать функции {И, ИЛИ, НЕ}, о их полносте можно сказать хотя бы из существования СДНФ и СКНФ, т. е. любая функция может быть приведена хотя бы к одной из совершенных форм.

А доказать очень просто.

1) НЕ х= х|x
2) x1 И х2= НЕ (х1|x2)=(x1|x2)|(x1|x2)
3) x1 ИЛИ x2=(НЕ х1) И (НЕ х2)=(x1|x1) И (x2|x2)= ((x1|x1)|(x2|x2))|((x1|x1)|(x2|x2))

пишешь функцию (для 3х переменных) f=a0+a1x1+a2x2+a3x3+a12x1x2+a13x1x3+a23x2x3+a123x1x2x3, цифры являются индексами; + - это +в кружочке(обозначение такое %).

=>f=1+x1+x3+x1x3 т.к. в f входит x1x3 => не линейна, была ты линейна если бы f не содержала бы параных или тройных. т.е. как получил хотяб 1 парное, то уже не линейна

Спасибо огромное, ребята !!!

Плюс в кружочке =) это сложение по модулю 2, напоминает в Паскале xor.

Многочлены Жегалкина
Многочленом Жегалкина называется формула вида
f(x1,….,xn) = a0 + a11. . .1n x11. . .1n.
1<11<...1r<n
Коэффициенты a0,a11. . .1n Î 90,1), a число слагаемых равно 2n.

Теорема Жегалкина. Каждая функция алгебры логики f(x1,….,xn) может быть представлена в виде многочлена Жегалкина, при том единственным образом.

Алгоритм построения многочлена Жегалкина
Способ 1.
1. Находим по таблице функции все наборы {a=(a1,….,an)}, для которых f(x1,….,xn)=1. Если таких наборов нет, то полагаем f=0. Если же функция f на всех наборах равна 1, то полагаем f=1. В случае, когда f – константа, алгоритм закончен.
2. Составляем СДНФ функции f.
3. В СДНФ каждый знак V меняем на
4. Упрощаем полученное выражение, если возможно, использую формулу xy xy=y
5. В полученном выражении каждое отрицание x1 заменяем на x1 1.
6. Раскрываем скобки в полученной формуле, содержащей только операции +,& и константу 1.
7. Приводим подобные члены, использую тождество x x=0. В итоге получаем многочлен Жегалкина данной функции.
Способ 2. Метод неопределенных коэффициентов.
1. Составляем систему линейных уравнений, содержащий 2n уравнений и 2n неизвестных (коэффициенты многочлена Жегалкина)
a0,a1,...,an,a12,a13,...,a12...n:
(1) P(b)=f(b)
где P(x1,….,xn)=a0 a1x1 ... anxn ... a12...nx1x2...xn- искомый многочлен Жегалкина для функции f(x1,….,xn), наборы b пробегают все множество двоичных наборов длины n {b=(b1,….,bn)}, правая часть в уравнения (1) находится по таблице функции f. Отыскав из системы (1) коэффициенты a0,....,a12...n, найдем тем самым искомый многочлен Р.
Определение. Функция f(x1,….,xn) называется линейной, если ее многочлен Жегалкина исчерпывается линейной частью a0 a1x1 ... anxn, иными словами, в многочлене Жегалкина коэффициенты при произведениях переменных равны 0.
Из определения многочлена Жегалкина следует, что для любой функции алгебры логики коэффициенты a0,a1,...,an вычисляются по следующим формулам:
(2) a0=f(0,....,0)
a1=f(0,....,0) f(1,0,....,0)
.....................................
an=f(0,....,0) f(0,....,0,1)

Алгоритм определения линейности (нелинейности) булевой функции
Способ 1. Для заданной функции найти ее полином Жегалкина (алгоритм см. выше) и по его виду сделать вывод о линейности или нелинейности функции.
Способ 2.
1. По таблице данной функции f(x1,….,xn) и по формулам (2) вычисляем коэффициенты a0,a1,...,an.
2. Выписываем многочлен Q(x1,….,xn)=a0 a1x1 ... anxn и проверяем, задает ли он данную функцию f. Для этого строим таблицу истинности функции Q(x1,….,xn) и сравниваем ее с таблицей истинности функции f(x1,….,xn). Если эти таблицы совпадают, то функция f(x1,….,xn) - линейна, и Q(x1,….,xn) есть ее многочлен Жегалкина. В противном случае функция f - нелинейная.
На практике полезным оказывается следующие утверждение.

Теорема. Носитель функции fÎP2(n) отличной от константы и являющейся линейной, содержит 2n-1 двоичных наборов.
Примеры. 1. Функция, заданная таблицей 1, не является константой, поэтому она нелинейная в силу теоремы о носителе линейной функции: Nr содержит 3 набора, а в случае линейности в Nr было бы 4 набора.
2. Проверим, что функция g0 из таблицы 3 линейна. Найдем ее многочлен Жегалкина P(x1,x2)=a0 a1x1 a2x2 a12x1x2. Система уравнений (1) в данном случае имеет вид: a0=1, a0 a1=0, a0 a2=0, a0 a1 a2 a12 =1. Последовательно из этих уравнений находим все коэффициенты многочлена Жегалкина и его вид оказывается следующий:
P(x1,x2)=1 x1 x2 , и значит функция линейна.

Полнота и замкнутость
4.1. Определение полных систем и замкнутых классов
Определение. Система функций (f1,f2,….,fs.....) из Р2 называется (функционально) полной, если любая функций fÎP2 может быть записана в виде формулы через функции этой системы.
Пример полных систем: 1) P2 – множество всех функций алгебры логики;
2) B{|x, x&y, xVy}; 3) B={|x, x&y}; 4) B={|x, xVy}; 5) B={x→y, |x}; 6) B={1,&,+};
7) B=x↓y; 8)B=x|y.
Определение. Полная система функций В называется базисом, если она перестает быть полной при удалении из нее произвольной одной функции.
Определение. Пусть М некоторое подмножество функций из Р2. Тогда множество всех функций из Р2, представимых в виде формулы через функции множества М, называется замыканием множества М и обозначается через [М].
Очевидно, что [М]ÊM, т.е. функции из М являются и функциями из [М]. Обратное, вообще говоря, неверно.
Определение. Множество (класс) М функций из Р2 называется замкнутым (функционально), если [М]=М.
Примеры замкнутых классов даны в следующем пункте.

Основные замкнутые классы
Классы T0 и T1
Обозначим через Т0 множество функций fÎP2, сохраняющих константу aÎ(0,1), т.е. значение функции f на наборе из сплошных констант (a,....,a) есть a. Таким образом, определены два класса – Т0 и Т1. Классу Т1 принадлежит, например, функции 1, х, х&у, хVу и не принадлежат функции 0 и |х. Классу Т0 принадлежат, например, функции
0, х, x y, но не принадлежат функции 1 и |х.
Утверждение. Классы Т0 и Т1 замкнуты.

Класс S
Определение. Функции f*(x1,….,xn) называется двойственной к функции f(x1,….,xn), если f* (x1,….,xn)= f(x1,….,xn)
Из определения следует, что (f*)*=f и если fÎP2(n) имеет вектор значений (a0,a1,….,a2n-1), то f*~(a2n-1,….,a1,a0) . Отсюда, используя таблицу 3, легко получить следующую таблицу двойственных функций.

f 1 0 X
X X&Y XVY X&Y
X Y X~Y X→Y X|Y X↓Y
f* 0 1 X
X XVY X&Y XVY X~Y
X Y
XY X↓Y X|Y
Таблица 4
Теорема (о двойственной функции). Если F(x1,….,xn)=f(f1(x),....,fk(x)), то F*(x1,….,xn)= f*(f*1(x),....,f*k(x)), где х=(x1,….,xn).
Из этой теоремы вытекает принцип двойственности: если формула F над B=(f1,….,fk) реализует функцию f(x1,….,xn), то формула, полученная из F заменой f1 на f*1 (i=1,...,k), реализует функцию f*(x1,….,xn).
К примеру, в соответствии с принципом двойственности, пользуясь таблицей 4 получаем: если F(x,y,z)=x~(yVz), то F*(x,y,z)=x (y&z).
Определение. Функция f(x1,….,xn) называется самодвойственной, если f*=f.
Множество всех самодвойственных функций обозначается через S. Из таблицы 4 видно, что х и х лежат в S, а остальные функции, приведенные в этой таблице, классу S не принадлежат.
Из определения самодвойственности следует, что f самодвойственная тогда и только тогда, когда f на противоположных наборах принимает противоположные значения, а значит, вектор значений функции fÎS должен быть следующего вида:
f~(a0,a1,....,a2n-1-1,a2n-1-1,....,a1,a0).
Это означает, что у самодвойственной функции вектор значений после деления его пополам: (a0,a1,....,a2n-1-1 | a2n-1,....,a2n-1)должен иметь компоненты, расположенные симметрично относительно середины, противоположного значения, т.е.:
a2n-1-1 = a2n-1 (равенство для первой симметричной пары).
a2n-1-2 = a2n-1+1 (равенство для второй симметричной пары).
(3) …………………………………………….
a0 = a2n-1 (равенство для последней 2n-1-ой симметричной пары).
Если, хотя бы одно из 2n-1 равенств в (3) не выполнено, то fÏS (несамодвойственна). К примеру рассмотрим функцию от трех переменных, заданную таблицей 1 (см. п.1). Ее вектор значений имеет вид: (0,0,1,0,1,0,0,1). Вторые от начали и конца компоненты этого вектора – нулевые. Значит, условие самодвойственности нарушается на паре противоположных наборов: (0,0,1) и (1,1,0). Поэтому функция, заданная таблицей 1, не самодвойственная.
Из принципа двойственности вытекает следующее.

Утверждение. Класс S замкнут.
Особый интерес представляют несамодвойственные функции.
Лемма S (о несамодвойственности функции). Из несамодвойственной функции f(x1,….,xn) путем подстановки вместо переменных x1, i=1,...,n, функции х и х можно получить одну из констант 0 или 1.
Приведем пример, демонстрирующий лемму S, из которого видно, как нужно осуществлять подстановку х и … вместо переменных в функцию fÏS, чтобы полученная таким образом функция от одной переменной х была константой. Пусть f(x,y,z) – функция, заданная таблицей 1. Выше показано, что f – несамодвойственна, т.к.

(4) f(0,0,1)=0, f(1,1,0)=0

Каждый из двух противоположных наборов (0,0,1) и (1,1,0), на которых нарушается самодвойственность, и функция f принимает нулевое значение, определяет набор показателей а1 в степенях xai: x0, x0, x1 или x1, x1, x0 (см. определение степени xa в п.3.1.). Эти наборы и подставляем вместо переменных x,y,z в соответствующем порядке для получения нулевой константы. Рассмотрим оба варианта:
f(x,y,z)| =f(x0, x0, x1)=f(x,x,x)=g1(x).
|x=x0, y=x0, z=x1
f(x,y,z)| =f(x1, x1, x0)=f(x,x,x)=g2(x).
|x=x1, y=x1, z=x0

Равенства (4) показывают, что g1(x)= g2(x)=0 и при х=0 и при х=1.
Таким образом, оба варианта подстановки дают нулевую константу.

Класс М
Определение. Для двух наборов a=(a1,....,an) и b=(b1,....,bn) выполнено отношение предшествования: a<b, если a1<b1, i=1,….,n. (Говорят: набор а предшествует набору b).
Например, (0,1,01)<(1,1,0,1), но наборы (0,1) и (1,0) не связаны отношением предшествования: нельзя сказать, что (0,1) предшествуют (1,0), и нельзя сказать, что (1,0) предшествует (0,1).
Определение. Функция f(x1,….,xn) называется монотонной, если для любых двух наборов a и b длины n таких, что a<b, имеет место неравенство f(a)<f(b).
Обозначим через М множество монотонных функций.
Определение. Функция f немонотонна (обозначаем: fÏM), если существует пара наборов a,b, таких что a<b, но 1=f(a) и f(b)=0.
Про булеву функцию важно знать: монотонна они или немонотонна.
Способы определения монотонности (немонотонности) булевой функции
(а) Немонотонной является функция f(x1,….,xn), не равная тождественно 1, если f(0,....,0)=1, т.е. первая компонента вектора значений функции f единичная f~ (1……...).
(b) Немонотонной является функция f(x1,….,xn), не равная тождественно 0, если f(1,......,1)=0, т.е. последняя компонента вектора значений функции f нулевая: f~(……..0).
© Если функция f не относится к пунктам, описанным в пунктах (а) и (b), то нужно применять следующий.
Алгоритм проверки монотонности булевой функции f(x1,….,xn)
1. Записать все наборы из носителя функции Nr в лексикографическом упорядочении Nr =(a1,....,an).
2. Последовательно для каждого f=1,....,Т найти множество M1={a=(a1,....,an):a1<a} Проверить условие
(5) M1 Í Nr
Если условие (5) выполняется для всех F=1,....,n, то fÎM. В противном случае fÏM. Причем при первом f, для которого нарушается условие (5), алгоритм прекращает работу.
Нетрудно проверить, используя указанные выше способы, что функции 0, 1, x&y, xVy монотонны, функции x y, x~y, x|y, x↓y немонотонны.
Лемма М (о немонотонной функции). Из немонотонной функции f путем подстановки вместо ее переменных констант 0 и 1, а также х можно получить функцию 1х.
Приведем пример, демонстрирующий лемму М, из которого видно, какую подстановку надо делать в немонотонную функцию, чтобы получить 1х. Рассмотрим функцию, заданную таблицей 1 f(x,y,z)~(0,0,1,0,1,0,0,1). По таблице видно, что f(1,0,0)=1, f(1,0,1)=0, при этом (1,0,0)=а<b=(1,0,1), поэтому функция f немонотонна. Сравним пару наборов a и b, на которых нарушается монотонность. Они отличаются лишь по последней компоненте. Тогда, очевидно, следующая постановка х=1, у=0, z=x даст функцию одной переменно х
g(x)=f(x,y,z) | =f(1,0,x),
|x=1, y=0, z=x
при этом g(x)=|x, в силу отмеченных выше свойств наборов а и b.

Класс L
Определение. Класс L – это множество линейных функций (определение линейности, а также алгоритм проверки линейности см. в п.3.2.)
Утверждение. Класс L замкнут.
Лемма L (о нелинейности функции). Из нелинейной функции f можно путем подстановки вместо всех ее переменных, кроме двух констант 0 и 1 и быть может навешивания отрицание на оставшиеся две переменные получить одну из следующих функций x&y, xVy, 1(x&y), 1(xVy).
Приведем пример, демонстрирующий лемму L, из которого видно, как можно получить из нелинейно функции, используя указанную в лемме процедуру, одну из четырех функций: конъюнкцию, дизъюнкцию или их отрицания. Пусть f – функция, заданная таблицей 1. В пункте 3.2. доказано, что f нелинейная. Представим f в виде многочлена Жегалкина. Используем для этого метод неопределенных коэффициентов. Пусть f(x,y,z)=a0 a1x a2y a3z a12xy a13xz a23yz a123xyz, тогда, составив для коэффициентов a0,....,a123 систему (1) и решив ее, получим: a0=0, a1=1, a2=1, a3=0, a12=0, a23=1, a13=1, a123=1.
Таким образом,
(6) f(x,y,z)=x y yz xz xyz.
Подставим вместо какой-то одной переменной значение 0 и 1 так, чтобы в правой части равенства (6) не пропали совсем нелинейные слагаемые. Подходящими являются следующие подстановки:
(7) f(x,y,1)=x y y1 x1 xy1 = xy,
(8) f(0,y,z)=y yz=y(z 1)=yz
Не подходи подстановка z=0, т.к. f(x,y,0)= x y и нелинейные слагаемые отсутствуют.
После подходящей подстановки констант вместо всех, кроме двух переменных функции видно, нужно или нет навешивать отрицание на оставшиеся переменные. Например, в случае (7) это не нужно, т.к. одна из возможных функций уже получена – конъюнкция. А в случае (8) нужно навестить отрицание на переменную z, тогда
f(0,y,z)=yz = yzИ опять получим в результате конъюнкцию.

Теорема Поста
Замкнутые T0, T1, S, M и L попарно различны, что видно из нижеприведенной таблицы 5.

T0 T1 S M L
0 + - - + +
1 - + - + +

X - - + - +
Таблица 5.
Знак + в таблице означает, что соответствующая функция содержится в классе, а знак – обозначает противоположную ситуацию.
Теорема Поста (о функциональной полноте). Система функций В=(f1,.....,ft,.……) полна в том и только в том случае, когда она целиком не содержится ни в одном из 5 замкнутых классов T0, T1, S, M и L.
Алгоритм построения стандартной полной системы по системе функций, удовлетворяющей условиям теоремы Поста.
Считаем, что в системе функций В имеет место f1ÏT0, f2ÏT1, f3ÏS, f4ÏM, f5ÏL.
1. Получение констант 0 и 1
Рассмотрим функцию f1(x1,…...,xn) .Возможны два случая.
а) Пусть f1(1,.....,1). Тогда, поскольку f1ÏT0 имеем f(0,….,0)=1=f(1,…..,1). Поэтому функция g(x)=f1(x,….,x)=1. Константа 0 получается в этом случае как функция, реализованная формулой h(x)=f2(f1(x),....,f1(x)), где х=(х,……,х). Напомним, что f2ÏT1 и значит f2(1,.....,1)=0.
б) Пусть f1(1,….,1)=0. Тогда g(x)=f1(x)=|x. Далее возьмем функцию f3ÏS и воспользуемся леммой S. Путем подстановки в функцию f3 вместо ее переменных функций х и |х получим константу а, реализованную в виде формулы над множеством (f1, f3). Константу |а получим, используя уже имеющуюся функцию 1х. Очевидно, что константа |а также реализуется формулой над (f1, f3).


PS. если у учебник есть по дискреткке-скажи афтара.А то почитать нгде-приходится на лекции ходить