Полином Жегалкина

Уфимский государственный авиационный технический университет Кафедра АПРиС Курсовая работа по дискретной математике

«Полином Жегалкина»

Выполнили:

Проверила:

Шерыхалина Н.М.

Уфа — 2008

Оглавление Цель работы Введение Теоретическая часть Алгоритм Блок-схемы Листинг программы Тестирование программы Заключение

• Список использованной литературы:
• Цель работы
• Целью данной работы является изучение булевых функций, разработка алгоритма их представления в виде полинома Жегалкина и написания программы, реализующей этот алгоритм.

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

Теоретическая часть

Полнота и замкнутость

Определение 1: Система функций из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Пример:

1) Само множество ;

2);

3) — не полна.

Теорема 1. Пусть даны две системы функций из

(I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство: Пусть. В силу полноты системы I, функцию h можно выразить в виде формулы .

По условию теоремы

Поэтому

ч. т. д.

Примеры:

1) — полная.

2) — тоже полная, так как .

3) — тоже полная.

4) — тоже полная, так как

. ((2) — I)

5) — неполная.

Докажем это от противного.

Предположим, что .

Но .

Противоречие.

6) — неполная (сохраняет константу 0).

6') — полная.

7) — неполная (сохраняет константу 1).

8)

тогда взяв в качестве системы I систему 2) можно заключить, система функций 8) — полная. Тем самым, справедлива

Теорема Жегалкина. Каждая функция из может быть выражена при помощи полинома по модулю 2 — (полинома Жегалкина):

где. (1)

Имеем: число разных сочетаний равно числу подмножеств множества из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных полиномов Жегалкина равно, т. е. равно числу различных булевых функций.

Т. о. получаем единственность представления функций через полином Жегалкина.

Способы представления функции в виде полинома Жегалкина

1) Алгебраические преобразования

.

Пример:

2) Метод неопределенных коэффициентов

— искомый полином Жегалкина (реализующий функцию).

Вектор из формулы (1) будем называть вектором коэффициентов полинома .

Нам нужно найти неизвестные коэффициенты .

Поступаем так. Для каждого составим уравнение, где — выражение, получаемое из (1) при. Это дает систему из уравнений с неизвестными, она имеет единственное решение. Решив систему, находим коэффициенты полинома .

3) Метод, базирующийся на преобразовании вектора значения функции

Пусть — вектор значений функции.

Разбиваем вектор на двумерные наборы:

.

Операция T определена следующим образом:

.

Применяем операцию Т к двумерным наборам:

Используя построенные наборы, конструируем четырехмерные наборы, которые получаются в результате применения операции Т к четырехмерным наборам, выделяемым из .

Затем от четырехмерных наборов переходим (аналогично) к восьмимерным и т. д., пока не построим — мерный набор. Он и будет искомым вектором коэффициентов полинома .

Пример:

Пусть вектор значений функций = (0,0,0,1,0,1,1,1)

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

Определение 2: Пусть M — некоторое подмножество функций из P2. Замыканием M называется множество всех булевых функций, представимых в виде формул через функции множества M. Обозначается [M].

Замечание. Замыкание инвариантно относительно операций введения и удаления фиктивных переменных.

Примеры.

1) M=P2, [M]=P2.

2) M={1,x1x2}, [M] - множество L всех линейных функций вида

(ci{0,1}).

Свойства замыкания:

1) Если М замкнуто, то [M]=M;

2) [[M]]=[M];

3) M1M2 [M1][M2];

4) [M1M2][M1][M1].

Определение 3. Класс (множество) M называется (функционально) замкнутым, если [M]=M.

Примеры.

1) Класс M=P2 функционально замкнут;

2) Класс {1,x1x2} не замкнут;

3) Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M — полная система, если [M]=P2.

Алгоритм

булевой функция полином жигалкин

В данной программе был реализован метод неопределенных коэффициентов для построения полинома Жегалкина.

1. Получить таблицу истинности для определенного количества переменных;

2. Заполнить значения функции для каждого из наборов таблицы истинности;

3. Последовательно вычислить неизвестные коэффициенты;

4. Записать функцию в виде полинома Жегалкина с вычисленными коэффициентами.

.

Листинг программы:

#include

#include

int FuncVolume (int &f)

{

do {cout <<" Vvedite znachenit funkcii na dannom nabore :" <

cin>>f;

if ((f≠0)&&(f≠1))

cout<<" Error!!! Funkciya mojet prinimat' znachenie libo 0 libo 1! n" ;

}

while ((f≠0)&&(f≠1));

return f;

}

void main ()

{

clrscr ();

const N=8;

int m[5];

int f[N], a[N];

for (int i =0; i

{

FuncVolume (f[i]);

}

a[0]= f[0];

a[3]=f[0]^f[1];

a[2]=f[0]^f[2];

a[1]=f[0]^f[4];

m[0]=f[1]^a[2]^a[3];

a[5]=m[0]^f[3];

m[1]=f[1]^a[1]^a[3];

a[6]=m[1]^f[5];

m[2]=f[1]^a[1]^a[2];

a[4]=m[2]^f[6];

m[3]=a[3]^a[4]^a[5];

m[4]=m[2]^m[3]^a[6];

a[7]=m[4]^f[7];

cout<<" nnTablica istinnosti dlya dannoy funkcii: nn" ;

cout<<" x₁ x₂ x₃ fnn" ;

cout<<" 0 0 0 «<

<<" n 0 0 1 «<

<<" n 0 1 0 «<

<<" n 0 1 1 «<

<<" n 1 0 0 «<

<<" n 1 0 1 «<

<<" n 1 1 0 «<

<<" n 1 1 1 «<<<» nn" ;

cout<<" nnZnachenie koefficientov v polimome Jigalkina: nn" ;

for (i=0; i

{

cout<<" a_" <<" «<<<» n" ;}

cout<<" Polinom Jigalkina dlya dannoy funkcii imeet vid: n f = «<

<<» ^(«<

getch ();

}

Тестирование программы:

На каждом наборе вводятся единицы, то есть функция является тождественной единицей. Простейшая проверка на правильность работы программы:

Так же реализована проверка на правильный ввод данных:

Заключение

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

1. Яблонский С. В.

Введение

в дискретную математику. — М.: Наука. — 1986

2. Н. А. Ахметова, З. М. Усманова Дискретная Математика. Функции алгебры логики учебное электронное издание — Уфа — 2004

3. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учебное пособие. — 3-е изд., перераб. — М.: ФИЗМАТЛИТ, 2005.