1. Знания и их представления
Данные отдельные факты, характеризующие объекты, процессы, явления и их свойства.
Знания основаны на данных, но представляют собой результат мыслительной деятельности человека, обобщают его опыт и получаются в результате практической деятельности человека. В отличие от данных знания имеют более сложную структуру и хранятся в специальном виде (в виде базы знаний). С помощью БД можно получить информацию о конкретном предмете, процессе или ситуации, причем лишь ту, которая была ранее туда помещена. При работе компьютерных программ данные выступают в роли объекта обработки, они пассивны. Программа находит их, изменяет и снова записывает в определенное место памяти. БЗ отличаются от БД наличием встроенных механизмов логического вывода. Благодаря этому знания ведут себя активно. Встроенные процедуры позволяют не только делать иными имеющиеся знания, но и получать из них новые.
Знания можно разделить на процедурные и декларативные. Процедурные знания описывают последовательность действий – это алгоритмы, программы. Все остальные знания считаются декларативными.
При обработке знаний они трансформируются следующим образом:

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

Для ПЗ разработан ряд формализмов. Наибольшей выразительностью обладает исчисление предикатов первого порядка.
Вычислительный формализм состоит из двух частей:

• Дескриптивный язык
• Множество процедур, способных реализовывать формальный смысл описаний, составленных на дескриптивном языке.

Конечной целью ПЗ является создание программы, поведение которой будет отражать структуру системы в определенном аспекте. Пролог служит примером такого формализма.
Существует несколько методов представления знаний в ИС:

• Логическая модель представления знаний;
• Модели на основе нечетной логики;
• Представление знаний с помощью продукционных правил;
• Представление знаний с помощью фреймов;
• Представление знаний с помощью сетевой модели (семантическая сеть).

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

2. Логические модели

В рамках логической модели знания представляются в системе логики предикатов первого порядка.
Примеры логических моделей представления фактов (в данном случае: "Петров посещает лекции" и "Петров – студент"), носящих название атомарной формулы, с помощью предикатов:
ПОСЕЩЕНИЕ (Петров, лекции)
СТУДЕНТ (Петров)
Примеры являются правильно построенными логическими формулами, включающими кванторы существования $ и общности ".
($х)     [ДЕЛЬФИН(х)   Ú  УМНЫЙ(х)]
("x)    [СЛОН(х)   ®  ЦВЕТ(х, Серый)]
Эти формулы могут быть интерпретированы так: "некий дельфин наделен умственными способностями" и "все слоны имеют серую окраску".
Логический вывод осуществляется с помощью силлогизма (если из А следует В, а из В следует С, то из А следует С).
Достоинствами логической модели представления знаний являются единственность теоретического обоснования и возможность реализации системы формально точных определений и выводов.
Однако при решении сложных задач попытка представить неформализованные знания эксперта, среди которых преобладают эвристики, в системе строгой логики наталкивается на серьезные препятствия. Это связано с тем, что в отличие от строгой логики, так называемая, "человеческая логика" обладает нечеткой структурой. Поэтому большая часть достижений в области систем с базами знаний до настоящего момента была связана с применением нелогических моделей.

3. Продукционные модели

В продукционной модели (модели правил) знания представлены совокупностью правил вида "ЕСЛИ-ТО". Системы с базами знаний, основанные на этой модели, называются продукционными системами.
Продукционные системы бывают двух диаметрально противоположных типов – с прямыми и обратными выводами. Типичными представителями первого типа являются системы, используемые для решения задач диагностического характера, а типичными представителями систем второго типа – системы, используемые для решения задач проектирования.
Системы продукций с прямыми выводами среди систем, основанных на использовании знаний, имеют наиболее давнюю историю, поэтому они являются в некотором смысле основополагающими. Эти системы включают три компонента: базу правил, состоящую из набора правил вывода, базу данных, содержащую множество фактов, и интерпретатор для получения логического вывода на основании этих знаний. База правил и база данных образуют базу знаний, а интерпретатор соответствует механизму логического вывода. Вывод выполняется в виде цикла "понимание –  выполнение", причем в каждом цикле выполняемая часть выбранного правила обновляет базу данных. В результате содержимое базы данных преобразуется от первоначального к целевому, т.е. целевая система синтезируется в базе данных.
Пример. Пусть данные, хранящиеся в базе данных, представляют собой образцы в виде наборов символов, например, "намерение – отдых", "место отдыха – горы" и т.п. Правила, накапливаемые в базе правил, содержат в условной части либо одиночные образцы, либо несколько условий, соединенных союзом "и", а в заключительной части – образцы, дополнительно помещаемые в базу данных. Рассмотрим два примера подобных правил:
Правило 1.
ЕСЛИ             "намерение – отдых" и
"дорога ухабистая"
ТО       "использовать джип"
Правило 2.
ЕСЛИ             "место отдыха – горы"
ТО       "дорога ухабистая"
После того как в базу данных заносятся образцы "намерение – отдых" и "место отдыха – горы", рассматривается возможность применения этих правил. Сначала механизм вывода сопоставляет образцы из условной части правила с образцами, хранящимися в базе данных. Если все образцы имеются в базе данных, то условная часть считается истинной, в противном случае – ложной. В данном примере образец "намерение – отдых" существует в базе данных, а образец "дорога ухабистая" отсутствует, поэтому условная часть правила 1 считается ложной. Что касается правила 2, то его условная часть истинна. Поскольку в данном случае существует только одно правило с истинной условной частью, то механизм вывода сразу же выполняет его заключительную часть и образец "дорога ухабистая" заносится в базу данных. При попытке вторично применить эти правила получается, что можно применить лишь правило 1, поскольку правило 2 уже было применено и выбыло из числа кандидатов. К этому времени содержимое рабочей памяти было дополнено новым образцом – результатом применения правила 2, поэтому условная часть правила 1 становится истинной, и содержимое базы данных пополняется образцом его заключительной части – "использовать джип".
В системе продукций с обратными выводами механизм логического вывода основан на ином принципе. Поясним этот принцип на том же примере. Допустим, что цель – это "использовать джип", и исследуем сначала возможность применения правила, подтверждающего этот факт. Поскольку образец "намерение – отдых" из условной части правила 1 уже занесен в базу данных, то для достижения цели достаточно подтвердить факт "дорога ухабистая". Однако если принять образец "дорога ухабистая" за новую цель, то потребуется правило, подтверждающее этот факт. Поэтому исследуем возможность применения правила 2. Условная часть этого правила в данный момент является истинной, по­этому правило 2 можно сразу же применять. При этом база данных пополнится образцом "дорога ухабистая", и в результате возможности применения правила 1 подтверждается цель "использовать джип".
Итак, упорядочим сильные и слабые стороны хорошо известных систем продукций. Сильные стороны:
-        простота создания и понимания отдельных правил;
-        простота пополнения и модификации;
-        простота механизма логического вывода.
Слабые стороны:
-        неясность взаимных отношений правил;
-        сложность оценки целостного образа знаний;
-        крайне низкая эффективность обработки;
-        отличие от человеческой структуры знаний;
-        отсутствие гибкости в логическом выводе.

4. Сетевые модели

Семантической сетью называется структура данных, имеющая определенный смысл как сеть. Стандартного определения семантической сети не существует, но обычно под ней подразумевают систему знаний, имеющую определенный смысл в виде целостного образа сети, узлы которой соответствуют понятиям и объектам, а дуги – отношениям между объектами. Следовательно, всевозможные сети можно рассматривать как сети, входящие в состав семантической сети.
Например, если "Петров" и "студент" являются узлами сети, то, установив между этими узлами связь "есть", получим смысловое предложение "Петров есть студент". Аналогичное предложение можно получить, если глагольную связку "есть" принять за отдельный узел и установить связь, имеющую грамматический смысл, из другого узла к этим трем узлам.
Например, текст «В поле, засеянном рожью, растет высокая сосна. Под ней лежит покрытый мхом валун» - будет выглядеть так:

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

5. Фреймовые модели

Фреймовая модель, или модель представления знаний, основанная на фреймовой теории, представляет собой систематизированную психологическую модель памяти человека и его сознания. Важным моментом в этой теории является понимание фрейма – структуры данных для представления некоторого концептуального объекта. В общем случае фрейм можно представить в виде следующей структуры.
(Имя фрейма:
Имя слота 1 (значение слота 1);
. . . . . . .
Имя слота 2 (значение слота 2);
Имя слота N (значение слота N)).
Значением слота может быть практически что угодно: числа, формулы, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов. В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет реализовывать во фреймовых представлениях иерархический принцип.
Например, фрейм служащего может выглядеть следующим образом:
(Служащий:
Фамилия (Иванов);
Год рождения (1974);
Специальность (Программист);
Стаж (3)).
Все фреймы взаимосвязаны и образуют единую фреймовую систему, в которой органически объединены декларативные и процедурные знания. Поскольку концептуальному представлению свойственна иерархичность, целостный образ знаний строится в виде одной фреймовой системы, имеющей иерархическую структуру.
Язык представления знаний, основанных на фреймовой модели, особенно эффективен для структурного описания сложных понятий и решения задач, в которых в соответствии с ситуацией желательно применять различные способы вывода. В то же время на таком языке затрудняется управление завершенностью и постоянством целостного образа. В частности, по этой причине существует большая опасность нарушения присоединенной процедуры.
Фрейм с неопределенными слотами называется прототипом. Когда слоты получают некоторое значение, образуется экземпляр фрейма. При исключении любого слота фрейм теряет полноту, а иногда и смысл.

6. Понятие формальной системы

Формальная теория — это понятие, разработанное в рамках формальной логики в качестве основы для формализации теории доказательства.
Формальная теория — это:

• множество символов, образующих алфавит;
• множество слов в алфавите, которые называются формулами;
• подмножество формул, которые называются аксиомами;
• множество отношений на множестве формул, которые называются правилами вывода.

Множество символов может быть конечным или бесконечным. Обычно для образования символов используют конечное множество букв, к которым при необходимости, приписываются в качестве индексов целые числа или выражения.
Множество формул обычно задаётся индуктивным определением, например, с помощью формальной грамматики. Как правило, это множество бесконечно. Множества и в совокупности определяют язык или сигнатуру формальной теории.
Множество аксиом может быть конечным или бесконечным. Если множество аксиом бесконечно, то, как правило, оно задаётся с помощью конечного числа схем аксиом и правил порождения конкретных аксиом из схемы аксиом. Обычно аксиомы делятся на два вида: логические аксиомы (общие для целого класса формальных теорий) и нелогические или собственные аксиомы (определяющие специфику и содержание конкретной теории).
Множество правил вывода, как правило, конечно.
В логике, формализованный язык совместно с дедуктивным аппаратом, с помощью которого из одних правильно построенных формул могут быть получены другие. Любая формальная система располагает формализованным языком, состоящим из примитивных символов, которые объединяются в соответствии с определенными правилами построения (положениями о допустимых в системе выражениях), а также набором теорем, выведенных из ряда аксиом. В аксиоматических системах примитивные символы выбираются произвольно, а все остальные символы определяются на основе примитивных. Например, в евклидовой геометрии такие понятия, как «точка», «прямая» и «лежать на» обычно рассматриваются как примитивные термины. Из примитивных символов составляются правильно построенные формулы, некоторые из которых попадают в перечень аксиом; а также устанавливаются правила вывода одной формулы (вывода) из другой или других формул (посылок). В рамках формальной системы теоремой называется формула, которую возможно доказать посредством конечной последовательности правильно построенных формул, каждая из которых либо является аксиомой, либо обоснованно выведена из ранее доказанных формул.

Исчисление высказываний — это формальная теория, в которой осуществляется попытка формализации понятий логического закона и логического следования.
Высказывание — это повествовательное предложение, которое истинно или ложно. В исчислении высказываний значимым является лишь истинностное значение высказывания («истина» — 1, «ложь» — 0), поэтому используемые в дальнейшем высказывательные (пропозициональные) переменные могут принимать одно из этих значений.
Логические связки
Кроме высказывательных переменных, в исчислении высказываний используются так называемые логические связки. Если p — высказывание, то через  будем обозначать отрицание этого высказывания.
Значение двуместных логических связок → (импликация), v (дизъюнкция) и ^ (конъюнкция) определяются так:                                       
0 0          1          0          0
0 1          1          0          1
1 0          0          0          1
1 1          1          1          1
Формулы исчисления высказываний

• Атомарные формулы (состоящие из одной высказывательной переменной) являются формулами исчисления высказываний.
• Если  — формулы исчисления высказываний, то ,  и  — формулы исчисления высказываний.
• Если p — формула исчисления высказываний, то  — формула исчисления высказываний.

Тождественно истинные формулы (тавтологии)
Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных.
Правило вывода
Под рассуждением будем понимать вывод, позволяющий из некоторых предложений, называемых посылками, сделать заключение. Рассуждение состоим из последовательности посылок, т.е. высказываний об известных свойствах объекта, на основании которых делается заключение о некоторых новых свойствах объекта.
Рассуждение считается правильным, если из истинных посылок не может быть получено ложное заключение. Рассуждение, соответствующее ТИ формулам, является правильным. Каждая ТИ формула может быть объявлена законом логики или правилом вывода.

Исчисление предикатов первого порядка и теории первого порядка отличаются тем, что в них допускается применение кванторов только лишь к переменным. Однако установлено, что большинство теорий более высоких порядков сводимо к теориям первого порядка. Каждая теория первого порядка располагает системой аксиом, включающей логические (общие) и собственные (частные) аксиомы. Исчисление предикатов первого порядка - это теория первого порядка, не имеющая собственных аксиом. Дополнение исчисления предикатов аксиомами, присущими некоторой предметной области, превращает его в частную теорию первого порядка, относящуюся к этой области.
Исчисление предикатов первого порядка является определенным расширением исчисления высказываний, поэтому на основе каждого исчисления высказываний может быть построено соответствующее ему исчисление предикатов.
В логике высказываний любые высказывания рассматриваются как единое неделимое целое и не важна их структура.
Язык теорий первого порядка богаче языка исчисления высказываний благодаря использованию (нелогических) предметных переменных, что влечет за собой необходимость рассмотрения логических и нелогических функций от нелогических переменных (наряду с логическими переменными и логическими связками исчисления высказываний). Множество символов теорий первого порядка включает подмножества:
 - символов предметных констант;
 - функциональных символов (функторов);
 - предикатных символов (предикатов);
 - символов предметных переменных;
 - логических символов;
 - вспомогательных символов.
Правилами вывода в теориях первого порядка являются следующие два основных правила: modus ponens (правило заключения), по которому из формул A и (A ->B)выводится формула B; правило обобщения (связывания квантором общности), по которому из формулы A выводится формула  . Наряду с названными основными правилами вывода, как обычно, используются и другие правила, в качестве которых выступают многие выведенные в исчислении предикатов теоремы.
Логика первого порядка как формальная модель рассуждений
Являясь формализованным аналогом обычной логики, логика первого порядка дает возможность строго рассуждать об истинности и ложности утверждений и об их взаимосвязи, в частности, о логическом следовании одного утверждения из другого, или, например, об их эквивалентности. Рассмотрим классический пример формализации утверждений естественного языка в логике первого порядка.
Возьмем рассуждение «Каждый человек смертен. Конфуций — человек. Следовательно, Конфуций смертен». Обозначим «x есть человек» через ЧЕЛОВЕК(x) и «x смертен» через СМЕРТЕН(x). Тогда утверждение «каждый человек смертен» может быть представлено формулой: (∀x)(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) утверждение «Конфуций — человек» формулой ЧЕЛОВЕК(Конфуций), и «Конфуций смертен» формулой СМЕРТЕН(Конфуций). Утверждение в целом теперь может быть записано формулой
(∀x)(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) ∧ ЧЕЛОВЕК(Конфуций) → СМЕРТЕН(Конфуций)

9. Правила вывода логики предикатов

Правилами вывода в теориях первого порядка являются следующие два основных правила: modus ponens (правило заключения), по которому из формул A и (A ->B)выводится формула B; правило обобщения (связывания квантором общности), по которому из формулы A выводится формула  . Наряду с названными основными правилами вывода, как обычно, используются и другие правила, в качестве которых выступают многие выведенные в исчислении предикатов теоремы.
Рассуждение следует признать правильным, если существует последовательность формул, каждая из которых является посылкой или получается из предыдущих формул по правилу вывода. Последняя формула есть заключение.
Вводится новое правило вывода, называемое введение единичного:

10. Доказательство методом резолюции

Доказательство теорем сводится к доказательству того, что некоторая формула G (гипотеза теоремы), является логическим следствием множества формул F1,...,Fk (допущений). Т.е. сам текст теоремы может быть сформулирован следующим образом "если F1,...,Fk истинны, то истинна и G". Такой метод доказательства теорем называется методом резолюций.
Правило резолюции. Из дизъюнктов (X v F) и (¬X v G) выводим дизъюнкт (F v G). Или другими словами, дизъюнкт (F v G) является логическим следствием дизъюнктов (X v F) и (¬X v G).
Метод резолюций. Для доказательства того, что формула G является логическим следствием множества формул F1,...,Fk метод резолюций применяется следующим образом. Сначала составляется множество формул {F1,...,Fk, ¬G}. Затем каждая из этих формул приводится к конъюнктивной нормальной форме (конъюнкция дизъюнктов) и в полученных формулах зачеркиваются знаки конъюнкции. Получается множество дизъюнктов S. И, наконец, ищется вывод пустого дизъюнкта из S. Если пустой дизъюнкт выводим из S, то формула G является логическим следствием формул F1,...,Fk. Если из S нельзя вывести #, то G не является логическим следствием формул F1,...,Fk.
Рассмотрим пример доказательства методом резолюций. Пусть у нас есть следующие утверждения:
"Яблоко красное и ароматное."
"Если яблоко красное, то яблоко вкусное."
Докажем утверждение, что "яблоко вкусное".
Введем множество формул, описывающих простые высказывания, соответствующие вышеприведенным утверждениям. Пусть:
X1 — "Яблоко красное."
X2 — "Яблоко ароматное."
X3 — "Яблоко вкусное."
Тогда сами утверждения можно зависать в виде сложных формул.
X1 & X2 — "Яблоко красное и ароматное."
X1 —> X3 — "Если яблоко красное, то яблоко вкусное."
Тогда утверждение, которое надо доказать выражается формулой X3.
Итак, докажем, что X3 является логическим следствием (X1 & X2) и (X1 —> X3). Сначала составляем множество формул с отрицанием доказываемого высказывания; получаем:
{(X1 & X2), (X1 —> X3), ¬X3}.
Теперь приводим все формулы к конъюнктивной нормальной форме и зачеркиваем конъюнкции. Получаем следующее множество дизъюнктов:
{X1, X2, (¬X1 v X3), ¬X3}.
Ищем вывод пустого дизъюнкта (в этом выводе третий и последний элементы получены по правилу резолюции, остальные являются элементами исходного множества дизъюнктов):
X1, (¬X1 v X3), X3, ¬X3, #.
Получили пустой дизъюнкт, значит утверждение о том, что яблоко вкусное верно.
Метод резолюций применим и к логике предикатов первого порядка (далее просто логика первого порядка). Однако, чтобы сделать метод рабочим, требуется внести ряд изменений и дополнений в версию для логики высказываний.

11. Логическое программирование

Исторически сложилось так, что термином "логическое программирование" обозначают использование в качестве языка программирования некоторого подмножества чистой логики первого порядка. Это означает, что для выражения концепции действия применяется математическое понятие отношения или предиката.
Часто встречается еще более узкое толкование понятия логического программирования, когда язык ограничивается применением хорновских предложений, а механизм вывода - определенным вариантом метода резолюций. На этих принципах создан Пролог и сходные с ним языки программирования. В основе этих языков лежит возможность интерпретировать одно и то же выражение, как логическое утверждение
A, если B1 и B2 и ... Bn
и как определение процедуры
чтобы выполнить A
выполнить B1;
выполнить B2;
...
выполнить Bn.
Но такое узкое понятие следует признать слишком ограничительным. Многие языки программирования заслуживающие названия "логических" не вписываются в эту схему. С другой стороны, тот же Пролог содержит элементы логики второго порядка.
Тем не менее, Пролог остается наиболее распространенным языком логического программирования. На примере Пролога можно рассмотреть специфические свойства логических программ, которые делают логическое программирование хорошо подходящим для некоторых применений, таких как дедуктивные базы данных, синтаксический анализ (особенно неоднозначных грамматик) и сложные комбинаторные задачи.
Дальнейшее развитие логических языков продолжается в двух главных направлениях, которые можно назвать "алгоритмическим" и "переборным". Первое ориентировано главным образом на решение задач, для которых известны эффективные алгоритмы и требуются более тонкие средства управления, чем присутствующие в Прологе. Второе ориентировано на задачи, для которых нет эффективных алгоритмов, и где существенное место занимает перебор вариантов. Языки этого направления заменяют несколько примитивный перебор с возвратами, характерный для Пролога, более изощренными методами.
Написание программы на логическом языке
Как правило программы пишутся исходя из процедурной семантики логического языка, то есть как и на императивных языка, а затем дорабатываются с целью придать им декларативный смысл. Это вполне оправданная методика и она оказывается особенно удачной в случае если задача хорошо знакома и известен алгоритм ее решения. Но для очень сложных программ более практическим оказывается противоположный подход.
Сначала программа записывается как набор чисто логических утверждений. Она может быть очень неэффективной или даже не завершаться, но она обязана быть логически правильной. Затем в программу включаются алгоритмические знания. Программа (или часть программы) переписывается с учетом процедурной семантики. Часто модификация программы состоит в переупорядочивании последовательности правил или целей в правилах. Иногда полезным оказывается изменение представления данных. В то же время следует заботиться о том, чтобы не нарушить логическую семантику. Наконец, при необходимости добавляются элементы управления и другие внелогические операции. Полностью сохранить логическую семантику при этом удается далеко не всегда, но по крайней мере надо постараться это сделать.
Достоинства этого способа в том, что обычно намного проще понять задачу, рассматривая только ее логику, а попытка одновременно учитывать порядок выполнения операций только запутывает.

12. Язык логического программирования Пролог

Пролог означает – ПРОграммирование в ЛОГике. Он был разработан на основе логического доказательства теорем и первоначально использовался для исследований в области обработки естественного языка. Пролог применяется главным образом в приложениях типа экспертных систем и интеллектуальных баз данных, он также полезен и для  разработки обычных приложений. Этот язык использует более быстрые механизмы получения логического вывода, чем большинство других языков.
Программирование в Прологе существенно отличается от обычного программирования и требует несколько другого подхода в написании программы. Здесь утверждаются логические отношения, а Пролог используется, чтобы определить, являются ли некоторые конструкции истинными, и если да, то каким образом был получен такой вывод. Отсюда следует декларативный стиль программирования.
Пролог-программу, можно ввести в компьютер одним из двух способов:
1) при помощи текстового редактора создается файл с программой, которая затем загружается интерпретатором Пролога;
2) программа вводится во время сеанса работы с интерпретатором Пролога.
Непосредственный ввод программы будет происходить так:
?- consult(user).
знает(оля, витя).
знает(коля, света).
знает(коля, витя).
quit.
?-
Ввод команды consult(user), что в переводе на русский язык означает “просмотр(пользователь)”, переключает интерпретатор в режим ввода программы. Ввод команды quit возвращает интерпретатор обратно в командный режим, о чем свидетельствует появление сообщения подсказки ?-.
Вы вводите текст после подсказки “?-”, остальное обеспечивается Прологом. При работе с ним, важно не забывать добавлять конечную точку и нажимать клавишу Enter. Если Вы забудете точку (а такое может случиться), Вы можете ввести ее в следующей строке.
Если Вы “проконсультируетесь” с вашим файлом снова, то получите две копии ваших предикатов в приемнике. Чтобы заменить старую версию в приемнике, выберите Listener/Reconsult, или просто нажмите кнопку панели с символами “Re”. Вы можете также повторно  проконсультироваться непосредственно из приемника.

13. Факты и правила

Факты
Программа на Прологе состоит из множества фраз, и ее можно рассматривать как сеть отношений, существующих между термами. Терм обозначает некоторую сущность, принадлежащую миру. Фраза – это либо факт, либо правило. Факт – это утверждение о том, что соблюдается некоторое конкретное отношение.
Пример:  знает (оля, витя).
Факт состоит из имени предиката знает и списка термов, заключенного в скобки.
Одним из видов термов являются атомы. Атом – это константа, которая обычно записывается в виде некоторого слова, начинающегося с маленькой буквы. Термы “оля”  и “витя” являются атомами.
Предикат может обладать произвольным количеством аргументов. Нижеследующий факт показывает, что БГТУ расположен по адресу  ул. Костюкова 48.
Пример: расположение(бгту, костюкова, 48).
Простейшая Пролог-программа  - это множество фактов, которое неформально называют  базой данных. Пример базы данных, состоящей из фактов “знает”:
знает(оля, витя).
знает(коля, света).
Знает(коля, витя).
Правила
Правило – это факт, значение истинности которого зависит от истинных значений условий, образующих тело правила.
Форма записи правила:
заголовок :- тело.
Пример:
начальник(Familia, Oklad) :-  служ(Familia, Oklad), Oklad > 100.
Заголовок правила имеет такую же форму как и факт. Обозначение :- читается как “если”, затем следует тело правила. Каждое условие, входящее в тело, называется подцелью. Для того чтобы заголовок правила оказался истинным, необходимо, чтобы каждая подцель, входящая в тело была истинной.
Пример:
Предположим, что создана база данных “раб_смена”. Каждый факт этой базы определяет смену, в которую работает служащий.
раб_смена(оля, дневная).
раб_смена(коля, вечерняя).
раб_смена(витя, вечерняя).
раб_смена(толя, дневная).
Следующее правило устанавливает, что два человека знают друг друга, если они работают в одну и ту же смену:
знает2(A,B):- раб_смена(А, Smena), раб_смена(B, Smena).

14. Процедуры

Смысл фразы языка Пролог может быть понят либо с позиций декларативного подхода, либо с позиций процедурного подхода. Декларативный смысл подчеркивает статическое существование отношений. Порядок следования подцелей в правиле не влияет на декларативный смысл этого правила.
При процедурной трактовке подчеркивается последовательность шагов, которые выполняет интерпретатор при обработке запроса. Таким образом приобретает значение порядок следования подцелей в правиле.
Пример: база данных “путешествие”.
Эта база данных содержит факты, каждый из которых имеет по три аргумента. Каждый факт устанавливает, что можно совершить путешествие из одного города (1-й аргумент) в другой город (2-й аргумент) воспользовавшись некоторым видом транспорта (3-й аргумент).
путешествие(белгород, орел, поезд).
путешествие(брянск, дятьково, автобус).
путешествие (губкин, белгород, автобус).
путешествие(орел, брянск, поезд).
Два правила “можно_путешествовать” устанавливают либо прямую, либо косвенную связь между двумя городами.  Косвенное отношение будет соблюдаться в том случае, если возможно путешествие из одного города в другой через третий – промежуточный город.
можно_путешествовать(A,B):- путешествие (А, B,_).                                                     % (1)
можно_путешествовать(A,B):- путешествие(A,С,_), путешествие (С, B,_).                 % (2)
Считается, что между этими двумя правилами неявно присутствует соединитель “или”.
С декларативных позиций оба этих правила можно прочесть так:
Путешествие из города А в город B будет возможным, если либо

1. существует прямая транспортная связь между этими городами, либо
2. можно совершить путешествие из города А в некоторый промежуточный пункт С, а затем добраться из города С в город В.

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

1. Найти прямую транспортную связь между городами, либо
2. найти вид транспорта, связывающий город А и город C, а затем найти транспортную связь между городами С и B.

Пример запроса к базе данных можно_путешествовать:
Есть ли транспортная связь между городами Губкин и Орел?
?- можно_путешествовать(губкин, орел).
Yes 
Ответ получен по фразе (2).
При обработке этого запроса интерпретатор вначале проверяет фразу (1). Если фраза (1) дает отрицательный ответ, то интерпретатор переходит к проверке фразы (2).
Обработку последнего запроса можно представить в виде эквивалентной последовательности запросов:
?-можно_путешествовать(губкин, орел).     
                   %первая подцель первого правила “можно_путешествовать”
                   ?- путешествие (губкин, орел,_).
                   no
                   %первая подцель второго правила “можно_путешествовать”
                   ?- путешествие (губкин, С,_).
                   С = белгород
                   %вторая подцель второго правила “можно_путешествовать”
                   ?- путешествие (белгород, орел,_).
                   yes
yes

15. Рекурсивные процедуры

Классическим примером рекурсивного определения в Прологе может служить программа «предок».
Предположим, имеем  дерево родственных отношений:

Создадим соответствующую базу данных  “родитель”
родитель(пам,боб).
родитель(том,боб).
родитель(том,лиз).
родитель(боб,энн).
родитель(боб,пат).
родитель( пат, джим).
Создадим также два правила:
предок(A,B):- родитель(A,B).                                                     %(1)
предок(A,B):- родитель(С,B), предок(A, C).                          %(2)
Первое правило – для ближайших предков.  Второе  для отдаленных предков.
Любая рекурсивная процедура должна включать по крайней мере по одной из компонент:

1. Нерекурсивную фразу, определяющую исходный вид процедуры, т.е. вид процедуры в момент прекращения рекурсии.
2. Рекурсивное правило. Первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов.

Фраза (1) процедуры предок определяет исходный вид этой процедуры. Как только данная фраза станет истинной, дальнейшая рекурсия прекратится. Фраза (2) – это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель родитель(С, B), входящая в тело этого правила, вырабатывает значение переменной С. Затем располагается рекурсивная подцель предок(A, C), в которой используется этот новый аргумент.

16. Типы отношений

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

17. Механизм ответов Пролог-системы

Вопрос к системе - это всегда последовательность, состоящая из одной или нескольких целей. Для того, чтобы ответить на вопрос, система пытается достичь всех целей. Что значит достичь цели? Достичь цели - это значит показать, что утверждения, содержащиеся в вопросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, система должна к тому же найти конкретные объекты, которые (будучи подставленными вместо переменных) обеспечивают достижение цели. Найденные конкретизации сообщаются пользователю. Если для некоторой конкретизации система не в состоянии вывести цель из остальных предложений программы, то ее ответом на вопрос будет "нет".
Таким образом, подходящей интерпретацией пролог-программы в математических терминах будет следующая: пролог-система рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя - как теорему; затем она пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом.
Графическое представление шагов вычисления имеет форму дерева. Вершины дерева соответствуют целям или спискам целей, которые требуется достичь. Дуги между вершинами соответствуют применению (альтернативных) предложений программы, которые преобразуют цель, соответствующую одной вершине, в цель, соответствующую другой вершине. Корневая (верхняя) цель достигается тогда, когда находится путь от корня дерева (верхней вершины) к его листу, помеченному меткой "да". Лист помечается меткой "да", если он представляет собой простой факт. Выполнение пролог-программы состоит в поиске таких путей. В процессе такого поиска система может входить и в ветви, приводящие к неуспеху. В тот момент, когда она обнаруживает, что ветвь не приводит к успеху, происходит автоматический возврат к предыдущей вершине, и далее следует попытка применить к ней альтернативное предложение.

18. Декларативный и процедурный смысл Пролог-программ

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

19. Объекты данных Пролога

На рис. приведена классификация объектов данных Пролога. Пролог-система распознает тип объекта по его синтаксической форме в тексте программы. Это возможно благодаря тому, что синтаксис Пролога

Рис. Обьекты данных Пролога.
предписывает различные формы записи для различных типов объектов данных. В гл. 1 мы уже видели способ, с помощью которого можно отличить атомы от переменных: переменные начинаются с прописной буквы, тогда как атомы - со строчной. Для того, чтобы пролог-система распознала тип объекта, ей не требуется сообщать больше никакой дополнительной информации (такой, например, как объявление типа данных).
Атомы и числа
В гл. 1 мы уже видели несколько простых примеров атомов и переменных. Вообще же они могут принимать более сложные формы, а именно представлять собой цепочки следующих символов:
прописные буквы А, В, ..., Z
строчные буквы а, b, ..., z
цифры 0, 1, 2, ..., 9
специальные символы, такие как
        +  -  *  /   =  :  .  &  _  ~

Числа в Прологе бывают целыми и вещественными. Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, поэтому диапазон целых чисел ограничен интервалом между некоторыми минимальным и максимальным числами, определяемыми конкретной реализацией Пролога. Обычно реализация допускает диапазон хотя бы от -16 383 до 16 383, а часто, и значительно более широкий.
Переменные
Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Они начинаются с прописной буквы или с символа подчеркивания:
Если переменная встречается в предложения только один раз, то нет необходимости изобретать ей имя. Можно использовать так называемую "анонимную" переменную, которая записывается в виде одного символа подчеркивания. Рассмотрим, например, следующее правило:
        имеет ребенка( X) :- родитель( X, Y).
Структуры
Структурные объекты (или просто структуры) - это объекты, которые состоят из нескольких компонент. Эти компоненты, в свою очередь, могут быть структурами. Например, дату можно рассматривать как структуру, состоящую из трех компонент: день, месяц, год. Хотя они и составлены из нескольких компонент, структуры в программе ведут себя как единые объекты. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтор. Для нашего примера подойдет функтор дата. Тогда дату 1-е мая 1983 г. можно записать так:
Все компоненты в данном примере являются константами (две компоненты - целые числа и одна - атом). Компоненты могут быть также переменными или структурами. Произвольный день в мае можно представить структурой:
Синтаксически все объекты данных в Прологе представляют собой термы.

20. Списки

Списки обозначаются следующим образом:
[ терм1,терм2 | X]
Символ | разделяет список на две части: начало списка и остаток списка.
Пример3. Унификация списка.
?- [F|R]=[1,2,3,4,5].
F = 1
R = [2, 3, 4, 5].  % остаток списка является списком
yes
?- [F1,F2|R]=[1,2,3,4,5].
F1 = 1
F2 = 2
R = [3, 4, 5].
yes
Применение рекурсивных процедур для обработки списков

Рекурсивная процедура должна состоять из фразы, определяющей условие окончания рекурсии, а затем следует фраза, выполняющая действия с заголовком списка, которая далее вызывает рекурсию сама себя с аргументом, которым служит остаток списка.
Пример. Вывод элементов списка.
% фраза, определяющая условие окончания рекурсии
печатать_элементы([ ]).
% рекурсивное правило
печатать_элементы(Первый|Остаток]):-
  write(Первый), nl,                                                            % вывод первого элемента
  печатать_элементы(Остаток).                                   % рекурсивный вызов
Пример. Процедура Найти_слово
найти_слово(Slovo,[]):-fail. % Поиск заканчивается если список пуст или
найти_слово(Slovo,[Slovo|Y]). % слово совпадает с первым элементом списка
найти_слово(Slovo,[X|Y]):-найти_слово(Slovo,Y).
?-найти_слово(стул,[в, доме, есть, стул]).
yes.
?-найти_слово(забор,[в, доме, есть, стул]).
no.
Пример. Подсчет суммы элементов списка.
%  фраза, определяющая условие окончания рекурсии
сумма([],0):-!.
% рекурсивное правило
сумма([A|B],S):-сумма(B,S1),S is S1+A.
?- сумма([1,2,3],X).
X = 6
Пример. Объединение двух списков в третий.
присоединить([],S,S).
присоединить([X|S1], S2, [X|S3]):- присоединить (S1, S2,S3).

21. Управление выполнением программы на Прологе

Выполнение запроса.
Работу интерпретатора языка Пролог можно трактовать как рекурсивный циклический процесс унификации и вычисления подцелей. Действия интерпретатора инициируются запросом. В ходе выполнения этих действий интерпретатор «опустится» в структуру текущей программы настолько глубоко, насколько это окажется необходимым для того, чтобы найти факты, требующиеся для определения истинностного значения запроса. Затем интерпретатор вернется в исходное состояние, доказав или оказавшись не в состоянии доказать истинность запроса.
После того как пользователь вводит запрос интерпретатору, этот запрос активизируется. Интерпретатор приступает к анализу фраз текущей программы в поисках первой фразы, заголовок которой будет унифицироваться с запросом.
Неудача запроса и возврат назад.
Если активный запрос достигает конца соответствующего множества фраз, то он завершится неудачей. Если такой активный запрос служит частью составного запроса и не является первой подцелью этого составного запроса, то интерпретатор возвратится назад, чтобы повторно проанализировать предыдущую подцель составного запроса. Если активный запрос является первой подцелью составного запроса, то неудача активного запроса приводит к неудаче всего составного запроса. Когда интерпретатор возвращается назад, ликвидируются все конкретизации переменных, выполненные последним активным запросом.
Указание интерпретатору вернуться назад.
После того как интерпретатор найдет один ответ на запрос, пользователь может попросить найти еще один ответ. Для этого вводится символ ; , который означает отказ от только что полученного ответа. Это заставляет интерпретатор возвратиться назад и приступить к поиску другого ответа. Точнее, ввод символа ; приводит к неудаче запроса, активизированного самым последним (т.е.  запроса, расположенного в вершине стека).
Предикат «Сократить»
Пространство поиска запроса – это множество всех возможных ответов, рассматриваемых интерпретатором при выполнении запроса. Существует специальный встроенный предикат «сократить», который дает указание интерпретатору не возвращаться назад далее той точки, где стоит этот предикат.
Пример запроса с предикатом «сократить»:
?- a(X), b(Y), !, с(X,Y,Z).
При выполнении данного запроса интерпретатор пройдет через предикат «сократить» только в том случае, если подцель а(X) и b(X) окажутся успешными. После того как предикат «сократить» будет обработан интерпретатор не сможет возвратиться назад для повторного рассмотрения подцелей «a» и «b», если подцель «с» потерпит неудачу при текущих значениях переменных X и Y.
Проверка типа терма
В языке Пролог имеются встроенные предикаты, предназначенные для проверки типа терма.
var(X)
Этот предикат даст значение истина, если его аргумент будет не конкретизированной переменной. Пример:
?- var(X)
да
?- X = лондон, var(X).
нет
nonvar(X)
Этот предикат будет истинным, если его аргумент будет термом любого вида, кроме не конкретизированной переменной. Пример:
?- X = [париж, лондон, нью-йорк, токио],  nonvar(X).
да
Действия с текущей программой
Существуют встроенные предикаты, позволяющие программными средствами изменять текущее множество фраз программы.
Предикат assert (принять) добавляет к текущей программе фразу X.
Пример:
?- assert(король(людовиг, франция)).
да
?- король(людовиг, X).
X = франция
Предикат retract (удалить) удаляет из текущей программы первую фразу, которая унифицируется с X.
?- retract(король(людовиг, франция)).
да
?- король(людовиг, X).
нет

22. Реализация на Прологе семантических сетей

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