Метод Лупанова синтеза схем
Теорема: |
Любая булева функция от аргументов в базисе имеет схемную сложность . |
Представление функции
Поделим аргументы функции на два блока: первые
и оставшиеся .Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1. Строки индексируются значениями первых
переменных, столбцы — значениями оставшихся ; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.Разделение на полосы
Разделим таблицу на горизонтальные полосы шириной
(последняя полоса, возможно, будет короче остальных; её ширину обозначим ). Пронумеруем полосы сверху вниз от 1 до .Рассмотрим независимо некоторую полосу. Заметим, что среди её столбцов при небольшом
будет много повторений; далее про одинаковые столбцы, находящиеся в одной полосе, будем говорить, что они одного сорта.Определение: |
Сорт некоторого столбца данной полосы — его класс эквивалентности по отношению поэлементного равенства столбцов данной полосы. |
Число сортов столбцов
-й полосы обозначим как . Понятно, что для любой полосы (для последней ).Функция для одной полосы
Пусть для некоторого
- — произвольный столбец -й полосы -го сорта (точное положение столбца далее не будет иметь значения, по определению сорта)
- — аргументы функции, соответствующие -й строке -й полосы.
Тогда введём булеву функцию
Другими словами, если строка, соответствующая аргументам функции
, находится в -й полосе, то функция возвращает значение, записанное в столбце сорта для этой строки. Если же эта строка находится в другой полосе, то функция вернёт 0. Иллюстрация принципа работы функции приведена на рис. 2.Вывод исходной функции для фиксированной части параметров
Поскольку изначальный столбец
складывается из столбцов соответствующих сортов в полосах, , где — номер сорта столбца полосы , являющегося соответствующей частью столбца .Мультиплексор и дешифратор
Для упрощения доказательства теоремы будем использовать элементы мультиплексор и дешифратор.
Определение: |
Мультиплексор (англ. multiplexer) — логический элемент, получающий на вход
|
Определение: |
Дешифратор (или демультиплексор, англ. demultiplexer) — логический элемент, получающий на вход
|
Оба элемента представимы схемами с числом элементов
с помощью базиса . Доказательство этого факта у читателя будет возможность рассказать на практике.Доказательство
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции
(представление Лупанова, англ. Lupanov -representation).Для удобства поделим схему на блоки:
- Блок A — дешифратор, которому на вход подали 1 и в качестве двоичного представления числа.
- Блок B — схемная реализация всех . Функцию можно реализовать как , где — выдал ли дешифратор "1" на -м выходе -й полосы.
- Блок C — схемная реализация всех . (здесь - фиксированные параметры, см. п. 3.1)
- Блок D — мультиплексор, получающий на вход все и параметры функции в качестве двоичного представления числа. Результат работы схемы — вывод мультиплексора.
Положим
; . Тогда число элементов в блокахИтого, имеем схему c числом элементов
, откуда следует, что , ч.т.д.Ссылки
Литература
- Яблонский С.В. Введение в дискретную математику — М.:"Наука", 1986 — стр. 361