Введение в схемы, автоматы и алгоритмы

Введение в схемы, автоматы и алгоритмы

Автоматическое зарядное устройство для автомобиля

Автоматическое зарядное устройство для автомобильных свинцово-кислотных аккумуляторов.

Данная схема позволяет автоматически заряжать автомобильные аккумуляторы.
Зарядный ток через батарею в зависимости от напряжения на ней (прикладываемого к Б-Э переходу VT1), регулируется транзистором VT1, коллекторным напряжением которого управляется индикатор заряда на светодиоде (по мере зарядки ток заряда уменьшается и светодиод постепенно гаснет) и мощный составной транзистор, содержащий VT2, VT3, VT4.
Резистор R3 ограничивает максимальный зарядный ток, поэтому он должен быть достаточно мощным, не менее 10 Вт, наверное лучше проволочным.
Момент полного заряда батареи (и уменьшение зарядного тока до нуля) определяет необходимое напряжение на ней - обычно достаточно 12.5 В (!). Konstantin (RK1NA) утверждает (и ,похоже, меня он тоже убедил), что электро-химические потенциалы используемых материалов свинцовых аккумуляторов позволяют обеспечить ПОЛНУЮ зарядку батареи лишь при напряжении в 13.8 В (!).
Т.е. необходимо устанавливать порог заряда чуть больше 13.8 В, например 13.9 В, при котором обеспечивается зарядка "до отказа", на полную емкость батареи.
Этот порог устанавливается резистором R1, порог зависит от типа применяемых транзисторов

Булевы функции от 1-ой и 2-х переменных

Перечислим вначале все булевы функции от 1-ой переменной . Как мы знаем, их всего четыре.

1. 
   - константа 0;
2. 
   - константа 1;
3. 
   - тождественная функция;
4. 
   Эта функция называется отрицанием
   
   
   и обозначается
   
   (используется также обозначение
   
   , а в языках программирования эта функция часто обозначается как
   
   ).

В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

Таблица 1.2. Булевы функции от 2-х переменных

0  0 0  1 1  0 1  1		0 0 0 0		1 1 1 1		0 0 1 1		1 1 0 0		0 1 0 1		1 0 1 0		0 0 0 1		0 1 1 1		1 1 0 1		0 1 1 0		1 0 0 1		1 1 1 0

Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

• 
  - константа 0;
• 
  - константа 1;
• 
  - функция, равная 1-му аргументу;
• 
  - отрицание
  
  ;
• 
  - функция, равная 2-му аргументу;
• 
  - отрицание
  
  ;
• 
  - конъюнкция, читается "
  
  и
  
  " (используются также обозначения
  
  ,
  
  ,
  
  и
  
  AND
  
  ));
• 
  - дизъюнкция, читается "
  
  или
  
  " (используются также обозначения
  
  ,
  
  и
  
  OR
  
  ));
• 
  - импликация, читается "
  
  влечет
  
  " или "из
  
  следует
  
  " (используются также обозначения
  
  , и ( IF
  
  THEN
  
  ));
• 
  - сложение по модулю 2, читается "
  
  плюс
  
  " (используется также обозначение
  
  );
• 
  - эквивалентность, читается "
  
  эквивалентно (равносильно)
  
  " (используется также обозначение
  
  );
• 
  - штрих Шеффера (антиконъюнкция), иногда читается как "не
  
  и
  
  ".

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.
Отметим, что функции и фактически не зависят от значений обоих аргументов, функции и не зависят от значений аргумента , а функции и не зависят от значений аргумента .
Определение 1.1. Функция не зависит от аргумента , если для любого набора значений
остальных аргументов имеет место равенство . Такой аргумент называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.
Функции и называются равными, если функцию можно получить из функции путем добавления и удаления фиктивных аргументов.
Например, равными являются одноместная функция и двухместная функция , так как вторая получается из первой добавлением фиктивного аргумента . Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.

Булевы функции от n переменных

Булевы функции1) названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения. С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.
Обозначим через двухэлементное множество . Тогда - это множество всех двоичных последовательностей (наборов, векторов) длины . Булевой функцией от
переменных (аргументов) называется любая функция . Каждый из ее аргументов может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из также может быть 0 или 1. Обозначим через множество всех булевых функций от переменных. Нетрудно подсчитать их число:
Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим табличное представление, а также представление с помощью логических формул. В лекциях 2 и 3 будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

Деревья

Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерахических структур.
Определение 1.10. Граф называется деревом, если

1. в нем есть одна вершина
   
   , в которую не входят ребра; она называется корнем дерева;
2. в каждую из остальных вершин входит ровно по одному ребру;
3. все вершины достижимы из корня.

На рисунке 2 показан пример дерева
С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.
Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины , подграф дерева , включающий все достижимые из вершины и соединяющие их ребра из , образует поддерево дерева с корнем . Высота вершины - это высота дерева . Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

Рис. 1.2.  Дерево G1
Если из вершины ведет ребро в вершину , то называется отцом , а - сыном (в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины ведет путь в вершину , то называется предком , а - потомком . Вершины, у которых общий отец, называются братьями
или сестрами.
Пример 1.4. В дереве на рис. 1.2
вершина является корнем, вершины - листья. Путь - одна из ветвей дерева . Вершина является отцом (родителем) вершин и а каждая из этих вершин - ее сыном (ребенком). Между собой вершины и являются братьями (сестрами). Глубина равна 1, а высота - 2. Высота всего дерева равна 3.
Для деревьев часто удобно использовать следующее индуктивное определение.
Определение 1.11. Определим по индукции класс графов , называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.

1. Граф
   
   , с единственной вершиной
   
   и пустым множеством ребер
   
   является деревом (входит в
   
   ).
   Вершина
   
   называется корнем этого дерева.
2. Пусть графы
   
   с корнями
   
   принадлежат
   
   , а
   
   - новая вершина, т.е.
   
   . Тогда классу
   
   принадлежит также следующий граф
   
   , где
   
   ,
   
   . Корнем этого дерева является вершина
   
   .
3. Других графов в классе
   
   нет.

Рисунок 1.3 иллюстрирует это определение.


Рис. 1.3.  Индуктивное определение ориентированных деревьев

Определения ориентированных деревьев 1.10 и 1.11 эквивалентны.

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

Дерево называется бинарным или двоичным , если у каждой его внутренней вершины имеется не более двух сыновей, причем ребра, ведущие к ним помечены двумя разными метками (обычно используются метки из пар: "левый" - "правый", 0 - 1, - и т.п.)

Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.

Дизъюнктивные и конъюнктивные нормальные формы

Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции и .
Пусть - это множество пропозициональных переменных. Введем для каждого обозначения: и . Формула
(), в которой и все переменные разные, т.е. при , называется элементарной конъюнкцией (элементарной дизъюнкцией).
Определение 1.4.Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид
где каждая формула - это элементарная конъюнкция. называется совершенной ДНФ, если в каждую из ее конъюнкций входят все переменных из
Аналогично, формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е.
где каждая формула - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую входят все переменных из
Рассмотрим произвольную булеву функцию , зависящую от переменных из . Oбозначим через
множество наборов значений переменных, на которых принимает значение 1, а через
множество наборов, на которых принимает значение 0, т.е. и
Определим по этим множествам две формулы:

и
Теорема 1.1.
(1) Если функция не равна тождественно 0, то формула - это совершенная ДНФ, задающая функцию .
(2) Если функция не равна тождественно 1, то формула - это совершенная КНФ, задающая функцию .
Пример 1.2. Например, для функции , представленной в таблице 1.1
совершенная ДНФ равна
, а ее совершенная КНФ:
Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере может быть задана более простой ДНФ: .

Формулы

Как мы видели, табличное представление булевых функций подходит лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от большего числа аргументов и оперировать различными представлениями одной и той же функции.
Мы будем рассматривать формулы, построенные над множеством элементарных функций . Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.
Зафиксируем некоторое счетное множество переменных . Определим по индукции множество формул над с переменными из . Одновременно будем определять числовую характеристику формулы , называемую ее глубиной, и множество ее подформул.
Определение 1.2.
а) Базис индукции. 0, 1 и каждая переменная является формулой глубины 0, т.е. . Множество ее подформул состоит из нее самой.
б) Шаг индукции. Пусть и - формулы, . Тогда выражения и
являются формулами. При этом , а . Множество подформул включает саму формулу и для все подформулы формулы , а для все подформулы формул и
Каждой формуле сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.
Базис индукции. Пусть . Тогда или
В первом случае задает функцию , во втором - функцию, тождественно равную константе .
Шаг индукции. Пусть - произвольная формула глубины . Тогда
или
для некоторой булевой связки . Так как то формулам и соответствующие функции и уже сопоставлены. Тогда формула
задает функцию , а формула
задает функцию .
Для определения функции, задаваемой небольшой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующей подформулой.
Пример 1.1. Например, для формулы функция задается выделенным столбцом следующей таблицы.

Таблица 1.3. Функция

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1		0  0  0 1  0  0  0  0 1  0  0  1  1 0  1  0  1  1 0  1  1  1  0 1  0  1  1  0 1  0  1  1  1 0  1  1  1  1 0  1		1 1 0 1 1 0 0 1		0  0  0  0  1  0 1  1  0  0  1  0 0  0  0  0  0  1 1  1  0  0  0  1 0  1  1  1  1  0 1  0  1  1  1  0 0  0  1  0  0  1 1  1  1  0  0  1

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

Графы

Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.
Граф (ориентированный) - это пара, где - конечное множество вершин (узлов, точек) графа, а - некоторое множество пар вершин, т.е. подмножество множества или бинарное отношение на . Элементы называют ребрами (дугами, стрелками, связями). Для ребра вершина называется началом , а вершина - концом , говорят, что ребро ведет из в .
В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.
Заметим, что в графе может быть ребро вида , называемое петлей.
Пример 1.3. На рис. 1.1 приведен пример графа . Здесь , В графе ребро является петлей, полустепень исхода вершины равна 2, а полустепень захода для нее равна 1.

Рис. 1.1.  Граф G1
Во многих приложениях с вершинами и ребрами графов связывается некоторая дополнительная информация. Обычно она представляется с помощью функций разметки вершин и ребер.
Определение 1.6.
Размеченный граф - это граф , снабженный одной или двумя функциями разметки вида: и , где и - множества меток вершин и ребер, соответственно.
Упорядоченный граф - это размеченный граф , в котором ребра, выходящие из каждой вершины , упорядочены, т.е. помечены номерами , где - полустепень исхода , т.е. .
Упорядоченный граф с полустепенью исхода вершин называется бинарным.
В качестве множества меток ребер часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.
Часто на одном множестве объектов определено несколько различных бинарных отношений. Для представления такой ситуации служат мультиграфы.
Определение 1.7. Мультиграф состоит из конечного множества вершин и мультимножества ребер состоящего из пар вершин в которое эти пары могут входить по нескольку раз.



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

Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.

Определение 1.8. Изоморфизм графов. Два графа и называются изоморфными, если между их вершинами существует взаимно однозначное соответствие такое, что для любой пары вершин из ребро ребро .

Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин : и/или ребер: .

Многие приложения графов связаны с изучением путей между их вершинами.

Определение 1.9.

Путь в (мульти)графе - это последовательность ребер вида . Этот путь ведет из начальной вершины в конечную вершину и имеет длину . В этом случае будем говорить, что достижима из . Будем считать, что каждая вершина достижима сама из себя путем длины 0. Путь в графе (не мультиграфе!) можно также определять как соответствующую последовательность вершин: где при .

Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может, первой и последней, различны.

Циклом в графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины различны.

Если в графе нет циклов, то он называется ациклическим.

Следующее утверждение непосредственно следует из определений.

Лемма 1.1.Если в графе имеется путь из вершины в вершину , то в нем имеется и простой путь из в .

Эквивалентность булевых формул

Определение 1.3.Булевы формулы и называются эквивалентными, если соответствующие им функции и
равны.
Обозначение: . Эквивалентные формулы называют также тождественно равными, а выражения вида логическими тождествами.
Таким образом, эквивалентные формулы являются различными заданиями одной и той же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств), отражающих существенные свойства логических операций и важные соотношения между различными операциями. Они часто позволяют находить для булевых функций по одним задающим их формулам более простые формулы. Большинство из приводимых тождеств имеют собственные имена. Часто их называют законами логики.
Пусть - это одна из функций . Для этих трех функций выполнены следующие две эквивалентности (законы ассоциативности и коммутативности).
(1) Ассоциативность:
(2) Коммутативность:
(3) Дистрибутивные законы:
(4) Двойное отрицание:
(5) Законы де Моргана (внесение отрицания внутрь скобок):
(6) Законы упрощения:
Некоторые законы упрощения имеют собственные названия: эквивалентности в первой строке называются законами идемпотентности, - это закон противоречия, - это закон исключенного третьего.
Следующие две эквивалентности позволяют выразить импликацию и сложение по модулю 2 через дизъюнкцию, конъюкцию и отрицание.

(7)

(8)

Правильность этих эквивалентностей легко устанавливается прямым вычислением функций для их левых и правых частей.
Соглашения об упрощенной записи формул. Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, не зависят от расстановки скобок. Поэтому вместо формул
и мы будем для упрощения писать Аналогично, будем использовать выражения и
для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно. Будем также опускать внешние скобки в записи формулы, если ее внешней функцией является одна из функций .
Таким образом, с использованием этих соглашений формула
может быть записана как

Табличное представление

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

Таблица 1.1. Табличное представление функции

.  .  .
.  .  .        .  .  .        .  .  .      .  .  .  .  .  .   .  .  .

Наборы аргументов в строках обычно располагаются в лексикографическом порядке: существует такое , что при а . Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя - .
При больших табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых
оно достаточно наглядно.

Введение в схемы, автоматы и алгоритмы

Логические схемы (схемы из функциональных элементов)

Многие элементы в современной электронике являются устройствами, преобразующими некоторые входные сигналы (данные) в выходные. Логические схемы, в отечественной литературе чаще называемые схемами из функциональных элементов, представляют собой математическую модель таких устройств, в которых временем выполнения преобразования входов в выходы можно пренебречь.
Чтобы не усложнять определение, зафиксируем конкретный базис B0={ , , ¬} и определим схемы в этом базисе.
Определение 2.1. Логической схемой (схемой из функциональных элементов) в базисе B0 называется размеченный ориентированный граф без циклов S=(V,E), в котором

1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
2. в каждую из остальных вершин входит одно или два ребра; вершины, в которые входит одно ребро помечены функцией ¬, а вершины, в которые входят по два ребра, - одной из функций
   
   или
   
   . Такие вершины называются функциональными элементами.

Как и для деревьев, для ориентированных графов без циклов можно естественным образом ввести понятие глубины.
Определение 2.2. Глубина вершины v V в схеме S=(V,E) - это максимальная длина пути из входов S в v .
Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.
Пусть входы схемы S помечены переменными x1, … , xn. С каждой вершиной v V схемы S свяжем булеву функцию fv(x1,… , xn), реализуемую в этой вершине. Определим fv индукцией по глубине v .
Определение 2.3.
Базис: v имеет глубину 0. Тогда это входная вершина, которая помечена некоторой переменной xi. Положим fv(x1,… , xn) = xi.
Шаг индукции. Пусть всем вершинам w глубины k уже сопоставлены функции fw и пусть v - произвольная вершина глубины k+1. Тогда

• 
  если v помечена ¬ и в нее входит ребро (w,v) , то положим
  
  
• 
  если v помечена
  
  и в нее входят два ребра (w1,v) и (w2,v), то положим
  
  
• 
  если v помечена
  
  и в нее входят два ребра (w1,v) и (w2,v), то положим
  
  

Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1, то глубина вершины w не превосходит k и для нее fw уже определена по индукционному предположению.

Определение 2.4. Схема S реализует набор булевых функций g1, g2, … , gm, если для каждого i [1,m] в схеме существует такая вершина vi, что .

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

Определение 2.5. Сложность L(S) схемы S - это число функциональных элементов в S. Сложность L(f) булевой функции f(x1, …, xn) - это наименьшая из сложностей схем, реализующих эту функцию.

Отношения между булевыми функциями и схемами естественно приводят к двум следующим основным проблемам.

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

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

Пример 2.1. Рассмотрим схему S1

с тремя входными переменными x, y и z, изображенную на рис. 2.1 и решим для нее проблему анализа.


Рис. 2.1.  Схема S1

В соответствии с данным выше определением вершины схемы S1 реализуют следующие функции:

fa(x,y,z) = x y, fb(x,y,z) = ¬ z, fc(x,y,z) = ¬ fa(x,y,z)=¬( x y), fd(x,y,z) = fc(x,y,z) z = ¬( x y) z, fe(x,y,z) =fa(x,y,z) fb(x,y,z)= x y ¬ z и, наконец, ff(x,y,z) =fd(x,y,z) fe(x,y,z) = (¬( x y) z) ((x y ) ¬ z).

Глубина этой схемы D(S1)= 4, а ее сложность L(S1)=6. В то же время формула для результирующей функции ff содержит 7 функциональных знаков. За счет чего достигнута экономия? За счет того, что функция (x y) в схеме S1 вычисляется один раз в вершине a, а в формуле приходится вычислять ее дважды.

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

Схемы и линейные программы

Указанное выше свойство характерно и для программ, в которых один раз вычисленное значение выражения можно использовать неоднократно. Рассмотрим один из простейших классов программ - линейные или неветвящиеся программы. Такие программы представляют последовательности присваиваний вида:

где X, X1, … , Xk - переменные, F - имя k-местной базисной функции.
В случае нашего базиса B0={ , , ¬} линейная программа состоит из присваиваний вида: Z = X Y, Z = X Y и Z = ¬ X.
Линейная программа P с выделенными входными переменными X1, … , Xn
порождает для каждого набора ?1, …, ?n значений входных переменных естественный процесс вычисления: вначале переменным X1, … , Xn присваиваются значения ?1, …, ?n, соответственно, а каждой из остальных переменных присваивается значение 0. Затем последовательно выполняются присваивания программы P, в результате чего каждая из переменных Z программы получит заключительное значение PZ(?1, …, ?n).
Определение 2.6.
Скажем, что программа P со входными переменными X1, … , Xn
вычисляет в выходной переменной Z функцию F(X1, …, Xn), если для любого набора значений входов ?1, …, ?n после завершения работы PZ(?1, …, ?n)=F(?1, …, ?n) .
Между схемами и линейными программами имеется тесная связь.
Теорема 2.1.

1. По каждой логической схеме S со входами x1, … , xn и функциональными элементами v1, …, vm можно эффективно построить линейную программу PS со входными переменными x1, … , xn и рабочими переменными v1, …, vm, которая в любой переменной vi, i=1,…,m, вычисляет функцию
   
   .
2. По каждой линейной программе P со входными переменными X1, … , Xn, вычисляющей в выходной переменной Z некоторую функцию F(X1, …, Xn) можно эффективно построить логическую схему SP со входами X1, … , Xn, в которой имеется вершина v такая, что fv((X1, …, Xn) = F(X1, …, Xn).

Доказательство. (1) Пусть S - схема со входами x1, … , xn и функциональными элементами v1, …, vm. Построим по ней линейную программу PS со входными переменными x1, … , xn следующим образом. Упорядочим все входные и функциональные вершины S по глубине (вершины одной глубины в любом порядке): u1, …, un+m.
Программа PS будет последовательностью m присваиваний.

• Пусть вершина un+i помечена ¬ и в нее входит
• ребро из uj. Тогда в качестве i-ой команды поместим в PS присваивание un+i= ¬ uj.
• Пусть вершина un+i помечена \circ
  
  {
  
  ,
  
  } и в нее входят ребра из uj и uk. Тогда в качестве i-ой команды поместим в PS присваивание un+i= uj ? uk.

Упорядочение вершин по глубине гарантирует, что j