Логика в информатике - Logic in computer science

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

Логика в информатике покрывает перекрытие между полем логика и что из Информатика. По сути, эту тему можно разделить на три основных направления:

  • Теоретические основы и анализ
  • Использование компьютерных технологий в помощь логикам
  • Использование концепций из логики для компьютерных приложений

Теоретические основы и анализ

Логика играет фундаментальную роль в информатике. Некоторые из ключевых областей логики, которые особенно важны: теория вычислимости (ранее называвшаяся теорией рекурсии), модальная логика и теория категорий. В теория вычислений основан на концепциях, определенных логиками и математиками, такими как Церковь Алонсо и Алан Тьюринг.[1][2] Черч впервые показал существование алгоритмически неразрешимых проблем, используя свое понятие лямбда-определимости. Тьюринг дал первый убедительный анализ того, что можно назвать механической процедурой и Курт Гёдель утверждал, что нашел анализ Тьюринга «идеальным».[3]Кроме того, некоторые другие основные области теоретического пересечения логики и информатики:

  • Теорема Гёделя о неполноте доказывает, что любая логическая система, достаточно мощная, чтобы характеризовать арифметику, будет содержать утверждения, которые нельзя ни доказать, ни опровергнуть в рамках этой системы. Это имеет прямое приложение к теоретическим вопросам, касающимся возможности доказательства полноты и правильности программного обеспечения.[4]
  • В проблема с рамой это основная проблема, которую необходимо преодолеть при использовании логика первого порядка для представления целей и состояния агента искусственного интеллекта.[5]
  • В Переписка Карри – Ховарда это отношение между логическими системами и программным обеспечением. Эта теория установила точное соответствие между доказательствами и программами. В частности, он показал, что термины в простом типизированном лямбда-исчислении соответствуют доказательствам интуиционистской логики высказываний.
  • Теория категорий представляет собой взгляд на математику, который подчеркивает отношения между структурами. Он тесно связан со многими аспектами информатики: системами типов для языков программирования, теорией систем переходов, моделями языков программирования и теорией семантики языков программирования.[6]

Компьютеры в помощь логикам

Одно из первых приложений, использующих термин искусственный интеллект была система Logic Theorist, разработанная Аллен Ньюэлл, Дж. С. Шоу и Герберт Саймон в 1956 году. Одна из вещей, которую делает логик, - это брать набор логических утверждений и делать выводы (дополнительные утверждения), которые должны быть истинными по законам логики. Например, если дана логическая система, которая гласит: «Все люди смертны» и «Сократ - человек», правильным выводом будет «Сократ смертен». Конечно, это банальный пример. В реальных логических системах утверждения могут быть многочисленными и сложными. С самого начала стало понятно, что этому виду анализа может значительно помочь использование компьютеров. Теоретик логики подтвердил теоретические работы Бертран Рассел и Альфред Норт Уайтхед в своей влиятельной работе по математической логике Principia Mathematica. Кроме того, логики использовали последующие системы для проверки и открытия новых логических теорем и доказательств.[7]

Логические приложения для компьютеров

Математическая логика всегда оказывала сильное влияние на область искусственный интеллект (AI). С самого начала работы в этой области было понятно, что технология автоматизации логических выводов может иметь большой потенциал для решения проблем и вывода выводов из фактов. Рон Брахман описал логика первого порядка (FOL) как метрика, по которой все AI представление знаний формализмы должны быть оценены. Нет более общего или мощного известного метода описания и анализа информации, чем FOL. Причина, по которой FOL просто не используется в качестве компьютерного языка, состоит в том, что он на самом деле слишком выразителен в том смысле, что FOL может легко выражать утверждения, которые ни один компьютер, независимо от его мощности, никогда не сможет решить. По этой причине каждая форма представления знаний - это в некотором смысле компромисс между выразительностью и вычислимостью. Чем выразительнее язык, чем он ближе к FOL, тем больше вероятность того, что он будет медленнее и склонен к бесконечному циклу.[8]

Например, ЕСЛИ ТО правила, используемые в экспертные системы приближается к очень ограниченному подмножеству ВОЛС. Вместо произвольных формул с полным набором логических операторов отправной точкой является просто то, что логики называют modus ponens. Как результат, системы на основе правил могут поддерживать высокопроизводительные вычисления, особенно если они используют преимущества алгоритмов оптимизации и компиляции.[9]

Другой важной областью исследований логической теории была программная инженерия. Исследовательские проекты, такие как Программный помощник на основе знаний и программы Programmer's Apprentice применяли логическую теорию для проверки правильности спецификаций программного обеспечения. Они также использовали их для преобразования спецификаций в эффективный код на различных платформах и для доказательства эквивалентности реализации и спецификации.[10] Такой формальный подход, основанный на преобразовании, часто требует гораздо больше усилий, чем традиционная разработка программного обеспечения. Однако в определенных областях с соответствующими формализмами и шаблонами многократного использования этот подход оказался жизнеспособным для коммерческих продуктов. Подходящими доменами обычно являются такие, как системы вооружений, системы безопасности и финансовые системы в реальном времени, где отказ системы имеет чрезмерно высокие человеческие или финансовые затраты. Примером такого домена является Очень крупномасштабная интегрированная (СБИС) дизайн - процесс проектирования микросхем, используемых для процессоров и других важных компонентов цифровых устройств. Ошибка в микросхеме - это катастрофа. В отличие от программного обеспечения, микросхемы не могут быть исправлены или обновлены. В результате существует коммерческое обоснование использования формальных методов для доказательства того, что реализация соответствует спецификации.[11]

Еще одно важное применение логики в компьютерных технологиях было в области языки фреймов и автоматические классификаторы. Языки фреймов такой аис KL-ONE имеют жесткую семантику. Определения в KL-ONE можно напрямую сопоставить с теорией множеств и исчислением предикатов. Это позволяет специализированным средствам доказательства теорем, называемым классификаторами, анализировать различные объявления между наборами, подмножествами и отношениями в данной модели. Таким образом, модель может быть проверена, и любые несогласованные определения будут отмечены. Классификатор также может выводить новую информацию, например определять новые наборы на основе существующей информации и изменять определение существующих наборов на основе новых данных. Уровень гибкости идеален для работы в постоянно меняющемся мире Интернета. Технология классификатора построена на таких языках, как Язык веб-онтологий чтобы обеспечить логический семантический уровень существующего Интернета. Этот слой называется Семантическая сеть.[12][13]

Временная логика используется для рассуждения в параллельные системы.[14]

Смотрите также

Рекомендации

  1. ^ Льюис, Гарри Р. Р. Льюис Элементы теории вычислений Проверять | url = ценить (помощь).
  2. ^ Дэвис, Мартин (11 мая 1995 г.). «Влияние математической логики на информатику». В Рольф Херкен (ред.). Универсальная машина Тьюринга. Springer Verlag. ISBN  9783211826379. Получено 26 декабря 2013.
  3. ^ Кеннеди, Джульетта (2014-08-21). Устный перевод Гёделя. Издательство Кембриджского университета. ISBN  9781107002661. Получено 17 августа 2015.
  4. ^ Хофштадтер, Дуглас Р. (1999-02-05). Гедель, Эшер, Бах: вечная золотая коса. Основные книги. ISBN  978-0465026562.
  5. ^ Маккарти, Дж.; П.Дж. Хейс (1969). «Некоторые философские проблемы с точки зрения искусственного интеллекта». Машинный интеллект. 4: 463–502.
  6. ^ Барр, Майкл; Чарльз Уэллс (1990). Категория Теория для компьютера. Прентис-Холл.
  7. ^ Ньюэлл, Аллен; Дж. К. Шоу; H.C. Саймон (1963). «Эмпирические исследования с помощью машины логической теории». В Эде Фейгенбауме (ред.). Компьютеры и мысль. Макгроу Хилл. стр.109–133. ISBN  978-0262560924.
  8. ^ Левеск, Гектор; Рональд Брахман (1985). «Фундаментальный компромисс в представлении знаний и рассуждении». В Рональде Брахмане и Гекторе Дж. Левеке (ред.). Чтение в представлении знаний. Морган Кауфманн. п.49. ISBN  0-934613-01-X. Хорошая новость в сокращении обслуживания KR до доказательства теорем состоит в том, что теперь у нас есть очень четкое, очень конкретное представление о том, что должна делать система KR; Плохая новость заключается в том, что также ясно, что услуги не могут быть предоставлены ... решить, является ли предложение в FOL теоремой ... неразрешимо.
  9. ^ Форджи, Чарльз (1982). «Rete: быстрый алгоритм для решения проблемы соответствия множеству шаблонов / множеству объектов *» (PDF). Искусственный интеллект. 19: 17–37. Дои:10.1016/0004-3702(82)90020-0. Архивировано из оригинал (PDF) на 2013-12-27. Получено 25 декабря 2013.
  10. ^ Рич, Чарльз; Ричард С. Уотерс (ноябрь 1987 г.). "Ученик программиста: обзор исследования" (PDF). Эксперт IEEE. Получено 26 декабря 2013.
  11. ^ Ставриду, Виктория (1993). Формальные методы в схемотехнике. Синдикат прессы Кембриджского университета. ISBN  0-521-443369. Получено 26 декабря 2013.
  12. ^ МакГрегор, Роберт (июнь 1991). «Использование классификатора описания для улучшения представления знаний». Эксперт IEEE. 6 (3): 41–46. Дои:10.1109/64.87683. S2CID  29575443.
  13. ^ Бернерс-Ли, Тим; Джеймс Хендлер; Ора Лассила (17 мая 2001 г.). «Семантическая сеть Интернет. Новая форма веб-контента, значимая для компьютеров, откроет революцию новых возможностей». Scientific American. 284: 34–43. Дои:10.1038 / scientificamerican0501-34. Архивировано из оригинал 24 апреля 2013 г.
  14. ^ Колин Стирлинг (1992). «Модальная и временная логика». У С. Абрамского; Д. М. Габбай; Т. С. Э. Майбаум (ред.). Справочник по логике в компьютерных науках. II. Издательство Оксфордского университета. С. 477–563. ISBN  0-19-853761-1.

дальнейшее чтение

внешняя ссылка