НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

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

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

  1. Джим человек. Все люди имеют мозг. Следовательно, Джим имеет мозг.
  2. Джим человек. Все люди имеют по 5 ног. Следовательно, у Джима 5 ног.
  3. Джим человек. У Джима есть мозг. Следовательно, все люди имеют мозг.
  4. Все люди смертны. Джим человек. Следовательно, Джим смертен.
  5. Все люди смертны. Джим смертен. Следовательно, Джим человек.

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

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

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

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

Р

из Р следует Q

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

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

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

из Р следует Q

из Q следует R

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

из Р следует R

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

Программа 4.6

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

Anna woman [Анна женщина]

х human if [x человек, если]

(either x man or x woman)

[x мужчина или х женщина]

x mortal if [x смертен, если]

x human [x человек]

В ответ на вопрос

is (Alan human)

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

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

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 следует Т.

Программа 4.7

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

(Ann is a woman) true [(Анна - женщина) истина ]

X true if [x истина, если]

Y implies X and [из Y следует X и]

Y true [Y истина]

(X is a man) implies (X is human)

[из (X - мужчина) следует (X - человек)]

(X is a woman) implies (X is human)

[из (X - женщина) следует (X - человек)]

(X is human) implies (X thinks)

[из (X - человек) следует (X - мыслит)]

(X thinks) implies (X is intelligent)

[из (X - мыслит) следует (X - разумен)]

(X is intelligent) implies (X can learn)

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

(X is intelligent) implies (X can reason)

[из (X - разумен) следует (X может рассуждать)]

В ответ на запрос

all (x : х 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 и списковых структур.

Программа 4.8

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

X ON (Alf Bert Colin) [X из-списка (Альфред Берт Колин)]

(X is a woman) true if [(X женщина) истина, если]

X ON (Anne Betty Clare)

[X из-списка (Анна Бетти Клер)]

(X is a child) true if [(ребенок) истина, если]

X ON (David Helen Jim)

[X из-списка (Дэвид Элен Джим)]

(X is human) true if [(X человек) истина, если]

Y ON (man woman child) and

[Y из-списка (мужчина женщина ребенок) и]

(X is a Y) true [(X являются Y) истина ]

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

X ON (Fido Rover Spot) [X из-списка (Фидо Ровер Спот)]

(X thinks) true if [(X мыслит) истина, если]

(X is human) true [(X человек) истина]

(X can reason) true if [(X может рассуждать) истина, если]

(X thinks) true [(X мыслит) истина]

(X can learn Y) true if [(X может научиться Y) истина, если]

(X can reason) true [(X может рассуждать) истина]

(X can learn tricks) true if

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

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

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

is ((Alf is a man) true)

[верно ((Альфред мужчина) истина)]

YES

[ДА]

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

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

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

David

[Дэвид]

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

is ((x is a man) true)

[верно ((мужчина) истина)]

YES

[ДА]

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

is ((x is a cat) true)

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

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

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

is ((Hellen can reason) true)

[верно ((Элен может рассуждать) истина]

YES

[ДА]

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

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

все люди мыслят,

из "х - мыслит" следует "х может рассуждать";

Элен - дитя,

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

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

is ((Alf can learn programming) true

[верно [(Альфред может обучиться программированию) истина]

YES

[ДА]

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

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

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

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

is ((Fido can learn programming) true)

[верно ((Фидо может обучиться программированию) истина)]

NO

[НЕТ]

all (X: (Fido can learn X) true

[определить все (X : (Фидо может обучиться X) истина)]

tricks

[проделки]

all (x: (x can learn programming) true)

[определить все (х: (х может обучиться программированию истина)]

Аlf

Bert

Colin

и т. д.

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

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

X ON (Alf Anne David)

[из-списка (Альфред Анна Дэвид)]

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

X ON (Bert Betty Helen)

[X из-списка (Берт Бетти Элен)]

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

X ON (Colin Clare Jim)

[X из-списка (Колин Клер Джим)]

(X is 1 subject) true if

X ON (walking talking digging)

[(X из-группы 1) истина, если]

[X из-списка (ходить говорить копать)]

(X is 2 subject) true if

X ON (reading writing arithmetic prolog)

[(X из-группы 2) истина если]

[X из-списка (читать писать арифметика пролог)]

(X is 3 subject) true if

X ON (physics algebra)

[(X из-группы 3) истина, если]

[X из-группы (физика алгебра)]

(Einstein is a genius) true

[(Эйнштейн гений) истина]

(X can learn advanced Y) true if

(X is a genius) true and

(Z can learn Y) true

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

([X гений) истина и (Z может научиться Y) истина]

(X can learn Y) true if

(X is Z) true and

(Y is Z subject) true

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

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

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

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

[верно ((Бетти может обучиться Прологу) истина)]

YES

[ДА]

is ((Betty can learn algebra) true)

[верно ((Бетти может обучиться алгебре) истина]

NO

[НЕТ]

all (x: (Colin can learn x) true)

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

walking [

ходить]

talking

[говорить]

и т. д.

is (Einstein can learn advanced tricks) true

[верно (Эйнштейн может обучиться сложным проделкам) истина]

YES

[ДА]

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

all (x: х true)

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

all (x у: (х у) true)

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

all (x у z: (х у z) true)

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

all (x у: (х саn у) true

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

all (x у: (х саn у) true

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь