<<
>>

ЛОГИКА ПРЕДИКАТОВ

Предикат Р(х17 х2, ..., хп) — это логическая функция п переменных, которая в зависимости от значений переменных х х2, ..., хп принимает два значения: истина (Т) или ложь (В).
Обычно такого рода предикат называют га-местным. ПредикатР(ах, а2, ..., ап), имеющий истинное значение и полученный при подстановке или конкретизации хх = ах, х2 = а2, ..., хп = ап, где а1 — объекты или константы, называется фактом. Приведем примеры предикатов с различным числом аргументов.

1. Предикат нульместный или простое высказывание:

А — выключатель включен;

В — вилка исправна.

2. Предикат одноместный:

положителъный(х) — число х > 0; большой(у) — животное у большое.

Предикаты становятся фактами при подстановке х = 8 и у — медведь, т. е.

положительный(8) = Т; большой(медведь) = Т.

3. Предикат двухместный, выражающий отношение:

больше(х1, у у) — число х1 больше, чем ух; любит(х2, у2) — животное х2 любит пищу у2.

Первый предикат приобретает значение «истина» и является фактом при х1 = 2, у1 = 1. Второй предикат может стать фактом при такой подстановке: х2 = овца, у2 = трава. Полученные факты имеют вид:

болъше(2у 1); любит{овца, трава).

Ложными предикаты болъше(х у{), любит(х2, у2) будут соответственно при хг = 2,у1 = Зих2 = заяц, у2 = мясо.

4. Предикат трехместный:

сумма(х, у, г) — г является суммой х и у.

Очевидно, что при х = 2,у = 3, 2 = 5 значение этого предиката истинное, получаем факт сумма(2, 3, 5), а при х = 5, у = 7, 2 = 3 — ложное.

Для предикатов справедливы все ранее рассмотренные логические операции и законы логики.

Для работы с предикатами в 1972 г. шотландским ученым Р. Ковальским был предложен язык логического

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

Благодаря правилам и переменным система логического вывода позволяет выводить такие знания, которые в явном виде в базе знаний отсутствуют.

Совокупность фактов и правил образует базу знаний (БЗ). БЗ может быть использована для решения задачи поиска знаний с привлечением целевого утверждения — предиката цели. БЗ вместе с предикатом цели называется логической программой. БЗ в системе логического программирования делится на две части: описание фактов и описание логических правил. Как это делается, разберем на небольшом примере семьи.

Представим информацию о семье:

Нина мать Андрея,

Олег отец Андрея,

Андрей сын Нины,

Андрей сын Олега,

Петр отец Нины

в виде совокупности фактов — двухместных предикатов:

матъ(Нина, Андрей). отец(Олег, Андрей).

сын(Андрей, Нина). (4.1.1)

сын(Андрей, Олег). отец(Петр, Нина).

Кроме того, можно получить новое знание о деде сначала в виде высказывания

если Петр отец Нины И Нина мать Андрея, то Петр дед Андрея,

а затем в виде логического правила с двухместными предикатами

если отец(Петр, Нина) И мать(Нина, Андрей), то дед(Петр, Андрей).

Предложение справедливо для любых имен людей, имеющих такие семейные связи, если заменить переменными х имя Петр, у имя Нина, г имя Андрей и переписать его как

если отец(х, у) И мать(у, г), то дед(х, г). (4.1.2)

Правило (4.1.2) может быть также записано в эквивалентной форме

дед(х, г) если мать(у, г) И отец(х, у)

или в форме правила на языке Пролог

дед(х, г):- матъ(у, г), отец(х, у). (4.1.3)

Запятая между предикатами (,) выполняет логическую операцию конъюнкции.

Предикат дед(х, г), находящийся слева от знака «:-», называется головой правила, а предикаты матъ(у, г), отец(х, у), находящиеся справа от этого знака, — телом правила. Соединяя факты (4.1.1) и правило (4.1.3), получим БЗ на Прологе:

мать(Нина, Андрей). отец(Олег, Андрей). сын(Андрей, Нина). сын(Андрей, Олег). отец(Петр, Нина). дед(х, г):- мать(у, г), отец(х, у).

К БЗ можно сделать два типа запросов: на подтверждение цели и на определение значения переменной. Один из запросов на подтверждение цели можно сформулировать так: «является ли Андрей сыном Нины? » и записать в виде предиката цели:

? сын(Андрей, Нина).

Ответом будет «да».

Начиная с первого, каждый предикат-факт БЗ сопоставляется с предикатом цели сын(Андрей, Нина). Два предиката-факта или предикат-факт и предикат-цель сопоставимы, т. е. соответствуют друг другу, если выполняются 3 условия:

1) имена предикатов одинаковы (побуквенное совпадение);

2) предикаты имеют равное количество аргументов;

3) аргументы, расположенные на одних и тех же позициях, сопоставимы.

Сопоставление аргументов осуществляется по следующим правилам:

■ аргументы-константы (буквы, слова, цифры и знаки)

сопоставимы, если они совпадают;

■ переменная сопоставима с константой (тогда переменная получает значение константы).

При сопоставлении цели сын(Андрей, Нина) с каждым фактом БЗ полное совпадение (по имени предиката и константам) с третьим фактом сын(Андрей, Нина) выражается словом «да».

Рассмотрим запросы второго типа.

Пусть требуется найти имя отца Андрея. Тогда целью будет предикат

? отец(х;, Андрей).

Последовательное сопоставление цели отец(х, Андрей) с фактами БЗ становится успешным для второго факта отец{Олег, Андрей), в результате переменная х получит значение Олег.

Ответом будет х = Олег.

Теперь определим имя деда Андрея. Предикатом цели будет

? дед(х, Андрей).

Сопоставление цели дед(х, Андрей) с фактами будет успешным для головы правила дед(х, г). Тогда переменная z получит значение Андрей, предикат мать(у, z) после подстановки z = Андрей будет иметь вид матъ(у, Андрей), а исходная цель распадется на две цели мать(у, Андрей) и отец(х, у), которые должны быть подтверждены фактами БЗ. Первая цель мать(у, Андрей) сопоставима с фактом мать(Нина, Андрей), в результате чего у получает значение Нина, а второй целью отец(х, у) после подстановки у = Нина становится отец(х, Нина).

Цель отец(х, Нина) сопоставима с пятым фактом отец(Петр, Нина). Переменная х получает значение Петр. Итак, все цели подтверждены.

Ответом будет х = Петр.

Рассмотрим примеры составления запросов, использующих логическую операцию отрицания not и предикат вывода write(x) переменной х.

П4.1.8. На примере логической программы, представленной БЗ о родственниках:

сын(Олег, Петр). сын(Петр, Анна). сын(Олег, Вера). сын(Виктор, Ольга). сын(Николай, Сергей). сын(Виктор, Николай). женщина(Анна). женщина(Вера). женщина(Ольга).

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

Решение. В предикате БЗ сын(х, у) вторым аргументом у является либо имя отца (Петр, Сергей, Николай), либо имя матери (Анна, Вера, Ольга). Поэтому в запросе, помимо подцели сын(х, у), следует использовать предикат not женщина(у), истинный, если у — имя мужчины, и предикат вывода write(y). Таким образом, запрос, выводящий имена отцов, будет иметь вид

сын(х, у), not женщина(у), write(y).

Запрос, выводящий имена матерей, запишется так: сьш(х, у), женщина(у), write(y).

Для получения имен дедушек воспользуемся следующими соображениями. Из предиката сын(х, у) следует, что у — имя отца, если у является мужчиной, т. е. становится истинным предикат not женщина(у). В нашем случае х = Виктор, у = Николай. Далее, если у является сыном г (сын(у, г)) и г — мужчина (not женщина(2)), то 2 является дедом х. В базе данных 2 = Сергей, следовательно Сергей является дедом Виктора. Итак, запрос к БЗ, позволяющий выводить имена дедушек, содержит следующие предикаты совместно с предикатом вывода write:

сын(х, у), not женщина(у),

сын(у, 2), not женщина(2), write(2).

Запрос для получения имен бабушек отличается от предыдущего тем, что предикат not женщина(г) заменяется на предикат женщина(2). В результате получаем

сын(х, у), not женщина(у), сын(у, 2), женщина(г), write(2).

И наконец, из комбинации подцелей сын(х, у), not женщина(у), сын(у> г) можно получить имя внука х, если х является мужчиной, т. е. истинен предикат not жен- щина(х). Таким образом, получим запросы, позволяющие вывести имена внуков:

сын(х, у), not женщина(у),

сын(у, 2), not женщина(х), write(x).

Правила, выполняющие перечисленные выше задачи поиска информации, в голове правила содержат искомые предикаты, а в теле правила — соответствующие выражения запросов без или с предикатом вывода write. Так, правило, предназначенное для определения имен у отцов (отец(у, х)) запишется в виде

отец(у, х):- сын(х, у), not женщина(у).

Аналогичным путем запишутся правила для определения имен матерей:

матъ(у, jc):— сын(х, у), женщина(у).

дедушек:

дедушка(г, х):- сьш(х, i/), not женщина(у), сын(у, 2), noi женщина(г).

бабушек:

бабушка(г, х):- сын(х, ¿/),

rcof женщина(у), сын(у, г), женщина(г).

и внуков:

внук(х, г):- сьш(х, г/), nof женщина(у), сын(у, 2), not женщина(х).

ЗАДАЧИ

ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ № 2

С4.2.1. Используя двухместные предикаты сестра(*,•), лшть(ж,ж) или от.ег4(#,*), составьте правило с переменными х, г/, 2, определяющее двухместный предикат ття(*,*).

С4.2.2. Используя двухместные предикаты брат(ж,ж), лгаягг>(ж,ж) или отец(ж,ж), составьте правило с переменными х, г/, 2, определяющее двухместный предикат длдя(ж,ж).

С4.2.3. Используя двухместные предикаты жено(*,*) или мать(*,*)7 мать(♦,•) или лгг/ж*(*,ж), составьте правило с переменными х, у, 2, определяющее двухместный предикат свекровъ{* ,•).

С4.2.4. Используя двухместные предикаты отец(*,•) или муж(*,•), дг

<< | >>
Источник: Ю. И. КУДИНОВ, Ф.Ф. ПАЩЕНКО, А. Ю. КЕЛИНА. ПРАКТИКУМ ПО ОСНОВАМ СОВРЕМЕННОЙ ИНФОРМАТИКИ. 2011

Еще по теме ЛОГИКА ПРЕДИКАТОВ:

  1. Позиции-предикаты
  2. Позиции-предикаты
  3. Логики
  4. ESTJ и ENTJ Экстраверты-логики
  5. ГЛАВА 1 Логика трансформации
  6. Логики и этики
  7. Марсианская и венерианская логика
  8. ЛОГИКА «5». ХАРАКТЕРИСТИКИ
  9. ISTP и INTP Интроверты-логики
  10. ЛОГИКА «55». ХАРАКТЕРИСТИКИ
  11. Развитие логики
  12. Шутка логика
  13. (T) Логика — Этика (F)
  14. Хаос вопросов со строгой логикой построения