Полином Жегалкина
Размещено на /
Уфимский государственный авиационный технический университет
Кафедра АПРиС
Курсовая работа
по дискретной математике
«Полином Жегалкина»
Выполнили:
Проверила:
Шерыхалина Н.М.
Уфа – 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.
Размещено на