шпаргалки дискретная математика. Шпоры (лекции). Предметная область или Универсум совокупность всех предметов, которые она изучает. Литерал
 Скачать 85 Kb.
|
|
Предметная область или Универсум - совокупность всех предметов, которые она изучает. Литерал - это элементарная формула или отрицание элементарной формулы. Дизъюнкт - это литерал или дизъюнкция конечного числа литералов. Конъюнктивная нормальная форма - это формула, которая является дизъюнктом или конъюнкцией конечного числа дизъюнктов. Пусть имеются две элементарные формулы 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 и «=..». Вначале рассмотрим предикат =.., который записывается как инфикс- ный оператор и читается как «юнив» (univ). Цель Term =.. List является истинной, если List — список, содержащий главный (самый внешний) функтор терма Term, за которым следуют его параметры. • functor(?Term, ?Functor, ?Arity) Предикат выдает истину, если терм Term имеет функтор Functor и его арность равна Arity. • arg(?N, +Term, ?Value) Предикат выдает истину, если терм Term является составным и его N-ый по-порядку аргумент (нумерация идет с 1) унифицируется с Value. • name(?AtomOrInt, ?List) Предикат выдает истину, если List есть список кодов ASCIIсимволов, составляющих первый аргумент (атом или число). Ввод и вывод Существуют текущие входной и выходной потоки. По умолчанию текущим входным потоком считается клавиатура, а выходным потоком — экран. Переключение между потоками осуществляется с помощью процедур: • see (+File) — файл становится текущим входным потоком; • tell (+File) — файл становится текущим выходным потоком; • seen — закрывается текущий входной поток; • told — закрывается текущий выходной поток. Файлы читаются и записываются двумя способами: как последовательности символов и как последовательности термов. Встроенные процедуры для чтения и записи символов и термов таковы: • read(-Term) — вводит следующий терм; • write(+Term) — выводит Term; • put(+Char) — выводит символ, Char должно быть целочисленное выражение, значение которого есть код ASCII или атом в виде одной литеры; • get0(–КодСимвола) — вводит следующий символ; • get(–КодСимвола) — вводит ближайший следующий «печатаемый» символ. Характерной особенностью Пролога является эквивалентность программ и данных — и то и другое представлено логическими термами. Смысл встроенного предиката call(X) в Прологе состоит в передаче терма X в качестве цели. Доступность метапеременных означает, что в качестве целей в конъюнктивных вопросах и в теле предложений разрешается использовать переменные. В процессе вычисления, в момент обращения к такой переменной, ей должно быть сопоставлено значение — терм. Информация о фактах, которые не являются истинными, или об отношениях, которые не соблюдаются, называется негативной. Если правило P не представлено в текущей программе, то считается, что представлено отрицание P. Множество предложений текущей программы называется миром. Это — замкнутый мир, поскольку интерпретатор ведет себя так, как-будто бы в этом мире содержатся все возможные знания. предположение об открытости мира: если правило P отсутствует в текущей программе, то считается, что P ни истинно, ни ложно. запрос может обладать одним из трех допустимых истинностных значений: истина, ложь или неизвестно. Если запрос признан неизвестным, то программа может предпринять какие-то особые действия. По умолчанию интерпретатор языка Пролог руководствуется предположением о замкнутости мира. Поэтому если требуется, чтобы поведение программы соответствовало предположению об открытости мира, то это нужно выражать в явном виде при составлении программы. Программирование второго порядка Программирование на Прологе расширяется введением методов, отсутствующих в модели логического программирования. Эти методы основаны на свойствах языка, выходящих за рамки логики первого порядка. Они названы методами второго порядка,поскольку речь здесь идет о множествах и их свойствах, а не об отдельных элементах. Предикат findall(+Var, +Goal, -Bag) создает список всех конкретизаций переменной Var, полученных при бэктрекинге (перебор с возвратом) при выполнении цели Goal, и унифицирует результат с Bag. Bag — пустой список, когда Goal не имеет решения. Предикат apply(+Term, +List) присоединяет элементы списка List к аргументам терма Term и вызывает полученный терм в качестве цели. Например, apply(plus(1),[2,X]) вызывает plus(1, 2, X) Предикат checklist(+Pred, +List) проверяет все ли элементы списка List удовлетворяют предикату Pred. Операции с базой данных База данных, в соответствии с реляционной моделью баз данных, представляет собой спецификацию набора отношений. Любая Пролог-программа может рассматриваться как подобная база данных; в ней спецификация отношений частично является явной (факты), а частично неявной (правила). Некоторые встроенные предикаты позволяют модифицировать эту базу данных во время выполнения программы. Предикат assert(+Term) добавляет факт или правило в программу (в базу данных в оперативной памяти). Term добавляется как последний факт или правило соответствующего предиката. При выполнении предиката retract(+Term), когда терм Term унифицируется с первым подходящим фактом или правилом в базе данных, факт или правило удаляется из базы данных. Предикат retractall(+Term) удаляет все факты или правила в базе данных, которые унифицируются с Term. Те предикаты, которые будут добавляться или изменяться с помощью предикатов assert и retract, необходимо объявить в программе как динамические. dynamic Предикаты asserta и assertzпредоставляют возможность управлять позицией вставки: asserta добавляет в начало базы данных, а assertz (так же как и assert) — в конец. |