Реферати українською » Математика » Поліном Жегалкіна


Реферат Поліном Жегалкіна

>Уфимский державний авіаційний технічний університет

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

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

по дискретної математиці

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

Виконали:

Перевірила:

>Шерихалина М.М.

Уфа – 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,x1x2}, [M] – безліч L всіх лінійних функцій виду

, (>ci{0,1}).

Властивості замикання:

1) Якщо М замкнуто, то [>M]=M;

2) [[>M]]=[M];

3)M1M2 [>M1][M2];

4) [>M1M2][M1][M1].

Визначення 3. Клас (безліч) M називається (функціонально) замкнутим, якщо [>M]=M.

Приклади.

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

2) Клас {>1,x1x2} не замкнутий;

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>

>intFuncVolume (>int &>f)

{

 >do {>cout <<">Vvediteznachenitfunkciinadannomnabore :"<<>endl;

 >cin>>f;

 >if ((>f!=0)&&(f!=1))

        cout<<"Error!!!Funkciyamojetprinimat'znachenielibo 0libo1!n";

 }

 >while ((>f!=0)&&(f!=1));

 >returnf;

}

>voidmain()

{

 >clrscr();

 >constN=8;

 >intm[5];

 >intf[N],a[N];

 >for (>int і =0;i<N; і++)

 {

 >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<<"nnTablicaistinnostidlyadannoyfunkcii : >nn";

 >cout<<"x_1x_2x_3fnn";

 >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<<"nnZnacheniekoefficientov vpolimomeJigalkina : >nn" ;

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

 {

 >cout<<"a_"<<i<<" "<<>a[i]<<"n";}

 >cout<<"PolinomJigalkinadlyadannoyfunkciiimeetvid : nf = "<<>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.


Схожі реферати:

Навігація