Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
часть I Искусственный интеллект.doc
Скачиваний:
5
Добавлен:
01.05.2025
Размер:
6 Мб
Скачать
☆

Лекция 8

3.1.5. Формальные методы вывода решений в аксиоматических теориях.

Под аксиоматической теорией, построенной на основе данной системы аксиом, понимается совокупность всех теорем, доказываемых исходя из этой системы аксиом. Аксиоматическая теория считается определённой, если выполнены следующие

условия:

1.Задан язык теории.

2.Опрелено понятие формулы в этой теории.

3.Выделено некоторое множество формул, называемых аксиомами.

4.Определены правила вывода в этой теории.

Основным вопросом практического использования любой теории является проблема доказательства теорем данной теории или, что одно и тоже, определения принадлежности правильно построенной формулы (ППФ) в этой теории, выражающей доказуемую теорему, системе аксиом теории. В исчислении высказываний эта задача сводится к доказательству того, что ППФ утверждения является доказуемой формулой. Следует отметить, что доказуемая формула, принадлежащая множеству аксиом, является тождественно-истинной формулой. Исходя из этого замечания и определения формулы, доказуемой в данном исчислении можно предложить два способа доказательства доказуемости формулы в исчислении высказываний: семантический и синтаксический. Первый основан на семантике (истинностных значениях) формулы, а второй - на синтаксических преобразованиях аксиом.

Например: доказать что  выводима. Рассмотрим два способа доказательства семантический и синтаксический.

Семантический способ.

Обозначим = и =, тогда исходная формула примет вид: . Составим таблицу истинности для этой формулы.

Таблица 10



1

0

1

0

1

1

0

0

0

0

0

1

0

0

0

1

1

1

1

1

Таким образом, при всех комбинациях значений переменных формула принимает только значение истина, следовательно, эта формула является тождественно-истинной и доказуемой в исчислении высказываний.

Синтаксический способ.

Возьмём аксиому 3 II-ой группы исчисления высказываний и заменим  на , а  на  получим:  также выводимую формулу. Выполним подстановку 



получим:



Обозначим: ; ;

 - докажем что эти формулы доказуемы. Выполним подстановку 

 1 акс.IV гр

получим:    заметим, что условием этой импликации является 1-ая аксиома III-ей группы и по правилу заключения формула доказуема. Заменим в формуле на , а на получим, что формула также доказуема. Применяя правило заключения к доказуемой формуле  и помня что доказуема, получим, что также доказуема. Применяя правило заключения к формуле и исходя из доказуемости , получим доказуемость исходной формулы. В этом примере синтаксический способ доказательства требует некоторых навыков в использовании правил вывода и аксиом, а также кажется более трудоёмким и сложным чем семантический, хотя на самом деле всё определяется данным примером. Рассмотрим другой пример.

По подозрению в совершённом преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом ложь.

Браун: “ Я совершил это. Джон не виноват.”

Джон: “ Браун не виноват. Преступление совершил Смит”.

Смит: “Я не виноват, виновен Браун”.

Определите имя старика, мошенника и чиновника и кто из них виноват, если известно что преступник один.

Семантический способ решения.

Обозначим высказывания: Б - виноват Браун, Д - виноват Джон, С - виноват Смит. Тогда утверждения, высказанные задержанными примут вид:

1. БД; 2. БС; 3. БС и истинной должна быть общая дизъюнкция всех утверждений: А=(БД) (БС) ( БС).

Составим таблицу истинности для всех вариантов высказываний, утверждений и общей дизъюнкции.

Таблица 11

номер вариа-нта

Б

Д

С

БД

БС

БС

А

1

2

3

4

5

6

7

8

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

1

0

1

0

0

1

0

1

0

0

0

0

0

1

1

1

1

0

1

0

Проведём анализ вариантов, когда А-истинно.

Варианты: 2,3 и 5 отпадают, т.к. в этих случаях существует одновременно два преступника, а это противоречит условию задачи (“преступник один”).

Вариант 4 также отпадает, т.к. в этом случае два утверждения, высказанные задержанными одновременно истинны, а это противоречит условию (“правду говорит только один старик”).

Отсюда следует, что верным остаётся 7-ой вариант, соответствующий всем условиям задачи и следовательно преступник Смит. В этом варианте 2-ое утверждение, высказанное задержанным Джоном является истинным, следовательно Джон-старик(“старик говорил правду”) и остаётся утверждать, что чиновник-Браун.

Синтаксический способ.

Рассмотрим данную задачу как теорию предметной области, которой соответствует набор аксиом и в которой верны правила вывода. В качестве аксиом теории выберем утверждения, высказанные задержанными:

1. БД;

2. БС;

3. БС.

По условиям задачи только одно утверждение является истинным (“правду говорил старик”) и, следовательно, только один из вариантов утверждений является аксиомой теории. Рассмотрим предположение, что первое утверждение является аксиомой, тогда третье утверждение тоже правда, т.к. преступник был один, если предположить, что третье утверждение – аксиома, то по этой же причине первое утверждение тоже правда, а это противоречит условиям задачи (“правду говорил только один”). Следовательно, единственно верной аксиомой этой теории является второе утверждение, которое высказал Джон, о том, что Браун не виноват, а преступление совершил Смит. Таким образом, получаем следующее решение задачи: Джон-старик, Смит-преступник, Браун-чиновник. В данном примере синтаксический способ решения задачи кажется более простым и лёгким, таким образом, как уже отмечалось выше, трудоёмкость способа определяется задачей.

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

Синтаксический способ для исчисления предикатов.

Пример: Доказать, что формула xxx xxx является общезначимой.

Используя равносильности алгебры высказываний и алгебры

предикатов проведём следующие преобразования этой формулы:

xxxxxxxx xxxxxxx xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxxxxxxxxxx

истина истина истина. Исходная формула общезначима.

Таким образом, для теорий, построенных как на исчислении высказываний, так и на исчислении предикатов существует принципиальная возможность доказательства теорем вычислительным способом.

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

В 1936г. американский математик А.Черч доказал, что проблема разрешимости алгебры предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить к какому классу формул относится любая формула алгебры предикатов. В этом смысле говорят о неразрешимости исчисления предикатов. Вместе с тем доказано (Эрбран, 1930г.), что исчисление предикатов первого порядка полуразрешимо, т.е. доказано существование процедуры подтверждения выводимости некоторой ППФ из заданногомножества формул 1n, если известно, что эта ППФ является теоремой. Основной процедурой, позволяющей реализовать эту полуразрешимость, является правило резолюции Дж. Робинсона (1965 г.), имеющее различные модификации.

Теории первого порядка отличаются от теорий высших порядков тем, что не допускают в своём изложении предикаты, которые имеют в качестве возможных значений своих аргументов другие предикаты и функции. Кроме того, они не допускают кванторные операции по предикатам или функциям. Процесс доказательства теоремы некоторой теории или общезначимости ППФ для данной ситемы аксиом с использованием правила резолюций основан на опровержении отрицания этой ППФ. В этом случае к системе аксиом теории добавляется отрицание доказуемой ППФ и с помощью правила резолюций доказывается противоречивость новой системы аксиом. Такая схема построения доказательства теоремы называется процедурой опровержения. Ещё одним ограничением правила резолюций является то, что этот метод применим к аксиомам теории и доказуемой теореме только тогда, когда выражающие их формулы записаны в виде дизъюнкт (фраз, предложений) Хорна. Дизъюнкта Хорна это формула, состоящая из дизъюнкций одной позитивной и остальных негативных элементарных формул, т.е формула вида: 12n Аксиомы теории, выраженные в виде дизъюнкт Хорна имеют вполне объяснимую интерпретацию.

Преобразуем общую форму дизъюнкта Хорна на основании закона равносильности к виду 12n, получим импликацию, в виде которой обычно записывают закон предметной области. Здесь из истинности посылок и самой импликации (формула является аксиомой теории) следует истинность заключения (обратное неверно: из ложности посылок не следует ложность заключения). Набор законов или система аксиом теории образуется путём объединения знаком конъюнкция  отдельных законов или аксиом теории. Однако, можно показать, что любую ППФ исчисления предикатов можно по определённой методике привести к дизъюнктам Хорна, объединённых знаком конъюнкции.