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

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

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

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

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

Выполнили:

Проверила:

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

Уфа – 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 определена следующим образом:

. ............