Xreferat.com » Рефераты по математике » Полином Жегалкина

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

Размещено на /

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

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


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

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

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


Выполнили:

Проверила:

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


Уфа – 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}).


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

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


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

Размещено на

Похожие рефераты: