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



 

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

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

ØA1ÚØA2Ú…ÚØAkÚB1ÚB2Ú …Ú Bn ,  где элементарные формулы (предикаты) ØAi и Bj называются литерами, причем Bj ¾ положительная литера, а ØAi ¾ отрицательная литера.

Если k³1 и n=1, то такая клауза имеет вид ØA1ÚØA2Ú…ÚØAkÚB и называется клаузой Хорна или хорновским дизъюнктом. Хорновский дизъюнкт содержит не более одной положительной литеры.

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

Ø(A1&A2&…&Ak)ÚB, а эта формула равносильна формуле A1&A2&…&Ak®B, что соответствует правилам “Если …,то”.

На языке Пролог дизъюнкт Хорна записывается в другом виде B:¾ A1,A2,…,Ak. При такой записи «,» соответствует знаку конъюнкции &, а знак “:¾” соответствует знаку импликации .

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

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

B:¾ .

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

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

? :¾ A1,A2,…,Ak.

Такое выражение называется вопросом или запросом, а предикаты A1,A2,…,Ak называются целями, или целевыми утверждениями.

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

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

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

 

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

 

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

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(t1,t2,…,tk), где f — символьный атом, определяющий функциональную константу или главный функтор, а t1,t2,…,tk — термы, каждый из которых может быть составным термом. Составной терм по-другому называется структурой;
book(Author,Title,Year) — пример составного терма.

 


 


Дата добавления: 2018-04-04; просмотров: 233;