Логика в информатике — это направления исследований и отраслей знания, где логика применяется в информатике и искусственном интеллекте. Логика очень эффективна в этих областях^[1].

Область применения

Включаются следующие основные применения:

• исследования в логике, вызванные развитием компьютерных наук. Например, аппликативные вычислительные системы, теория вычислений и модели вычислений;

• формальные методы и логика рассуждения о понятиях. Например, семантическая сеть^[2], семантическая паутина;

• булева логика и алгебра для разработки аппаратного обеспечения компьютеров;

• решение задач и структурное программирование для разработки прикладных программ и создания сложных систем программного обеспечения

• доказательное программирование — технология разработки алгоритмов и программ с доказательствами правильности алгоритмов;

• фундаментальные понятия и представления для компьютерных наук, которые являются естественной областью для формальной логики. Например, семантика языков программирования^[3];

• логика знания и предположения. Например, искусственный интеллект;

• Язык Пролог и логическое программирование для создания баз знаний и экспертных систем и исследований в сфере искусственного интеллекта;

• логика для описания пространственного положения и перемещения;

• логика в информационных технологиях. Например, реляционная модель данных. реляционные СУБД, реляционная алгебра, реляционное исчисление^[4];

• логика вычислений с объектами. Например, комбинаторная логика, суперкомбинаторы^[5];

• логика для компилирования программного кода и его оптимизации. Например, категориальная абстрактная машина;

• логика для эквивалентного преобразования объектов. Например, λ-исчисление;

• переизложение логики и математики в терминах, понятных специалистам в компьютерных науках^[6].

Этот список продолжает пополняться.

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

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

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

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

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

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

В результате программисты пишут программы с большим числом ошибок, которые они не могут ни выявить, ни исправить. Массированное тестирование программ на ЭВМ приносит программистам несомненную пользу, однако не дает гарантий полного избавления от ошибок.

Практика применения и изучения доказательных методов программирования показала, что эта технология вполне доступна студентам математических факультетов, которым вполне по силам написание доказательств правильности алгоритмов, после проверки и тестирования программ на ЭВМ.

Наибольший эффект в освоении технологий доказательного программирования наблюдается в олимпиадах по информатике и программированию, где победителями и призёрами становятся те студенты, которые освоили технику тестирования программ на ЭВМ и составления алгоритмов и программ без ошибок.

См. также

• Комбинаторная логика
• Программирование
• Парадигма программирования
• Структурное программирование
• Логическое программирование
• Информатика
• Решение задач
• Доказательное программирование

Примечания