Программу Пролог Логика
Найти программу: Рейтинг программ > Пролог. ЗАО НПФ ЛОГИКА. Перед загрузкой проверьте компьютер с помощью Reg Organizer. ___ ___ Категории. Все категории.
Программа ПРОЛОГ ЛОГИКА >>> Скачать Бесплатно >>> Официальный сайт >>> Скачать руководство пользователя пролог логика. Лекция 2: Введение в Пролог и логическое программирование. Пример простой программы на LISP - Продолжительность: 17:53. Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка. Язык сосредоточен вокруг небольшого набора основных механизмов, включая сопоставление с образцом, древовидного представления структур данных и автоматического перебора с возвратами.
— Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости. Пролог — уникален.
Это единственный язык представляющий парадигму декларативного программирования; это язык, который имеет сотни различных имплементаций, но они все равно называются Prolog, добавляя лишь префиксы и суффиксы к названию; это живой язык в котором не происходит никаких существенных изменений более 20 лет; это, наверное, единственный настолько популярный язык программирования, который не имеет применения в реальном программировании. Почему же Prolog? Пролог — уникален по своей природе, он появился благодаря счастливому совпадению ( таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций.
Программа Пролог Логика
Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog. В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач.
Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций. Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+, от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток:) Как правильно читать программы на прологе Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык.
Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста. Понятия В языке существует 2 понятия предикаты (условия) и объекты (они же переменные и термы). Предикаты выражают некоторое условие, например объект зеленый или число простое, естественно что условия имеют входные параметры. Например greenobject(Object), primenumber(Number). Сколько в предикате параметров, такова и арность предиката. Объектами — являются термы, константы и переменные.
Константы — это числа и строки, переменные — выражают неизвестный объект, возможно искомый, и обозначаются как строчки с большой буквы. Оставим пока термы и рассмотрим простейшую программу. Программа Программа — это набор правил, вида Если условие1 и условие2 и то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).
A:- B1, B2.% правило читается как: Если B1 и B2, то A нечетноепростое(Число):- простое(Число), нечетное(Число).% Если 'Число' - простое и нечетное, то 'Число' - нечетноепростое Как видно имя переменной имеет область видимости — это правило. Математически верно, правило звучит: для любой переменной — «Число», если оно простое и нечетное, то оно простоенечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетнопростое. Поэтому имя переменной очень важно! Если в левой части (до:- ) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число — простое и нечетное, то Число2 — простое нечетное. Получается все числа простыенечетные! Это самая распространенная ошибка в Прологе.
A:- B1, B2.% правило читается как: Если B1 и B2, то A нечетноепростое(Число):- простое(Число), нечетное(Число).% Если 'Число' - простое и нечетное, то 'Число' - нечетноепростое Пример — совершенные числа совершенноечисло(Ч):- число(Ч), суммаделителейбезчисла(Ч, СуммаДелителей), равно(СуммаДелителей, Ч). Равно(Объект, Объект). Суммаделителейбезчисла(1, 1). Суммаделителейбезчисла(Число, Сумма):- числопредыдущее(Число, Предыдущее), суммаделителейчисладочисла(Число, Сумма, Предыдущее). Суммаделителейчисладочисла(Число, 1, 1).
Суммаделителейчисладочисла(Число, Сумма, Делитель):- делитсяна(Число, Делитель), числопредыдущее(Делитель, Предыдущее), суммаделителейчисладочисла(Число, СуммаПред, Предыдущее), сложить(СуммаПред, Делитель, Сумма). Суммаделителейчисладочисла(Число, Сумма, Делитель):- неделитсяна(Число, Делитель), числопредыдущее(Делитель, Предыдущее), суммаделителейчисладочисла(Число, Сумма, Предыдущее). Для начала формально прочитаем, что означают правила:. Если «Ч» — число и для «Ч» и «СуммаДелителей» выполняется условие суммаделителейбезчисла, проще говоря СуммаДелителей есть сумма делителей числа «Ч», и «Ч» равно «СуммаДелителей», то «Ч» совершенное число. 1 — совершенное число. Правила могут не иметь условий, в этом случае они называются фактами. Всякий объект «О» равен «О».
В принципе существует, стандартный предикат '=', но можно вполне заменить на свой. Факт суммаделителейбезчисла 1 равна 1. Если сумма делителей «Число» до предыдущего числа «Число» равна «Сумма», то это и есть суммаделителейбезчисла. Таким образом выражается, сумма делителей X меньше либо равных Y, так как X делится на X, поэтому берем Y = X — 1. Далее 3 предиката определяют сумму делителей число меньше либо равных Y (Делитель), 1-й случай Y равное 1, 2-й случай Число делится на Y, тогда суммаделителей(X, Y) = суммаделителей(X, Y-1) + Y, и 3-й случай Число не делится на Y, тогда суммаделителей(X, Y) = суммаделителей(X, Y-1). Программа — как набор определений Существует второй способ прочтения данных правил, менее математический и более естественный, основанный на «определениях». Можно заметить, что в Прологе все правила слева (в части то) содержат только одно условие, что по сути является «определением» это условия.
Например, 1-ое правило определение совершенных чисел. «Ч» совершенное число, когда «Ч» число и сумма делителей «Ч» равна «Ч». Одинаковые предикаты группируются по имени объединяясь условием «или». То есть к определению можно добавить: «Ч» совершенное число, когда., или когда «Ч» — это 1. Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы проверить истинность некоторого утверждения.
Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делитсяна». Интересный факт, что в Прологе нет ни циклов, ни присвоения переменных, ни объявления типов, а если вспомнить еще про термы и отсечение, то язык становится алгоритмически полным. Термы Термы имеют рекурсивное определение, как именованная совокупность объектов. Терм = 'имя'(объект, объект.), пример person('Name', 'Surname'), '+'(1, 2), person(address('Некоторый адрес'), surname('Фамилия'), phone('Телефон')). Если рассматривать терм, как математическое понятие, то терм является функцией, а точнее функтором, то есть '+'(1, 2) — означает, что существует такой объект, который равен 1+2. Это абсолютно не означает, что 1+2 = 3, в Прологе — это выражение неистинно, точно так же как и в группе остатков по модулю 2, там 3 вообще не существует.
Опять же с математической точки зрения Переменные связываются словом Для Всех, а если в утверждении необходимо слово существует то, для этой цели применяется терм (функтор). Для любого числа существует число-факториал:- factorial(X, fact(X)). С точки зрения программирования терм можно объяснить гораздо проще: терм — это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние — переменная. Пример — целочисленная арифметика нат(0).
Нат(число(Число)):- нат(Число). Плюс(0, Число, Число). Плюс(число(Ч1), Ч2, число(Рез)):- плюс(Ч1, Ч2, Рез). Умножить(0, Число, 0). Умножить(число(Ч1), Ч2, Рез2):- умножить(Ч1, Ч2, Рез), плюс(Рез, Ч2, Рез2). Определение свойства нат (натуральное число).
0 — натуральное число, если Число натуральное, то существует объект число(Число), которое тоже является натуральным. Математически терм «число» выражает функцию +1, с точки зрения программирования «число» рекурсивная структура данных, вот ее элементы: число(0), число(число(0)), число(число(число(0))). Отношение плюс — 0 + Число = Число. Если Ч1 + Ч2 = Рез, то (Ч1+1) + Ч2 = (Рез+1). Отношение умножить — 0. Число = 0. Если Ч1.
Ч2 = Рез и Рез + Ч2 = Рез2, то (Ч1+1). Ч2 = Рез2. Очевидно эти утверждения верны для обычной арифметики, но почему тогда мы не включили такие же очевидные как Число + 0 = Число. Ответ простой: избыточность очень плохо для любого определения. Да, это может помогать вычислениям, своеобразная преждевременная оптимизация, но побочными эффектами могут быть противоречия в определениях, неоднозначный вывод утверждения, зацикливание интерпретатора. Как Prolog понимает предикаты и как доказывает утверждения Конечно чтение программ, помогает ощутить стиль Пролог, но не делает понятным для чего и как данные определения могут использоваться. Полноценной программой, примеры приведенные выше, назвать нельзя так как не хватает входной точки.
Входной точкой в Пролог является запрос, аналог запроса к базе данных SQL или аналог вызова главной функции в функциональном программировании. Примеры запросов: нат(Число) — найти натуральное число, плюс(0, 0, Результат) — найти результат сложения 0 и 0 в переменной Результат, нат(0) — проверить является ли 0 натуральным числом и др. Конечно, результаты запросов не трудно предсказать из логических соображений, но крайне важно понять, как программа их получила. Все-таки Пролог не черный ящик, а язык программирования, и в отличие от базы данных, где строится SQL-план и запрос может выполняться по-разному на разных Базах данных, Пролог имеет вполне определенный порядок выполнения. Дело в том, что в Базе данных мы вполне знаем какой ответ мы хотим получить исходя из данных в таблице, к сожалению глядя на Пролог программы достаточно сложно сказать, какие утверждения логически выводимы, поэтому понять как работает Пролог интерпретатор гораздо проще.
Рассмотрим на примере запроса плюс(0, 0, Результат): 1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число).
Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0. Запрос нат(Число): 1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.
Запрос плюс(Результат, 0, число(0)): 1. Находим резолюцию с правилом плюс(0, Число, Число): Результат = 0, 0 = Число, число(0) = Число, но (!) Число = 0 = число(0) — не возможно так как 0 совпадает число(0). Следовательно ищем резолюцию со следующим правилом. Находим резолюцию с правилом плюс(число(Ч1), Ч2, число(Рез)), получаем число(Ч1) = Результат, Ч2 = 0, число(Рез) = число(0), отсюда Рез = 0.
У этого правила, есть условия которые мы должны проверить, учитывая результаты резолюции (значения переменных), плюс(Ч1, Ч2, Рез) - плюс(Ч1, 0, 0). Запоминаем значение переменных в стеке и формируем новый запрос плюс(Ч1, 0, 0) 3. Решая запрос плюс(Ч1, 0, 0) находим резолюцию с плюс(0, Число, Число) и получаем Ч1 = 0 и Число = 0. Возвращаемся по стеку к предыдущим переменным Результат = число(Ч1) = число(0). Ответ найден число(0). Соответственно сейчас пролог машина решила уравнение X + 0 = 1.
Грамотное составление правил на языке Пролог, очень сложная штука, но если их составить компактно, то можно получать не только прямые ответы и решения, но и обратные. Пример запроса плюс(Число, Число, Число): ответ да, Число = 0.
Пример запроса плюс(0, 0, 0): ответ нет, при первой же попытке все резолюции не выполняются. Пример запроса плюс(Число, Число, число(Число)): ответ да, Число = 1.
Решение уравнения X + X = X + 1. Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число), сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел.
Другой пример, запрос плюс(Число, число(0), Число2), будет выдавать последовательность всех пар решения уравнения X + 1 = Y. Заключение К сожалению, разумный размер топика, не дал мне подобраться к главной теме, а именно к решению сложных логических задач на языке Пролог, не обладая стратегией их решения. Большие куски кода на Прологе могут отпугнуть не только начинающих, но даже опытных программистов.
Цель данной статьи показать, что программы на Прологе могут простым образом читаться на естественном языке, а также исполняться простейшим интерпретатором. Главная особенность Пролога — это не черный ящик и не библиотека, который решает сложные логические задачи, в Mathematica можно ввести алгебраическое уравнение и она выдаст решение, но последовательность выполняемых шагов — неизвестна. Пролог не может решать общие логические задачи (у него отсутствует логическое «или» и «отрицание»), иначе бы его вывод был недетерминированный как линейной резолюции. Пролог — это золотая середина, между простым интерпретатором и машиной для доказательства теорем, сдвиг в любую сторон приводит к потери одного из свойств. В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу ( решившему первым приз): Написать предикат, который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3.
Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 = X=4. Метки:. Добавить метки Пометьте публикацию своими метками Метки необходимо разделять запятой. Например: php, javascript, андронный коллайдер, задача трех тел. Назовите еще языки этой парадигмы? Mercury я бы не брал в счет, по сути дела, такой же Пролог, просто с разными фишками из функционального программирования.
Возможно Рефал можно назвать другим языком. Пролог не печален:) Просто порог вхождения крайне высок, я периодически слежу за обновлениями XSB и SWI-Prolog и поверьте они развиваются. Среду разработки можно взять Eclipse с плагином. Проблема Пролога в том, что его одного нельзя использовать исключительно для написания программы, так как времена консольных приложений прошли (все уже написаны). А для того, чтобы его использовать в связке не все берутся. Хотя могу привести пример: я использую сейчас Пролог для настройки голосовой помощи на разных языках, так как числа читаются абсолютно по-разному в разных языках, то файлы конфигураций в виде правил Пролога идеально подходят:), обычные property файлы просто не дают гибкости. И между прочим много пользователей прекрасно справилось с локализацией своего языка при помощи Пролога.
Технически, есть мнение, что «декларативные» языки — это такой странный термин, который включает в себя сразу всё, что не включается в «императивные» языки — т.е. И логические (Prolog, Mercury), и функциональные (Lisp и все-все-все), и DSL (HTML, XML, CSS, XSLT, Make), и dataflow-ориентированные (Clojure, PD, Simulink, LabView и т.д.) В этом плане — термин — спорный, и если говорить про логические и constraint-ориентированные языки — то, о чем статья, собственно — то там действительно вариантов кроме Prolog и тучи его диалектов — явно немного. Mercury да Oz, по сути. Ну, Erlang еще — с бооольшой натяжкой. Пролог единственный который я знаю язык логического программирования, но даааалеко не единственный декларативный.
Haskell, Lisp реализуют парадигму декларативного программирования, например. Пролог достаточно печален, т.к.
Создан давно и развивается достаточно медленно. Он очень крут, но его функциональность можно реализовать на F# или подобном языке достаточно просто (да, я пробовал, причем на C#) и получить куда более функциональную среду, т.к. Она будет частью кода данной программы. Пролог это язык для реализации алгоритмов с большим неявным перебором вариантов (логический вывод, нахождение зависимостей, перебор ходов в шахматах) и он действительно хорош, но достаточно неповоротлив в плане интеграции (я интегрировал visual prolog с.net). Насчет интеграции не поворотлив, это отговорки ленивых, которые уже забыли как компилировать C код, того же, и подключать нативные библиотеки. И тем более отговорки, потому как есть библиотеки, которые например обычный ассемблерный (конечно не любой), переводят в Java байткод.
Просто Пролог — не мейнстрим. А куда ему развиваться? Вы про какой Пролог? Мне кажется SWI-Prolog и XSB очень даже активно развиваются. ИМХО, Visual Prolog не долюбливаю (извращенцы, писать UI на Прологе и операции присваивания). Декларативные языки программирования включают несколько подклассов, логические только один из них. К декларативным относятся все функциональные языки (чисто функциональные), языки запросов к базам данных и т.д.
Вообще язык реализует декларативную парадигму программирования, если с его помощью описывается в большей степени определение задачи, а не конкретный алгоритм ее решения. Пролог яркий, но не единственный логический язык программирования. Например существует его ровесник Дейталог, тоже логический, хотя основан на другой теории. Интересно как использовать пролог в связке с другими языками и какую реализацию использовать? Я так и не нашёл ни одной годной реализации, всё очень примитивно. Выяснил, что SWI-Prolog это самая продвинутая реализация.
Так вот это очень недоразвитый проект. Ничего практически полезного с ним сделать нельзя. Документация по интеграции с другими системами ужасная. Очень сложный сишный код, который периодически падает по непонятным причинам. Например, — библиотека работы с swi-prolog из python. Есть аналогичная библиотека для хаскеля Попробуйте сделать с их помощью многопоточную программу. Чтобы с интерпретатором могли работать сразу несколько потоков.
Это невозможно. Я думаю что у пролога большое будущее. Но писать исполняемый код на нём большое извращение.
Пролог идеален только в качестве языка запроса к дедуктивным базам данных. В конце концов SQL это частный случай пролога. На прологе можно намного проще делать всякие outer join и выполнять рекурсивные запросы без использования хранимых процедур. Реально проще. Осталось только написать такую дедуктивную СУБД. Потому что бухгалтерский, а особенно налоговый учет в наших СНГшных краях крайне нестабилен.
И для успешных бух. Решений необходима система с возможностями быстрого внесения модификаций. Вот выпустили налоговики очередное письмо-разъяснение, которое отличается от предыдущих какой-то мелочью — в 1С нужно только формулу подредактировать (иногда даже без перезапуска рабочей базы, если это касается расчета зарплаты), а на языке логического программирования пришлось бы половину программы переписать, что бы подстроится под «прихоти» налоговиков (а через месяц они еще что-то потребуют изменить в расчетах угрожая за невыполнение штрафами). Что вы такое рассказываете:) Как быстро обновить можно базу данных?
Представьте все ваши правила по расчету 1С бухгалтерии лежат в таблице базы данных: запустив один SQL Update вы можете за 1 секунду внести изменения, причем не останавливая работу БД. Пролог по сути дела та же БД только там можно хранить не только факты, но и правила. Существуют такие запросы как assert/retract. На практике вы конечно можете столкнуться со скомпилированными предикатами в некоторых имплементациях, но если иметь эту функциональность в виду, то все будет тип топ. Еще одно замечание: База Данных, Пролог, возможно 1С скрипт, более понятный инструмент для непрограммистов, чем языки общего назначения — C, Java, Basic. Не могу с вами спорить, так как пролог изучал только на протяжении одного семестра (и это был Turbo Prolog).
Хочу только отметить, что ставки и границы налогов, формулы расчета зарплатных начислений делаются в 1С в пользовательском интерфейсе без необходимости делать запросы на языке SQL к БД. Править код нужно при более сложных изменениях. Пример из жизни за эту зиму/весну — налоговики хотели сначала что бы рассчитывали ЕСВ, а потом облагали разность с начислением 15% до границы и 17% все что свыше, но по результатам месяца получения взносов они увидели, что денег приходит чуть меньше чем они хотели и они выпустили разъяснение, что нужно сначала обложить начисления 15% и 17% процентами, а из остатка вычитать ранее рассчитанный ЕСВ (таким образом завышена база для 17%). Так вот в письме все очень просто — разъяснение дается с формулами знакомыми всем по школьной алгебре. Такие правки легко и просто вносить «неспециалистам» (достаточно найти только «где»). А вот сможет ли среднестатистический выпускник школы со знаниями алгебры и с пониманием «что от него хотят налоговики» подправить правила Пролога?
Вероятно по этой причине императивные языки (такие как 1С, Basic, Pascal, С, Java и прочие) более популярны и понятны для неспециалистов, чем логические и функциональные. Согласен с вами, но вы говорите об инфраструктуре программы 1С, а не языка. Если пользователям дать удобный интерфейс редактировать таблицы в БД и рассказать в какой таблице подредактировать, то он прекрасно будет справляться и даже полюбит эту функциональность, так как никого не надо будет звать. Вершиной программирования для непрограммистов я все же считаю Excel, потому что людям не надо пользоваться дополнительными программами и не надо искать (!), где редактировать. Все прямо in place (WYSIWIG). К сожалению Excel зародился standalone программой, а если бы он изначально использовался как корпоративная база данных и база функций, то ничего бы другого и не надо было. Для начала скажу, что мне тоже кажется неправильным говорить что Пролог единственный декларативный или «логический» язык программирования.
В каком-то смысле это даже не совсем язык программирования, ведь все задачи решаются одним и тем же методом — перебора. Но его описательная мощь и простота удивительна! Что касается Пролога и курса Логического программирования и Искусственного Интеллекта, то они мне очень понравились — это реально весело. И мне очень нравится что они заставляют программистов думать совершенно по-другому.
Упоминая о создании пролога нужно ещё и говорить о том, что решение задач методом полного перебора вариантов (а это то как он их решает, строит деревья решений) является долгим и неэффективным при использовании именно детерминированных машин. Конечно, не детерминированных пока не существует (и на мой взгляд и не будет, потому что не может), но это задача пока официально не решена, а в то время инженеры-программисты её очень надеялись решить, поэтому создатели Пролога могли надеяться на его более успешное распространение Пролог действительно очень легко воспринимается теми, кто не сталкивался с программированием (и наверное воспринимается ими легче, чем теми кто программировал, но не сталкивался с Прологом). Отношения между объектами в Прологе описываются очень легко и красиво, почти в категориях естественного языка.
Именно поэтому люди его легко понимают.Он изначально создавался для того, чтобы любой человек мог описать задачу На Прологе иногда очень легко реализовывать задачи, которые написаны на обычных, императивных, языках программирования, и наоборот. Например решается на Прологе таким же количеством строк кода, сколько предложений уходит на её описание в текстовом виде. А вот на императивных языках Вам бы ещё долго пришлось бы описывать алгоритмы перебора. Ну как правильно написал vics001, в вашем случае и X и Y в is — переменные. Пролог еще не знает чему они равны, когда видит предикат is. Он не может вычислить X знаю Y, либо наоборот, поэтому обозлиться на вас. Для таких вещей нужен SMT-solver, Пролог такое не умеет (кроме некоторых академических диалектов, которые пишутся на раз для того чтоб опубликовать статью).
В моём же случае, сначала находится X из предиката seq/1. Теперь Х имеет какое-то значение, и значение N находится уже зная его, как будто это просто присваивание (хоть это и не совсем так). алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно) Это не так.
Во-первых метод резолюций, а не алгоритм. Во-вторых, метод резолюций — это доказательство суждения методом утверждения на основе опровержения. То есть доказательство основано на опровержении обратного утверждения. Это не то же самое, что доказать любую теорему, поскольку метод не всегда дает результат но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание Здесь Вы не правы, основная проблема Пролога, которая в свое время затормозила его развитие — необходимость наличия как раз служебных предикатов, как assert, что делает его не совсем чистым декларативным, а добавляет черты процедурности. Также в спецификации Пролога определен служебный предикат not (как раз логическое отрицание) и некоторые другие, которые делают правила Пролога не хорновскими дизъюнктами. Вы правы, метод (!) резолюций, а последовательность в какой проводить резолюции между дизъюнктами, образует алгоритм (например, простейший алгоритм — метод линейной резолюции).
Алгоритм действительно доказывает любую теорему, если доказательство существует. Технически берется утверждение, которое необходимо доказать и его отрицание добавляется в теорию (к начальным аксиомам).
Если теория оказывается противоречивой, значит, противоречие будет найдено (это гарантирует метод резолюций) и значит теорема верна. Формально если проследить все резолюции дизъюнктов приведшие к противоречию, это и будет доказательство «от противного». Если утверждение не является теоремой, то вывод достаточно печален, доказать это может и не получится.
Определение предиката not через отсечение: not(A):- A,!, fail. Если бы отрицание было действительно логическим то в Прологе бы допускалась запись вида: A;B;C:- D, E, F. В принципе появление логического отрицания равносильно появлению логического Или. Если бы резолюция доказывала любую теорему, математика бы вымерла. Повторюсь, опровержение противоположного утверждения не всегда возможно, метод резолюции не всегда дает ответ об истинности исходного утверждения.
Программа Пролог
Вообще, метод резолюции по определению позволяет доказать невыполнимость множества дизъюнктов, а применительно к доказательству теорем его возможности весьма ограничены. простейший алгоритм — метод линейной резолюции алгоритм и метод — не одно и то же.
Хотя это вопрос терминологии. Отсечение само по себе есть элемент процедурности. Проблема с отрицанием заключается именно в потери дизъюнктом вида хорновского, что приводит к теоретическим ограничениям. В Дейталоге, например, отсечения и отрицания нет, поэтому он является более чистым, чем Пролог.
A;B;C:- D, E, F. Пролог по определению имеет дело с хорновскими дизъюнктами. Представленная запись — не он. Вторую часть я прокомментировать не могу, так как потерял суть обсуждения. А вот первую вполне, так как хотел бы сделать это абсолютно понятным для всех даже далеких от математики. Метод резолюций докажет любую верную теорему, если она представляется логикой первого порядка. Возможно на это потребуется 100 лет современного компьютера, но это теоретически не важно.
Истинность исходного утверждения равносильна противоречивости теории, состоящей из аксиом и отрицания исходного утверждения. Для использования для доказательства реальных утверждений в математике встречаются вполне конкретные сложности: 1. Обычно в математике встречаются теории с равенством, то есть используется отношение равенства 2.
Даже в простейшая арифметика является теорией второго порядка (позволяет использовать кванторы для предикатов, для любого предиката и т.п.), потому что содержит математическую индукцию. Формализация современной математики, то есть приведение все к букве закона математической логики, встречает сопротивление других математиков, которые считают, что излишняя формализация затрудняет понимание и останавливает прогресс математики. Ведь еще Гедель доказал, что любая теория должна постоянна пополняться аксиомами, наиболее правдивыми в реальности. В общем, для того, чтобы сформулировать теорему Мат Анализа, потребуется много работы и я еще не видел ни одного автоматического доказательства теоремы из Мат. Вот эта книга в принципе все рассказывает в подробностях: Чень Ч., Ли Р. // Математическая логика и автоматическое доказательство теорем И да главная теорема о группах была сначала доказана при помощи компьютера, а потом была переписана на 500 страниц.
Из-за чего возник большой математический спор может теоремы доказанные компьютером должны проверяться тоже компьютером. Еще одним примером является задача о раскраске планарных графов в 4 цвета. Книгу читал, спасибо. Ваше объяснение корректно, собственно, я и хотел, чтобы в статье было уточнение «любая теорема, представимая в виде множества дизъюнктов логики первого порядка».
Но никак не «любая теорема, это неверно. Гедель не доказал, а выдвинул предположение. А для метода резолюции характерной чертой является комбинаторный взрыв количества опорных утверждений (исходных дизъюнктов и их резольвент). Так что Ваше утверждение ну уж очень громкое. Насчет второй части я поясню.
Пролог имеет дело с хорновскими дизъюнктами, поскольку для них метод резолюции имеет самую простую форму. В хорновских дизъюнктах допустимо только одно утверждение с отрицанием, посему выражение вида pred(X, Y):- not(X), pred1(X, Y).
Пролог Скачать
(выражение утрированное) не является хорновским дизъюнктом, что приводит к определенным проблемам (каким — разговор отдельный). И относительно оператора отсечения и служебных предикатов. Из-за них Пролог не является чистым декларативным языком, поскольку для него характерно: 1. Чувствительность к порядку 2. Оператор отсечения и предикаты типа assert явно задают порядок вычислений, т.е.
Приводят к потере декларативной природы. Алгоритм унификации Prolog'а настолько тривиален, что откровенно непонятно, зачем в современном мире привязываться к его (откровенно устаревшим) реализациям.
Вот, скажем, Prolog реализованный в Haskell в 200 строчек: А вот — более идиоматичный вариант реализации той же идеи: DCG, несомненно, хороши — но у них есть ряд недостатков, успешно решённых в eDSL-парсерах того же Haskell (с тем же успехом способных разбирать контекстно-зависимые грамматики, причём заметно эффективней). Нужно ли учить Prolog? Несомненно — настолько же, насколько нужно учить механизм работы тайпчекера Хиндли-Милнера.
Стоит ли использовать в работе именно Prolog, а не какую-нибудь из современных реализаций его идей?