Не отобразилась форма расчета стоимости? Переходи по ссылке

Не отобразилась форма расчета стоимости? Переходи по ссылке

Курсовая работа на тему «Полином Жегалкина»

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

Курсовая работа с гарантией

Оглавление

Цель работы

Введение

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

Алгоритм

Блок-схемы

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

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

Заключение

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

Цель работы

Нужна помощь в написании курсовой?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Подробнее

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

Введение

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

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

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

Определение 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}).

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

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

[[M]]=[M]; M1⊆M2 ⇒ [M1]⊆[M2]; [M1∪M2]⊇[M1]∪[M1].

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

Примеры.

Класс M=P2 функционально замкнут; Класс {1,x1⊕x2} не замкнут; Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

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

Алгоритм

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

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

Нужна помощь в написании курсовой?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Цена курсовой

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

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

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

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

.

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

#include

#include

int FuncVolume (int &f)

{

do {cout <<«Vvedite znachenit funkcii na dannom nabore :»<<endl;

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<N; 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_1        x_2        x_3         fnn»;

cout<<» 0         0         0         «<<f[0]

<<«n 0         0         1         «<<f[1]

<<«n 0         1         0         «<<f[2]

<<«n 0         1         1         «<<f[3]

<<«n 1         0         0         «<<f[4]

<<«n 1         0         1         «<<f[5]

<<«n 1         1         0         «<<f[6]

<<«n 1         1         1         «<<f[7]<<«nn»;

cout<<«nnZnachenie koefficientov v polimome Jigalkina : nn» ;

for (i=0; i<N;i++)

{

Нужна помощь в написании курсовой?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Подробнее

cout<<«a_»<<i<<» «<<a[i]<<«n»;}

cout<<«Polinom Jigalkina dlya dannoy funkcii imeet vid : n f = «<<a[0]

<<«^(«<<a[1]<<«*x_1)^(«<<a[2]<<«*x_2)^(«<<a[3]<<«*x_3)^(«<<a[4]<<«*x_1*x_2)^n^(«<<a[5]<<«*x_2*x_3)^(«<<a[6]<<«*x_1*x_3)^(»

<<a[7]<<«*x_1*x_2*x_3)»;

getch();

}

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

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

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

Заключение

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

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

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

Нужна помощь в написании курсовой?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Подробнее

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

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

Средняя оценка 0 / 5. Количество оценок: 0

Поставьте оценку первым.

Сожалеем, что вы поставили низкую оценку!

Позвольте нам стать лучше!

Расскажите, как нам стать лучше?

401

Закажите такую же работу

Не отобразилась форма расчета стоимости? Переходи по ссылке

Не отобразилась форма расчета стоимости? Переходи по ссылке