Изоморфизм СФЭ — структурное совпадение схем как помеченных графов с сохранением входов, выходов, меток элементов и порядка их аргументов. Эквивалентность — функциональное свойство. Две схемы эквивалентны, если реализуют одинаковые системы ФАЛ. Поэтому изоморфизм гарантирует эквивалентность, но эквивалентные схемы могут иметь совсем разную
Для элементов, реализующих симметрические функции, порядок входящих дуг несущественен. Схемы, отличающиеся только допустимой перенумерацией таких аргументов, называют квазиизоморфными. Они также
Что важно запомнить
- Изоморфизм сравнивает структуру и метки СФЭ.
- Эквивалентность сравнивает реализуемые системы булевых функций.
- Изоморфные СФЭ обязательно эквивалентны. Обратное неверно.
- Квазиизоморфизм разрешает менять нумерацию входов у элементов с симметрической
- Различие этих отношений важно при подсчёте схем и при эквивалентных преобразованиях.
Структурное отношение
СФЭ рассматривается как помеченный ориентированный граф с выделенными входами и выходами. Две схемы изоморфны, если существует взаимно однозначное соответствие их вершин и дуг, сохраняющее направленность, входные и выходные позиции, функциональные метки и нумерацию аргументных дуг. Это означает, что схемы различаются только именами или способом изображения одной и той же
Функциональная эквивалентность
Две СФЭ эквивалентны, когда на соответствующих выходах реализуют одинаковые системы ФАЛ. Структуры при этом могут быть разными: одна схема может содержать общий промежуточный элемент, другая — два дублированных вычисления, но их выходные функции совпадут. Каждая СФЭ, в частности, эквивалентна системе формул, полученной раскрытием её вычислений от выходов к
Квазиизоморфизм
Если базисная функция \(\varphi_i\) симметрична по аргументам, перестановка нумерации входящих в соответствующий элемент дуг не меняет реализуемое значение. Поэтому курс вводит более слабое структурное отношение — квазиизоморфизм, при котором такие перестановки допускаются. В соответствующих вершинах квазиизоморфных схем реализуются подобные формулы и одинаковые ФАЛ, следовательно, квазиизоморфизм также влечёт
Иерархия здесь односторонняя: структурное совпадение даёт функциональное совпадение, но из равенства функций восстановить единственную структуру нельзя. Именно поэтому при перечислительных оценках отдельно считают классы с точностью до изоморфизма или квазиизоморфизма.
Пример простыми словами
У элемента И функция x₁∧x₂ симметрична. Если две входные дуги поменять местами, значение элемента не изменится. Поэтому схемы могут перестать совпадать как строго упорядоченные изображения, но остаются квазиизоморфными и эквивалентными. Совсем другая схема, реализующая ту же итоговую функцию за счёт иных преобразований, может быть эквивалентной уже без всякого изоморфизма.
Частые ошибки
- Отождествлять эквивалентность с изоморфизмом. Эквивалентность требует только равенства выходных функций.
- Разрешать переставлять входы любого элемента при квазиизоморфизме. Это допустимо лишь там, где соответствующая базисная функция симметрична.
- Считать, что эквивалентные СФЭ обязаны иметь одинаковые L, R и D. Структура и её функционалы могут различаться.
