Энциклопедия эпистемологии и философии науки - логика в компьютерных науках

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

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

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

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

Рост сложности и объема компьютерных программ потребовали разработки средств их верификации и автоматического синтеза. Логики программ возникли как один из видов динамических логик. Когда возникла эта задача, оказалось, что в современной полимодальной логике уже давно созданы необходимые математические средства. На семантическом уровне модальные операторы интерпретируются вычислительными операциями. Это позволяет корректно сформулировать предусловия и постусловия применимости процедур и функций. При таком подходе были построены логические аксиоматизации ряда языков программирования.

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

Стремление наделить компьютеры элементами интеллекта привело к созданию такой области исследований, как искусственный интеллект. Логика в данном случае оказалась незаменимым инструментом. Умный компьютер должен уметь не только вычислять, но и рассуждать. Программы должны перестать быть просто набором последовательно выполняемых процедур. Решение задачи должно получаться в результате некоторого рассуждения, быть его продуктом. Первый настоящий язык логического программирования — Prolog — «родился» в 1971. Был предложен и реализован на практике новый универсальный подход к решению задач. Достаточно на подходящем логическом языке просто описать предметную область, указав существенные взаимоотношения ее элементов. Это и есть программа в новом смысле. Всякое же вычисление — это получение ответов на различные типы вопросов относительно описанной предметной области, (напр., верно ли, что предметы а, Ь, с находятся в отношении R(a,b,c)?) или найти все предметы х, у, z, находящиеся в отношении R(x,y,z). Любую программу, написанную на традиционных языках программирования, можно записать на языке Prolog. При этом оказалось, что эти программы имеют гораздо более компактный и удобочитаемый код. В отличие от синтеза программ по доказательству, в Prolog'e с помощью специального эффективного алгоритма унификации реализуется принцип связывания переменных.

Возникновение этого языка дало мощный толчок для построения логических баз данных и баз знаний. Напр., чтобы описать все типы родственных отношений между людьми, нет необходимости хранить их полное перечисление. Достаточно хранить лишь информацию об отношениях «Быть родителем(х,у)», «Мужчина(х)», «Женщина(х)». Все остальные возможные родственные отношения определяются через них. Если базы данных, по своей сути, хранят и позволяют эффективно пользоваться информацией об известных фактах.то теперь появилась реальная возможность хранить в компьютерах накопленное человеческое знание. Появились базы знаний. Задача эффективного их использования потребовала создания новых типов компьютерных программ, получивших название экспертных систем. В зависимости от типа предметной области требуются различные способы рассуждений, в основе которых могут лежать вероятностная, нечеткая, многозначные, немонотонные и др. логики. Все они нашли применение в экспертных системах.

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

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

В.И. Шалак

Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация»

И.Т. Касавин

2009