uzluga.ru
добавить свой файл

Фразы Хорна.


Метод резолюций для логики высказываний

Метод резолюций можно применять к любому множеству дизъюнктов с целью проверки их невыполнимости (противоречивости). Рассмотрим сначала метод резолюций для логики высказываний.

Литеры A и ~A называются контрарными, а множество {A, ~A} – контрарной парой.

Допустим, что в дизъюнкте C1 существует литера L1 , контрарная литере L2 в дизъюнкте C2. Вычеркнем литеры L1 и L2 из дизъюнктов C1 и C2 соответственно и построим дизъюнкцию оставшихся дизъюнктов. Построенный дизъюнкт называется резольвентой дизъюнктов C1 и C2. Резольвента двух дизъюнктов является их логическим следствием. Резольвента двух единичных дизъюнктов (если она существует) – пустой дизъюнкт.

Резолютивный вывод C из множества дизъюнктов S есть такая конечная последовательность C1, C2, ..., Ck дизъюнктов, в которой каждый Ci (i=1, ..., k) или принадлежит S, или является резольвентой дизъюнктов, предшествующих Ci и Ck=C.

Дизъюнкт C может быть выведен или получен из S, если существует вывод C из S. Для невыполнимого множества дизъюнктов в результате последовательного применения правила резолюций получается пустой дизъюнкт.

Вывод из множества S пустого дизъюнкта называется опровержением (доказательством невыполнимости) S.

Фразы Хорна.

Дизъюнкт - это совокупность литер, одни из которых не содержат, а другие содержат знак отрицания. Если первые записывать через точку с запятой слева от знака ":-", а вторые - без знака отрицания через запятую справа от знака ":-" и в конце каждого дизъюнкта ставить точку, то получим выражение вида:

A1;A2;…;An:- B1,B2,…,Bm

Из каждых двух дизъюнктов, представленных в таком виде, используя метод резолюций, можно получить новый дизъюнкт, являющийся следствием двух первых. Если одна и та же атомарная формула появляется в левой части одного дизъюнкта (литера без отрицания) и в правой части другого (литера с отрицанием), то новый дизъюнкт, полученный в результате слияния исходных дизъюнктов и вычеркивания повторяющейся рассматриваемой атомарной формулы, является следствием исходных дизъюнктов. При форме записи это означает вычеркивание контрарных пар, находящихся по разные стороны от знака ":-". Например, даны два дизъюнкта:

A;B;C:-D,E,F.

G;H:-A,M,N.

Полученный в результате их слияния и вычеркивания повторяются литеры A новый дизъюнкт:

B;C;G;H:-D,E,F,M,N

является следствием исходных. Вычеркивание повторяющейся слева и справа от знака ":-" литеры А аналогично рассмотренномy ранее вычеркиванию контрарной пары А и ~А.

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

Если дизъюнкты содержат переменные, то для получения резольвенты атомарные формулы не обязательно должны быть идентичными, они должны быть лишь сопоставимыми (унифицируемыми). При сопоставлении формул происходит конкретизация значений переменных (конкретизация переменных), в результате которой формулы становятся идентичными. Например, при сопоставлении формул A(x) и A(b) происходит конкретизация переменной x, которая принимает значение, равное b.

Хорновский дизъюнкт - это дизъюнкт, содержащий не более одной литеры без отрицания. Например:

A:-B,C,D;

A:-B1,B2,Bn.

Приведенным хорновским дизъюнктам эквивалентны следующие формулы логики предикатов первого порядка:

BUCUD ®A;

B1UB2U Bn ®A

(переменные в этих формулах не указаны).

Существует два вида хорновских дизъюнктов.

Хорновский дизъюнкт с заголовком - это дизъюнкт, содержащий одну литеру без отрицания. Он может содержать одну или несколько литер с отрицанием или не содержать их вообще, например:

A:-B,C, ...,D;

A:-B;

A:-.

Последний из приведенных дизъюнктов можно записывать без знака ":-", то есть в виде А.

Хорновский дизъюнкт без заголовка - это дизъюнкт, не содержащий литер без отрицания, например:

:-B,C, ...,D;

:- A.

В результате применения метода резолюций к двум хорновским дизъюнктам с заголовками вновь получается хорновский дизъюнкт с заголовком. Известно, что пустой дизъюнкт не имеет заголовка. Следовательно, если все дизъюнкты имеют заголовки, то из них могут быть получены только дизъюнкты с заголовками.

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

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

Любая задача, которая может быть выражена с помощью хорновских дизъюнктов, должна иметь только один дизъюнкт без заголовка (целевой); все остальные дизъюнкты должны быть с заголовками (гипотезы).

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

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

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


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

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

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

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

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

При описании синтаксиса конструкций используются следующие обозначения:

Символ ::= читается как "по определению" ("это", "есть"). Слева от разделителя располагается объясняемое понятие, справа - конструкция, разъясняющая его. Например,

<Имя> ::= <Идентификатор>

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

Символ | означает в нотации БНФ "или", он применяется для разделения различных альтернативных растолкований определяемого понятия.

Пример. Десятичную цифру можно определить следующим образом:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать);

Пример. Запись <Целое число> ::= [-]<Положительное целое число>

означает, что целое число можно определить через положительное целое число, перед которым может стоять знак минус.

Символ * обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа *используют фигурные скобки ({,}).

Пример. Определить положительное целое число в нотации БНФ можно следующим образом: <Положительное целое число> ::= <цифра>[<цифра>]*.

То есть положительное целое число состоит из одной или нескольких цифр.

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

Предложения бывают двух видов: фактыправила.

Предложение имеет вид

A:-

B1,... , Bn.

A называется заголовком или головой предложения, а B1,..., Bn - телом.

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

Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факт - это предложение, у которого тело пустое.

Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде: мама(Наташа, Даша).

Факт представляет собой безусловно истинное утверждение.

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

Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:

<Предикат>::=<Имя> | <Имя>(<аргумент>[,<аргумент>]*),

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

Аргументом или параметром предиката может быть константа, переменная или составной объект. Число аргументов предиката называется его арностью илиместностью. Про переменные мы поговорим чуть-чуть позже, а подробное рассмотрение констант отложим до пятой лекции. Пока отметим, что константа получает свое значение в разделе описания констант, а переменная означивается в процессе работы программы.

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

Соответственно, приведенный выше пример факта можно записать в Турбо Прологе, например, так:

mother("Наташа", "Даша").

Некоторые предикаты уже известны системе, они называются стандартными или встроенными.

В Турбо Прологе предложения с одним и тем же предикатом в заголовке должны идти одно за другим. Такая совокупность предложений называется процедурой.

В приведенном выше примере про то, что Наташа является мамой Даши, мама - это имя двухаргументного предиката, у которого строковая константа "Наташа"является первым аргументом, а строковая константа "Даша" - вторым.

Правило - это предложение, истинность которого зависит от истинности одного или нескольких предложений. Обычно правило содержит несколько хвостовыхцелей, которые должны быть истинными для того, чтобы правило было истинным.

В нотации БНФ правило будет иметь вид:

<Правило>::=<предикат>:-<предикат>[,<предикат>]*.

Пример. Известно, что бабушка человека - это мама его мамы или мама его папы.

Соответствующие правила будут иметь вид:

бабушка(X,Y):-

мама(X,Z),мама(Z,Y).

бабушка(X,Y):-

мама(X,Z),папа(Z,Y).

Символ ":-" означает "если", и вместо него можно писать if.

Символ "," - это логическая связка "и" или конъюнкция, вместо него можно писать and.

Первое правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - мамой Y. Второе правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - папой Y.

В данном примере X, Y и Z - это переменные.

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

Переменные могут быть свободными или связанными.

Свободная переменная - это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.

Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким-то значением и ей сопоставлен некоторый объект, то эта переменная уже не может быть изменена.

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания "_". Анонимная переменная применяется в случае, когда значение переменной не важно. Каждая анонимная переменная - это отдельный объект.

Семантические модели Пролога

В Прологе обычно применяются две семантические модели: декларативная и процедурная. Семантические модели предназначены для объяснения смысла программы.

В декларативной модели рассматриваются отношения, определенные в программе. Для этой модели порядок следования предложений в программе и условий вправиле не важен.

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

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

Использование языка Пролог.


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

Однако, в отличие от некоторых приверженцев Пролога, я не склонен думать, что Пролог — лучший язык всех времен и народов, универсальный "решатель" любой задачи. На наш взгляд, для каждого языка существует свой класс задач, для решения которых он подходит лучше других языков программирования. Соответственно, для решения любой задачи есть оптимальный язык (языки) программирования. Многие задачи,хорошо решаемые императивными языками типа Паскаля и Си, плохо решаются на Прологе, и наоборот. Поэтому совсем даже неплохо, если человек владеет не одним инструментом решения задач, а может воспользоваться наиболее подходящим из имеющихся в его распоряжении. Давайте посмотрим, в каких областях наилучшим образом себя показал Пролог.

Основные области применения Пролога:

  • быстрая разработка прототипов прикладных программ;

  • автоматический перевод с одного языка на другой;

  • создание естественно-языковых интерфейсов для существующих систем;

  • символьные вычисления для решения уравнений, дифференцирования и интегрирования;

  • проектирование динамических реляционных баз данных;

  • экспертные системы и оболочки экспертных систем;

  • автоматизированное управление производственными процессами;

  • автоматическое доказательство теорем;

  • полуавтоматическое составление расписаний;

  • системы автоматизированного проектирования;

  • базирующееся на знаниях программное обеспечение;

  • организация сервера данных или, точнее, сервера знаний, к которому может обращаться клиентское приложение, написанное на каком-либо языке программирования.

Области, для которых Пролог не предназначен: большой объем арифметических вычислений (обработка аудио, видео и т.д.); написание драйверов.

Факты и правила в языке Пролог


Программист на Прологе описывает объекты (objects) и отношения (relations), а затем описывает правила (rules), при которых эти отношения являются истинными. Например, предложение:

Билл любит собак. (Bill likes dogs.)

устанавливает отношение между объектами Bill и dogs (Билл и собаки); этим отношением является likes (любит). Ниже представлено правило, определяющее, когда предложение "Билл любит собак" является истинным:

Билл любит собак, если собаки хорошие. (Bill likes dogs if the dogs are nice.)

Факты

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

Ниже представлено несколько предложений на естественном языке с отношением "любит" (likes):

Билл любит Синди. (Bill likes Cindy)

Синди любит Билла. (Cindy likes Bill)

Билл любит собак. (Bill likes dogs)

А теперь перепишем ли же факты, используя синтаксис Пролога:

likes (bill,cindy).

likes(cindy,bill).

likes(bill,dogs).

Факты, помимо отношений, могут выражать и свойства. Так, например, предложения естественного языка "Kermit is green" (Кермит зеленый) и "Caitlin is girl" (Кейтлин - девочка) на Прологе, выражая те же свойства, выглядят следующим образом:

green(kermit).

girl(caitlin).

Правила

Правила позволяют вам вывести один факт из других фактов. Другими словами, можно сказать, что правило - это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Ниже представлены правила, соответствующие связи "любить" (likes):

Синди любит все, что любит Билл. (Cindy likes everything that Bill likes)

Кейтлин любит все зеленое. (Caitlin likes everything that is green)

Используя эти правила, вы можете из предыдущих фактов найти некоторые вещи, которые любят Синди и Кейтлин:

Синди любит Синди. (Cindy likes Cindy)

Кейтлин любит Кермит. (Caitlin likes Kermit)

Чтобы перевести эти правила на Пролог, вам нужно немного изменить синтаксис, подобно этому:

likes(cindy,Something):-

likes(bill,Something).

likes(caitlin,Something):-

green(Something).

Символ :- имеет смысл "если", и служит для разделения двух частей правила: заголовка и тела.

Вы можете рассматривать правило и как процедуру. Другими словами, эти правила

likes(cindy,Something):-

likes(bill,Something)

likes(caitlin,Something):-

green(Something).

также означают: "Чтобы доказать, что Синди любит что-то, докажите, что Билл любит это" и "Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое". С такой "процедурной" точки зрения правила могут "попросить" Пролог выполнить другие действия, отличные от доказательств фактов, - такие как напечатать что-нибудь или создать файл.