49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.

Мультиграф G=<M,U,R>, в котором выделено k вершин (полюсов), называется k-полюсной сетью. Сеть G, задаваемая неориентированным мультиграфом с k полюсами, в которой каждое ребро помечено буквой из алфавита , называется k-полюсной контактной схемой.

(k+1)-полюсная схема, в которой один полюс выделен (входной), а остальные полюса (выходные) равноправны, называется (1,k)-полюсником.

Ребра контактной схемы называются контактами. Контакт, соответствующий логической переменной x_i, называется замыкающим, он пропускает ток при x_i=1. Контакт, соответствующий литере , называется размыкающим, ток через него проходит при x_i=0. Функции соответствует последовательное соединение контактов, а функции - параллельное.

Пусть a,b – полюса контактной схемы Σ, [a,b] – некоторая цепь из a в b, K_[a,b] – конъюнкция литер, приписанных ребрам цепи [a,b]. Функция f_a,b(X), определяемая формулой , в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, называется функцией проводимости между полюсами a и b схемы Σ. Говорят, что функция g(X) реализуется (1,k)-полюсником, если существует такой выходной полюс b_i, что f_a,bi(X)=g(X), где a – входной полюс. (1,1)-полюсники называются смежными, если они реализуют одну и ту же булеву функцию. Сложностью (1,1)-полюсника называется число контактов. (1,1)-полюсник, имеющий наименьшую сложность среди эквивалентных ему схем, называется минимальным. Сложность минимального (1,1)-полюсника, реализующего функцию f, называется сложностью функции f в классе (1,1)-полюсников и обозначается L_π(f).

Ориентированная бесконтурная сеть, в которой полюса делятся на входные и выходные, называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, некоторым функциональным символом. При этом должны выполняться следующие условия:

- если a – входной полюс, то полустепень захода вершины равна нулю:

- если вершина a не является полюсом и помечена n-местным функциональным символом f, то и дуги, входящие в a пронумерованы от 1 до n.

Функциональным элементов называется всякий подмультиграф схемы, состоящий из невходного полюса a, помеченного соответствующим символом f, и вершины, из которых исходят дуги в вершину a.

Говорят, что функция f реализуется схемой Σ, если существует такой выход a из схемы Σ, что функция f_a, соответствующая терму выхода a, эквивалентна функции f.

Схемы из функциональных элементов с одним выходом, у которых входные полюса помечены символами x₁,…,x_n, а вершины, отличные от входных, - символами , называются Xⁿ-функциональными схемами. Сложностью схемы из функциональных элементов называется число ее невходных вершин. Xⁿ-функциональная схема Σ, реализующая функцию f, называется минимальной, если всякая другая Xⁿ-функциональная схема, реализующая f, имеет сложность не меньшую, чем сложность схемы Σ. Сложность минимальной схемы, реализующей функцию f, называется сложностью функции f в классе схем из функциональных элементов и обозначается L(f).