4.10. Логическое следование в Прологе

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

Первая и вторая цепочки умозаключений являются корректными, хотя во второй из-за того, что одно из исходных утверждений ошибочно, в результате получилось абсурдное утверждение. Исходные утверждения третьей цепочки правильны, корректным получился и результат, но законы логики были нарушены: нельзя строить дедуктивный вывод от частного к общему. Четвертая цепочка представляет собой классический образец корректного логического вывода, а в пятой содержится ошибка: из того, что Джим смертен, не следует, что Джим человек.

Приведем еще два правила, которые помогут избежать рассмотренных ошибок.

1. Правило "modus ponens". Согласно этому правилу из истинности высказывания "из Р следует Q" (P IMPLIES Q) и из истинности Р выводится истинность Q.

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

Р

следовательно, Q

2. Правило цепочки. Если истинны "из Р следует Q" и "из Q следует R", то можно заключить, что "из Р следует R".

Например, из высказываний "все собаки - животные" и "животные не умеют думать" следует "собаки не умеют думать". Запишем это правило в следующем виде:

из Р следует Q

из Q следует R

следовательно,

из Р следует R

Программа 4.6 иллюстрирует применение только что описанных правил:

Alan man [Алан мужчина]

[верно (Алан человек)]

Пролог-система ответит утвердительно, а на запрос

all (x : х human)

[определить все (х : х человек)]

будут получены ответы "Alan" и "Ann". Если ввести запрос

all (x : х mortal)

[определить все (х : х смертны)]

Пролог-система также выдаст ответы "Alan" и "Ann", полученные с помощью правила цепочки и "modus ponens".

Работа программы 4.6 иллюстрирует возможности Пролога делать "самостоятельные" логические выводы из заданных высказываний. Причем следует отметить, что точный алгоритм вывода не задается. В программе 4.7, построенной с помощью только двух отношений - true и implies,- правило modus ponens задается в явном виде, а применение правила цепочки реализуется встроенными средствами Пролога. Отметим, что правило цепочки можно расширить, например, следующим образом: если из Р следует Q, из Q следует R, из R следует S, а из S следует Т, то из любого из высказываний Р, Q, R и S следует Т.

(Alan is a man) true [(Алан - мужчина) истина]

[определить все (х : х истинно)]

программа 4.7 выведет из высказываний "Alan is a man" и "Ann is a woman", что Алан и Анна - люди. Отметим, что программирование правила modus ponens в другом виде:

X true if Y true and Y implies X

[X истинно, если Y истинно и из Y следует X]

приведет к бесконечным возвратам при попытках вывести новые факты из уже выведенных и через некоторое время система сообщит о нехватке места в памяти. Читатель может в качестве упражнения проверить на практике, что получится при внесении указанных изменений в программу 4.7. Попробуйте также при внесении изменений в данное правило программы 4.7, кроме того, удалить из него условие Y true. Введите после этого запрос all (х : х true). Тогда кроме двух запрограммированных в явном виде фактов (первые две строки программы) будут выданы ответы типа:

X is human

X thinks

и т. д. На запрос "is (David is human) true" будет получен утвердительный ответ. Другими словами, если логический вывод строится на основе аргументов, значения которых не определены, то в этом случае могут быть получены как истинные, так и ложные результаты, и логическая система становится бесполезной.

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

Говоря о программах 4.6 и 4.7, следует обратить внимание на следующие четыре момента.

1. Для достаточно большого числа отношений программа 4.6 может оказаться слишком длинной и не уместиться в памяти ЭВМ.
2. В программе 4.7 использовать отношение implies на самом деле не обязательно. Данное отношение применяется лишь для демонстрации правила цепочки и можно его заменить на условное предложение Пролога if. Однако в ряде случаев следует применять implies вместо if.
3. Всегда следует стремиться к общности для того, чтобы создавать более компактные и более эффективные программы. Например, одно условие "if х is а у" может заменить несколько таких условий, как "if x is a man" и "if x is a women" и т. д.
4. Списковые конструкции позволяют в компактной форме представлять сложные отношения.

При написании программы 4.8 были использованы более эффективные средства программирования, чем в рассмотренных выше двух программах. Заметим, что программа 4.8 строится с помощью отношения true и списковых структур.

(X is a man) true if [(X мужчина) истина, если]

(X is a dog) true [(X собака) истина]

Данная программа может быть использована, например, для проверки какого-либо факта:

is ((Alf is a man) true)

[ДА]

В другом случае ее можно применять для поиска нужного элементарного данного:

one (x: (x is a child) true)

[Дэвид]

Может быть введен запрос в более общей форме:

is ((x is a man) true)

[ДА]

В последнем случае программа подтверждает, что существует х, удовлетворяющее отношению "(х is a man) true". В другом случае на запрос

is ((x is a cat) true)

[верно ((х кошка) истина)]

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

На примере рассмотренной программы можно убедиться з способности Пролога делать логические выводы. Например:

is ((Hellen can reason) true)

[ДА]

В данном случае Пролог-система "рассуждает" следующим образом:

все дети - люди,

следовательно, Элен может рассуждать.

Программа может также сделать следующий вывод:

is ((Alf can learn programming) true

[ДА]

С помощью правила

(X can learn Y) true if (X can reason) true

[(X может научиться Y) истина, если (X может рассуждать) истина]

Пролог система может сделать произвольное число логических выводов типа, рассмотренных выше. Вот еще несколько таких примеров:

is ((Fido can learn programming) true)

и т. д.

Данная программа с точки зрения практического ее применения довольно далека от совершенства, поскольку ее работа основана на мнении, что человек может обучиться чему угодно. Более полезна будет программа, в которой более точно определена способность к обучению в более сложной форме. Для этого в программе 4.8 вместо восьмого предложения добавим следующий фрагмент:

(X is 1) true if [(X 1) истина если]

[(X Z) истина и (Y из-группы Z) истина]

Теперь можно проверить работу данной программы с помощью следующего диалога:

is ((Betty can learn Prolog) true) true)

[ДА]

Вообще изучать на практике логические механизмы Пролога очень полезно для начинающих. Это занятие довольно увлекательно и часто приводит к неожиданным результатам. Кроме того, . такие упражнения способствуют лучшему пониманию логики языка. В качестве такого упражнения можно рекомендовать читателю проанализировать ответы на следующие вопросы:

all (x: х true)

[определить все (х у: (х может | у) истина)]