Модуль 2. Булевы функции

Высказывания и логические связки. Формулы логики высказываний. Общезначимые, выполнимые и противоречивые формулы.

Основные законы логики. Булевы функции. Нормальные формы. Разложение функции алгебры логики по переменным. Нормальные формы. Теорема о совершенной дизъюнктивной нормальной форме. Совершенная конъюнктивная нормальная форма.

Минимизация булевых функций в классе ДНФ. Метод минимизирующих карт. Минимизация ДНФ методом Квайна. Минимизация частично-определенных булевых функций.

Контактные схемы.

Полные системы. Примеры полных систем (с доказательством полноты). Теорема Жегалкина о представимости функции алгебры логики полиномом. Полином Жегалкина. Классы булевых функций. Теорема Поста о полноте. Алгоритм
выражения произвольной булевой функции через функции полной системы

Последнее изменение: понедельник, 28 сентября 2026, 09:38