для чего нужна математическая логика
Для чего нужна математическая логика
ну а теперь немного о жизни.
В математической логике было дано точное определение алгоритма и вычислимости. Вопрос о существовании алгоритмов имеет для математики первостепенное значение (например, алгоритм существования решений для системы уравнений). Были получены разрешающие алгоритмы для ряда теорий, например, элементарной геометрии, упорядоченного поля действительных чисел, атомной булевой алгебры и т.д. Неразрешимы теории (т.е. не существует единого алгоритма для решения всех задач) элементарной арифметики, анализа, класса всех конечных симметрических групп (т.е.групп перестановок), аксиоматических систем теории множеств.
В последние годы большое внимание уделяется теории сложности алгоритмов и вычислений. Выяснилось, что одного только существования алгоритма, решающего ту или иную массовую проблему, далеко не достаточно для практики. После уточнения понятия сложности вычисления стали исследовать вопросы такого рода, как внутренняя сложность вычислимой функции, ее криптографическая стойкость, приобретающие особую актуальность с развитием сетей связи, вычислительной техники и автоматизированных систем управления.
а историю с философией вы зачем учите. чтобы мозг ваш начал учиться анализировать ситуацию вокруг вас.
а зачем вы учили матанализ и геометрию. наверное, чтобы потом написать какие-то полезные программы для решения конкретных практических задач!
метод резолюций, например, является основой логического программирования (а это, в свою очередь, база в разработке систем искусственного интеллекта и экспертных систем)
формулы алгебры логики используюстя в РКС, на которых построена любая ЭВМ.
с их же (формул) помощью решаются довольно легко различные логические задачи, где есть куча условий и их все нужно проанализировать, свести во едино и сделать верное умозаключение.
спросите, зачем вам нужна эта наука? так вы же пришли учиться в вуз! если вам нужны знания только для выполнения механической работы, связанной с компами, сетями и прочим, тогда надо было идти в техникум, там не углубляются в теоретическую науку настолько!
Зачем мы изучаем математическую логику?
Логика есть наука о законах и формах познающего мышления. Логика изучает мышление, но не всякое мышление, а лишь те мыслительные процессы, которые направлены на обнаружение и обоснование истины, на решение некоторой задачи, на поиск путей преодоления тех или иных трудностей, встающих перед нами как в профессиональной деятельности, так и в обыденной жизни.
В этом отношении логика сходна с грамматикой, которую мы изучали в школе. Грамматика тоже исследует и описывает формы языковых выражений, отвлекаясь от их содержания. Известное стихотворение «Бармаглот» из «Алисы в Зазеркалье» Льюиса Кэрролла начинается со следующих строк:
«Варкалось. Хливкие шорьки
И хрюкотали зелюки,
Как мюмзики в мове.»
При изучении логики мы вводим различные формальные языки. Дело в том, что формальные языки всегда проще, чем структура естественных языков. Иногда естественный язык может быть очень сложен.
Вот как, например, Марк Твен обыгрывает особенности словообразования в немецком языке [25, с. 59]:
Однажды в тех местах, в городе Шраттертроттэле, был схвачен негодяй, убивший готтентотку, мать двоих детей.
Преступника поймали и за неимением других помещений посадили в одну из клеток для кенгуру, о которых выше было сказано. Он бежал, но снова был изловлен. Счастливый своей удачей, негр-охотник быстро явился к старшине племени.
— Как какого? Этого самого! Латтенгиттерветтеркоттэрбейтельратте.
— Яснее! Таких у нас много… Непонятно, чему ты так радуешься?
— Я поймал щраттертроттэльхоттентотенмуттэраттэнтэтэр-латтенгиттерветтеркоттэрбейтельратте! Вот кого!
Тут начальник подскочил, точно подброшенный пружиной:
— Так что же ты мне сразу не сказал этого так коротко и ясно, как сейчас?!»
Математическая логика, возникшая почти 100 лет назад в связи с внутренними потребностями математики, нашла применение в теоретическом и практическом программировании и, судя по всему, взаимодействие этих двух наук в недалеком будущем сможет принести новые плоды.
Почему программисты обратились к математической логике, а логики заинтересовались программированием? Математическая логика, занимается построением формальных языков, предназначенных для представлений таких фундаментальных понятий, как функция, отношение, аксиома, доказательство, и изучение основанных на этих языках логических и логико-математических исчислений.
Для формализации семантики программы (это полезно при разработке трансляторов) необходим аппарат математической логики (уже использовались : l-исчисление Черча, теория областей Дана Скотта).
Другие приложения математической логики в программировании:
теория логического вывода:
правильность программ относительно спецификаций:
задачи представления и обработки знаний;
проблемы сложности вычислений;
элементная логическая база компьютеров.
Что такое ЛОГИКА – зачем она нужна. Виды логики
Логика. Не каждый человек задумывался о том, что такое логика. Хотя логическое мышление присутствует в жизни повсеместно от простых бытовых дел до решения сложных математических задач. Оно неотделимо от науки и творчества, повседневных диалогов и решения насущных дел.
Логика – что это?
Этот термин имеет древнегреческие корни. Он образован от древнегреческого слова «логос», что понимают, как слово, рассуждение, мысль, смысл или разум. Самое простое определение логики – это наука о правильном мышлении, здравомыслии. Она зародилась примерно в V в. до н.э. благодаря трудам философа и мыслителя Аристотеля, который и считается основателем традиционной логики.
Существуют и другие толкования:
Зачем нужна логика?
Основной целью логического мышления является изучение определенной последовательности событий, явлений или действий, их взаимосвязи. То есть человек с помощью разума накапливает имеющиеся знания, аккумулируя их из разных источников, и строит причинно-следственные связи. Индивид руководствуется не своим эмпирическим опытом, а достоверными фактами.
Разобравшись с тем, что такое логика, можно сделать вывод о ее необходимости для:
Виды логики
Благодаря сохранившимся историческим документам доподлинно известно, что логика как наука о законах и формах мышления зародилась примерно 2500 лет назад. С тех пор она претерпевала определенные изменения, которые привели к выделению трех основных видов логики:
Формальная логика
Самым древним считается раздел философии под названием формальная, формально-фактическая или дискретная логика, отцом которой и был знаменитый Аристотель. Он рассматривал эту науку как возможность восприятия и оперирования формальными фактами и связями между ними без учета содержания. Выясняя, какие проблемы решает формальная логика, отметим, что она проверяет правильность рассуждений в современном мире. Важно абстрагироваться от конкретики и учитывать только общую форму суждения или вопроса.
Простым примером можно назвать констатацию факта: «на улице тепло и сухо, поэтому я пойду и прогуляюсь». Такой тип мышления заложен в каждом человеке, ведь впервые видя собеседника, индивид оценивает его внешний вид и подмечает другие особенности, складывая пазл в единую картину. Если же увиденное не соответствует принятым стандартам, то шаблон ломается.
Математическая логика
В начале XIX в. традиционная формальная теоретическая логика пополняется арсеналом математических методов с использованием искусственных языков. Так сформировалась символическая или современная логика, как ее принято называть. Математический подход позволил вывести способность к рассуждению ученых в разных областях науки на новый уровень,
Такая модель упрощает процесс познания благодаря замене слов привычного языка, которые могут нести двусмысленность и неточность, формальными символами. Многие проблемы, которые изучает математическая логика, невозможно сформулировать привычными словесными выражениями с использованием известных методов. Нередко такую науку в более широком плане причисляют к металогике или метаматематике.
Диалектическая логика
Немецкий философ Гегель и последователи марксистской материалистической теории основатели так называемую диалектическую логику, базой для развития которой стала дискретная логика. В ее основе лежит метод руководства не только формой, но и содержанием явлений, объектов и процессов. То есть такая наука о познавательной деятельности может рассматривать не отдельные противоположности, а их связь и схожесть между собой. У этого раздела философии существуют свои законы и принципы:
Законы логики
Как и в любой науке, здесь существуют определенные правила. Закон логики – это принцип, которому необходимо следовать, чтобы из истинных суждений получить правильный вывод. Их разработал и сформулировал еще Аристотель, изучая формальную логику, в которой использовались словесные суждения. Существует четыре базовых закона, нарушение которых приводит к появлению умышленных или неумышленных ложных выводов:
Закон тождества
Изучая, что такое наука логика, непременно сталкиваются с ее первым законом тождества или равенства. Некоторые именуют его принципом постоянства. Суть состоит в том, что на всем протяжении логического рассуждения изначальное понятие должно сохранять свой первоначальный смысл. Искажение, которое свойственно многим языкам и двойственность, многозначность, могут привести к ложным выводам.
Примером несоблюдения этого принципа является простой диалог:
Закон непротиворечия
Еще одним фундаментальным постулатом является закон непротиворечия. Его суть состоит в том, что два противоположных высказывания не могут быть одновременно истинными. Одно или оба из них обязательно окажутся ложными. Можно привести простой пример иллюстрации этого закона:
Закон исключенного третьего
Нередко студенты изучая, что такое наука логика, путают предыдущий закон с принципом исключенного третьего. Они схожи, но суть каждого все же отличится. Этот закон сформулирован так, что истинным может быть либо само суждение, либо же его отрицание. Третьего не дано. То есть закон оперирует не противоположными понятиями, а противоречащими друг другу. К примеру:
Закон достаточного основания
Четвертый закон – логического мышления, был сформулирован не Аристотелем, а лишь в XVIII в. озвучен Готфридом Лейбницем. Суть принципа состоит в том, что любой тезис будет иметь силу только тогда, когда будет подтвержден аргументами. Причем они должны быть такими, чтобы исходная мысль четко вытекала из них.
Самым ярким и знаменитым примером применения закона достаточного основания в жизни является принцип так называемой презумпции невиновности:
Как развить логику?
Многие философские термины и примеры могут показаться обывателю сложными и мало применимыми в обычной жизни. Однако каждый из указанных выше законов мы часто неосознанно можем встретить в любом споре или диалоге, когда собеседники, стремясь ввести друг друга в заблуждение, сознательно или неосознанно их нарушают. Навыки того, как развить логическое мышление, могут пригодиться каждому индивиду для достижения успехов в разных сферах науки и жизни.
Логическое мышление закладывается у человека в раннем возрасте, а умение мыслить абстрактно формируется примерно в 7-8 лет и развивается всю жизнь. Для качественного и полноценного его развития нейропсихологи советуют:
Логика математическая
Математическая логика — это раздел современной формальной логики (см. Логика формальная), в котором логические выводы исследуются посредством логических исчислений на основе математического языка, аксиоматизации и формализации. В качестве другого названия современного этапа в развитии логики (см. Логика) используется также термин «символическая логика» (см. Логика символическая). Иногда термин «математическая логика» употребляется в более широком смысле, охватывая исследование свойств дедуктивных теорий, именуемое металогикой (см. Металогика) или метаматематикой. В целом, определение «математическая логика» подчёркивает её сходство с математикой, основывающееся, прежде всего, на методах построения логических исчислений на основе строгого символического языка, аксиоматизации и формализации. Они позволяют избежать двусмысленной и логической неясности естественного языка, которым пользовалась при описании правильного мышления традиционная логика, развивавшаяся в рамках философии (см. Философия).
Математические методы дали логике такие преимущества, как высокая точность формулировок, возможность изучения более сложных, с точки зрения логической формы, объектов. Многие проблемы, исследуемые в математической логике, вообще невозможно было сформулировать с использованием только традиционных методов. Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном (формализованном) языке. Такие точные языки имеют две составляющие: синтаксис (см. Синтактика) и семантику (см. Семантика). Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие — нет.
Уже в Античности (в частности Аристотелем) широко применялись буквенные обозначения для переменных. Идея построения универсального языка для всей математики, для формализации на базе такого языка математических доказательств и вообще любых рассуждений выдвигалась в XVII веке Г. В. Лейбницем. Но только к середине XIX века стало очевидным, что существующая логическая парадигма, а именно аристотелевская силлогистика (см. Силлогистика), уже не отвечает требованиям развития науки того времени. С одной стороны, значительные успехи абстрактной алгебры в особенности в теории групп позволили перенести алгебраические методы на другие области науки. Это с успехом проделала английская школа, основоположником которой можно считать А. де Моргана, который в 1847 году опубликовал книгу «Formal Logic; or The Calculus of Inference, Necessary and Probable». Им открыты названные в его честь законы де Моргана, разработана теория отношений и в 1838 определено понятие математической индукции.
Однако наибольшую известность получили работы Дж. Буля. В 1847 году он публикует брошюру «Mathematical Analaysis of Logic», а в 1854 — свой главный труд по логике «An Investigation into the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probabilities». Как и де Морган, Дж. Буль был одним из тех математиков из Кембриджа, которые признали чисто абстрактную природу алгебры. Они заметили, что простейшие операции над множествами подчиняются законам коммутативности, ассоциативности и дистрибутивности. Оставалось только провести аналогию между объединением и сложением, пересечением и умножением, пустым классом и нулём, универсальным классом и единицей. Работы Буля 1847 и 1854 годов можно считать началом алгебры логики (см. Алгебра логики), первоначальный этап развития которой был завершён Э. Шрёдером в трёхтомной монографии «Vorlesungugen uber die Algebra der Logik» (1890–1905).
С другой стороны, возникновение и развитие математической логики связано с работами Г. Фреге и Ч. С. Пирса. После того, как Фреге в 1879 и Пирс в 1885 году ввели в язык алгебры логики предикаты, предметные переменные и кванторы, возникла реальная возможность построения системы логики в виде логического исчисления, что и было сделано Фреге, который по праву считается основателем математической логики в её современном понимании. Пытаясь реализовать идеи Лейбница, Фреге в своём труде «Begriffsschrift» предложил символическую запись для строгих рассуждений. Хотя его нотация сейчас совсем не используется (например, формулы рисовали в виде двумерного дерева), Фреге в действительности впервые построил исчисление предикатов. Исчисление предикатов есть формальная система, состоящая из двух частей: символического языка и логики предикатов (см. Логика предикатов). Кроме этого для исчисления предикатов Фреге даёт строгое определение понятия «доказательство», которое является общепринятым и по сей день.
Основы современной логической символики были разработаны Дж. Пеано, чьи интересы, как и Фреге, концентрировались вокруг оснований математики и развития формально-логического языка. Его широко известный труд «Formulaire de mathématiques», опубликованный (в соавторстве) в годах, был нацелен на развитие математики в её целостности, исходя из некоторых фундаментальных постулатов. Логическая запись Пеано была принята, хотя и частично модифицирована, А. Н. Уайтхедом и Б. Расселом в их широко известной трёхтомной «Principia Mathematica» (1910–1913), а затем воспринята Д. Гилбертом. Таким образом, в логику был введён символический язык. Создание такого искусственного языка и с его помощью таких объектов, как логические исчисления, строго формализующие различные теории в виде некоторого конечного списка аксиом и правил вывода, было вызвано, в первую очередь, потребностями математики, ставившей проблемы, для решения которых средства традиционной логики были непригодны.
Основным стимулом развития математической логики в начале XX века была проблема оснований математики. К. Вейерштрасс, Р. Дедекинд и Г. Кантор показали, что в качестве фундамента всей классической математики может рассматриваться арифметика целых чисел. Дедикинд и Пеано аксиоматизировали арифметику, а Фреге дал определение натурального числа как множества всех равномощных множеств. Таким образом, вся математика сводилась к теории множеств. Рефлексия над феноменом множеств привела к обнаружению ряда парадоксов в теории множеств, ответом на которые стало развитие четырёх направлений в основаниях математики:
Развитие и применение технического аппарата самой логики в первую очередь относится к программе Д. Гилберта (начиная с 1904 года), где была поставлена главная задача: найти строгое основание для математики посредством доказательства её непротиворечивости, то есть доказательства того факта, что в ней недоказуема никакая формула вида A вместе с формулой
А. Для этого потребовалось развить теорию доказательств, после чего, считал Гилберт, используя только финитные методы, можно будет доказать непротиворечивость теории множеств и самой теории действительных чисел и таким образом решить проблему оснований математики. Однако результат К. Гёделя о неполноте арифметики (1931) убедительно показал, что программа Гилберта невыполнима. Теорема Гёделя о неполноте утверждает, что всякая достаточно богатая теория необходимо содержит утверждения, которые нельзя ни доказать, ни опровергнуть, не опровергнув самой теории.
С годов XX века начинается современный этап развития математической логики. Он связан с применением точных методов при изучении формальных аксиоматических задач. Суть их состоит в описании рассматриваемой теории на базе строгого логико-математического языка (формализация), с последующими процедурами логического анализа теории, а именно с точки зрения непротиворечивости (например, таких теорий, как элементарная геометрия, арифметика, анализ достаточно надёжных оснований) и полноты. Основным объектом современной математической логики являются исчисления. В качестве их компонентов выступают: язык (формальный); аксиомы; правила вывода. На их основе стало возможным дать точное определение доказательства, получить точные утверждения о невозможности доказательства тех или иных предложений теории.
Обширным полем деятельности для современной математической логики является теория рекурсии, которая в первую очередь имеет дело с проблемой разрешимости: доказуема или нет формула A из некоторого множества посылок. Эти исследования привели к теориям вычислимости, к созданию компьютерных программ автоматического поиска доказательств. Решение проблемы разрешимости послужило основным стимулом для создания теории алгоритмов. Формулировка тезиса Чёрча — Тьюринга, утверждающего, что понятие общерекурсивной функции является уточнением интуитивного понятия алгоритма, стало наиболее важным достижением математической логики. Только после уточнения понятия алгоритма выяснилось, что в хорошо известных разделах математики существуют алгоритмически неразрешимые проблемы.
Важное место в современной математической логике занимает теория моделей (см. Теория моделей), которая изучает фундаментальные связи между синтаксическими свойствами множеств предложений формального языка, с одной стороны, и семантическими свойствами их моделей, с другой; и вообще, изучаются соотношения между моделями и теориями, а также преобразование моделей. Зачастую модели используются как инструмент для того, чтобы показать, что некоторая формула A не может быть дедуцирована из определённого множества постулатов или, если A есть аксиома, то показать недоказуемость A из остальных аксиом системы, к которой A принадлежит (если это возможно). Тогда A является независимой аксиомой.
Наряду с этим стало очевидно, что те впечатляющие результаты, которые были получены средствами математической логики, и в первую очередь в области оснований математики, привели к некоторому гипостазированию функции и предмета самой этой логики. Так, в предисловии к «Handbook of Mathematical Logic» (1977) Дж. Барвайс пишет: «Математическая логика традиционно подразделяется на четыре раздела: теория моделей, теория множеств, теория рекурсии и теория доказательств». В свою очередь в «Encyclopedia Britanica» (CD–1998), уже применительно к математической логике, четыре указанных раздела названы «четырьмя главными областями исследования». Более точно было бы говорить о применении технического аппарата логики в данных областях, поскольку теория множеств и теория рекурсии сами по себе являются самостоятельными математическими дисциплинами и не являются частью математической логики. Теория доказательств для некоторых математиков-логиков превратилась чуть ли не в «метаматематику» (термин Гилберта), а теория моделей давно вышла за пределы логической семантики.
Развитие современной логики показывает, что термин «математическая логика» постепенно сужается и часто используется для обозначения области исследования тех типов рассуждений, которыми пользуются математики, тем самым приобретая всё большее методологическое и прикладное значение, прежде всего в рамках вычислительной математики и связанных областей. В целом, символизация и представление различных логических теорий в виде исчислений стало обычным делом и поэтому строго разделить современные логические исследования на относящиеся к математической логике и не относящиеся к ней порой просто невозможно.
Роль логического программирования, и стоит ли планировать его изучение на 2021-й
Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.
Итак, пришло время второй ссылки. Что это будет? Статья на Хабре? Может быть статья на ином ресурсе? Прочитав пару первых абзацев на разных сайтах, вы, скорее всего, мало что поймете, так как, во-первых, материал обычно ориентирован на знающего читателя, во-вторых, хорошей и понятной информации по теме не так много в русскоязычном интернете, в-третьих, там почему-то постоянно речь идёт о некоем «прологе» (речь о языке программирования Prolog, разумеется), но сам язык, кажется, использует мало кто (почётное 35 место в рейтинге TIOBE). Однако наш герой не теряет мотивации и, спустя некоторое время, натыкается на эту самую статью, желая, все-таки понять:
Что такое логическое программирование
Какова история его создания и фундаментальные основы (серьезно, какому новичку это может быть интересно?)
Зачем и где его применяют
Стоит ли лично вам его изучать
Что ж, постараюсь ответить просто и понятно, обходя страшные термины и не вспоминая исторических личностей.
Что такое логическое программирование
В школе на уроках информатики многие, если не все, слышали про Pascal (а кто-то даже писал на нем). Многие также могли слышать про Python, C/C++/C#, Java. Обычно программирование начинают изучать именно с языков из этого набора, поэтому все привыкли, что программа выглядит как-то так:
Этот яркий, но малоинформативный пример призван показать, что обычно команды выполняются одна за другой, причем мы ожидаем, что следующие инструкции (команды) могут использовать результат работы предыдущих. Также мы можем описывать собственные команды, код которых будет написан подобным образом. Остановимся на том, что как завещал Фон Нейман, так компьютер и работает. Машина глупа, она делает то, что скажет программист, по четкому алгоритму, последовательно выполняя инструкции. Не может же, в конце концов, компьютер, подобно мыслящему живому существу, делать выводы, строить ассоциативные ряды… Или может?
Давайте устроимся поудобнее рядом со своим компьютером и порассуждаем о жизни и смерти вместе с Аристотелем:
Следовательно, Сократ смертен.
Звучит логично. Но есть ли способ научить компьютер делать выводы как Аристотель? Конечно! И вот тут мы вспомним о Prolog-e, который так часто мелькает при поиске информации о логическом программировании. Как несложно догадаться, Prolog (Пролог) является самым популярным чисто логическим языком программирования. Давайте рассуждения об этом языке оставим на следующие разделы статьи, а пока что продемонстрируем «фишки» логических языков, используя Пролог.
Напишем небольшую программу, где перечислим, кто является людьми (ограничимся тремя) и добавим правило «всякий человек смертен»:
Что ж, давайте спросим у компьютера, смертен ли Сократ:
Компьютер выдал нам сухое «true», но мы, конечно, вне себя от счастья, так как вот-вот получим премию за успешное прохождение нашим умным устройством теста Тьюринга.
Предикат a от трех аргументов вернет истину, если удастся доказать истинность предикатов b, c и d. Читаются правила справа налево следующим образом: «Если b от X истинно И c от Y, Z истинно И d истинно, то a от X, Y, Z истинно».
Уже на таком небольшом примере видно, что мы не описываем четко последовательность действий, приводящую к нужному результату. Мы описываем необходимые условия, при выполнении которых результат будет достигнут. Тут будет к слову упомянуть, что раз компьютер сам для нас выводит способ достижения результата на основе известных правил, то и использовать один и тот же код можно по-разному:
Теперь начнём делать запросы к программе (всё те же предикаты):
Как видите, очень удобно. Стало быть, первым и очевидным применением логического программирования (об эффективности поговорим ниже) является работа с базами данных. Мы можем достаточно естественным образом описывать запросы, комбинируя предикаты, причем научить писать такие запросы можно даже человека, совершенно не знакомого с логическим программированием.
Какие задачи и как можно решать с помощью логического программирования
Давайте рассмотрим ряд учебных примеров (без подробного описания, все же статья обзорная) и подумаем, как те или иные подходы можно применять в реальной жизни. Начну с примера, призванного продемонстрировать, почему логическое программирование удобно, и за что же его любят математики. А именно, опишем правила вычисления производной:
Пусть производная получилась довольно громоздкой, но мы и не ставили цель её упростить. Главное, из примера видно, что правила вывода производной на Prolog-е описываются очень близким образом к их математическому представлению. Чтобы сделать подобное на привычных языках программирования, пришлось бы вводить понятие дерева выражений, описывать каждое правило в виде функции и т. д. Тут же мы обошлись 8-ю строками. Но здесь важно остановиться и задуматься: компьютер не начал работать как-то иначе, он все ещё обрабатывает последовательности команд. Стало быть, те самые деревья, которые где-то все-таки должны быть зашиты, чтобы программа работала, действительно присутствуют, но в неявном виде. Деревья эти именуют «деревьями вывода», именно они позволяют подбирать нужные значения переменных, перебирая все возможные варианты их значений (существует механизм отсечения, который является надстройкой над логической основой языка, но не будем об этом).
Давайте на простом примере рассмотрим, что из себя представляет перебор, а затем то, чем он может быть опасен.
Ага…то есть Петя, Петя и ложь… Что-то не так, подумает программист и попробует разобраться. На самом деле, перебирая все варианты значений X, Пролог пройдёт по такому дереву:
Представим, что перед нами в ячейках расположены три чёрных и три белых шара (как на картинке выше), которые требуется поменять местами. За один ход шар может или передвинуться в соседнюю пустую клетку, или в пустую клетку за соседним шаром («перепрыгнуть» его). Решать будем поиском в ширину в пространстве состояний (состоянием будем считать расположение шаров в ячейках). Суть этого метода заключается в том, что мы ищем все пути длины 1, затем все их продления, затем продления продлений и т. д., пока не найдем целевую вершину (состояние). Почему поиск в ширину? Он первым делом выведет самый оптимальный путь, то есть самый короткий. Как может выглядеть код решения:
Со стороны улучшения алгоритма можно предложить использовать поиск в глубину. Но как же, он ведь не даст оптимального результата? Сделаем просто: ограничим глубину поиска. Так мы точно не забьём стек и, возможно, получим ответ. Поступим так: проверим, есть ли пути длины 1, затем длины 2, затем длины 4 и т. д. Получим так называемый поиск с итерационным заглублением:
Во-первых, здесь стоит обратить внимание, что мы не используем очереди, а также внешних предикатов (кроме reverse, но он для красоты). Это потому, что поиск в глубину естественен для Пролога (ищите картинку с деревом выше). Во-вторых, пусть мы и делаем вроде как «лишние» действия, то есть для каждого нового значения глубины проходим по всем путям заново, мы практически не теряем в скорости относительно поиска в ширину (может в несколько раз, но не на порядок), при этом значительно экономим память. В-третьих, мы наконец-то получаем ответ, и это самое главное. Приводить его не буду, так как он займет много места, но для интриги оставлю вам его длину: 16.
С другой стороны, задачу можно было бы решить, не меняя код поиска, а лишь изменив правила перемещения шаров. Обратим внимание, что нам заранее известны входные и выходные данные. Приглядевшись становится понятно, что нет никакого смысла в движении фишек «назад». Действительно, если чёрным нужно встать в правые позиции, то какой смысл делать ходы влево? Перепишем предикаты движения:
Хм, код стал даже проще. Запустив мы убедимся, что поиск (оба варианта), во-первых, работает, во-вторых, работает быстро, в-третьих, работает быстро и выводит результат. Это успех. Мало того, что мы решили задачку, только что был создан самый настоящий искусственный интеллект. Программа получает входные данные и желаемый результат, а затем сама ищет, как его достигнуть. Да, это однозначно успех.
Зачем и где применяют логическое программирование
Давайте вернемся к рассмотренным примерам и попробуем представить, как это можно использовать на практике.
И тут крайне важно отметить, что решения на логических языках оказываются столь же неэффективны, сколько удобны (если речь не идёт о нишевых, специализированных решениях). Программа на императивном языке всегда обгонит аналогичную программу на логическом, но затраты на написание кода в ряде случаев (в том числе описанных выше) падают в разы. На практике вы вряд ли столкнетесь именно с Prolog-ом. Он, конечно, выразителен (можно описывать сложные вещи просто), хорошо расширяется, на нем легко писать надежный код и решать определенные задачи (в т. ч. просто логические задачки), но есть и ряд недостатков: пролог сильно уступает по скорости императивным языкам, а также не особенно поддерживается и не развивается, что делает его применение на практике практически невозможным.
Стоит ли планировать его изучение на 2021-й
Тут оставлю своё субъективное мнение, разделённое на две части:
И здесь остаётся лишь пожелать продуктивного 2021-го года!
Хочется выразить особую благодарность Дмитрию Сошникову за знакомство с этой удивительной парадигмой.