Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Полином Жегалкина
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 15:59:58 18 апреля 2011 Похожие работы
Просмотров: 1918 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Уфимский государственный авиационный технический университет

Кафедра АПРиС

Курсовая работа

по дискретной математике

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

Выполнили:

Проверила:

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

Уфа – 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,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. Записать функцию в виде полинома Жегалкина с вычисленными коэффициентами.

x1 x2 x3 f
0 0 0 f1
0 0 1 f2
0 1 0 f3
0 1 1 f4
1 0 0 f5
1 0 1 f6
1 1 0 f7
1 1 1 f8

.









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

#include<iostream.h>

#include<conio.h>

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

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

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]<<"\n\n";

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

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:42 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:41 29 ноября 2015

Работы, похожие на Курсовая работа: Полином Жегалкина
Шпаргалки по геометрии, алгебре, педагогике, методике математики (ИГПИ ...
Кольцом называется числ. множ. На котором выполняются три опер-ии: слож, умнож, вычит. Полем наз. Числ множ. На котором выполняются 4 операции: слож ...
Кольцо полиномов от 1 неизв-го A[x]=(A[x],у, 1,+, -,*) - обл-ть целостности. => Если степень f(x)=n и степень g(x)=m => степень f(x)g(x)=n+m. Пусть А - обл-ть целостности.
Пусть прямая задана направляющим вектором a"{m,n} и фикс. точкой M(x0,y0) Угловым кооф-ом прямой называется отношение второй координаты направляющего вектора к первой. k=n/m Если m ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 3494 Комментариев: 3 Похожие работы
Оценило: 3 человек Средний балл: 3 Оценка: неизвестно     Скачать
Конспект лекций по дискретной математике
Приложение Булевой алгебры к синтезу комбинационных схем Двоичная система логики: 1. Элементы Булевой алгебры: а) числа b) переменные с) операции d ...
Булева функция g(x) называется импликантой булевой функции f(x), если для любого набора аргументов, на которых g(x)=1, f(x) также равна единице.
Задача декомпозиции булевой функции в общем случае состоит в таком разделении множества ее аргументов на ряд подмножеств, при котором можно выразить исходную функцию f(x) через ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1650 Комментариев: 4 Похожие работы
Оценило: 2 человек Средний балл: 2 Оценка: неизвестно     Скачать
Исследование движения центра масс межпланетных космических аппаратов
2. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ 2.1. ВВЕДЕНИЕ В данной работе проводится исследование движения центра масс МКА под действием различных возмущающих ...
m_f << x << '\t' << Fz << '\t' << Fs << '\t' << Fl << '\t' << Fa
cout << "Rp=" << Rp_p2 << "Ra=" << Ra_p2 << '\n';
Раздел: Рефераты по астрономии
Тип: реферат Просмотров: 313 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Основы C
Кафедра: Автоматика и Информационные Технологии ОСНОВЫ С ОГЛАВЛЕНИЕ Введение Глава 1. Основы языка Си 1.1. Алфавит 1.2. Основные конструкции Си 1.3 ...
1. В С++ ключевое слово void не обязательно (эквивалентно int m(); и int m(void))
int x1,y1,x2,y2,x3,y3,p1,p2,p3,k;
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 1164 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Matlab
Министерство образования Республики Беларусь Учреждение образования "Гомельский государственный университет им. Ф. Скорины" Математический факультет ...
polyval(p,x) - поэлементное вычисление значений полинома p на множестве x, где x может быть как вектором, так и матрицей.
где F - заданное преобразование y=F(x), x0 - как-то выбранное начальное приближение, xk - значение переменной x на k-й итерации, а сама переменная x может быть любой - числом ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 1611 Комментариев: 3 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Булевы функции
1.Основные понятия булевой алгебры Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата ...
Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В ...
Предполный класс S не совпадает с множеством P2 всех возможных булевых функций, однако, если в него включить любую, не входящую в S, булеву функцию, то новый функционально ...
Раздел: Рефераты по математике
Тип: контрольная работа Просмотров: 8912 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Полином Жегалкина (2471)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151335)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru