Конструктная компьютерная реализация булевой алгебры

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

Конструктами называют высокоуровневые типы данных, конструируемые в диалоговой системе структурированного программирования ДССП [1]. Конструкт — это процедурно интерпретируемый формат, как правило, битный вектор параметрически задаваемой длины с набором процедур, реализующих базисные операции над его значениями. Например, конструкт “Комплексное число” — двухкомпонентный числовой вектор с определенными над ним операциями.

Особый интерес представляют неарифметические конструкты, в частности, интерпретирующие тот же вектор битов как представленной в той или иной форме выражение булевой алгебры. Они открывают возможность программируемого преобразования выражений, выявления отношений, которыми взаимосвязаны выражения, решения логических уравнений, в чем Дж. Буль небезосновательно усматривал “наиболее общую проблему логики” [2].

Будем интерпретировать n-битный вектор как упорядоченный перечень терминов x, y, z, …, w. Другими словами, сопоставим данные термины битам вектора как значения индекса: x-бит, y-бит, …, w-бит. Такой вектор естественно кодирует четко определенные совокупности терминов: если термин принадлежит отображаемой совокупности, то обозначенный им бит вектора принимает значение 1, а если не принадлежит, то 0. Так в случае четырехбитного вектора xyzw совокупность терминов x и z отображается значением 1010, а пустая совокупность 0000.

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

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

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

Литература

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

Заметки о трехзначной логике
Опубликовано в Доклады 11-й Всероссийской конференции "Математические методы распознавания образов ". – М.: ВЦ РАН, 2003. С. 33 – 34.