2.2 Стандартные формы представления формул исчисления предикатов.

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

Клаузальной формой (клаузой или предложением) в исчислении предикатов называется формула, представляющая собой несколько предикатов или их отрицаний, объединенных знаками дизъюнкции. В общем случае клаузу можно представить в следующем виде:

A₁A₂…A_kB₁B₂ … B_n , где элементарные формулы (предикаты) A_i и B_j называются литерами, причем B_j  положительная литера, а A_i  отрицательная литера.

Если k1 и n=1, то такая клауза имеет вид A₁A₂…A_kB и называется клаузой Хорна или хорновским дизъюнктом. Хорновский дизъюнкт содержит не более одной положительной литеры.

Дизъюнкт Хорна можно преобразовать с помощью правила де Моргана:

(A₁A₂…A_k)B, а эта формула равносильна формуле A₁A₂…A_kB, что соответствует правилам “Если …,то”.

На языке Пролог дизъюнкт Хорна записывается в другом виде B: A₁,A₂,…,A_k. При такой записи «,» соответствует знаку конъюнкции , а знак “:” соответствует знаку импликации .

В языке Пролог используются только хорновские дизъюнкты, называемые правилами. При этом B называется заголовком правила, а конъюнкция A₁,A₂,…,A_k называется телом правила. Знак “:” читается как “Если”. Таким образом, правило является условным предложением языка Пролог.

В клаузе Хорна атомарные формулы A₁,A₂,…,A_k могут отсутствовать, т.е. k=0, n=1. В этом случае правило имеет пустое тело:

B: .

Это означает, что предикат B истинен всегда, такая конструкция в языке Пролог называется фактом.

Если в хорновском предложении отсутствует заголовок правила, т.е. k1, n=0, то правило принимает вид:

? : A₁,A₂,…,A_k.

Такое выражение называется вопросом или запросом, а предикаты A₁,A₂,…,A_k называются целями, или целевыми утверждениями.

Если в хорновской клаузе k= n=0 , клауза называется пустым дизъюнктом, имеет обозначение  и интерпретируется как тождественно ложная формула.

Предложения языка Пролог являются либо правилами, либо фактами, либо запросами. Логическая программа на Прологе  это конечная последовательность фактов и правил.

3. Синтаксис языка программирования Пролог.

3.1. Основные элементы языка Пролог.

Алфавит языка Пролог включает следующие символы:

1. A, B, C, …, Z, a, b, c,…,z — прописные и строчные буквы латинского алфавита.

2. 0,1,2,3,4,5,6,7,8,9 — цифры.

+ - = * / < > [ ] : ; , | . —специальные знаки

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

Переменная в Прологе — это последовательность латинских букв, цифр и знака подчеркивания, начинающая с прописной буквы или знака подчеркивания. Например, X, all, S1 — переменные. Переменные используются для представления объектов, значения которых определяются в ходе решения задачи. Переменные записываются в качестве аргументов предикатов в Пролог— программе и в запросах. Если значение аргумента предиката не принимается во внимание, то этот аргумент обозначается анонимной переменной, то есть в место имени переменной указывается знак подчеркивания «_».

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

Атомы могут быть трех типов:

1. символьный атом — это последовательность латинских букв, цифр и знака подчеркивания, начинающая со строчной буквы. Например, may, all, factorial — символьные атомы. Символьные атомы не должны содержать пробелы. Символьные атомы используются для обозначения предметных, функциональных и предикатных констант.

2. Последовательность специальных знаков есть атом, например, :- >= *.

3. Любое слово из букв латинского и русского алфавита и цифр, заключенное в апострофы, например, ‘Mary’, ‘Маша’,’1_мая’, ‘Arity_Prolog’. Пробелы в символьных атомах не допустимы.

Числа в языке Пролог используются целые и вещественные. Целые числа записываются так же, как в любом другом языке программирования; целые отрицательные числа записываются со знаком, в записи положительных чисел знак можно опустить, например, 135, 0, -89.

Вещественные константы могут быть представлены в форме с фиксированной точкой и с плавающей точкой, например, 135.712 и 0.135712E+3,соответственно.

Строки — это последовательности символов, заключенная между знаками $. Строки используются в задачах обработки текстов на естественных языках. $$ — пустая строка. Знак $ внутри строки записывается дважды. Строки могут включать пробелы, например, $1 января 2003 года $ есть строка, и $Turbo-Prolog$ тоже строка.

Составной терм — это конструкция вида f(t₁,t₂,…,t_k), где f — символьный атом, определяющий функциональную константу или главный функтор, а t₁,t₂,…,t_k — термы, каждый из которых может быть составным термом. Составной терм по-другому называется структурой; book(Author,Title,Year) — пример составного терма.