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

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

Алгоритм

Блок-схемы

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

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

Заключение

Список использованной литературы:


Цель работы

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


Введение

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


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

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

Определение 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,x1Åx2}, (M) – множество L всех линейных функций вида

, (ciÎ{0,1}).

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

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

2) ((M))=(M);

3) M1ÍM2 Þ (M1)Í(M2);

4) (M1ÈM2)Ê(M1)È(M1).

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

Примеры.

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

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

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

Новое определение полноты. M – полная система, если (M)=P2.


Алгоритм

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

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

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

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

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

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

x1x2x3f
000f1
001f2
010f3
011f4
100f5
101f6
110f7
111f8

 .









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

#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<<"\n\nTablica istinnosti dlya dannoy funkcii : \n\n";

 cout<<"x_1        x_2   x_3   f\n\n";

 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       "<

 cout<<"\n\nZnachenie koefficientov v polimome Jigalkina : \n\n" ;

 for (i=0; i

 {

 cout<<"a_"<

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

<<"^("<

 <

 getch();

}


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

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


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



Заключение

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


Список использованной литературы

1. Яблонский С.В. Введение в дискретную математику. — М.: Наука. — 1986

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

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

Подобные работы:

Актуально: