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

⇐ ПредыдущаяСтр 3 из 17Следующая ⇒

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

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

Ø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 , клауза называется пустым дизъюнктом, имеет обозначение ð и интерпретируется как тождественно ложная формула.

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

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

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

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

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) — пример составного терма.

Дата добавления: 2018-04-04; просмотров: 682; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!