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

Содержание

Слайд 2

Теорема.
Любая функция алгебры логики от n переменных может быть представлена полиномом

Теорема. Любая функция алгебры логики от n переменных может быть представлена полиномом
Жегалкина и это представление единственно.

Слайд 3

Сложение по модулю 2

строгая дизъюнкция, исключающее «или», жегалкинское сложение, M2…

Сложение по модулю 2 строгая дизъюнкция, исключающее «или», жегалкинское сложение, M2…

Слайд 4

Свойства операции сложение по модулю 2

Возможно разложение в СДНФ (освобождение от М2

Свойства операции сложение по модулю 2 Возможно разложение в СДНФ (освобождение от М2 или строгой дизъюнкции)
или строгой дизъюнкции)

Слайд 5

Свойства операции сложение по модулю 2

Связь между дизъюнкцией
и суммой по модулю

Свойства операции сложение по модулю 2 Связь между дизъюнкцией и суммой по
два (строгой дизъюнкцией)

Операции с константами

Слайд 6

Полином (многочлен) Жегалкина: функция от 2 логических переменных

полиномиальные коэффициенты (принимают значение равное

Полином (многочлен) Жегалкина: функция от 2 логических переменных полиномиальные коэффициенты (принимают значение
0 или 1)

функция от 3 логических переменных

Слайд 7

Полином (многочлен) Жегалкина от n логических переменных:

Всего здесь 2ⁿ слагаемых.
ꚛ -

Полином (многочлен) Жегалкина от n логических переменных: Всего здесь 2ⁿ слагаемых. ꚛ
означает сложение по модулю 2,
Все полиномиальные коэффициенты являются константами (равными нулю или единице).

Слайд 8

Алгоритм построения ПЖ
(с помощью эквивалентных преобразований)
Минимизируем булеву функцию любым известным нам способом
Заменяем

Алгоритм построения ПЖ (с помощью эквивалентных преобразований) Минимизируем булеву функцию любым известным
дизъюнкцию суммой по модулю 2
3. Заменяем
Используем распределительный закон
(раскрываем скобки)
5. Применяем и

Слайд 9

Метод неопределенных коэффициентов (по таблице истинности или вектору значений функции)

Метод неопределенных коэффициентов (по таблице истинности или вектору значений функции)

Слайд 10

Иван Иванович Жегалкин (1869-1947) – российский и советский математик и логик,

Иван Иванович Жегалкин (1869-1947) – российский и советский математик и логик, профессор
профессор Московского университета. Заслуженный деятель науки РСФСР один из основоположников современной математической логики. Из его открытий наибольшую известность получил так называемый полином Жегалкина. Жегалкин награжден Орденом Трудового Красного Знамени.
Жегалкин предложил в 1927 году в качестве
удобного средства для представления функ-
ций булевой логики многочлен, названный
полиномом Жегалкина.
Известный советский математик Николай
Лузин, вспоминая студенческие годы,
говорит, что из профессоров не боялся лишь
Жегалкина.

Слайд 11

А теперь самостоятельно потрудимся над получением полинома Жегалкина
в тетрадях.

А теперь самостоятельно потрудимся над получением полинома Жегалкина в тетрадях.

Слайд 12

Вариант А

Вариант А

Слайд 13

Вариант Б

Вариант Б

Слайд 14

Вариант В

Вариант В

Слайд 15

Вариант Г

Вариант Г

Слайд 16

Вариант Д

Вариант Д

Слайд 17

Дополнительное задание.
Пусть функция задана вектором значений
f = (11001011).
Найти полином

Дополнительное задание. Пусть функция задана вектором значений f = (11001011). Найти полином Жегалкина.
Жегалкина.
Имя файла: Полином-Жегалкина.pptx
Количество просмотров: 51
Количество скачиваний: 0