Контактные схемы и π-схемы: структура, функционирование и меры сложности

Контактная схема (КС) — сеть, в которой рёбра или дуги являются контактами, помеченными переменной x_i или её отрицанием. При наборе входных значений контакт проводит тогда и только тогда, когда соответствующий литерал равен 1. Функционирование КС определяется наличием проводящего пути между её полюсами. Сложность \(L(\Sigma)\) равна числу контактов.1

π-схемы — рекурсивный подкласс КС, строящийся из одного контакта последовательным и параллельным соединением. Параллельное соединение реализует дизъюнкцию функций проводимости, последовательное — конъюнкцию. Поэтому π-схемы тесно связаны с формулами с поднятыми отрицаниями.1

Что важно запомнить
  • Контакт x_i проводит при x_i=1, контакт ¬x_i — при x_i=0.
  • После фиксации входного набора остаётся подграф проводящих контактов. Выход равен 1 при наличии пути от входного полюса.1
  • \(L(\Sigma)\) для КС — число контактов.
  • π-схема строится из контактов только последовательным и параллельным соединением.
  • Параллельное соединение соответствует ∨, последовательное — ∧. Для π-схемы существует эквивалентная формула с \(R(F)=L(\Sigma)\).1

Контакты и проводимость

Контактная схема представляет собой сеть, чьи рёбра или ориентированные дуги помечены булевыми переменными либо их отрицаниями. Контакт x_i замкнут на наборе α, если α_i=1, а контакт ¬x_i — если α_i=0. Для ориентированного контакта проводимость разрешена только в направлении дуги.1

После подстановки набора α из схемы мысленно удаляют все непроводящие контакты. Получившуюся сеть можно обозначить Σ|α. Функция проводимости между вершинами v и u равна 1 тогда и только тогда, когда в Σ|α существует допустимый путь от v к u. Для одно-входной многовыходной КС функции проводимости от входа к выходным полюсам и образуют реализуемую систему ФАЛ.1

Сложность контактной схемы

Базовая мера курса — \(L(\Sigma)\), число контактов схемы. Здесь контакт является структурным ресурсом независимо от того, сколько путей создаёт сеть. Поэтому нельзя путать сложность КС с числом вершин или числом проводящих путей.

π-схемы

π-схемы вводятся рекурсивно. Один контакт является простейшей π-схемой. Если две π-схемы соединить параллельно между общими полюсами, результирующая функция проводимости равна дизъюнкции их функций. При последовательном соединении выход первого блока связывается со входом второго и функция проводимости равна конъюнкции.1

Поэтому дерево последовательных и параллельных соединений непосредственно соответствует формуле. Лемма 6.1 утверждает: каждой π-схеме соответствует эквивалентная формула с поднятыми отрицаниями, причём \(R(F)=L(\Sigma)\). Верно и обратное соответствие. Это даёт структурное моделирование формул контактными схемами.1

Важно, что произвольная контактная схема может содержать более общую сетевую структуру и не обязана быть π-схемой. Именно общая графовая организация КС далее делает их эквивалентные преобразования существенно сложнее формульных.

Пример простыми словами

Функцию (x₁∨x₂)∧¬x₃ можно реализовать π-схемой так: контакты x₁ и x₂ соединить параллельно, а полученный блок последовательно соединить с контактом ¬x₃. Путь от входа к выходу существует ровно тогда, когда хотя бы один из x₁,x₂ равен 1 и одновременно x₃=0.

Частые ошибки
  • Считать контакт логическим вентилем. Контакт лишь проводит или не проводит. Функция возникает из существования пути в сети.
  • Игнорировать ориентацию дуги у ориентированного контакта.
  • Считать любую контактную схему π-схемой. π-класс ограничен последовательными и параллельными композициями.
  • Считать \(L(\Sigma)\) числом полюсов или вершин. В этой модели L — число контактов.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 2, §6, контактные и π-схемы, лемма 6.1, МГУ, факультет ВМК