Файл: Предметная область или Универсум совокупность всех предметов, которые она изучает. Литерал.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 27
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Предметная область или Универсум - совокупность всех предметов, которые она изучает.
Литерал - это элементарная формула или отрицание элементарной формулы.
Дизъюнкт - это литерал или дизъюнкция конечного числа литералов.
Конъюнктивная нормальная форма - это формула, которая является дизъюнктом или конъюнкцией конечного числа
дизъюнктов.
Пусть имеются две элементарные формулы Aи Bязыка первого порядка. Эти формулы могут содержать индивидные (предметные) переменные. В некоторых случаях возможна такая подстановка термов вместо переменных в этих формулах, что формулы Aи B(вообще говоря, различные) становятся тождественными. Такая подстановка называется унификацией.
Хорновским дизъюнктом называется дизъюнкт, содержащий не более одного позитивного литерала.
Дизъюнкт, состоящий только из одного позитивного литерала, называется фактом.
Дизъюнкт, имеющий позитивный и негативные литералы называется правилом.
Логическая или, точнее, хорновская логическая программа состоит из набора хорновских дизъюнктов.
В языках программирования процедурной (операционной) семантикой называют описание последствий отдельных шагов вычислений, которые имеют место при выполнении программы. Декларативная (функциональная) семантика - описание функций программы, т.е. установление отношения между входными и выходными данными.
Вычисление целей интерпретатор Пролога осуществляет с помощью поиска в глубину с возвратом (в дереве целей): правило вычислений всегда выбирает первую слева подцель в текущем списке целей, а правило поиска выбирает из программы первое предложение, голова которого унифицируема с данной подцелью. Если вычисление заходит в тупик, т.е. ни одно из утверждений программы не применимо к текущему списку целей, то происходит возврат назад по построенной ветви и для предыдущего состояния пробуется первое из еще не применявшихся к нему утверждений программы.
Объекты (элементы) описываемого мира в Прологе представляются с помощью термов. Терм - это имя объекта. Существует 4 вида термов:
атомы, числа, переменные и составные термы.
Переменные записываются с помощью произвольных латинских и русских букв, цифр и знаков подчеркивания, но первый символ должен быть всегда прописной латинской буквой или знаком подчеркивания _. Символ подчеркивания является особым случаем – анонимной переменной (переменной без имени), которая применяется, когда ее значение не используется в программе.
Атомы могут формироваться тремя перечисленными ниже способами.
1. Строки букв (латинских или русских), цифр и знаков подчеркивания, начинающиеся со строчной буквы.
2. Строки некоторых специальных символов (не содержащие в себе пробелов): << >> >>> >+< +++ => <= <=> <-> ::+ :: .:.
3. Строки любых символов, заключенные в ординарные апострофы. Внутри могут быть пробелы. Например: 'X', '......123.....'.
Числа в Прологе бывают целыми и вещественными.
Составные термы (или структуры) состоят из имени структуры (представленного атомом) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми. Составные термы можно рассматривать как имена каких-то сложных объектов из предметной области. Имя структуры называется функтором. Нельзя помещать символ пробела между функтором и открывающей круглой скобкой.
Отметим, что синтаксически предикаты имеют такое же строение, как составные термы: предикат состоит из имени предиката (представленного атомом) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми. В качестве имен предикатов можно использовать любые атомы.
Нельзя помещать символ пробела между именем предиката и открывающей круглой скобкой.
Количество аргументов предиката называется его арностью (местностью). В программе могут присутствовать предикаты с одинаковыми именами и разной арностью.
Составные термы и предикаты представлены в программах, в префиксной форме: сначала имя, а потом аргументы, но в том случае, когда всего два аргумента, удобно использовать также инфиксную запись: имя помещается между аргументами.
Левая рекурсия - это рекурсия, когда предикат сначала вызывает себя, а только потом другие предикаты.
Применяя арифметические операции и функции к переменным и константам (числам и атомам) и используя при необходимости скобки,
можно сконструировать составные термы, которые называются арифметическими выражениями.
Для вычисления арифметических значений специально используется предопределенная операция is. Операция is вынуждает систему выполнить вычисление. Т.е. предикат is сначала вызывает вычисление правого операнда, а потом производит унификацию полученного значения и левого операнда. При этом невозможно переменной, имеющей значение, с помощью is присвоить новое значение (и любым другим способом).
Следует отметить, что предикат унификации и предикат проверки на равенство «=:=» отличаются друг от друга; например, они по-разному ведут себя в целях X=Y и X=:=Y. Первая цель вызывает унификацию термов X и Y, и если объекты унифицируются, то это может привести к конкретизации некоторых переменных в термах X и Y. В этом случае вычисление не выполняется. С другой стороны, операция =:= вызывает вычисление арифметических выражений, но не может стать причиной какой-либо конкретизации переменных.
Список — это простая структура, широко используемая в нечисловом программировании. Список представляет собой последовательность, состоящую из любого количества элементов.
Можно дать следующее неформальное рекурсивное определение списка:
• список может быть пустым (тогда он не содержит элементов) или
• список состоит из головы (это просто терм) и хвоста (это снова список).
.(a,.(b,.(c,[])))
один из видов списков — список кодов ASCII символов. Такие списки могут быть представлены в виде строк
Бинарные деревья можно задать с помощью тернарного функтора tree(Left,Root,Right), где Root — элемент, находящийся в вершине, а Left и Right — соответственно левое и правое поддерево. Пустое дерево изображается атомом nil.
p(nil, …):-
p(tree(L,X,R),…):-
Прологовские операторы суть функторы и имена предикатов (унарных и/или бинарных), записанных до, после или между аргументами.
Некоторые встроенные бинарные операторы (имена арифметических операций) обладают ассоциативностью. Это, в частности, дает возможность писать такие арифметические выражения, как a+b+c или a*b*c, не используя скобок.
Если в выражении присутствует несколько различных бинарных операторов, то структура термов определяется в соответствии с расстановкой скобок и приоритетами операций.
Программист может определять новые операции, вставляя в программу (обычно, одна из первых строчек) предложения специального типа, называемые
директивами (компилятору).
:- op(600,xfx,имеет).
Операторы, как и функторы, обычно используются только для объединения объектов в структуры, для повышения наглядности программы.
Операторы представляются атомами. Приоритет оператора задается целым числом из диапазона 1–1200.
Типы операторов подразделяются на три группы, которые обозначаются спецификаторами типа, такими, как xfx. Эти три группы перечислены ниже.
• Инфиксные операторы: xfx, yfx, xfy.
• Префиксные операторы: fx, fy.
• Постфиксные операторы: xf, yf.
Спецификаторы выбираются таким образом, чтобы они отражали структуру терма: f представляет оператор, а x и y —операнды.
с помощью директивы op можно переопределить
В процессе достижения цели Пролог-система осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Такой перебор — полезный программный механизм, поскольку он освобождает пользователя от необходи-
мости программировать его самому. С другой стороны, ничем не ограниченный перебор может стать источником неэффективности программы. Поэтому иногда требуется его ограничить или исключить вовсе. Для этого в Прологе предусмотрена конструкция «отсечение».
Отсечение записывается в виде символа «!», который вставляется между целями и играет роль некоторой псевдоцели (предикат без аргументов, который всегда истинен).
Символ «!» предотвращает возврат из тех точек программы, в которых он поставлен.
Назовем «целью-родителем» ту цель, которая унифицировалась с головой предложения, содержащего отсечение. Когда в качестве цели встречается отсечение, такая цель сразу же считается успешной и при этом заставляет систему принять те альтернативы, которые были выбраны с момента активизации целиродителя до момента, когда встретилось отсечение. Все оставшиеся в этом промежутке (от цели-родителя до отсечения) альтернативы не рассматриваются.
Преимущества отсечения
• При помощи отсечения часто можно повысить эффективность программы. Идея состоит в том, чтобы прямо сказать Пролог-системе: не пробуй остальные альтернативы,так как они все равно обречены на неудачу.
• Применяя отсечение, можно описать взаимоисключающие правила. Выразительность языка при этом повышается.
Недостатки отсечения
Нарушается соответствие между процедурным и декларативным смыслом программы.
Изменение порядка следования предложений, содержащих отсечения, может повлиять на декларативную семантику программы.
Встроенный предикат not («не») имеет один аргумент.
Этим аргументом является цель, значение истинности которой (после обработки данного запроса) заменяется противоположным. Если запрос успешен, то отрицание этой цели (запроса) является неудачей, и наоборот, если запрос терпит неудачу, то его отрицание будет успехом.
Недостатки отрицания
Оказывается отрицание в Прологе определено через отсечение.
true («истина») и fail («неудача»). Эти предикаты не имеют аргументов, первый всегда истинен, второй всегда ложен.
\+(P) :-
P,!,fail.
\+(P):-
true.
Поэтому к сознательно принятому недостатку отрицания («замкнутый мир») добавляются и недостатки отсечения.
Рекурсия
Этот принцип состоит в том, что задача сводится к нескольким случаям, принадлежащим к двум группам. Тривиальные, или граничные, случаи. Общие случаи, в которых решение составляется из решений отдельных (более простых) вариантов первоначальной задачи.
Граничный случай — список пустой.
Общий случай (рекурсивный переход) — список не пустой. Тогда он имеет голову и хвост. Пишем соответствующее правило.
В Прологе информацию из одного вызова предиката в другой вызов предиката (одноименного или другого) передают с помощью параметров. В этих параметрах хранят ин-
формацию, изменяют ее и накапливают постепенно результат.
Этот прием называется методом накапливающего параметра.
Проверка типа термов
var(X). Выполняется успешно, если X во время проверки — не конкретизированная переменная.
• nonvar(X). Выполняется успешно, если X — не переменная или X — уже конкретизированная переменная.
• atom(X). Принимает истинное значение, если X во время проверки обозначает атом.
• integer(X). Принимает истинное значение, если X ввремя проверки обозначает целое число.
• float(X). Принимает истинное значение, если X во время проверки обозначает число c плавающей точкой.
• number(X). Принимает истинное значение, если X во время проверки обозначает число.
• atomic(X). Принимает истинное значение, если X во время проверки обозначает число или атом.
• compound(X). Принимает истинное значение, если X во время проверки обозначает составной терм (структуру).
Для декомпозиции термов и создания новых термов предусмотрены предикаты: functor, arg, name и «=..». Вначале рассмотрим предикат =.., который записывается как инфикс-