Научная литература
booksshare.net -> Добавить материал -> Физика -> Арратуна Р. -> "Оптические вычисления" -> 44

Оптические вычисления - Арратуна Р.

Арратуна Р. Оптические вычисления — М.: Мир, 1993. — 441 c.
Скачать (прямая ссылка): opticheskievichesleniya1993.pdf
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 175 >> Следующая

из необходимых тестов, служащих для установления принадлежности
многозначной логической функции каноническому множеству. В этом случае
такие многозначные логические функции и их оптическая реализация могли бы
послужить новыми элементами оптических многозначных логических схем.
4.2. Проблема полноты в двоичной логике
Перед тем как приступить к обсуждению общих вопросов многозначной логики,
рассмотрим несколько более простой двоичный случай. Желающие ознакомиться
с этими вопросами более глубоко могут обратиться к работам [1, 2]. В
двоичной логической системе имеются два определенных логических уровня.
Эти уровни обычно обозначаются как 0 и 1. В общем случае комбинаторная
логическая система будет иметь п входных сигналов, обозначаемых как
вектор х=(лгь х2, ..., хп) и пг выходных сигналов, обозначаемых как
вектор у=(уи у2, ут). Элементы каждого из векторов могут принимать
значения О
Глава 4. Многозначная логика в оптических вычислениях
115
или 1. Корректные схемы комбинаторной логики не требуют обратной связи
выхода со входом, или любых соединений между выходными элементами [1-3].
Релейно-контактная схема / просто преобразует входной сигнал х в выходной
сигнал у, т. е. y = f(x). Упростим обсуждение и обратимся к случаю
большого числа входных сигналов и одного выходного. Задание таблицы
истинности и реализацию желаемых выходных значений на основе заданных
входных сигналов обычно проводят на основе практики. Аппаратное
обеспечение реализации заданной таблицы истинности вытекает из комбинации
определенных стандартных элементов. Простые релейно-коитактные
компоненты, из которых строят функции произвольной сложности, называют
элементарными логическими функциями (ЭЛФ). Здесь уместен вопрос о том,
когда множество ЭЛФ является полным, т. е. может ли произвольная
логическая функция быть представлена корректной комбинацией элементов из
множества ЭЛФ?
Для того чтобы установить условия логической полноты, требуется
определить пять свойств ЭЛФ: монотонность, линейность,
самодвойственность, сохранение 0 и 1. Для того чтобы дать определение
монотонной ЭЛФ, требуется определить понятие упорядоченности. Рассмотрим
два двоичных n-мерных вектора а= (аь а2, ..., ап) и Ь= {Ьи Ь2, . ,
Ьп). Теперь а^Ь, если каж-
дый элемент а меньше, либо равен в обычном арифметическом смысле,
соответствующего элемента Ь. ЭЛФ / монотонна, если при а<Ь и /(а) = 1
справедливо /(b) = 1. ЭЛФ / линейна, если она может быть записана в виде
двоичного линейного полинома
/(*i, *2 хп) = а0 + а1х1 + а2х2+. . .+а"хп (mod 2), (4.1)
где а, - константы, принимающие значение либо 0, либо 1. ЭЛФ / является
самодвойственной, если в результате подачи на вход дополнения ее входного
сигнала на выходе получаем дополнение ее выходного сигнала для всех
возможных входных сигналов, т. е.
/ (Al> *^2> * * * " *4l) ~ / (*Ч" X2i • * * " Хп)'
Дополнением 0(1) служит 1(0). ЭЛФ / сохраняет 0(1), если, подавая на все
входы 0(1), на выходе получим 0(1). Примером монотонной функции может
служить логическое И, а логическое ИСКЛЮЧАЮЩЕЕ ИЛИ не является таковой.
Постоянная функция /= 1 и ИСКЛЮЧАЮЩЕЕ ИЛИ линейны, а ЭЛФ ИЛИ-HE не
обладает линейностью. ЭЛФ НЕ является самодвойственной, но И таковым не
является. Однако И сохраняет и 0, и 1, в то время как ИЛИ-HE не сохраняет
0, а ИСКЛЮЧАЮЩЕЕ ИЛИ не сохраняет 1.
В качестве примера проверим двоичную переключающую функцию на выполнение
пяти указанных выше условий. Рас-
116
Часть II. Многозначная и пороговая логика
Таблица 4.1. Таблица истинности для двоичной переключающей функции из
примера 4.1
*1 *2 *3 h
°1 0 0 0 1
Й2 0 0 1 0
а3 0 1 0 0
"4 0 1 1 1
"5 1 0 0 0
ае 1 0 1 1
"7 1 1 0 1
"8 1 1 1 0
смотрим приведенную ниже функцию трех логических переменных, потенциально
являющуюся ЭЛФ.
Пример 4.1
Рассмотрим табл. 4.1. Проверка каждого из рядов показывает, что Д не
монотонна. Проводя непосредственные алгебраические действия, обнаружим,
что Д может быть выражено как
f1=l+x1 + x2 + x3 (mod 2) (4.2)
и, следовательно, Д является и линейной, и самодвойственной. Проверка
строки ai показывает, что "не сохраняется нуль", в то время как проверка
строки а& показывает, что Д также "не сохраняет 1".
После того как ЭЛФ определены, можно, опираясь на работу [4], ответить на
вопрос, касающийся их полноты. Множество ЭЛФ является полным, если оно
содержит хотя бы одну элементарную функцию из следующих пяти классов:
ЭЛФ, не сохраняющая 0;
ЭЛФ, не сохраняющая 1;
ЭЛФ, не являющаяся самодвойственной;
ЭЛФ, не являющаяся линейной;
ЭЛФ, не являющаяся монотонной.
Доказательство достаточности этих условий требует определенных
математических выкладок, а необходимость может быть установлена
непосредственно. Заметим, что если все ЭЛФ, например, сохраняют 0, то
очевидно, что функции, взятые от функций, сохраняющих 0, также будут
сохранять 0. Однако если из заданного множества требуется получить такую
логическую функцию I, что /(0, 0, ..., 0) = 1, то эта функция не может
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 175 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed