Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364142
Теги названий
Разделы
Авиация и космонавтика (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)
Иностранный язык (62791)
Информатика (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)
Остальные рефераты (21693)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Полином Жегалкина
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 15:59:58 18 апреля 2011 Похожие работы
Просмотров: 1995 Комментариев: 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

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

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

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



Результаты(171459)
Комментарии (1976)
Copyright © 2005-2017 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru