![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если отношение 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. Возникает задача нахождения в классе ~(φ) дизъюнктивной нормальной формы, имеющей наиболее простое строение.
Дата публикования: 2014-11-04; Прочитано: 482 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!