Фактор-множества и фактор-алгебра

Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M, то множество классов эквивалентности называется фактор множеством множества M относительно эквивалентности R и обозначается M/R

Здесь есть подмножество элементов множества M эквивалентных x , называемых классом эквивалентности.

Из определения фактор-множества следует, что оно является подмножеством булеана: .

Функция называется отождествлением и определяется следующим образом:

Теорема. Фактор-алгебра F _n/~ изоморфна алгебре булевых функций B _n

Доказательство.

Искомый изоморфизм ξ: F _n / ~ → B _n определяется по следующему правилу: классу эквивалентности ~(φ) сопоставляется функция f_φ, имеющая таблицу истинности произвольной формулы из множества ~(φ). Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из В_п найдется формула , представляющая функцию f, то отображение ξ сюръективно. Сохранение операций , 0, 1 при отображении ξ проверяется непосредственно. ЧТД.

По теореме о функциональной полноте каждой функции , не являющейся константой 0, соответствует некоторая СДНФ ψ, принадлежащая классу ~(φ) = ξ^-1(f) формул, представляющих функцию f. Возникает задача нахождения в классе ~(φ) дизъюнктивной нормальной формы, имеющей наиболее простое строение.