|
Оглавление
Предисловие
Изучение логических уравнений, их классификация и разработка эффективных методов их решения имеют большое значение, поскольку именно к ним в значительной степени сводится решение многих научных и технических задач, возникающих, например, при синтезе и анализе дискретных вычислительных и управляющих устройств, формализации поиска и доказательства теорем в формальных теориях, поиске неисправностей в технических системах. Эти задачи принято называть логическими. В течение долгого времени богатым источником логических задач служит теория автоматов, с успехом использующая такие развитые аппараты современной дискретной математики, как теория булевых функций и теория графов. В теории автоматов рассматриваются сложные дискретные автоматические устройства, составленные из простых элементов. Основной ее проблемой является проблема отношения между структурой и реализуемой ею функцией, основной задачей – логический синтез, цель которого – получение структуры с заданными заранее функциональными свойствами. Задачу синтеза можно сформулировать как задачу декомпозиции заданной функции по системе операторов, реализуемых элементами, из которых должна быть построена структура. Эта задача в свою очередь сводится к решению системы логических уравнений. Достаточно важна и задача анализа заданной структуры дискретного устройства, особенно в связи с проблемой поиска неисправностей. К нахождению корней системы логических уравнений сводится, например, поиск устойчивых состояний устройства, структура которого описывается данной системой. Другим источником логических задач, интенсивно развивающимся в настоящее время, является проблема создания "искусственного интеллекта". В рамках этой проблемы проводится исследование задач, формализация которых сопряжена с большими трудностями, Такие задачи принято называть "интеллектуальными" или "творческими". Как правило, это также и логические задачи, многие из которых удается сформулировать как задачи решения логических уравнений того или иного типа. Решение логических уравнений в общем виде связано с необходимостью реализации сильно ветвящегося процесса поиска корней, обширным перебором промежуточных решений. Как правило, этот перебор настолько велик, что его не удается реализовать даже на современных быстродействующих ЭВМ. Однако, учитывая особенности конкретных уравнений, процесс поиска корней часто удается существенно ускорить. Поэтому основной путь развития эффективных методов решения логических уравнений – это классификация уравнений и разработка соответствующих методов для каждого класса. Именно этот путь и нашел отражение в настоящей монографии, в которой автор попытался обобщить относящийся к рассматриваемой проблеме материал, рассеянный по научной периодической литературе, добавив к нему некоторые результаты своих исследований. В книге рассматриваются логические уравнения некоторых типов и методы их решения. Вначале излагаются элементы булевой алгебры, знакомство с которыми необходимо для чтения последующего материала. Затем вводятся логические уравнения и рассматриваются разные варианты постановки задачи "решить логическое уравнение", показаны различные типы логических уравнений и способы их решения, рассчитанные как на "ручную " реализацию, так и на использование ЭВМ. В заключение приводится список литературы, который может оказаться полезным для читателя, желающего поближе познакомиться с рассматриваемой проблемой и смежными областями. Об авторе
Окончил Томский гос. университет (1956), В 1959–71 гг. ассистент, старший научный сотрудник, заведующий лабораторией счетно-решающих устройств, профессор, заведующий кафедрой математической логики и программирования в Томском университете. В 1971–94 гг. заведующий лабораторией логического проектирования, с 1994 г. главный научный сотрудник Института технической кибернетики Национальной АН Беларуси, одновременно профессор Белорусского государственного университета информатики и радиоэлектроники. Работы по теории автоматов, системному программированию, логико-комбинаторным методам в технике и информатике. Предложил язык программирования логических задач ЛЯПАС, на базе которого была создана серия систем автоматизированного проектирования дискретных устройств, и методы реализации параллельных алгоритмов логического управления взаимодействующими процессами. Разработал серию практически эффективных алгоритмов минимизации булевых функций и систем, решения больших систем логических уравнений и переопределенных систем линейных логических уравнений с приложениями в логическом синтезе и защите информации. Обобщил методы теории булевых функций на конечные предикаты, разработал логический подход к распознаванию образов в пространстве булевых и многозначных признаков. Автор более 400 научных работ, в т. ч. 11 монографий. Основные труды: LYaPAS: A programming language for logic and coding algorithms (with M. A. Gavrilov). Academic Press, N.-Y., L., 1969; Алгоритмы синтеза дискретных автоматов. М., 1971; Логический синтез каскадных схем. М, 1981; Логические уравнения. Мн., 1975; Boolesche Gleichungen: Theorie, Anwendung, Algorithmen (mit D. Bochmann und Ch. Posthoff). VEB Verlag Technik, Berlin, 1984; Логика распознавания. Мн., 1988; Параллельные алгоритмы логического управления. Мн., 1999; Полиномиальная реализация частичных булевых функций и систем. Мн., 2001 (совм. с Н. Р. Тороповым). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||