Компьютеризация булевой алгебры в диалоговой системе структурированного программирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Владимирова, Юлия Сергеевна

• Владимирова, Юлия Сергеевна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Владимирова, Юлия Сергеевна

ВВЕДЕНИЕ.

ГЛАВА 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 битов) и простотой процедур доступа (шкала обрабатывается как битный вектор, а цепь представляет собой двухуровневый динамический формат).

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Владимирова, Юлия Сергеевна, 2004 год

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.