02042001 (1109968)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

2 апреля 2001 г.

Определение. Схема из функциональных элементов (СФЭ) – это ориентированный граф без ориентированных циклов, в каждую вершину которого входит ребер. При этом каждой вершине приписывается символ: переменная , если в эту вершину входит ноль ребер; отрицание , если в вершину входит одно ребро; конъюнкция или дизъюнкция , если входят два ребра; некоторым вершинам приписывается звездочка *.

Пример:

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

Видно, что такое индуктивное сопоставление задано корректно.

Определение. Функции, соответствующие вершинам, отмеченным *, называются реализуемыми данной СФЭ.

В указанном выше примере реализуется функция .

Есть физическая интерпретация СФЭ, в которой они рассматриваются как математические модели реальных электронных схем: если на вход поддаются какие-то значения (наличие тока как обычно соответствует единице, отсутствие – нулю), то на выходе получается значение функции на этом наборе. Такое понимание СФЭ находит применение в электронике.

Определение. Элементами схемы называются вершины, помеченные , или . Сложностью схемы называется число ее элементов; она обозначается . Если - функция, то сложностью функции называется , функция называется функцией Шеннона.

Например, можно показать (здесь мы не будем этого сделать), что .

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

Видно, что сложность такой СФЭ равна , откуда следует, что .

Задача. Доказать, что, на самом деле, .

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

.

В ней будет ровно дизъюнкция, так что сложность всей схемы , откуда .

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

.

Здесь мы использовали, что . Сложность этой схемы равна

Таким образом, получено

Утверждение. .

(Поскольку в дальнейшем наряду с СФЭ будут рассматриваться контактные схемы, чтобы избежать путаницы, там, где из контекста не понятно, о какой сложности идет речь, будем различать их с помощью верхних индексов-сокращений «СФЭ» и «КС».)

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

1) единице, если ;

2) нулю, если и в КС нет цепей, соединяющих и ;

3) если и существует цепь, соединяющая их, то для каждой цепи надо взять конъюнкцию всех ее ребер, а затем дизъюнкция всех таких цепей.

.

Пример:

Функция проводимости равна (Остальные цепи, соединяющие и , равны нулю, поскольку содержат какую-нибудь переменную вместе с ее отрицанием.)

Если граф неориентированный, то для любых и .

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

Определение. Сложность КС – это число ребер в ней. После этого можно определить сложность функции и так же, как это делалось для СФЭ. Обозначения такие же, только вместо будем писать .

Для любой функции построим КС, реализующую ее (построим КС такую, что присутствует в ее матрице проводимости), и для этого воспользуемся СДНФ функции .

Пусть - все наборы, на которых принимает 1. Заметим, что .

Схема при этом будет иметь вид:

.

Отсюда видим, что сложность любой функции от переменных не превышает , а потому имеет место

Утверждение. .

Контактные схемы можно истолковать в физическом свете как математические модели схем из электромагнитных реле (соответствующих ребрам КС). Этому были посвящены независимые работы Виктора Ивановича Шустакова, опубликованные во второй половине тридцатых годов, Шеннона («Описание контактных схем средствами математической логики», 1938 г.), а также некоторых японских ученых.

- эта штука (с одним из двух нарисованных контактов) соответствует одному ребру в КС.

Физическая проводимость становится равносильной тому, что реализуемая функция принимает значение 1 при поддаче тока.

В дальнейшем будет показано, как строить «экономные» (в смысле сложности) СФЭ и КС, учитывая специфику конкретных строящихся функций. Этот метод получил название «метод каскадов» и был описан в работе Шеннона 1949 г.; хотя там и не анализировалась сложность получаемых таким образом схем, мы затронем этот вопрос в нашем курсе.

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

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

.

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

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

Рассмотрим этот процесс на примере функции четности (она же сумма ) . Имеем , , , , , ... Ясно, что (содержит одну однородную и одну неоднородную линейные функции), а соответствующая схема имеет вид:

Ее сложность, как нетрудно заметить, равна (линейная!), и можно доказать, что она минимальна; это было проделано Кардо в 1952 г, хотя сама схема была известна еще Шеннону, который предъявил ее в своей работе 1949 г.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций