Алгебра Жегалкина

Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина.

A = <FB, ,,0,1>

 

 

Контрольные вопросы

1. Что такое ДНФ и КНФ? Дайте определение совершенного одночлена.

2. Булевы функции: нормальные формы, совершенные нормальные формы.

3. Получение совершенной дизъюнктивной и конъюнктивной нормальных форм.

4. Приведите правило преобразования формул в СДНФ и СКНФ.

5. Как булевы функции связаны с алгеброй высказывания?

6. Сформулируйте основные правила построения формул.

3. Минимизация булевых функций с помощью матрицы Квайна.

4. Минимизация булевых функций с помощью карт Карно.

5. Синтез с помощью булевых функций электронных схем (на примере сумматора).

6. дайте определение многочлена Жегалкина и сформулируйте теорему Жегалкина.

7. Представление булевых функций с помощью полинома Жегалкина.

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

9. В чем состоит метод неопределенных коэффициентов для построения многочлена Жегалкина?

10. Какой многочлен Жегалкина называется нелинейным?

11. Каков алгоритм определения линейности (нелинейности) булевой функции?

12. Функционально полные базисы. Теорема Поста.

 

 

Лекция № 12

Результат считается красивым, если из малого

числа условий удается полу­чить общие заключения,

относящиеся к широкому кругу объектов.

Б. Гнеденко