Логическое программирование
В основе – использование логики.
Историческая справка:
1969 – Absys (Фостер, Элькок)
Planner, MIT, Хьюит
Prolog (Colmeraver) – 1972
Ковальски
GNU Prolog, Пролог Д, Quintus, SICStus, SWI-Prolog, YAP
ISO Prolog – 1996
Turbo Prolog, Visual Prolog
LIC-Prolog
MU-Prolog
λ-Prolog
Mercury
Oz
Erlang
P#
Strand
ALF
Fril
Ciao
XSB
Golux – эквенциональный (Хэйес, 1973)
Основы логических исчислений
Логика – правило мышления, рассуждений.
Люди интересовались с давних времен.
Аристотель
Основание математики – начало 20-30 гг. XX века.
Логика сделала скачок и поднялась за счет того, что была формализована.
Применение математических методов.
Формализованные языки.
Формализованная логика оперирует формулами, состоящими из цепочек символов п некоторым правилам чисто синтаксического характера.
Синонимы: логическое мышление ≈ формализованная теорема ≈ формалиованная система ≈ аксиоматика ≈ логика.
Логик может быть множество разных.
Науки:
точные – достоверные (строгость)
описательные (не известны законы)
Теоремы о неполноте:
Гёдель
В любой сложной системе будут утверждаться недоказанные, но при этом истинные утверждения => логика не всесильна, есть ограничения => в основе математики ничего нет.
Принцип неопределенности физики:
Формальные теории.
Набор объектов: <A,F,V>
Алфавит
Правила построения формул
Набор аксиом
Набор правил вывода
Формула – цепочка символов из заданного алфавита
Аксиомы – подмножество формул данного исчисления, которые являются базовыми.
Правила вывода помогают сделать заключение о выводимости (доказуемости) в рамках данной логики.
Включают 2 части:
f1,f2…fₓ
g1,g2…gₓ
Доказанными являются формулы в знаменателе.
Вывод (доказательство) – последовательность формул; каждая из этих формул – аксиома, либо выводима на основании некоторого подмножества в предшествующей цепочке.
Пример формализованной системы:
А
={a,b,
}
F допускается любая цепочка из этих символов.
А а а а…а
Схема правил вывода:
М – внешний символ сокращения количества «а».
a a – выводимые Если - равенство, то а=1, b=( )
ba ab
b aa aab
b aaa aaab
Prolog – исчисление высказывания, логика предикатов первого порядка.
Логика высказываний – повествование утверждения i или l. Возможны связки.
И ˄
ИЛИ ˅
НЕ ̚
- импликация (следование).
При написании текста программ мы задаем аксиомы и правила вывода.
Задавая вопрос, можно использовать переменные.
Выражения в Prolog записываются в виде предикатов (формул от какого-то набора аргументов, применяемых значения i и l; аргументы могут быть атомы (const), переменные, функторы).
папа (Вася, Коля). (Вася – папа Коля, Вася и Коля – const).
?папа (Вася, Коля).
Да.
?папа(Вася, х).
Да, х=Коля.
?папа(х,у).
Да, х=Вася.
у=Коля.
?мама(х,Коля).
Нет.
Предикаты соответствуют математическим отношениям.
?plus(2,2,4).
Да
?plus(2,2,x).
Да, х=4.
?plus(x,2,4).
Да, х=2.
Пролог Д трассировка
GNU Prolog строчные, заглавные
Prolog - интерпретатор
Безымянная переменная __
папа(__, Коля). Выведет Да.
Факты.
Правила вывода.
Вопросы.
Терм – выражение.
Атом – терм.
Атом – const или переменная.
Функтор соответствует местности (арности) – также терм.
Арность – количество аргументов.
Функтор: имя(… , … , …).
Базовое предложение – предикат.
Предикат: имя(… , … , …).
Простейший вид предложения – факт. Используется для задания того, что выполняется какое-то отношение между объектами.
папа (Вася, Коля).
плюс(2,3,5).
Также можно самим придумать, как ввести кум, сват, золовка, невестка и т.д.
мужчина (Коля).
мужчина (Вася).
мама (Софья, Коля).
супруги (Вася, Софья).
?мама (Софья, Коля).
Да.
?мама (Софья, Нина).
Нет.
?мама (Софья, Х).
Х=Коля.
ЛЮБИТ(Вася, яблоки).
ЛЮБИТ(Маша, яблоки).
ЛЮБИТ(Коля, яблоки).
?ЛЮБИТ (Х, яблоки).
Вася, Маша, Коля.
?папа(Вася, Х), ЛЮБИТ(Х, яблоки).
Да, Х=Коля.
СЫН(Х,У):-ПАПА(У,Х), МУЖЧИНА(Х).
ДОЧЬ(Х,У):-ПАПА(У,Х), ЖЕНЩИНА(Х).
И – через запятую.
ИЛИ – несколько одноименных строчек.
СЫН(Х,У):-МАМА(У,Х), МУЖЧИНА(Х).
ДЕДУШКА(X,Z):-ПАПА(Х,У), ПАПА(У,Z).
РОДИТЕЛЬ(Х,У):-ПАПА(Х,У).
РОДИТЕЛЬ(Х,У):-МАМА(Х,У).
Определение семантики – множество выводимых из нее целей.