Троичное конструктное кодирование булевых выражений

Брусенцов Н. П., Владимирова Ю. С.

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

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

Пора бы придать компьютерной информатике здравый диалектический характер.

В этой статье речь пойдет об усовершенствованной конструктной реализации булевой алгебры в диалоговой системе структурированного программирования ДССП [1-3].

Конструктами в ДССП называются нестандартные, определяемые (конструируемые) пользователем типы данных, введением которых достигается высокоуровневая специализация этой системы в заданном классе приложений. Комплекс программ, обеспечивающий возможность декларирования конструктных переменных и реализующий базисный набор операций конструкта, называется, поддерживающим этот конструкт конструктивом [4]. Специализация и развитие ДССП в нужном направлении осуществляется дозагрузкой соответствующих конструктивов.

Конструкты типа "булево выражение" предоставляют возможность оперирования переменными, принимающими в качестве значений n-арные выражения булевой алгебры, и функционально полный набор базисных операций, позволяющих в сочетании с штатными средствами конструирования программ в ДССП эффективно реализовать логико-алгебраические процедуры [5].

Функционально конструкт определяется форматом принимаемых переменными значений и набором интерпретирующих эти значения базисных операций. Формат характеризуется структурой, информационной емкостью и способами доступа. Например, формат "вектор битов" с параметром n – длина вектора предоставляет доступ к отдельным битам по их номерам, а также к вектору в целом. Вектор битов надлежащим выбором базисных операций можно интерпретировать как двоичное число без знака, либо со знаком, как целое, либо дробное и т. п. Но тот же вектор битов можно интерпретировать как n-арную элементарную конъюнкцию (либо дизъюнкцию), приняв в качестве базисных операций побитные инверсию, конъюнкцию и дизъюнкцию.

Принцип отображения булевых выражений конструктами в простейших случаях заключается во взаимно однозначном сопоставлении входящих в выражение букв-переменных (следуя Аристотелю, будем называть их терминами) последовательно пронумерованным компонентам-битам в формате конструкта. Другими словами, каждая переменная представлена в формате конструкта собственным битом. Значение же, принимаемое битом, указывает статус его переменной в отображаемом выражении. Например, элементарная конъюнкция xyz'u отображается вектором 1101 при условии, что неинвертированному термину сопоставлена цифра 1, а инвертированному – цифра 0.

Заметим, что всевозможные 2ⁿ n-арные элементарные конъюнкции пронумерованы значениями отображающего n-битного вектора, интерпретируемыми как двоичные натуральные числа. В приведенном примере номера последовательно убывают от 1111 для xyzu до 0000 для x'y'z'u'.

Эта нумерация использована в конструкте, отображающем булевы выражения в совершенной дизъюнктивной нормальной форме (СДНФ). Его формат – 2ⁿ-компонентный вектор битов, пронумерованных n-битными числами от 11…1 до 00…0, и таким образом однозначно сопоставленных n-арным элементарным конъюнкциям. Биты, соответствующие входящим в отображаемое СДНФ-выражение конъюнкциям, принимают значение 1, а все прочие – значение 0. Например, при n = 2 отображающий вектор состоит из 4-х битов, пронумерованных числами 11, 10, 01, 00, которым соответствуют элементарные конъюнкции xy, xy', x'y, x'y', так что выражение xy v x'y отобразится в 1010, а выражение xy' v x'y v x'y' отобразится в 0111.

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

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

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

Шкалы и цепи, основанные на отображении элементарных конъюнкций и дизъюнкций векторами битов (двоичные конструкты), позволяют компьютеризовать алгебру совершенных нормальных форм, СДНФ- и СКНФ-выражений. В системе с двоичными конструктами эффективно реализуются процедуры синтеза и преобразования СНФ-выражений, такие как тождественное преобразование выражения в двойственную форму, инвертирование, получение дополнения, получение дуала (выражения, двойственного данному), получение единого выражения из нескольких заданных по предписанным взаимосвязям, выявление и доказательство отношений, в которых состоят сопоставляемые выражения, решение булевых уравнений [5, 6].

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

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

Сопоставив этим состояниям значения трита 1, -1, 0, которые далее ради удобства будем обозначать +, -, 0, получаем отображение n-тритным вектором не только индивидных конъюнкций и предполных дизъюнкций, но и элементарных n-арных конъюнкций и дизъюнкций произвольного вида. Так, конъюнкциям xyz'u, xz'u, yz', z' будут соответствовать значения 4-тритного конструкта-вектора К-типа: ++-+, +0-+, 0+-0, 00-0, а дизъюнкциям x' v y' v z v u', x' v z v u', y' v z, z – значения 4-тритного конструкта-вектора Д-типа: --+-, -0+-, 0-+0, 00+0.

Построенные на n-тритных векторах ДК- и КД-цепи при должным образом пересмотренных наборах интерпретирующих базисных процедур способны отображать теперь не только СНФ-выражения, но и произвольное булево выражение в нормальной форме с фиксированным порядком размещения терминов в элементарных конъюнкциях и дизъюнкциях. Например, выражение xy v x'y, отобразимое 2-арной двоичной ДК-цепью 11 01, троичной 2-арной цепью отобразимо как в СДНФ ++ -+, так и в минимальной ДНФ 0+, а выражение xy' v x'y v x'y' (двоичная ДК-цепь 10 01 00) троичной ДК-цепью отображается в четырех вариантах: +- -+ --, +- -0, 0- -+, -0 0-, -0 0-, т. е. в СДНФ, в двух тупиковых и в минимальной ДНФ.

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

Описанное усовершенствование компьютерной реализации булевой алгебры представляет собой один из результатов конструктного подхода к информатике. Результат фундаментальный, поскольку касается основы и вместе с тем открывает пути совершенствования последующих ступеней – алгебраизации силлогистики, модальной и диалектической логики [8], упорядочения теории вероятностей и нечетких множеств [9, 10].

Литература

1. Брусенцов Н. П., Златкус Т. В., Руднев И. А. ДССП-диалоговая система структурированного программирования // Программное оснащение микрокомпьютеров. – М.: Изд-во Моск. ун-та, 1982. С. 11-40.
2. Брусенцов Н. П. Микрокомпьютеры. – М.: "Наука", 1985. С. 141-170.
3. Развиваемый адаптивный язык РАЯ диалоговой системы программирования ДССП / Н. П. Брусенцов, В. Б. Захаров, И. А. Руднев, С. А. Сидоров, Н. А. Чанышев. – М.: Изд-во Моск. ун-та, 1987. 80 с.
4. Концептуальная характеристика РИИИС-процессора / Н. П. Брусенцов, С. П. Маслов, Х. Рамиль Альварес, С. А. Сидоров // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во ф-та ВМиК МГУ, 1996 г. С. 16-43.
5. Владимирова Ю. С. Конструктная реализация булевой алгебры // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во ф-та ВМиК МГУ, 1996 г. С. 44-69.
6. Брусенцов Н. П., Владимирова Ю. С. Решение булевых уравнений // Методы математического моделирования. – М.: Диалог-МГУ, 1998. С. 59-68. Solution of Boolean Equations. // Computational mathematics and modeling, Vol. 9 , № 4, 1998, pp. 287-295.
7. Брусенцов Н. П., Владимирова Ю. С. Троичный минимизатор булевых выражений // Программные системы и инструменты. Тематический сборник № 2. – М.: Факультет ВМиК МГУ, 2001. С. 205-207.
8. Брусенцов Н. П. Трехзначная диалектическая логика // Программные системы и инструменты. Тематический сборник № 2. – М.: Факультет ВМиК МГУ, 2001. С. 36-44.
9. Брусенцов Н. П., Деркач А. Ю. Логическая модель теории вероятностей и нечетких множеств Заде // Цифровая обработка информации и управление в чрезвычайных ситуациях. Материалы Второй международной конференции (28-30 ноября 2000 г., Минск.) – Минск: Институт технической кибернетики НАН Беларуси, 2000. Том 1, с. 41-44.
10. Брусенцов Н. П., Деркач А. Ю. Трехзначная логика, нечеткие множества и теория вероятностей // Программные системы и инструменты. Тематический сборник № 2. – М.: Факультет ВМиК МГУ, 2001. С. 88-91.

Заметки о трехзначной логике
Доложено на Ломоносовских чтениях 2002 г. на факультете ВМиК МГУ.

Опубликовано в: Программные системы и инструменты: Тематический сборник № 3 // Под ред. Л. Н. Королева.- М. Издательский отдел ВМиК МГУ, 2002, с. 6-10.