Способы программирования логическое программирование

4. Логическое программирование

Методология логического программирования — подход, согласно которому программа содержит описание проблемы в терминах фактов и логических формул, а решение проблемы система выполняет с помощью механизмов логического вывода.

Логическое программирование начинает свой отсчет времени с конца 60-х годов XX века, когда Корделл Грин предложил использовать резолюцию как основу логического программирования. Алан Колмеро создал язык логического программирования Prolog в 1971 году. Логическое программирование пережило пик популярности в середине 80-х годов XX века, когда оно было положено в основу проекта разработки программного и аппаратного обеспечения вычислительных систем пятого поколения.

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

Одним из недостатков логического подхода в концептуальном плане является специфичность класса решаемых задач.

Другой недостаток практического характера состоит в сложности эффективной реализации для принятия решений в реальном времени, скажем, для систем жизнеобеспечения.

Нелинейность структуры программы является особенностью декларативного подхода и, строго говоря, представляет собой оригинальную особенность, а не объективный недостаток.

в качестве примеров языков логического программирования можно привести Prolog (название возникло от слов PROgramming in LOGic) и Mercury.

Метод единообразия заключается в одинаковом применении механизма логического доказательства ко всей программе.

Метод унификации — это механизм сопоставления с образцом для создания и декомпозиции структур данных.

Общие сведения о языке Prolog, связь с исчислением предикатов.

ПРОЛОГ является языком исчисления предикатов. Предикат – это логическая формула от одного или нескольких аргументов. Можно ска- зать, что предикат – это функция, отображающая множество произволь- ной природы в множество .

Обозначаются предикаты F(x), F(x, y), F(x, y, z) и т. д..

Одноместный предикат F(x), определенный на предметной области M, является истинным, если у объекта x есть свойство F, и ложным – если этого свойства нет.

Двухместный предикат F(x, y) является истинным, если объекты x и y находятся в отношении F.

Многоместный предикат F(x1 , x2 , x3 . xN ) задает отношение меж- ду элементами x1 , x2 , . xN и интерпретируется как обозначение высказывания: “Элементы x1 , x2, x N находятся между собой в отношении F”.

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

Предикаты, которые нельзя разбить на отдельные компоненты, на- зывают атомарными. Сложные формулы строятся путем комбинирова- ния атомарных предикатов логическими соединителями И, ИЛИ и НЕ.

Пролог (Prolog) — это программирование на языке логики.

Этот язык используется для задач, которые сводятся к объектам и отношениям между ними.

Пролог является реляционным языком.

Пользоваиель должен установить какие формальные отношения и объекты существуют в решаемой задаче и установить какие отношения справедливы для поиска решения.

Пролог — это декларативный язык. Он отличается от процедурных (императивных) языков:

• императивный — как делать
• декларативный — что делать

• семантикой языка
• новыми фактами, которые Пролог выводит из имеющихся
• отчасти той управляющей информацией, которую задает программист

• сопоставление с образцом
• поиск с возвратом
• недетерменизм

• Система реализующая логический вывод в исчислении предикатов 1-го порядка
• Хорнова модель вычислений: доказательство некоторых формул исчисления как вычисление
• «Выражение Хорна» (дизъюнкты,клаузы) + принцип резолюции (как логический вывод)

1. A(t₁,t₂. t_n) — факт

1. ~A₁V~A₂V. ~A_nVA_m

1. Правило преобразования дизъюнкции в конъюнкции:

• В качестве механизма логического вывода используется метод резолюции с формулами: A₁VA₂. VA_n

• объявление фактов об объектах и отношениях
• определение правил
• формировки вопросов

Источник

Логическое программирование и кому оно нужно

Пару месяцев назад мы с вами бегло обсудили функциональное программирование, а теперь пришло время затронуть ещё один тип — логическое программирование. В некоторой литературе эти два типа часто объединяют, противопоставляя императивному, однако основные принципы всё же различны.

Что это

Логическое программирование основывается на выводе информации, являющейся результатом изучения фактов.Образно говоря, это чем-то похоже на процесс обучения ребенка, когда вам чётко надо задать окружающие объекты, которые трогать «нельзя», остальные же изначально помечаются, как «доступные». Получив ваши наставления ребёнок начинает изучать мир и, сопоставляя данные, принимает решения. В логическом программировании этот принцип повторяется практически в точности, но разумеется в чуть более сложной форме.

Самым известным представителем и пожалуй самым популярным из используемых, является язык Prolog.

Prolog

Раз мы заговорили об этом популярном представителе ветви логического программирования, то остановимся на нём немного подробнее. Он был основан в начале 70-х годов 20 века, когда компьютеры только-только стали доступными для широких масс. С точки зрения построения и синтаксиса это не самый простой язык, но с точки зрения понимания ответных действий машины — почти идеальный. Просто взгляните на код, которым можно описать автомобиль:

auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).

Согласитесь, такую структуру легко понять и идентифицировать параметры, а ведь это едва ли не самое сложное, что можно увидеть в Prolog.

Изначально именно поэтому ему была уготована больше просветительская участь, чем реально полезная. Но со временем Prolog оказался полезен на передовой — в создании искусственного интеллекта и при работе с базами данных. В свежем рейтинге TIOBE Prolog занял весьма достойное 38 место.

Рассмотрим основные плюсы и минусы этого языка.

1. Операции, совершаемые в логическом программировании всегда понятны;
2. Результат практически всегда не зависит от выбранного пути реализации;
3. Может быть использован в качестве невычислительного языка используя только выражения и факты.

1. Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;
2. Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;
3. Если предстоит иметь дело с вычислительными операциями, то логические языки программирования — не лучший выбор.

Кому изучать

Следуя примеру советских студентов, изучать логическое программирование будет полезно практически всем и в любом возрасте, просто потому, что это здорово развивает умение мыслить поступательно и логически. Плюс, как уже было сказано, если ваша работа так или иначе связана с созданием искусственного интеллекта или хотя бы с данными, то язык Prolog и ему подобные — станут полезным инструментом.

Почитать

Изучение языка, а тем более целого класса языков немыслимо без чтения хороших книг. Вот некоторые из них:

Программирование на языке ПРОЛОГ, Уильям Клоксин — базовый обучающий курс логического и, что важно, практического программирования;

Алгоритмы искусственного интеллекта на языке PROLOG, Иван Братко — занимательная книга, пошагово и достаточно интересно знакомящая читателя с языком Prolog через операции по созданию ИИ;

Problem Solving With Prolog, Джон Стобо — данное творение отличается чуть более углубленной подачей материала, рекомендуется использовать, как 2-3 книгу для изучения Prolog;

The Art Of Prolog: Advanced Programming Techniques, Леон Стерлинг — книга, выпущенная в MIT в далёких 80-х годах, не теряет свою актуальность и сегодня, в основном благодаря большому количеству примеров кода;

From Logic to Logic Programming, Кис Доетс — ещё одно произведение из MIT, но на этот раз про логическое программирование в целом. Уровень подготовки требуется достаточно серьёзный, поэтому подготовьтесь много “гуглить”.

Logic-Based Artificial Intelligence, Джек Минкер — самое старое творение, но при этом одно из самых фундаментальных.

Источник