Уфимскийгосударственный авиационный технический университет
Кафедра АПРиС
Курсоваяработа
по дискретнойматематике
«Полином Жегалкина»
Выполнили:
Проверила:
Шерыхалина Н.М.
Уфа – 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 f1 1 f2 1 f3 1 1 f4 1 f5 1 1 f6 1 1 f7 1 1 1 f8
/> .
/>
/>
/>
/>
/>
/>
/>
Листинг программы:
#include
#include
int FuncVolume(int &f)
{
do {cout
cin>>f;
if((f!=0)&&(f!=1))
cout
}
while((f!=0)&&(f!=1));
return f;
}
void main()
{
clrscr();
const N=8;
int m[5];
intf[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
cout
cout
cout
for (i=0;i
{
cout
cout
getch();
}
Тестирование программы:
/>
На каждом наборе вводятсяединицы, то есть функция является тождественной единицей. Простейшая проверкана правильность работы программы:
/>
Так же реализованапроверка на правильный ввод данных:
/>
Заключение
В курсовой работе былреализован метод неопределенных коэффициентов для представления функции в видеполинома Жегалкина. По данному алгоритму на языке С++ была написана программа,результат которой был продемонстрирован.
Список использованнойлитературы
1. Яблонский С.В. Введение вдискретную математику. — М.: Наука. — 1986
2. Н.А.Ахметова, З.М.УсмановаДискретная Математика. Функции алгебры логики учебное электронное издание – Уфа– 2004
3. Гаврилов Г. П., Сапоженко А. А.Задачи и упражнения по дискретной математике: Учебное пособие. – 3-е изд., перераб.– М.: ФИЗМАТЛИТ, 2005.