Лекция 7. 1. 7. 5. 2. 3. Сколемовская функция и предваренная нормальная форма

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

Пусть теперь формула F имеет другой вид:

В ее составе 2 однолитерных дизъюнкта , причем один из них является отрицанием другого. Такие литеры называются контрарными. Конъюнкция контрарных литер равна Л, и поэтому имеем невыполнимую функцию F=Л.

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

Формула Р находится в дизъюнктивной нормальной форме (ДНФ), тогда и только тогда, когда Р имеет вид

где каждая из Р₁, Р₂,..., Р_n есть конъюнкция литер.

Всякая формула может быть преобразована в нормальную форму путем использования законов эквивалентных преобразований. Приведем некоторые из них:

                                                                     (1)

                                                                                       (2)

                                                                (3а) 

                                                                                   дистрибутивные законы                             

                                                                  (3б)

(    закон двойного отрицания                                               (4)

- законы де Моргана       (5а); (5б)

 ■  закон исключения третьего                                             (6)

□ закон противоречия                                                            (7)

□= P; ■ = P                                                                        (8а); (8б)

■= ■; □ = □                                                                          (9а); (9б)

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

Рассмотрим основные правила вывода в логике высказываний.

Правило подстановки. Пусть Р — ППФ, содержащая атомарную форму­лу X. Тогда если Р — тавтология, то, заменяя в ней X всюду, где она входит, произвольной ППФ В, получают также тавтологию.

Modus ponens (правило заключения, или правило дедуктивного вывода). Положительная форма условно категорического силлогизма:

P→Q,, Р ├ Q (знак «├» означает «выводимость», т.е. формула  выводима из формулы ).

Таким образом, если импликация  истинна и  истинна, то и  тоже истинна.

Modus tollens. Отрицательная форма условно категорического силлогизма:

P→Q, Q ├ P.

Modus tollendo ponens. Форма разделительно категорического силлогизма. Отрицающее - утверждающий модус:

P Ú Q, P ├ Q.

Modus ponendotollens. Форма разделительно категорического силлогизма, так называемый утверждающе отрицающий модус:

P Ú Q,, P ├ Q.

Правило силлогизма (правило цепного умозаключения):

P→Q, Q→R, ├ P→R.

Правило контрапозиции:

P→Q, ├ Q→ P.

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

Пусть даны формулы P₁, P₂,..., P_n и формула Q. Говорят, что Q есть
логическое следствие формул P₁,..., P_n тогда и только тогда, когда для вся­кой интерпретации I, в которой P₁ Ù P₂ Ù...Ù P_n истинна, Q также истинна.
Здесь P₁, P₂,..., P_n называются аксиомами (или постулатами, или посылка­ми) Q.

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

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

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

В логике высказываний доказаны две теоремы (все известные теоремы бу­дут приводиться без доказательств), на которых основывается более краткий и простой способ вывода.

Теорема дедукции. Пусть даны формулы  и формула . Формула есть логическое следствие формул тогда и только тогда, когда формула общезначима.

Теорема о противоречивости. Пусть даны формулы  и формула . Формула есть логическое следствие формул тогда и только тогда, когда формула противоречива.

Эти две теоремы очень важны, так как позволяют прийти к следующему выводу: доказательство того, что отдельная формула есть логи­ческое следствие конечного множества формул, эквивалентно доказательству того, что некоторая связанная с ними формула общезначима или противоре­чива.

Применение некоторых рассмотренных понятий и правил вывода проил­люстрируем на простом примере.

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

Чтобы установить это заключение, обозначим утверждения:

1. F₁: если скорость движения конвейера непостоянна (S), то точность за­хвата роботом заготовки и установки ее под пресс уменьшается (Р).

2. F₂: если точность установки роботом заготовки под пресс уменьшается (Р), то увеличивается процент бракованных изделий (U).

3. F₃: скорость движения конвейера непостоянна (S).

4. F₄: увеличивается процент бракованных изделий (U).

Эти утверждения выразим в символической форме:

F₁: S→P; F₂: P→U; F₃: S; F₄: U.

Покажем, что F₄ истинно, как только F₁ Ù F₂ Ù F₃ истинно. Преобразуем форму­лу в нормальную форму:

(по формуле (2))

 (по коммутативному закону)

(по формуле (3б))

= ((□    (по формуле (7))

              (по формуле (8а))

    (по формуле (36))

= (S Ù□)      (по формуле (7))

= □             (пo формуле (9б))

                         (по формуле (8а))        

Следовательно, если формула истинна, то формула тоже истин­на. Так как истинна, только если S, Р и U все истинны, заключа­ем, что U истинна. Таким образом, U есть логическое следствие формул F₁, F₂ и F₃.

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

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

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

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

 - «Обезьяна находится в точке »,

 В - «Ящик находится в точке »,

- «Бананы находятся в точке »,

- «Обезьяна находится на Ящике»,

- «Обезьяна держит Бананы»,

- «Обезьяна, Ящик, Бананы находятся в разных точках»,

- «Обезьяна находится рядом с Ящиком».

Используя логические связки: , можно теперь строить более сложные умозаключения. Например:

1) . (Если все предметы находятся на своих исходных местах, т.е. в точках  соответственно, то справедливо сказать: «Обезьяна, Ящик, Бананы находятся в разных местах»).

2) . (Если «Обезьяна, Ящик, Бананы находятся в разных местах», то «Обезьяна находится не рядом с Ящиком»).

3) . (Если «Обезьяна, Ящик, Бананы находятся в разных местах», то «Обезьяна не находится на Ящике»).

4) . (Если «Обезьяна, Ящик, Бананы находятся в разных местах», то «Обезьяна не держит Бананы»).

Высказывания 2, 3, 4 можно объединить в одно с помощью логической связки «И»:

5) .

6) . (Если «Обезьяна, Ящик, Бананы находятся не в разных местах», то «Обезьяна стоит на Ящике» И «Обезьяна держит Бананы»).

7) . (Если «Обезьяна не на Ящике» то «Обезьяна не держит Бананы»).

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

                                                     (*)

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

, где .                          (**)

Эта формула говорит, что «Если Обезьяна, Ящик и Бананы не в исходных точках» И «Обезьяна на Ящике», то «Бананы в руках у Обезьяны».

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

 (***)

Теперь следует вычислить значения выражений слева и справа от знака . Если окажется, что формула справа принимает значение И как только все формулы (*), образующие левую часть, одновременно примут значение И, то логическая выводимость (**) и (*) доказана.

Так как формула (***) имеет 7 переменных, то таблица истинности будет содержать 2⁷ = 128 строк, что, вообще говоря, затруднительно выполнить.

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

Согласно этому методу надо доказать противоречивость следующей системы:

                                     (****)

Под номером 5 в (****) как раз и стоит отрицание формулы (**). Далее применяем метод резолюций. Для этого вначале все 5 предложений представим в виде конъюнкции элементарных дизъюнктов (КНФ).

Для первого предложения имеем:

Для второго предложения имеем:

Для третьего предложения имеем:

Для четвертого предложения имеем:

Для пятого предложения приведем цепочку преобразований:

Пользуясь правилом раскрытия конъюнкции по дизъюнкции, имеем для второго предложения

.

Для третьего предложения имеем:

.

Конъюнкция , очевидно, распадается на 3 одночленных дизъюнкта: .

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

Получили «пустой» (ложный дизъюнкт). Это значит, что выводимость формулы (**) из системы уравнений (*) доказана и утверждение (**) истинно. Отметим, что приведенная резолюция не единственно возможная. Можно и по-другому. Например,  и т.п.

ЗАДАНИЕ НА ЭКЗАМЕН Применив метод опровержения, основанный на принципе дедукции, доказать следующие следствия:

А)

B) ;

C)

Лекция 6. 1.7.5.2. Логика предикатов первого порядка. 1.7.5.2.1. Основные понятия и определения

Рассмотренная логика высказываний является грубой моделью представления знаний. Основной ее недостаток состоит в том, что высказывание рассматривается как единое целое, без анализа его внутренней структуры. Это ограничивает возможности исчисления высказываний при моделировании сложных логических построений. Например, пусть имеется классический силлогизм:

Все люди смертны,

Сократ – человек,

Следовательно, Сократ смертен.

С точки зрения логики высказываний имеем следующую формулу: . Но эта формула не является общезначимой, и, значит, не позволяет корректно выразить рассмотренный силлогизм.

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

Рассмотрим в начале основные понятия исчисления предикатов на простых примерах. Пусть заданы следующие предложения:

Лена и Таня сестры,

Грибы в лесу,

Капля долбит камень,

Снег белый,

Мальчик послал книгу брату.

В правилах исчисления предикатов эти предложения можно записать следующим образом:

а) СЕСТРЫ (Лена, Таня),

б) В (лес, грибы),

в) ДОЛБИТЬ (капля, камень),

г) БЕЛЫЙ (снег),

д) ПОСЫЛАТЬ (мальчик, брат, книга).

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

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

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

Предикатную формулу называют также атомом.

Но и термы бывают разными. В примере а) оба терма обозначены вполне конкретно – это имена Лена, Таня. В этом случае они называются индивидные константы.

Во втором предикате б) оба терма заданы в самом общем виде: какие-то грибы в каком-то лесу. Эти термы можно просто обозначить через буквы и . Их так на­зывают – индивидные (предметные) переменные.

Сами же предикатные символы, которые, как мы видели, много чего отображают, также обозначаются буквами – про­писными, латинского алфавита: Иногда к ним добавляются индексы: , а иногда указывают число мест: .

Говоря о терме, мы не упомянули еще один его вид: терм может быть выражен через функцию.

Разберем все сказанное на примерах.

1. ПИСАТЬ (Лермонтов, «Демон»). «Лермонтов написал «Демона»» - все ясно: ПИСАТЬ – предикатная константа, двуместный предикат, оба терма – индивид­ные константы. Обозначим через X множество стихотворений Лермонтова. Тогда предикат вида ПИСАТЬ (Лермонтов, ) означает: «Лермонтов написал какое-то стихотворение». А вот предикат ПИСАТЬ (у, х), где под у понимается какой-то человек, означает: «кто-то написал что-то», х и у здесь – индивидные переменные.

2. Обозначим через g некоторую функциональную константу, например, «быть вареным». Если картофель обозначить через s, то предикат НА (стол, g(s)) теперь истолкуется как «на столе вареная картошка». Пусть  - функциональная константа «быть отцом», а  - функциональная константа «быть матерью». В этом случае предикат следует истолковать просто как РОДИТЕЛИ. (Тот же  результат, впрочем, даст и более общая формула: , где  один и тот же ребенок).

Из рассмотренных примеров можно сделать некоторые выводы. Во-первых, термы нельзя менять местами. Иначе получится, что на картошке стоит вареный стол, а Демон написан «Лермонтова». И, во-вторых, не следует путать предикатный и функциональный символы. Предикат МАТЬ означает: есть мать . Либо это правда, либо это неправда, поэтому область значений этого предиката [1, 0] или [И, Л]. Функция означает «быть матерью», равенство  - «матерью является ». Область определения , вообще говоря, - все человечество, область значений  – все женщины определенного возраста.

Перейдем теперь к обобщению сказанного.

Исчисление предикатов, как всякая формальная теория , характеризуется следующим:

 наличием алфавита (словаря) ;

 множеством синтаксических правил ;

 множеством аксиом, лежащих в основе теории ;

 множеством правил вывода .

Словарь исчисления предикатов   содержит:

• индивидные символы (индивидные константы) ;

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

• функциональные символы (константы) ;

• высказывания ;

• предикатные символы (константы) .

Всякая функция или предикатный символ имеет определенное число ар­гументов (тогда говорят: n -местный функциональный символ или n -местный предикатный символ).

Терм есть всякая константа или переменная. Если f есть n -местный функциональный символ и t₁,…t_n — термы, то f(t₁,…t_n) — терм.

 Предикат есть отображение, которое отображает список констант в множество из двух элементов И и Л. Предикат P(t₁,…t_n), где Р — n-местный предикатный символ и t₁,…t_n — термы, является атомарной формулой логики предикатов первого порядка.

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

С помощью атомарных формул и введенных ранее пяти логических свя­зок можно строить различные формулы и выражения.

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

 Квантор читается как «все», «для всех», «всякий», «каков бы ни был» и т.п. Поэтому он называется квантором всеобщности (общности).

Квантор Ǝчитается как «некоторый», «хотя бы один», «существует» и т. п. Поэтому он называется квантором существования.

Так, например, выражение  читается: «для любого выполняется условие ».

Выражение  означает «существует хотя бы один , при котором выполняется , т. е. ».

Множество синтаксических правил исчисления высказываний применимо и в исчисления предикатов. Выражение, которое строится из атомарных формул, логических связок и кванторов, есть правильно построенная формула (или формула) логики пре­дикатов. Атомарная формула есть ППФ. Если Р и Q — ППФ, то , , , , — ППФ. Если Р — ППФ, а х — переменная в P, то и  — ППФ.

Поэтому правильно построенные формулы в рамках исчисления высказываний остаются правильно построенными формулами (ППФ) и в исчислении предикатов. Однако в исчислении предикатов добавляются еще два правила:

• атом есть формула;

• если  - формула и  - переменная, то и - тоже формулы.

Каждому квантору соответствует только одна переменная, в рассмотренных примерах это или . Эта переменная называется квантифицированной, она пишется сразу за квантором. Область действия квантора - формула, к которой применяется эта квантификация.

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

В качестве примера рассмотрим следующую формулу:

.

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

Каждую предикатную формулу можно интерпретировать, т. е. оценить ее как или . При этом можно оценить «перекрытие» кванторов на одну и ту же перемен­ную, так интерпретируется, как ,а интерпретируется как .

Одна и та же переменная может иметь свободные и связанные вхождения в одну и ту же формулу. Например, в формуле первое вхождение переменной свободно, а второе и третье — связанные. Переменная свободна, так как единственное вхождение свободно. Переменная называ­ется свободной (связанной) в данной формуле, если существуют свободные (связанные) ее вхождения в эту формулу.

Если  - двуместный предикат, то для него справедливы следующие равенства:

т.е. одноименные кванторы можно менять местами. Для разноименных кванторов, в общем, это делать нельзя. Однако справедливо такое условие:

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

 Однако к нему необходимо добавить еще аксиомы, учитывающие появление кванторов. Такими аксиомами являются следующие аксиомы:

Четвертая аксиома говорит, что если формула  истинна для всех значений , то она истинна и для некоторого значения  из этого же универсума (если все яблоки в данном ящике красные, то одно-то красное уж найдется всегда).

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

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

Смысл этого правила состоит в следующем: если правильно построенная формула (ППФ) в логике предикатов  истинна и  - некоторая константа, то формула  также истинна, т.е. справедливо следующее равенство:

Пусть, например, имеются формулы  и , которые обе истинны. Применяя специализацию, получим , т.е. , (специализация), где  (modus ponens ).

Формула P имеет определенный смысл, т. е. обозначает определенное ут­верждение, если существует какая-либо интерпретация. Интерпретация формулы Р логики предикатов состоит из непустой пред­метной области D и указания значений всех констант, функциональных симво­лов и предикатов из Р. Каждой константе ставится в соответствие определен­ный элемент из предметной области D; каждому n-местному функциональному символу ставится в соответствие n-мест­ная функция, отображающая Dⁿ в D, где ; каждому n-местному предикатному символу ставится в соответствие отображение Dⁿ в множество их двух элементов {И, Л}.

Рассмотрим несколько примеров построения предикатов.

Пример 1. Фраза «Кто не работает, тот не ест» в терминах исчисления предикатов запишется следующим образом: , где  - человек,  - предикатная константа РАБОТАТЬ, Е – предикатная константа ЕСТЬ.

Пример 2. Классический силлогизм:

Все люди смертны; Сократ – человек; Следовательно, Сократ смертен

можно переписать следующим образом:

для всех , если - человек, то  - смертен;

Сократ человек;

следовательно, Сократ смертен.

Обозначим через М «быть смертным», через Н «быть человеком». Тогда приходим к следующей формуле:

.

Пример 3. Фразу «В каждом городе найдется живущей в нем человек, который покажет достопримечательности этого города» в терминах исчисления предикатов можно записать следующим образом:

.

В этом выражении  - город,  - предикатная константа ГОРОД,  - краевед,  - предикатная константа, ЖИВУЩИЙ В,  - предикатная константа ПОКАЖЕТ ДОСТОПРИМЕЧАТЕЛЬНОСТЬ, - достопримечательности.

Пример 4. Фразу «Болтун – находка для шпиона» в терминах исчисления предикатов можно записать следующим образом:

Здесь P  – предикатная константа НАХОДКА, x– болтун, y – шпион.

Эту же фразу можно записать более подробно:

Здесь М – ЧЕЛОВЕК, В – БОЛТУН, Р – НАХОДКА, у – шпион.

Пример 5.  Пусть L –  означает ЛЮБИТЬ, ц – цветы, к – конфеты, х - девушка. Необходимо перевести на русский язык следующие выражения:

1.7.5.2.2. Преобразование формул в исчислении предикатов

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

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

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

Формула получает значение И, если А получает значение И для каждого  из .

Формула  получает значение И, если А получает значение И хотя бы при одном значении  из .

Пусть, например,  принимает значения в области и известно, что . Формула  означает, что для всех  формула  истинна. Это условие в данном примере не выполняется, поэтому . Формула  означает, что существует  при котором  истинна. Очевидно, что здесь .

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

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

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

                                                                        (10а)               

 

                                (10б)                 

 

                                                                                     (11а)

 

                                                                                     (11б)

 

                                                                                     (12а)  

 

                                                                                     (12б) 

 

                                                              (13а)  

 

                                                               (13б)   

 

                             (14а)                                                       

 

                               (14б)

 

В выражениях (14а) и (14б) производится переименование связанных переменных при условии, что переменная не появляется в формуле .

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

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

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

Сформулируем еще раз основные правила в логике предикатов.

Правила обобщения (правило связывания квантором общности). Пусть Q — формула, не содержащая свободных вхождений переменной х; Р(х) — формула. Тог­да, если формула выводима, то формула также выводима.

Правило связывания квантором существования. Пусть Q — формула, не содержащая свободных вхождений переменной х; Р(х) — формула. Тогда если формула  выводима, то формула также выводима.

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

Правило специализации. Это правило применяется для определения кон­кретного значения квантора общности, т. е. если некоторому классу объектов присуще какое-либо свойство, то любой объект этого класса будет обладать этим свойством: , т.е. a ├ P(a).

Правило конкретизации для квантора существования. Это правило позво­ляет перейти от формулы к высказыванию Р(а). Пусть a — определенный элемент, такой, что если истинно, то Р(а) также истинно. Тогда , т.е. ├ Р(а).

Эти правила вывода наряду с приведенными правилами подстановки, за­ключения (Modus Рonens), теоремой дедукции и др., а также законы эквива­лентных преобразований обладают для логики предикатов универсальной ис­тинностью и могут применяться либо для установления истинности утвержде­ний в целом, либо для вывода заключения или доказательства логических следствий.

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

Рассмотрим это на небольшом примере. Предположим, имеется сле­дующая информация, данная как утверждения:

1. R1 является реакцией n -го порядка.

2.Порядок реакции R1 есть 2.

3.Если есть реакция n -го порядка и , то кривая нормальной кон­центрации реакции повышается монотонно.

4.Кривая нормальной концентрации реакции R1 вогнута.

5.Если кривая нормальной концентрации реакции повышается моно­тонно, то реакторы должны быть связаны в единую серию.

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

Эти утверждения могут быть переведены в логику предикатов первого порядка.

Для этого введем следующие предикатные символы: R — тип реакции; Q — порядок реакции, Н — больше; С — кривая линия нормальной концентрации; S — связь реакторов; A — задание реакторам. Тогда приведенные выше утверждения будут иметь следующий вид:

1.

2. .

3.      4. .

     5.

6.

.

Рассмотрим вначале прямую цепочку рассуждений.

1) Применив посылки 1 и 2 к утверждению 3, получим следующее выражение:

     2) Применив полученный результат к утверждению 5, получим:

.

3) Применяем утверждение 4 и полученные результаты к утверждению 6:

.

Здесь двумя категориями ППФ, которые представляют утвердительные знания о специальной области, являются факты и правила. Утверждения 1, 2 и 4 являются примерами фактов, а утверждения 3, 5, 6 — примерами правил.

Рассмотрим возможность использования обратной цепочки рассуждений для получения заключения. Попытаемся доказать, что реакторы для реакции R1 должны быть связаны в серию. Для этого вызывается правило 5: S(х, се­рия). Это целевое утверждение может быть доказано, если будет доказана его подцель: С (х, повышается монотонно). Последнее утверждение доказывается использо­ванием правила 3, если могут быть доказаны следующие три подцели:

1) ; 2)  3) .

Это может быть удовлетворено фактами 1 и 2, содержащимися в БЗ, и зна­нием отношений числовых величин, которые предполагаются содержащимися в системе. Результатом является доказательство того, что цель S(х, серия) мо­жет быть удовлетворена имеющимися значениями.

Достоинством логики предикатов является:

- во-первых, возможность генерации но­вого знания из имеющихся в БЗ знаний,

- во-вторых - наличие формальной процедуры доказательства и вывода логических следствий,

- в-третьих, - достаточная изученность этого традиционного аппарата и хорошая воспринимаемость. 

Покажем на простом примере один из возможных подходов к построению интеллектуальной системы, основанный на применении логики предикатов 1-го порядка:

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

Введем следующие предикаты:

ЭЛЕМЕНТ (s, x, y)                                                                       (1)

СТРУКТУРА (x, y, соединить(s,t)),                                     (2)

где s – наименование элемента, x – преобразуемая элементом энергия, y – получаемая на выходе элемента энергия, t – подустройство (структура, быть может, пустая), соединяемая с элементом s.

Подставим в (1) соответствующие значения s, x, y. Для нашего случая получим три элемента:

1) ЭЛЕМЕНТ (КОТЕЛ, ТОПЛИВО, ПАР)

2) ЭЛЕМЕНТ (ТУРБИНА, ПАР, ВРАЩЕНИЕ)

3) ЭЛЕМЕНТ (ГЕНЕРАТР, ВРАЩЕНИЕ, НАПРЯЖЕНИЕ)

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

4) СТРУКТУРА (х, х, ПУСТО);

5) СТРУКТУРА (х, y, СОЕДИНИТЬ (s, t)) если ЭЛЕМЕНТ (s, x, z) и СТРУКТУРА (z, y, t);

Согласно четвертой закономерности устройство, не преобразующее физическую величину x, имеет пустую структуру. Пятая закономерность говорит, что устройство, преобразующее физическую величину x в величину y, состоит из элемента s и подустройства (т.е. структуры) t, если s преобразует величину x в некоторую другую величину z, а t преобразует z в y.

Заметим, что высказывания (предикаты) 1), 2) и 3) истинны для конкретных значений s, x, y, а высказывания 4), 5) истинны для любых x, y, s, t, т.е. являются некоторыми аксиомами.

В этих условиях задача синтеза устройства, преобразующего топливо в электрическое напряжение, ставится следующим образом: найти схему (соединение) U, такую, что СТРУКТУРА (ТОПЛИВО, НАПРЯЖЕНИЕ, U). Задача решается путем логического вывода с использованием закономерностей 4) и 5) и фактов 1), 2), 3).

СТРУКТУРА (ТОПЛИВО, НАПРЯЖЕНИЕ, ОБЕДИНИТЬ (ЭЛЕМЕНТ (КОТЕЛ, ТОПЛИВО, ПАР), СТРУКТУРА (ПАР, НАПРЯЖЕНИЕ, СОЕДИНИТЬ (ЭЛЕМЕНТ (ТУРБИНА, ПАР, ВРАЩЕНИЕ), СТРУКТУРА (ВРАЩЕНИЕ, НАПРЯЖЕНИЕ, СОЕДИНИТЬ (ЭЛЕМЕНТ (ГЕНЕРАТОР, ВРАЩЕНИЕ, НАПРЯЖЕНИЕ), СТРУКТУРА (НАПРЯЖЕНИЕ, НАПРЯЖЕНИЕ, ПУСТО))))).

Таким образом, решением является:

U= СОЕДИНИТЬ (КОТЕЛ, СОЕДИНИТЬ (ТУРБИНА, СОЕДИНИТЬ (ГЕНЕРАТОР, ПУСТО))).

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

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

Лекция 7. 1.7.5.2.3. Сколемовская функция и предваренная нормальная форма

Из любой правильно построенной формулы исчисления предикатов  можно исключить квантор существования . Действительно, если формула  не содержит переменной , то, очевидно,  и . Это элементарный пример исключения кванторов.

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