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

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

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

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

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

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