Логико-алгебраический процессор

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

Логико-алгебраический процессор представляет собой программно реализованную на компьютере систему обработки не количественных (числовых), а качественных (логических) данных. Компьютер служит в ней не столько вычислителем в арифметическом смысле, сколько преобразователем выражений алгебры логики, отображающих взаимосвязи качеств и охарактеризованных посредством них вещей. Зафиксировав избранные взаимосвязи в виде посылок, имеем логические уравнения, решением которых получаются вытекающие из данных посылок умозаключения. Таким образом, компьютеризируется именно тот способ математической логики, на котором настаивали Лейбниц, а затем Буль – дедукция сведена к решению уравнений, осуществляемому теперь компьютером.

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

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

Имеется n попарно различных критериев (качеств, признаков), относительно которых охарактеризованны рассматриваемые вещи. Совокупность этих n критериев, называемых далее первичными терминами, составляет Универсум – Вселенную рассмотрения. Если вещи охарактеризованы по каждому из n критериев однозначно: либо критерию x данная вещь необходимо удовлетворяет (не может не удовлетворять), либо антиудовлетворяет, то вещам сопоставлены четкие подсовокупности n-терминной совокупности. Полная совокупность таких вещей-индивидов есть булеан совокупности терминов – всего в Универсуме 2ⁿ индивидов.

В булевой алгебре четкие подсовокупности терминов выражаются n-арными элементарными (индивидными) конъюнкциями, в которые термины, присущие вещи, входят непосредственно, а антиприсущие – инвертированными, помеченными штрихом. Например, при n=4 конъюнкция xy'zw' означает индивид, которому присущи x и z, а y и w – антиприсущи.

Четкая подсовокупность n-терминной совокупности естественно кодируется вектором, биты которого однозначно сопоставлены терминам (проиндексированы терминами). Если термин принадлежит подсовокупности, то его биту присваивается значение 1, а если не принадлежит, то 0. Так, конъюнкция xy'zw' кодируется вектором 1010. Но надо указывать тип кодируемой совокупности, поскольку она может быть конъюнктивной либо дизъюнктивной. Индивидная конъюнкция отображается конструктом n-битная К-шкала, предполная дизъюнкция – n-битная Д-шкала.

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

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

Для представления сокращенных и минимальных ДНФ и КНФ, которые необходимо содержат неиндивидные конъюнкции и непредполные дизъюнкции, являющиеся нечеткими совокупностями терминов используется конструкт типа цепь n-тритных слов соответственно К- и Д-шкал [3].

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

Булевы выражения вводятся в общепринятой алгебраической записи в виде строк, автоматически отображаемых процессором в ДК-шкалы. При выдаче результатов производится обратное преобразование шкал и цепей в строки.

Литература

1. Концептуальная характеристика РИИИС-процессора / Н. П. Брусенцов, С. П. Маслов, Х. Рамиль Альварес, С. А. Сидоров // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во ф-та ВМиК МГУ, 1996. С. 16-43.
2. Владимирова Ю. С. Конструктная реализация булевой алгебры // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во ф-та ВМиК МГУ, 1996. С. 44-69.
3. Брусенцов Н. П., Владимирова Ю. С. Троичная компьютеризация булевой алгебры // Цифровая обработка информации и управление в чрезвычайных ситуациях. – Минск: Институт технической кибернетики НАНБ, 2002. Том 2. С. 195-199.

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

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