Уфімський державний авіаційний технічний університет
Кафедра Априс
Курсова робота
з дискретної математики
В«Поліном ЖегалкінаВ»
Виконали:
Перевірила:
Шерихаліна Н.М.
Уфа - 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
# include
int FuncVolume (Int & f)
{
do {cout <<"Vvedite znachenit funkcii na dannom nabore:" <
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
{
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 "<
<<" n 0 0 1 "<
<<" n 0 1 0 "<
<<" n 0 1 1 "<
<<" n 1 0 0 "<
<<" n 1 0 1 "<
<<" n 1 1 0 "<
<<" n 1 1 1 "<
cout <<" n nZnachenie koefficientov v polimome Jigalkina: n n ";
for (i = 0; i
{
cout <<"a_" <
cout <<"Polinom Jigalkina dlya dannoy funkcii imeet vid: nf = "<
<
getch ();
}
Тестування програми:
На кожному наборі вводяться одиниці, тобто функція є тотожною одиницею. Найпростіша перевірка на правильність роботи програми:
Так само реалізована перевірка на правильне введення даних:
Висновок
У курсовій роботі був реалізований метод невизначених коефіцієнтів для представлення функції у вигляді полінома Жегалкіна. За даним алгоритмом на мові С + + була написана програма, результат якої був продемонстрований.
Список використаної літератури
1. Яблонський С.В. Введення в дискретну математику. - М.: Наука. - 1986
2. Н.А.Ахметова, З.М.Усманова Дискретна Математика. Функції алгебри логіки навчальний електронне видання - Уфа - 2004
3. Гаврилов Г. П., Сапоженко А. А. Завдання і вправи з дискретної математики: Навчальний посібник. - 3-е изд., Перераб. - М.: Физматлит, 2005.
