В информатике , в частности в представлении знаний и рассуждениях и металогике , область автоматизированных рассуждений посвящена пониманию различных аспектов рассуждений . Изучение автоматизированных рассуждений помогает создавать компьютерные программы , которые позволяют компьютерам рассуждать полностью или почти полностью автоматически. Хотя автоматизированные рассуждения считаются подобластью искусственного интеллекта , они также связаны с теоретической информатикой и философией .
Наиболее развитыми подобластями автоматизированного рассуждения являются автоматизированное доказательство теорем (и менее автоматизированное, но более прагматичное подразделение интерактивного доказательства теорем ) и автоматизированная проверка доказательств (рассматриваемая как гарантированно правильное рассуждение при фиксированных предположениях). [ необходима ссылка ] Также была проделана обширная работа в области рассуждений по аналогии с использованием индукции и абдукции . [1]
Другие важные темы включают рассуждения в условиях неопределенности и немонотонные рассуждения. Важной частью области неопределенности является аргументация, где дополнительные ограничения минимальности и согласованности применяются поверх более стандартной автоматизированной дедукции. Система OSCAR Джона Поллока [2] является примером автоматизированной системы аргументации, которая является более конкретной, чем просто автоматизированный доказатель теорем.
Инструменты и методы автоматизированного рассуждения включают классическую логику и исчисления, нечеткую логику , байесовский вывод , рассуждения с максимальной энтропией и множество менее формальных специальных методов.
Развитие формальной логики сыграло большую роль в области автоматизированного рассуждения, что само по себе привело к развитию искусственного интеллекта . Формальное доказательство — это доказательство, в котором каждый логический вывод был проверен на соответствие фундаментальным аксиомам математики. Все промежуточные логические шаги предоставлены без исключения. Никакого обращения к интуиции, даже если перевод от интуиции к логике является рутинным. Таким образом, формальное доказательство менее интуитивно и менее подвержено логическим ошибкам. [3]
Некоторые считают, что летняя встреча в Корнелле 1957 года, на которой собралось много логиков и специалистов по информатике, стала началом автоматизированного рассуждения или автоматизированной дедукции . [4] Другие говорят, что она началась еще до этого с программы Logic Theorist 1955 года Ньюэлла, Шоу и Саймона или с реализации Мартином Дэвисом в 1954 году процедуры принятия решений Пресбургера (доказавшей, что сумма двух четных чисел является четной). [5]
Автоматизированное рассуждение, хотя и является важной и популярной областью исследований, пережило « зиму ИИ » в восьмидесятых и начале девяностых. Однако впоследствии эта область возродилась. Например, в 2005 году Microsoft начала использовать технологию верификации во многих своих внутренних проектах и планирует включить логическую спецификацию и язык проверки в свою версию Visual C 2012 года. [4]
Principia Mathematica была важной работой в формальной логике, написанной Альфредом Нортом Уайтхедом и Бертраном Расселом . Principia Mathematica — также означающая Принципы математики — была написана с целью вывести все или некоторые математические выражения в терминах символической логики . Principia Mathematica была первоначально опубликована в трех томах в 1910, 1912 и 1913 годах. [6]
Logic Theorist (LT) была первой программой, разработанной в 1956 году Алленом Ньюэллом , Клиффом Шоу и Гербертом А. Саймоном для «имитации человеческого мышления» при доказательстве теорем и была продемонстрирована на пятидесяти двух теоремах из второй главы Principia Mathematica, доказав тридцать восемь из них. [7] В дополнение к доказательству теорем программа нашла доказательство для одной из теорем, которое было более элегантным, чем то, что предоставили Уайтхед и Рассел. После неудачной попытки опубликовать свои результаты, Ньюэлл, Шоу и Герберт сообщили в своей публикации в 1958 году, The Next Advance in Operation Research :
Примеры формальных доказательств
Автоматизированные рассуждения чаще всего использовались для создания автоматизированных доказывателей теорем. Однако зачастую доказыватели теорем требуют некоторого человеческого руководства для эффективности и поэтому в более общем смысле могут считаться помощниками по доказательству . В некоторых случаях такие доказыватели придумывали новые подходы к доказательству теоремы. Logic Theorist является хорошим примером этого. Программа придумала доказательство для одной из теорем в Principia Mathematica , которое было более эффективным (требовало меньше шагов), чем доказательство, предоставленное Уайтхедом и Расселом. Программы автоматизированных рассуждений применяются для решения все большего числа задач в формальной логике, математике и информатике, логическом программировании , проверке программного и аппаратного обеспечения, проектировании схем и многих других. TPTP (Sutcliffe and Suttner 1998) представляет собой библиотеку таких задач, которая регулярно обновляется. Также на конференции CADE регулярно проводится соревнование среди автоматизированных доказывателей теорем (Pelletier, Sutcliffe and Suttner 2002); Задачи для конкурса выбираются из библиотеки TPTP. [17]