Моделирование формул π-схемами
Простейшая π-схема состоит из одного контакта \(x_i\) или \(\neg x_i\). Если Σ₁ и Σ₂ реализуют f₁ и f₂, то их параллельное соединение реализует f₁∨f₂, а последовательное — f₁∧f₂. Поэтому по дереву формулы с поднятыми отрицаниями можно рекурсивно построить π-схему, заменяя литералы контактами, ∨ параллельным соединением, а ∧ последовательным. Обратное преобразование строится тем же способом по рекурсивной структуре π-схемы.1
Лемма 6.1 курса даёт точное ресурсное соответствие: для построенной пары выполняется \(R(F)=L(\Sigma)\). Здесь ранг формулы равен числу вхождений переменных, а сложность контактной схемы — числу контактов.
Функционирование многополюсной КС
Пусть Σ имеет p входов a′₁,…,a′ₚ и q выходов \(a''_{1},\ldots,a''_q\). В каждой паре «вход — выход» возникает своя ФАЛ проводимости. Поэтому функционирование схемы описывается матрицей F=(F[i,j]) размера p×q, где F[i,j](α)=1 тогда и только тогда, когда на наборе α существует проводящий путь от a′ᵢ к a″ⱼ. Иначе говоря, для каждого α матрица F(α) является обычной матрицей достижимости сети Σ|α.1
Неразделённые полюса и обратная реализация
Если одни и те же m полюсов рассматриваются одновременно как входы и выходы, матрица функционирования имеет размер m×m. Она рефлексивна и транзитивна. Для неориентированной контактной схемы матрица дополнительно симметрична.1
Верно и обратное утверждение: любую m×m-матрицу ФАЛ, которая поточечно является рефлексивной, транзитивной и симметричной, можно реализовать неориентированной КС. В канонической конструкции для каждой пары полюсов i<j строят π-схему по совершенной ДНФ функции F[i,j], а затем объединяют эти подсхемы.1