4.2. Проблема полноты в двоичной логике

Перед тем как приступить к обсуждению общих вопросов многозначной логики, рассмотрим несколько более простой двоичный случай. Желающие ознакомиться с этими вопросами более глубоко могут обратиться к работам [1, 2]. В двоичной логической системе имеются два определенных логических уровня. Эти уровни обычно обозначаются как 0 и 1. В общем случае комбинаторная логическая система будет иметь входных сигналов, обозначаемых как вектор выходных сигналов, обозначаемых как вектор Элементы каждого из векторов могут принимать значения О

или 1. Корректные схемы комбинаторной логики не требуют обратной связи выхода со входом, или любых соединений между выходными элементами [1—3]. Релейно-контактная схема просто преобразует входной сигнал х в выходной сигнал у, т. е. Упростим обсуждение и обратимся к случаю большого числа входных сигналов и одного выходного. Задание таблицы истинности и реализацию желаемых выходных значений на основе заданных входных сигналов обычно проводят на основе практики. Аппаратное обеспечение реализации заданной таблицы истинности вытекает из комбинации определенных стандартных элементов. Простые релейно-контактные компоненты, из которых строят функции произвольной сложности, называют элементарными логическими функциями (ЭЛФ). Здесь уместен вопрос о том, когда множество ЭЛФ является полным, т. е. может ли произвольная логическая функция быть представлена корректной комбинацией элементов из множества ЭЛФ?

Для того чтобы установить условия логической полноты, требуется определить пять свойств ЭЛФ: монотонность, линейность, самодвойственность, сохранение 0 и 1. Для того чтобы дать определение монотонной ЭЛФ, требуется определить понятие упорядоченности. Рассмотрим два двоичных -мерных вектора Теперь если каждый элемент а меньше, либо равен в обычном арифметическом смысле, соответствующего элемента монотонна, если при справедливо линейна, если она может быть записана в виде двоичного линейного полинома

где — константы, принимающие значение либо 0, либо является самодвойственной, если в результате подачи на вход дополнения ее входного сигнала на выходе получаем дополнение ее выходного сигнала для всех возможных входных сигналов, т. е.

Дополнением служит сохраняет если, подавая на все входы на выходе получим Примером монотонной функции может служить логическое И, а логическое ИСКЛЮЧАЮЩЕЕ ИЛИ не является таковой. Постоянная функция и ИСКЛЮЧАЮЩЕЕ ИЛИ линейны, а ЭЛФ ИЛИ-HE не обладает линейностью. ЭЛФ НЕ является самодвойственной, но И таковым не является. Однако И сохраняет и 0, и 1, в то время как ИЛИ-HE не сохраняет 0, а ИСКЛЮЧАЮЩЕЕ ИЛИ не сохраняет 1.

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

Таблица 4.1. Таблица истинности для двоичной переключающей функции из примера 4.1

Рассмотрим приведенную ниже функцию трех логических переменных, потенциально являющуюся ЭЛФ.

Пример 4.1

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

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

После того как ЭЛФ определены, можно, опираясь на работу [4], ответить на вопрос, касающийся их полноты. Множество ЭЛФ является полным, если оно содержит хотя бы одну элементарную функцию из следующих пяти классов:

ЭЛФ, не сохраняющая 0;

ЭЛФ, не сохраняющая 1;

ЭЛФ, не являющаяся самодвойственной;

ЭЛФ, не являющаяся линейной;

ЭЛФ, не являющаяся монотонной.

Доказательство достаточности этих условий требует определенных математических выкладок, а необходимость может быть установлена непосредственно. Заметим, что если все ЭЛФ, например, сохраняют 0, то очевидно, что функции, взятые от функций, сохраняющих 0, также будут сохранять 0. Однако если из заданного множества требуется получить такую логическую функцию I, что то эта функция не может быть синтезирована. Например, элементарные логические функции И-НЕ и ИЛИ-HE обе являются полными.

Если отказаться от требования, что можно получить постоянные логические функции используя ЭЛФ, тогда условие получения всех возможных логических функций из множества ЭЛФ относят к критерию слабой полноты системы логических функций. Слабую полноту можно было бы рассматривать как более практичное соображение, потому что разработчик логики обычно осуществляет контроль по постоянным значениям входного сигнала. Множество ЭЛФ является слабо полным тогда и только тогда, когда оно содержит ЭЛФ, обладающие двумя свойствами: одну ЭЛФ, не являющуюся монотонной, и одну — не являющуюся линейной.

Очевидно, что любое множество, являющееся полным, одновременно является и слабо полным. ИСКЛЮЧАЮЩЕЕ ИЛИ никогда не является ни полной, ни слабо полной. ЭЛФ ИСКЛЮЧАЮЩЕЕ ИЛИ и И являются слабо полными. Обе функции сохраняют 0. Однако И является нелинейной, а ИСКЛЮЧАЮЩЕЕ ИЛИ — немонотонной. Отдельные ЭЛФ, такие как И-НЕ и ИЛИ-HE, удовлетворяющие требованиям слабой полноты, называются универсальными ЭЛФ. На этом завершается короткое обсуждение возможных канонических логических элементов для систем двоичной логики. В следующем разделе будет рассмотрена одна из возможных многозначных систем, обладающих слабой полнотой — модульные вычисления в ССОК. Такая система может быть реализована в оптике различными способами. Некоторые из этих способов будут описаны в последующих разделах.