Клаузальные формы

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

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

Общий вид дизъюнкта таков:

Здесь Рi, и Qi -позитивные литералы (атомарные формулы, в которых все переменные предполагаются универсально квантифицированными). Дизъюнкт без переменных назы­вается конкретизированным дизъюнктом. Приведенный выше дизъюнкт можно записать в эквивалентной форме:

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

Когда п позитивных литералов в дизъюнкте строго больше 1, то имеем дело с дизъюнктивной информацией (возможно, условной). В частности, при m=0 и п >1дизъюнкт содержи: только позитивные литеры: . С помощью таки» дизъюнктов можно представлять неполные сведения. Напри­мер, дизъюнкт Рисует(Миша) v Рисует(Петя) можно интер­претировать так: "хотя бы один из мальчиков Миша или Пе­тя рисует", но не уточняется, рисует только Миша, рисует ли только Петя или оба мальчика рисуют.

Если т>1 и n>1, дизъюнкт имеет самый общий вид и пред­ставляет условную дизъюнктивную информацию. Наличие такой дизъюнктивной информации позволяет выражать не­полные знания о мире. Однако формализовать рассуждения на основе таких знаний очень трудно. Поэтому в языках ло­гического программирования, простых дедуктивных база» Данных не используют такие дизъюнкты.

Хорновские дизъюнкты

В языках логического программирования, подобных Прологу, ограничиваются хорновскими дизъюнктами, т.е. дизъюнктами, содержащими не более одного позитивного литерала. При m>1и n= 1 дизъюнкт называется точным хорновским дизэюнктом, который имеет вид:

.

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

Если антецедент приведенной импликации не содержит литералов (m=0), то, очевидно, имеем дело с безусловной ин­формацией. Такой дизъюнкт называется унитарным пози­тивным дизъюнктом. Возможны два случая.

•Литерал Q не содержит переменных. Тогда он представ­ляет один конкретизированный литерал, например: Рисует(Миша). Такой дизъюнкт называется фактом. Так выра­жаются факты в Пролог-программах, конкретизации отно­шений в реляционных базах данных.

•Литерал Q содержит переменные. Тогда он представляет более общую информацию о термах (переменные рассматри­ваются универсально квантифицированнми).

•Негативные хорновские дизъюнкты.

Дизъюнкт, не содержащий ни одного позитивного литера­ла называется негативным. Если в таком дизъюнкте один нега­тивный литерал Ø Р. то он представляет элементарную нега­тивную информацию. Возможны два случая:

•Негативный литерал не содержит переменных. В этом случае он представляет собой элементарный негативный факт. Например, - Ø Рисует(Миша).

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

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

В логическом программировании негативный хорновский дизъюнкт представляется в виде вопроса, задаваемого систе­ме вывода.