автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Компьютеризация булевой алгебры в диалоговой системе структурированного программирования

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи

Владимирова Юлия Сергеевна

КОМПЬЮТЕРИЗАЦИЯ БУЛЕВОЙ АЛГЕБРЫ В ДИАЛОГОВОЙ СИСТЕМЕ СТРУКТУРИРОВАННОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2004

Работа выполнена в научно-исследовательской лаборатории ЭВМ факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: Брусенцов Николай Петрович,

кандидат технических наук

Официальные оппоненты: Рудаков Константин Владимирович, член-

корреспондент РАН, доктор физико-математических наук, профессор кафедры математических методов прогнозирования факультета ВМиК МГУ им. М.В. Ломоносова;

Кузичев Александр Сергеевич, кандидат физико-математических наук, ст. научный сотрудник кафедры теории вероятностей механико-математического факультета МГУ им. М.В. Ломоносова

Ведущая организация: Государственное Унитарное Предприятие Научно-

производственный Центр «СПУРТ»

Защита диссертации состоится " 28 "_мая 2004 г. в Д часов на

заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан "_ 2004 г.

Ученый секретарь диссертационного совета

профессор

Л

Н.П. Трифонов

Актуальность темы

В настоящее время в языках программирования реализованы операции над переменными и константами булевского типа. В то же время, известно, что булева алгебра позволяет работать с более сложными объектами - булевыми выражениями, термины в которых не фиксируются, а могут принимать произвольные значения. В булевой алгебре рассматривается вопрос о связи между выражениями, и, в частности, о решении булевых уравнений. Придание компьютеру способности аналитически решать подобного рода задачи, т. е. манипулировать не только значениями типа boolean, но и выражениями булевой алгебры представляет большой практический и теоретический интерес. Понимаемая таким образом компьютеризация булевой алгебры является существенным продвижением в деле автоматизации рассуждения и построения логических машин, которым в разное время занимались Р.Лулий, Г.В.Лейбниц, Дж.Буль, У.Джевонс, Л.Кэрролл, П.С.Порецкий, Я.Лукасевич.

Компьютерная система, реализующая булеву алгебру, позволяет автоматически анализировать представленные булевыми выражениями ситуации, что практически полезно и при изучении логики, и при ее использовании в языках программирования, управляющих системах, базах данных и базах знаний и т. п. В настоящее время появляется все больше публикаций, посвященных этому вопросу, например, работы Закревского А.Д., Шукиса А.А., Бахтиярова К.И., Уткина А.А., Обухова В.Е. и Павлова В.В., Горелика А. Л., Скрипкина В.А., Григорьяна Ю.Г.

Цель работы

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

РОС. НАЦИОНАЛЬНАЯ 3 БИБЛИОТЕКА

»

Основные результаты работы

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

2. Программно осуществлен логико-алгебраический процессор, реализующий булевы и теоретико-множественные операции над объектами типа «выражения булевой алгебры», что обеспечило возможность программировать произвольные преобразования этих выражений и автоматизировать решение алгебраических задач.

3. На базе созданного инструментария разработаны программы преобразования булевых выражений в заданную форму, выявления отношений, связывающих выражения друг с другом, решения булевых уравнений.

Научная новизна работы

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

Предложен и программно реализован в ДССП применительно к выражениям булевой алгебры способ кодирования алгебраических объектов.

Разработан и компьютеризован способ решения булевых уравнений.

Методы исследования

В работе используется конструктная технология программирования в диалоговой системе структурированного программирования ДССП. Выражения булевой алгебры моделируются как определяемые в ДССП высокоуровневые типы данных (конструкты).

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

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

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

В исследовании проблемы решения булевых- уравнений использован усовершенствованный метод Буля-Порецкого [3,7].

Практическая значимость работы

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

Апробация работы

Резльтаты работы докладывались на конференциях "Ленинские горы-95", "Ломоносовские чтения-96", "Ломоносовские чтения-97", "Ломоносовские чтения-99", "Ломоносовские чтения-2001", "Ломоносовские чтения-2002" и "Цифровая обработка информации и управление в чрезвычайных ситуациях", (Минск, 2002 г.), "Ломоносовские чтения-2003", «Математические методы распознавания образов - 11» (Пущино, 2003 г.).

Структура и объем диссертации

Диссертация состоит из введения, трех глав, заключения и библиографии. Общий объем диссертации 78 страниц. Библиография включает 59 наименований.

Содержание работы

ВО ВВЕДЕНИИ охарактеризованы проблемы создания алгоритмической системы, позволяющей манипулировать булевыми выражениями. Рассмотрены возможности компьютерной системы конструктной реализации булевой алгебры. Приведено краткое описание содержания диссертации.

В ПЕРВОЙ ГЛАВЕ изложены принципы конструктной технологам программирования, реализуемой в ДССП и развитой в данной диссертации.

Изначально ДССП наряду со средствами разработки структурированных программ предоставляла и механизм

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

Конструкты - это типы данных, конструируемые путем задания их формата и базисного набора процедур, определяющих интерпретацию представимых в этом формате значений.

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

Рассмотрим в качестве примера конструкт, которым в системе манипулирования булевых выражений кодируются ^терминные индивидные конъюнкции. Формат этого конструкта - п-6итный вектор, проинтерпретированный как упорядоченный перечень терминов х, у, I, ..., w. Другими словами, данные термины сопоставлены битам вектора как значения индекса: х-бит, у-бит, ..., w-бит. Такой вектор кодирует четко определенные совокупности терминов: если термин принадлежит отображаемой совокупности, то обозначенный им бит вектора принимает

значение 1, а если не принадлежит, то 0. Например, при л=3 совокупности ху? соответствует значение 111, я!у'г' - 000, а ху£ - ПО. Процедуры доступа формата л-битный вектор: засылка л-битного вектора в стек операндов; присваивание ему значения из стека; засылка в младший бит вершины стека значения бита, соответствующего определенному термину; присваивание заданному биту значения из младшего бита вершины стека.

Формат «л-битный вектор» интерпретируется как конъюнктивная совокупность терминов, т. е. л-терминная индивидная конъюнкция, заданием базисного набора процедур, включающего процедуры дизъюнкции, объединения, пересечения и инверсии. Полученный конструкт называется К-шкалой.

Возможна другая интерпретация л-битного вектора - в виде л-терминной дизъюнктивной совокупности терминов, т. е. предполной дизъюнкции. Соответствующий конструкт называетсяД-шкалой.

ВО ВТОРОЙ ГЛАВЕ подробно рассмотрены конструкты, кодирующие булевы выражения, а также построенная на их основе система манипулирования булевыми выражениями в целом. Исследованы практические возможности указанной системы.

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

Например, выражению ху' V ху соответствует четырехбитный вектор ОНО:

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

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

Несовершенные ДНФ и КНФ содержат нечеткие конъюнктивные или дизъюнктивные совокупности терминов, т. е. такие, в которых термин может быть не в двух, а в трех состояниях - «утверждение», «инверсия» и «умолчание». Поэтому терминам позиционно сопоставляются пары битов 2л-битного вектора, причем из четырех значений, которые может принять пара битов, принимаются во внимание только три: 01 кодирует х, 10 -х, 11 - умолчание х. Например, при п=3 совокупности х?, соответствует значение 011101, x'y'z' - 101010, a. x - 011111. Нечеткие совокупности

терминов могут быть двух видов, соответственно создано два конструкта: тритные К-шкала иД-шкала.

Произвольное выражение в несовершенной НФ отображается динамической цепью тритных шкал, элементами которой являются тритные К-шкалы в случае ДНФ и Д-шкалы в случае КНФ. Цепь содержит также служебный элемент, значение которого определяет, в какой нормальной форме, - конъюнктивной или дизъюнктивной, представлено отображенное цепью выражение. Поэтому одна и та же цепь может кодировать как КНФ, так и ДНФ. Например, выражение хуч г,' кодируется цепью тритных К-шкал: 0 010111 111110, а выражение (л: V у)(х' V г') -цепью 1 010111 101110, где первый элемент соответствует виду НФ.

Интерпретирующие процедуры конструкта К/Д-цепь реализуют преобразования булевых выражений, приведенных в НФ - конъюнкцию и дизъюнкцию выражений, дополнение и инверсию, приведение выражения в двойственную НФ, а также операции, применимые только к несовершенным НФ - склеивание элементарных конъюнкций и дизъюнкций, приведение к сокращенной и минимальной НФ.

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

В ТРЕТЬЕЙ ГЛАВЕ даются примеры созданных на основе описаных конструктов процедур обработки булевых выражений: процедуры выявления отношений между двумя заданными выражениями,

решения булевых уравнений и минимизации дизъюнктивных и конъюнктивных нормальных форм выражений.

Достаточное условие выполнимости выражения выявляется, если выражение приведено в ДНФ: любая конъюнкция, входящая в ДНФ, а также дизъюнкция нескольких таких конъюнкций, является достаточным условием выполнения всего выражения. Если выражение приведено в КНФ, то входящие в КНФ дизъюнкции, а также их конъюнкции, будут необходимыми условиями выполнения выражения.

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

Два выражения несоисключимы, когда невозможна ситуация, при которой оба выражения исключены, одно из них будет обязательно дано. Пример - выражения х и х' v у'. Их отрицания - выражения х' и ху не могут быть даны одновременно. Если два выражения таковы, что они не могут быть даны одновременно, то эти выражения несовместны. Пример -выражения ху и ху' таковы, что если одно из них дано, то другое не может быть данным и наоборот. Если же два выражения несовместны и несоисключимы, то такое отношение называется комплементарностью. Пример комплементраных выражений - ху и х!чу'. Наконец, между выражениями может не быть никакой связи. В этом случае говорят, что эти выражения независимы. Например, выражения F = х и G = у являются независимыми, поскольку не содержат общих терминов.

Разработана процедура OTN, котрая позволяет сравнивать два булева выражения, выявляя указанные отношения. Ниже приведена схема работы этой процедуры, e и g~ сравниваемые выражения.

Важный пример применения созданных конструктов - процедура решения систем булевых уравнений.

Решение булевых уравнений справедливо считать одной из главных задач булевой алгебры. Именно решение логических уравнений Джон Буль считал предметом математической логики: «Наиболее общая проблема логики может быть сформулирована так: задано логическое уравнение, содержащее символы х, у, I, ж. Требуется найти логически интерпретируемое выражение для выяснения отношения класса,

обозначенного через w, к классам, обозначенным через х, у, z, и т.д.» ["Законы мысли", стр. 87].

Решению булевых уравнений посвящена работа П.С. Порецкого «О способах решения логических равенств и об обратном способе математической логики». Порецкий приводит решения Дж. Буля, У. Джевонса и Э. Шредера, а также свое собственное.

Булевым уравнением называется выражение, посторенное с помощью связки " =", обозначающей отношение эквивалентности:

Это выражение устанавливает связь между входящими в него терминами: = 1, что равносильно утверждению данности

выражения

буквально: «Дано

Решить уравнение относительно х, означает привести его к такому виду, при котором в одной части уравнения остается только х, а в другой -булево выражение:

Воспользуемся свойством связки "эквивалентность": (х «* у) в ху V х'у'

и приведем исходное уравнение к такому виду, чтобы в правой части осталась единица:

V ё£ = 1

Такое преобразование может быть произведено с любым булевым уравнением, следовательно, можно считать, что с самого начала дано уравнение в виде:

Будем считать, что левая часть приведена в СДНФ. Тогда это уравнение можно записать в виде:

Ax v fix' = 1,

где А и В не содержат термин х. Полученное Порецким «полное» решение х = хА v х'В этого уравнения представляет собой результат его тождественного преобразования к виду, при котором искомый термин обособлен в левой (или правой) части равенства.

Такое рекурсивное определение термина содержит в точности ту же информацию, что и не преобразованное уравнение, и едва ли облегчает ее интерпретацию по сравнению с вариантами, в которых осуществлено только разложение по искомому термину. Значительно больше дает выделение как в уравнении, так и в его решении «свободного члена»:

х = хАВ vx'A'B' vAB'. Теперь и по уравнению непосредственно, и по его решению, принимая во внимание, что функции терминов

попарно несовместимы, нетрудно заключить, что при АВ = 1 значение х свободно, привходяще, при АВ' = 1 необходимо х - 1, при А'В = 1 необходимо х = О, при A'B' = 1 решение не существует.

Уравнение обращается в тождество при подстановке АВ' = l,x = 1, либо независимо от х. При = 1 уравнение

противоречиво.

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

Был также найден более непосредственный алгоритм построения решения булева уравнения в виде рекурсивного определения искомого терминал [1, с. 67]. Полученное определение x:

x = xFvx!F'

тождественно исходному уравнению

и, так как х и Р(х, у,отображаются ДК-шкалами, доставляет готовый алгоритм для построения ДК-шкалы, кодирующей решение.

Еще один пример применения кодирующих булевы выражения конструктов - процедура минимизации булевых выражений [5]. Предложенный алгоритм минимизации булевых выражений и соответствующая программная процедура построены с использованием трехзначной логики.

В булевой алгебре терминам допустимо присваивать только два значения: 0 и 1. Третье значение - не-0 и не-1, возникет, если термины оказываются связанными логическими условиями (отношениями). Обозначим это значение буквой с.

В процедуре минимизации выражений это третье играет главную роль. Минимизация осуществляется путем попарного «склеивания» п-арных конъюнкций, различающихся только по одному из терминов. Например:

ху'ги V ху'£и в ху'гаи.

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

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

Процедура минимизации начинается с выявления для каждого

члена СДНФ всех «парных» для него, т. е. склеивающихся с ним по тому или иному термину членов. Число этих возможностей склеивания члена назовем его «парностью». Парность принимает целые значения от 0 до п: члены, не допускающие ни одной склейки, характеризуются нулевой парностью, склеивающиеся только по одному из терминов - парностью 1, по двум - 2, по всем терминам - парность л.

Далее производится упорядочение СДНФ по возрастанию парности ее членов: первые места занимают члены нулевой парности, если они имеются, за ними следуют, если имеются, члены с парностью 1, затем 2, 3, ..., п. Такая упорядоченность позволяет естественно отделить включаемые в минимальную ДНФ неизменными члены нулевой парности и утратившие парность результаты склеек от тех членов, которые уже учтены в этих результатах («покрыты» ими) и должны быть опущены.

В силу упорядоченности в склеивающихся парах членов один член, назовем его ведущим, предшествует другому, ведомому. Ведомые члены можно игнорировать, если результат склейки образуется из ведущего члена элиминацией в нем тех терминов, по которым произведена склейка. Например:

хуги V ху'г'и V ху'ги и ху"ги V ху'гаи = хги V ху'и

Один и тот же член может оказаться ведущим относительно одного термина и ведомым относительно другого. Такой член относится к ведомым, т. е. игнорируется. Например:

хуги V ху'г'и' V ху'гич ху'г'и = ху"ги V ху'г'и" а хги V ху'г',

Процедура минимизации состоит в выявлении всех возможных

склеек, упорядочении по нарастанию парности и удалении всех ведомых членов, а в ведущих членах - удалении терминов, относительно которых допустимо склеивание.

Процедура реализована в ДССП на основе конструкта К/Д-цепь.

В ЗАКЛЮЧЕНИИ- приводится краткий итог диссертационной работы и формулируются основные результаты.

Основные положения работы изложены в следующих публикациях:

1. Владимирова Ю.С. Конструктная реализация булевой алгебры // "Интегрированная система обучения, конструирования программ и разработки дидактических материалов (учебно-методическое пособие)" под ред. Н.П.Брусенцова, М.: МГУ, 1996 г. С. 44-69.

2. Брусенцов Н.П., Владимирова Ю.С. Компьютерная система решения булевых уравнений // Компьютерные аспекты в научных исследованиях и учебном процессе. - М: Изд-во МГУ, 1996. С. 99-100.

3. Брусенцов Н.П., Владимирова Ю.С. Решение булевых уравнений // "Методы математического моделирования", М.: Диалог-МГУ, 1998. С. 59-68.

4. Brasentsov N.P., Vladimirova Yu.S. Solution of Boolean Equations. // Computational mathematics and modeling, Vol. 9, № 4,1998. Pp. 287-295.

5. Брусенцов Н.П., Владимирова Ю.С. Троичный минимизатор булевых выражений // Программные системы и инструменты. Тематический сборник № 2. Под ред. Л.Н. Королева - М.: Ф-т ВМиК МГУ, 2001. С. 205-208.

6. Брусенцов Н.П., Владимирова Ю.С. Троичная компьютеризация булевой алгебры // Третья международная конференция

«Цифровая обработка информации и управление в чрезвычайных ситуациях», Минск: Институт технической кибернетики Национальной академии наук Беларуси, 2002. Т. 2. С. 195-199.

7. Брусенцов Н.П., Владимирова Ю.С. Троичное конструктное кодирование булевых выражений // Программные системы и инструменты: Тематический сборник факультета ВмиК МГУ им. Ломоносова: № 3 под ред. Л.Н. Королева - М.: Ф-т ВмиК МГУ, 2002. С. 610.

8. Брусенцов Н.П., Владимирова Ю.С. Конструктная компьютеризация булевой алгебры // Доклады 11-й Всероссийской конференции «Математические методы распознавания образов». - М.: ВЦ РАН, 2003. С. 33-34.

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

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 21.04.2004 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 80 экз. Заказ 462. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.ВЛомоносова.

Чзи J

ВВЕДЕНИЕ.

ГЛАВА 1. КОНСТРУКТНАЯ ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ.

1. Процедурное программирование в ДССП. Общая характеристика конструктной технологии.

2. Описание ДССП.

3. Конструкты и конструктная технология программирования.

ГЛАВА 2. КОНСТРУКТНАЯ РЕАЛИЗАЦИЯ БУЛЕВОЙ АЛГЕБРЫ.

1. Общая характеристика компьютерной системы, реализующей булеву алгебру

2. Булева алгебра.

3. Совокупностная интерпретация булевой алгебры.

4. Общая характеристика конструктов типа «булево выражение».

5. Конструкты ДК- и КД-шкала битных слов. а) Кодирование булевых выражений конструктами ДК- и КД-шкала. б) Стек ДК- и КД-шкал.

6. Конструкты К- и Д-шкала тритных слов и К/Д-цепь.

7. Система манипулирования булевыми выражениями.

ГЛАВА 3. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ КОНСТРУКТОВ ТИПА «БУЛЕВО ВЫРАЖЕНИЕ».

1. Процедура выявления взаимосвязи, заданной булевым выражением.

2. Выявление отношений между двумя выражениями.

3. Решение булевых уравнений. а) Метод Буля-Порецкого. б) Уточнение метода Буля-Порецкого. в) Примеры применения уточненного метода. г) Компьютерная процедура решения систем булевых уравнений. д) Вычисление решения булева уравнения в виде рекурсивного определения искомого термина.

4. Минимизация булевых выражений.

В современных языках программирования реализованы операции над переменными и константами булевского типа, т. е. принимающими значения 0 и 1 («да» и «нет», «true» и «false»). Булевские выражения используются, например, для задания условий в условных операторах и операторах цикла. Возможность автоматического вычисления значений булевских выражений позволяет говорить о том, что в настоящее время на компьютерах реализована «булева арифметика».

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

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

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

Проблема логического вывода, неоднократно изучавшаяся математиками, может быть решена и иными средствами, нежели те, которые являются основой современных алгоритмов. Так, Дж. Буль, трактовавший логические выражения как выражения алгебры классов, свел задачу логического вывода к решению систем булевых уравнений [25]. Его метод решения уравнений, развитый и усовершенствованный в дальнейшем Э. Шредером, У. Джевонсом и П.С. Порецким [1, 25, 27] позволяет получать исчерпывающую характеристику ситуации, заданной системой уравнений.

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

Цель настоящей работы — создание компьютерной системы, реализующей булеву алгебру. Такая система предоставляет программный инструментарий для автоматического преобразования булевых выражений, а также позволяет создавать произвольные процедуры алгебраических преобразований булевых выражений, в частности и такие, применение которых затруднено в других программных системах. Например, в системе реализованы конъюнкция и дизъюнкция двух булевых выражений, а также дополнение и инверсия выражения. На основе указанных процедур в качестве примера реализован метод Буля-Порецкого решения систем булевых уравнений [6].

В настоящей работе реализация компьютерной алгебры достигнута путем кодирования выражений высокоуровневыми типами данных и программирования процедур манипулирования выражениями в закодированном виде. Созданы процедуры перевода булева выражения из строки символов во внутреннее представление и обратно; все преобразования выражений производятся с кодами выражений.

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

Конструкт как тип данных характеризуется форматом памяти и базисным набором процедур, интерпретирующих принимаемое им значение. Формат определяет структуру, информационную емкость и способы доступа к памяти конструкта, а набор интерпретирующих процедур устанавливает истолкование конструкта. Например, конструкт «целое без знака» определен на основе формата «вектор битов» посредством соответствующего базисного набора интерпретирующих процедур - арифметических операций. На основе этого же формата можно создать конструкт «строка символов», введя другой базисный набор интерпретирующих процедур.

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

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

На основе созданных процедур эффективно реализуются программы решения задач булевой алгебры. В качестве примеров разработаны программы решения булевых уравнений [6], выявления отношений между выражениями, минимизации булевых выражений [8]. Их характеристика дана в третьей главе.

Заключение

Основной результат данной работы заключается в разработке и программном осуществлении логико-алгебраического процессора, реализующего операции конъюнкции, дизъюнкции и отрицания над объектами типа «выражение булевой алгебры», и позволяющего программировать произвольные преобразования этих выражений [12]. Процессор создан путем введения высокоуровневых типов данных - конструктов, кодирующих булевы выражения. Набор операций процессора включает в себя комплекс программных средств, обеспечивающих декларирование и функционирование этих конструктов (так называемый конструктив), а также набор алгебраических процедур.

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

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

Расширить класс решаемых задач удалось посредством введения троичного кодирования элементарных конъюнкций и дизъюнкций и дополнением системы конструктом «К/Д-цепь».

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

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

1. Брусенцов Н.П. Искусство достоверного рассуждения. — М.: Фонд «Новое тысячелетие», 1998, 136 с.

2. Брусенцов Н.П. Начала информатики. М.: Фонд «Новое тысячелетие», 1994, 176 с.

3. Владимирова Ю.С. Конструктная реализация булевой алгебры. // «Интегрированная система обучения, конструирования программ и разработки дидактических материалов (учебно-методическое пособие)» под ред. Н.П.Брусенцова. М.: МГУ, 1996, с. 44-69.

4. Брусенцов Н.П., Владимирова Ю.С. Компьютерная система решения булевых уравнений. // Компьютерные аспекты в научных исследованиях и учебном процессе. М: Изд-во МГУ, 1996, с. 99-100.

5. Брусенцов Н.П. Трехзначная диалектическая логика. // Программные системы и инструменты. Тематический сборник № 2. М.: Факультет ВМиК МГУ, 2001, с. 36-44.

6. Брусенцов Н.П., Владимирова Ю.С. Решение булевых уравнений. // «Методы математического моделирования». М.: Диалог-МГУ, 1998, с. 59-68.

7. Brusentsov N.P., Vladimirova Yu.S. Solution of Boolean Equations. // Computational mathematics and modeling, Vol. 9, № 4, 1998. Pp. 287-295.

8. Брусенцов Н.П., Владимирова Ю.С. Троичный минимизатор булевых выражений. // Программные системы и инструменты. Тематический сборник № 2. Под ред. JT.H. Королева М.: Ф-т ВМиК МГУ, 2001, с. 205208.

9. Брусенцов Н.П., Владимирова Ю.С. Троичное конструктиве кодирование булевых выражений. // Программные системы и инструменты: Тематический сборник факультета ВмиК МГУ им. Ломоносова: № 3 под ред. Л.Н. Королева М.: Ф-т ВмиК МГУ, 2002, с. 6-10.

10. Брусенцов Н.П., Владимирова Ю.С. Конструктная компьютеризация булевой алгебры. // Доклады 11-й Всероссийской конференции «Математические методы распознавания образов». М.: ВЦ РАН, 2003, с. 33- 34.

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

12. Брусенцов Н.П., Захаров В.Б., Руднев И.А. Сидоров С.А.,

13. Чанышев Н.А. Развиваемый адаптивный язык РАЯ диалоговой системы программирования ДССП. М.: Издательство МГУ, 1987, 80 с.

14. Брусенцов Н.П., Маслов С.П., Рамиль Альварес X.,

15. Сидоров С.А. Концептуальная характеристика РИИИС-процессора. // Интегрированная система обучения, конструирования программ и разработка дидактических материалов. М.: Изд-во ф-та ВмиК МГУ, 1996, с. 16-43.

16. Брусенцов Н.П. Микрокомпьютеры. М.: Наука, 1985, 208 с.

17. Захаров В.Б. Исследование и разработка методов организации больших программ и структур данных для микрокомпьютерных систем, реализуемых в ДССП. Диссертация на соискание ученой степени кандидата физ.-мат. наук. М.: МГУ, 1988, 101 с.

18. Микрокомпьютерные системы обучения. Сб. статей. / Под редакцией Н.П. Брусенцова и С.П. Маслова. М.: Издательство МГУ, 1986, 128 с.

19. Грачев А.Ю. Структурирование данных в диалоговой системе программирования ДССП. Диссертация на соискание ученой степени кандидата физ.-мат. наук. М.: МГУ, 1991, 103 с.

20. Методические указания по программированию в ДССП. / Под редакцией Н.П. Брусенцова. М.: Издательство МГУ, 1988, 39 с.

21. Брусенцов Н.П. Диаграммы Л.Кэррола и аристотелева силлогистика. // Вычислительная техника и вопросы кибернетики. Вып. 13. М., Издательство МГУ, 1977, с. 164-182.

22. Аристотель. Сочинения в четырех томах. -М.: «Мысль», т. 1 1975, 550 е., т. 2- 1978, 687 с.

23. Boole G. An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities. London, 1854,448 p.

24. Яблонский C.B. Введение в дискретную математику. М.: «Высшая школа», 1979, 384 с.

25. Лейбниц Г.В. Сочинения в четырех томах. Т. 3. М: «Мысль», 1984, 734 с.

26. Порецкий П.С. О способах решения логических равенств и об обратном способе математической логики. Опыт построения полной и общедоступной теории умозаключений над качественными формами. -Казань, 1884,170 с.

27. Кэрролл Л. История с узелками. М: «Фолио», 2001,431 с.

28. Стяжкин Н.И. Формирование математической логики. М.: «Наука», 1967, 507 с.

29. Клини С.К. Введение в математическую логику. М.: «Иностранная литература», 1957, 526 с.

30. Лупанов О.Б. Лекции по математической логике. Ч. 1. М: Изд-во МГУ, 1970, 80 с.

31. Гильберт Д., Аккерман В. Основы теоретической логики. М.: Гос. издательство иностранной литературы, 1947, 304 с.

32. Акритас А.Г. Основы компьютерной алгебры с приложениями. М: «Мир», 1994, 554 с.

33. Вирт Н. Алгоритмы и структуры данных. М: «Мир», 1989, 360 с.

34. Дейкстра Э. Заметки по структурному программированию. // Дал У., Дейкстра Э., Хоор К.Структурное программирование. М: «Мир», 1975, с. 7-97.

35. Хоор К. О структурной организации данных. // Дал У., Дейкстра Э., Хоор К. Стуктурное программирование. М.: «Мир», 1975, с. 98-197.

36. Хювеннен Э., Сеппянен И. Мир ЛИСПа. Т. 1. -М: «Мир», 1990, 447 с.

37. Бахтияров К.И. Логические основы компьютеризации умозаключений. -М: 1986, 94 с.

38. Шукис А.А. Математическая логика. Вып. 2. Алгебра Буля. Барнаул: Алтайский политехнический ин-т, 1974, 216с.

39. Закревский А.Д. Логические уравнения. Минск: «Наука и техника», 1975, 95 с.

40. Н.Н. КатериночкинаЮ З.Е. Королева, Х.А. Мадатян, И.М. Платоненко. Методы решения булевых уравнений. // Сообщения по прикладной математике (АН СССР, ВЦ). М: ВЦ АН СССР, 1988, 18 с.

41. Горелик А.А., Скрипкин В.А. Методы распознавания. М: «Высшая школа», 1989, 231 с.

42. Кулинкович А.Е. Алгоритмизация построения умозаключений. // «Методология геологических наук». Киев: «Наука думка», 1979, с. 145161.

43. Обухов В.Е., Павлов В.В. Логические уравнения и прикладные задачи. // Академия наук Украины. Ин-т кибернетики им. В.М. Глушкова. Киев: «Наука думка», 1992, 186 с.

44. Сериков Ю.А. Алгебраический метод решения логических уравнений. // Изв. АН СССР. Техническая кибернетика. № 2, 1972, с. 114-124.

45. Лобанов В.И. Решение логических уравнений. // Научно-техническая информация. Сер.2., № 9,1998, с. 34-40.

46. Гомзулева В.Н. Решение логических уравнений в булевом базисе. // Вычислительная техника и машиностроение. № 3, 1978, с. 141-144.

47. Пошерстник М.С. Решение логических уравнений методом выделения переменных. //Автоматика и телемеханика. № 2, 1979, с. 132-140.

48. Леонтьев В.К., Нурлыбаев А.Н. Об одном классе систем булевых уравнений. // Журнал вычислительной математики и математической физики. № 15, 1975, с. 1568-1579.

49. Михайловский Л.В. Метод решения логических задач больших размеров. // Вопросы технической диагностики. № 17, 1977, с. 132-140.

50. Егиазарян Э.В. Об одном классе систем булевых уравнений. // Журнал вычислительной математики и математической физики. № 16, 1976,с. 1073-1077.

51. Розенфельд Т.К., Силаев В.Н. Булевы уравнения и декомпозиция булевых функций. // Изв. АН СССР. Техническая кибернетика. № 1, 1979, с. 114124.

52. Тесленко Е.А. Об одном подходе к задаче решения логических уравнений. // Автоматика и телемеханика. № 12, 1974, с. 151-159.

53. Григорьян Ю.Г. Алгоритмы решения логических уравнений // Журнал вычислительной математики и математической физики, Т. 2, № 1,1962, с. 16-189.

54. Смирнов В.А., Маркин В.И., Новодворский А.Е., Смирнов А.В. Логика и компьютер. Вып. 3. Доказательство и его поиск. М.: Наука, 1996, 254 с.

55. Белнап Н. Как нужно рассуждать компьютеру. // Белнап Н., Стил Т. Логика вопросов и ответов. М.: Прогресс, 1981, с. 208-239.

56. Поваров Г.Н., Петров А.Е. Русские логические машины. // Кибернетика и логика. Математико-логические аспекты становления идей кибернетики и развития вычислительной техники.-М.: Наука, 1978, с. 137-152.

57. Бирюков Б.В., Туровцева А.Ю. Логико-гносеологические взгляды Эрнста Шредера. // Кибернетика и логика. Математико-логические аспекты становления идей кибернетики и развития вычислительной техники. М.: Наука, 1978, с. 153-252.

58. Бирюков Б.В. Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики. М: «Знание», 1985, 192 с.

59. H.R.Andersen. An Introduction to Binary Decision Diagrams. //November 1994 Tech University of Denmark, 37 p.,http://www.cse.iitd.ernet.in/~sak/courses/foav/Andersen-BDDs.ps.gz

60. Seger C.-J., Bryant R.E. Formal verification by symbolic evaluation of partially-ordered trajectories. // Formal Methods in System Design,6(2), March 1995, pp. 121-146.