Курсовая работа: Полином Жегалкина

ч. т. д.

Примеры:

1) - полная.

2) - тоже полная, так как .

3) - тоже полная.

4) - тоже полная, так как

,

,

. ((2) – I)

5) - неполная.

Докажем это от противного.

Предположим, что .

Но .

Противоречие.

6) - неполная (сохраняет константу 0).

6’) - полная.

7) - неполная (сохраняет константу 1).

8)

тогда взяв в качестве системы I систему 2) можно заключить, система функций 8) – полная. Тем самым, справедлива

Теорема Жегалкина. Каждая функция из может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

,

где . (1)

Имеем: число разных сочетаний равно числу подмножеств множества из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных полиномов Жегалкина равно , т.е. равно числу различных булевых функций.

Т. о. получаем единственность представления функций через полином Жегалкина.

Способы представления функции в виде полинома Жегалкина

1) Алгебраические преобразования

.

Пример: