Логи́ческое программи́рование парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий. - презентация

1

2 Логи́чешское программи́рование парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логичешское программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.

3 Planner Prolog Mercury Visual Prolog Oz Fril OWL (Web Ontology Language) QA-4 Popler Conniver QLISP Ether

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

5 В основе языка представление действительности в модели данных «объект свойство» основан на концепции First-Order Logic (FOL), реализацию которой, в свою очередь, можно рассматривать как значительно более расширенную технику классического Prolog. OWL пригоден для описания не только веб- страниц, но и любых объектов действительности. Каждому элементу описания в этом языке (в том числе свойствам, связывающим объекты) ставится в соответствие URIURI (URI (англ. Uniform Resource Identifier) унифицированный (единообразный) идентификатор ресурса.).англ.

6

7 Дизъюнкция может быть записана в виде импликации: A 1 v А 2 v... v A n В 1 & B 2 & … & B m. Рассматривая логику предикатов 1-го порядка, импликация записывается так: A 1, А 2,..., A n В 1, B 2, …, B m (n 0, m 0) ( при этом принято посылку импликации писать справа, а заключение слева от знака операции).

8 За основу декларативного описания предметной области принимается специальная форма представления в виде фактов и правил. Факты это отношения или свойства, имеющие место между объектами данной предметной области. Факты имеют общий вид: property(objecti, object2,..., objectN) или relation(objecti, object2,..., objectN) где property это свойство объектов, a relation отношение между объектами.

9 Предложение: «Маше нравятся цветы». Факт: нравится (маша, цветы). где отношение это нравится, объекты маша, цветы. Предложение: «Шариковая ручка». Факт: ручка(шариковая) где шариковая является свойством объекта ручка.

10 Правила определяют одни отношения через другие. Правила это связанные отношения; они позволяют Прологу логически выводить одну порцию информации из другой. Правило принимает значение "истина", если доказано, что заданный набор условий является истинным.

11 Правила – это предложения вида H: - P 1, P 2,…, P n. Символ «:-» читается как «если», предикат H называется заголовком правила, а последовательность предикатов P 1, P 2,…, P n называется телом правила. Предикаты P 1, P 2,…, P n часто называют посылками. Заголовок следует из тела правила. Заголовок истинен, если истинны все посылки в теле правила. Если в программе встречается несколько правил с одинаковым заголовком, то это называется процедурой (правила в процедуре связаны по «или»). Пример: a:-b3, b4. a:-b1, b2. бабушка(X,Y):-родитель(X,Z), родитель(Z,Y), женщина(X).

12 relation(object,object,....object) :- relation(object,....object), relation(object,....object). Множество фактов, правил вместе с запросом представляют собой логическую программу (definite program).

13 Предложения: «Маше нравятся цветы». «Аня любит сына». «Сын Ани любит Машу». Факты: нравится(маша, цветы) любит(аня, сын) любит(сын, маша)

14 Предложения: « Оля любит всех, кого любит Аня». «Нам нравится все, что нравится человеку, которого мы любим». Правила: "Для любого X, если любит(аня, X), то из этого следует, что любит(оля, X)" или «если любит(аня, Х), то любит(оля, Х)». Запишем посылку справа, а заключение (следствие) слева от знака импликации, как это принято в логическом программировании. любит(оля, X) любит(аня, X). "Для любых X, Y, Z, если любит(Х, Y) и нравится (Y, Z), то из этого следует, что нравится(Х, Z)". нравится(Х, Z) любит(Х, Y) & нравится( Y, Z)

15 Запрос (цель) – это целевое утверждение, которое нужно доказать, исходя из множества фактов и правил программы, процесс доказательства представляет собой выполнение программы.

16 Сложные цели представляют собой конъюнкцию простых целей и имеют следующий вид: Цель: Q 1, Q 2,…,Q n, где запятая обозначает операцию конъюнкции, а Q 1, Q 2,…,Q n – подцели главной цели. Конъюнкция в Прологе истинна только при истинности всех компонент, в Прологе учитывается порядок оценки истинности компонент (слева направо). Пример внутренней цели: Goal: родитель(Y, Х), write(Y,родитель,X), fail.

17 1. Нравятся ли сыну Ани цветы? 2. Любит ли Аня Машу? 3. Кому нравятся цветы? 4. Кого любит Оля? 5. Нравятся ли цветы тому, кто любит Машу? 6. Нравятся ли Ане цветы? 1. нравится(сын(аня), цветы) 2. любит(аня, маша) 3. нравится(Х, цветы) 4. любит(оля, X) 5. любит(Х, маша), нравится(Х, цветы) 6. нравится(аня, цветы)

18

19

20 Атом - это отдельный объект, считающийся элементарным. Атомы и переменные могут представлять собой цепочки следующих символов: o прописные буквы А, В,..., Z o строчные буквы а, b,..., z o цифры 0, 1, 2,..., 9 o специальные символы: + - * / = :. & _ ~

21 Атомы можно создавать тремя способами: 1) из цепочки букв, цифр и символа подчеркивания _, начиная со строчной буквы: анна, nil, х 25, х_25, х_25AB, х_, х__у. 2) из специальных символов:, ======>,...,., : : = (Следует помнить, что часть цепочек специальных символов имеют в Прологе заранее определенный смысл. Например :- ). 3) из цепочки символов, заключенной в одинарные кавычки. Например, атом, начинающийся с прописной буквы. Заключая его в кавычки, он становится отличным от переменной: 'Дом', 'Лев_Толстой'.

22 Числа в Прологе бывают целыми и вещественными. integer - целое число в диапазоне от до 32767; real - действительные числа с фиксированной или плавающей точкой в диапазоне от -1Е+308 до 1Е-307. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - это язык, предназначенный в первую очередь для обработки символьной, а не числовой информации. При символьной обработке часто используются целые числа, например, для подсчета количества элементов списка.

23 Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Переменные в Прологе не описываются, хотя и имеют тип, имя и могут принимать различные значения. Имя переменной должно начинаться с заглавной буквы или с символа подчеркивания: Х, Результат, Объект 2, Список_участников, _х 23, _23. Максимальная длина имени переменной равна 250 знакам.

24 В Прологе производится проверка текущего значения переменной. Переменная называется: свободной (free), если она не имеет текущего значения, занятой, (связанной (bound), означенной,) если ей присвоено какое-либо значение. В зависимости от текущего значения переменой X выражение X=3+Y рассматривается как оператор присваивания (если X - свободная переменная), как оператор сравнения (если переменная X занята).

25 Анонимная переменная применяется, когда ее значение не используется в программе. Записывается в виде одного символа подчеркивания _. Возможное неоднократное употребление безымянной переменной в одном выражении применяется для того, чтобы подчеркнуть наличие переменных при отсутствии их специфической значимости.

26 Лексический диапазон имени - одно предложение. Например, если имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Внутри одного предложения каждое его появление обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, т.е. во всей программе.

27 Факт – это безусловно истинное утверждение Пролог-программы. Факт записывается в виде предиката с точкой на конце. Пример: часть(двигатель, автомобиль). земля_круглая. родитель(иван, маша).

28 Предикат - это единый объект состоящий из совокупности других объектов, называемых компонентами. Компоненты в свою очередь могут быть также предикатами. Название предиката стоит перед скобками, а компоненты внутри скобок перечисляются через запятую. Название предиката - ФУНКТОР. владелец (Маша, книга(Л.Толстой, Война и мир)). Функтор различается двумя параметрами: именем и числом параметров. Например, точка(X, Y, Z) и точка(X, Y) – разные предикаты.

29 domains /* секция объявления доменов */ database /* секция объявления динамических баз данных */ predicates /* секция объявления предикатов */ clauses /* предложения (факты и правила) */ goal /* подцель_1, подцель_2, и т. д. */

30 Объявляются любые нестандартные домены, используемые для аргументов предикатов. Домены в Прологе являются аналогами типов в других языках. Основными стандартными доменами Турбо-Пролога являются: char - символ, заключенный в одиночные кавычки (например, 'а'); integer - целое от до (переводится в вещественное автоматически, если необходимо); real - вещественное (например, , бе-94, -791 е+21); string - последовательность символов, заключенных в двойные кавычки (например, "нажмите ввод"); symbol - либо набор латинских букв, цифр и символов подчеркивания, в котором первый символ - прописная буква ( например, n_fax ) ; либо последовательность символов, содержащая пробелы или начинающаяся со строчной буквы, заключенная в кавычки (например, "Список СУБД"). file - символичешское имя файла, которое начинается с прописной буквы.

31 domains name, firm, type = symbol freq, vol = integer

32 Объявляются предикаты и типы (домены) аргументов этих предикатов. Имена предикатов должны начинаться со строчной латинской буквы, за которой следует последовательность букв, цифр и символов подчеркивания (до 250 знаков). В именах предикатов нельзя использовать символы пробела, минуса, звездочки, обратной (и прямой) черты. Объявление предикатов имеет форму: predicates predicateName1(domen11, domen12,..., domen1m) predicateNameN (domenN1, domenN2,..., domenNk)

33 predicates student( string,real) start good_student( string)

34 Размещаются факты и правила, с которыми будет работать Турбо-Пролог, выполняя цель программы. clauses predicateName1 (term11, term12,..., term1 к).... predicateNameN (termN1, terniN2,..., termNL).

35 clauses student("Петров",4.5). student("Сидоров",3.75). good_student( Name ) :- student( Name, В ), В >4. 4.">

36 Задается внутренняя цель программы. Это позволяет программе запускаться независимо от среды разработки. Если внутренняя цель включена в программу, то Турбо-Пролог выполняет поиск только одного первого решения, и связываемые с переменными значения не выводятся на экран. Если внутренняя цель не используется, то в процессе работы есть возможность вводить в диалоговом окне внешнюю цель. При использовании внешней цели Турбо-Пролог ищет все решения и выводит на экран все значения, связываемые с переменными.

37 Указывает на начало последовательности описаний предикатов динамической базы данных. Динамическая база данных является базой, в которую факты добавляются во время исполнения программы. Требования к описаниям предикатов такие же, как и в секции predicates. Факты, принадлежащие динамической базе данных, обрабатываются отличным от обычных предикатов образом для того, чтобы ускорить работу с БД большого объема. Факты динамической базы могут модифицироваться в течение сеанса работы, загружаться из дискового файла или записываться в дисковый файл.

38 /* программа 1 */ Predicates /* описание предиката */ любит(symbol, symbol) clauses любит (маша, цветы ). /* факт */ любит (петр, футбол). /* факт */ любит (петр, маша). любит (петр, X) :- likes (маша,X). /* правило */