Обсуждение:Полином Жегалкина

Зачем вообще на данной странице классы Поста?

Хотелось бы услышать аргументацию нужности текста о классах Поста на данной странице именно в виде текста, а не гиперссылки. — IlyaCk 15:24, 4 января 2011 (UTC)

Есть там вот эта строка:

• Этому требованию отвечает система функций ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$. На её основе и строятся полиномы Жегалкина.

Т.е. полином Жегалкина основан на полной системе функций => им можно выражать последовательности с любыми функциями. — 94.141.34.199 18:12, 3 ноября 2011 (UTC)

Тут суть вопроса была скорее в том, что а зачем формулировать весь критерий Поста, занимая без малого 5 строчек? Если можно бы было просто написать «при помощи критерия Поста можно доказать, что эта система полна». И всё, кому нужно — перейдёт по ссылке.

С другой стороны у меня вопрос а зачем в принципе привязывать критерий Поста? Почему не написать как факт: «система $\{\oplus ,\land ,1\}$ полна» и всё? В курсах по теории булевых функций это вообще обычно доказывают до формулировки критерия Поста. Тем более, в следующем разделе этот факт прямо доказывается без критерия Поста.

Ну и сам раздел называется предпосылки. То есть, я так подразумеваю, что вообще привело людей к тому, что они придумали и рассмотрели такую нормальную форму. Тот факт, что $\{\oplus ,\land ,1\}$ прямо не ведёт, что функцию можно выразить именно в виде многочлена, он ведёт, что можно выразить каким-то выражением из этих функций, который не обязательно многочлен. Из этого конечно нетрудно доказать, что многочленом таки можно выразить, но это уже будет следовать из свойств самих функций, а не того, что система полна. Есть куча полных систем, для которых никаких нормальных форм не рассматривают. Сам по себе факт полноты не является предпосылкой для введения такой нормальной формы. Предпосылкой для неё является то, что $\{0,1\}$ образует поле, а над конечным полем любая функция единственным образом представляется в виде многочлена степени меньше количества переменных. Вот этот факт из алгебры и является предпосылкой, но он уже описан в преамбуле.

Считаю, что раздел «Предпосылки» нужно удалить полностью. Arami Mira (обс.) 22:43, 12 мая 2024 (UTC)

Процедура преобразования

Ниже приведена паскаль-функция (Delphi 6.0), преобразующая таблицу истинности в полином Жегалкина. Входным параметром процедуры является текстовая строка, в которой закодирована таблица истинности функции (перечисляются значения функции по строкам таблицы истинности, например '10101001'). Функция возвращает полином Жегалкина в виде текстовой строки, где переменные обозначены латинскими буквами A, B, C, D... в порядке их следования в таблице истинности, знак операции конъюнкции опущен, операция исключающее ИЛИ обозначена знаком +. Функция использует алгоритм треугольника.

function toZhegalkin(s:string):string;
var i,j,k,L,N,M:integer;
A: array of boolean;
begin
L:=Length(s); if L=0 then exit;
if s[1]='1' then Result:='1';
N:=1;
for i:=1 to 16 do if N>=Length(s) then break else N:=N shl 1;
M:=i-1;
SetLength(A,N);
for i:=0 to N-1 do A[i]:=false;
for i:=1 to Length(s) do if s[i]='1' then A[i-1]:=true;
for i:=1 to N-1 do begin
 for j:=0 to N-2 do A[j]:=A[j] xor A[j+1];
 if A[0] then begin
   Result:=Result+'+'; j:=N; k:=M;
   while j>0 do begin
     if i and j >0 then Result:=Result+char(64-k+M);
     j:=j div 2;dec(k);
   end;
 end;
end;
end;

Тот же алгоритм на C#

static string toZhegalkin(string s)
        {
            if (s.Length == 0)
                return string.Empty;
            int N = 1, M = 0;
            string buffer = "";
            if (s[0] == '1')
                buffer += s[0];
            for (int i = 1; i < 16; i++)
            {
                if (N >= s.Length)
                    break;
                else
                    N = N << 1;
                M++;
            }
            bool[] A = new bool[N];
            for (int i = 0; i < N; i++)
                A[i] = (s[i] == '1') ? true : false;
            for (int i = 1; i <= N - 1; i++)
            {
                for (int j = 0; j < N - 1; j++)
                    A[j] ^= A[j + 1];
                if (A[0])
                {
                    buffer += '+';
                    for (int j = N, k = M; j > 0; j /= 2, k--)
                    {
                        if ((i & j) > 0)
                        {
                            buffer += (char)(64 - k + M);
                        }
                    }
                }
            }
            return buffer.ToString();
        }

Пример вызова функции: Delphi

writeln(toZhegalkin('10101001'));

C#

Console.WriteLine(toZhegalkin("10101001"));

Результат:

1+C+AB

Метод треугольника Паскаля

Обсуждаемая правка: [1]

Чтобы писать, что какое-то название ошибочное, надо привести источник это подтверждающий. Кроме того, неверно, что "эти два треугольника не имеют ничего общего". Как минимум способ построения у них одинаков: каждый элемент получается суммой двух соседних элементов из предыдущей строки. — Алексей Копылов 01:10, 15 июня 2017 (UTC)