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

В Китае обнаружили настолько огромную пещеру, что она имеет свой климат, туман и даже свои облака. Это самый настоящий «Затерянный мир»!

Эта огромная пещера была обнаружена в Китайской провинции Chongquing. Она настолько огромна, что имеет свой независимый климат.

 

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

 

Никто и не подозревал, что рядом с небольшой деревней расположена такая огромная подземная пещера. Она просто потрясающе огромная!

 

В ней даже есть своя бурная река.

 

Команда исследователей из 15 человек, наткнулась на это чудо подземного мира. совершенно случайно.

 

Клаузальная форма. Клаузы Хорна.

Формулы в виде Хорна имеют вид:

z и p_i – предикаты или их отрицания

,

где p_i- посылки, , а z – заключение

Такое правило называют правилом вывода или Хорна, или клаузами Хорна.

Если клаузы выглядят так: , то это заведомая ложь.

Если клаузы выглядят так: , то это факт.

 

Пример.

Пусть имеются предикаты:

М(x,y)=”x – мать y”

O(x,y)=”x – отец y”

Дед(x,y)=”x – дед y”

Запишем правила Хорна.

К1. Дед(x,y)← O(x,z), М(z,y)

К2. Дед(x,y)← O(x,z), O(z,y)

 

Любую логическую формулу можно преобразовать к одному или нескольким правилам Хорна с помощью следующей последовательности действий:

1. Исключение знака импликации → и эквивалентности ↔.

A ↔ B = (A → B) Ù (A → B)

A → B = ~A Ú B

 

2. Продвижение знака отрицания до атома

~(A Ú B) = ~A Ù ~B

~(A Ù B) = ~A Ú ~B

~(~A) = A

~("x)A(x) = ($x)~A(x)

~($x)A(x) =("x)~A(x)

 

3. Стандартизация переменных (переименование). Связанные переменные в случае, если они встречаются в других частях формул, переименовываются.

$y("x P(x,y) Ú $x Q(x,y))

$y("z P(z,y) Ú $x Q(x,y))

 

4. Вынесение кванторов, т.е. получение предваренной формы.

$y "z $x (P(z,y) Ú Q(x,y))

 

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

"z $x (P(z,a) Ú Q(x,a))

 

Если квантор существования стоит не на первом месте, то он отбрасывается и вхождение переменной заменяется на функцию от (k-1) переменной соответственно предшествующим кванторам всеобщности.

"z (P(z,a) Ú Q(f(z),a))

 

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

 

6. Кванторы всеобщности отбрасываются.

 

7. Получение конъюнктивной нормальной формы, т.е. формула должна быть преобразована в конъюнкцию дизъюнктов.

A Ù (B Ú C) = (A Ù B) Ú (A Ù C)

A Ù (B Ù C) = A Ù B Ù C

A Ú (B Ú C) = A Ú B Ú C

A₁ Ú A₂ Ú A₃ Ú(B₁ Ù B₂ Ù B₃)=(A₁ Ú A₂ Ú A₃ ÚB₁) Ù (A₁ Ú A₂ Ú A₃ ÚB₂) Ù (A₁ Ú A₂ Ú A₃ ÚB₃)

 

8. Запись в виде множества дизъюнктов

S={D₁, D₂, …, D_N}

 

9. Каждый дизъюнкт записывается в виде одного правила Хорна

~A Ú B=A → B

~A Ú ~B Ú C = C←A&B