Булевы функции

Теория
  • Булевы алгебры

    Булева алгебра: симметричное полукольцо с унарной операцией дополнения x → x с аксиомами x + x = 1, x x = 0. Подробнее
  • Булевы функции

    Булева функция — отображение f: Bn → B, где B — некоторая булева алгебра. Наибольший интерес — двухэлементная алгебра B. Табличный способ задания булевой функции. Примеры – функции одной и двух переменных.Подробнее
  • ДНФ и КНФ

    Стандартный базис. Элементарные формулы — литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Подробнее
  • Критерий Поста

    Пять классов Поста T0, T1, S. M, L. Их замкнутость. Критерий Поста: множество полно, если оно не содержится ни в одном из классов Поста. Примеры. Рассмотрим некоторые классы булевых функций: Подробнее
  • Минимизация ДНФ

    Минимальная ДНФ — наименьшее число литералов (вхождений переменных). Кратчайшая ДНФ — наименьшее число элементарных конъюнкций. Геометрия булева куба. Импликанты и простые импликанты. Сокращенная ДНФ. Подробнее