Лекция 3. лекция 2 Логическая модель представления знаний. Интеллектуальные информационные системы
 Скачать 187.6 Kb.
|
|
Логический подход к искусственному интеллекту Логической моделью представления знаний является исчисление предикатов. На исчислении предикатов базируется язык логического программирования (PROLOG — PROgramming with LOGics), который служит для представления знаний о предметной области. Определение предиката Предикат это логическая функция одной или нескольких переменных p(X1,X2,… Xn), определенная на множестве D и принимающая одно из двух значений, «истина» и «ложь», в зависимости от значений предметных переменных. Буква p предикатный символ. Предикат, зависящий от n переменных, называется n местным (или n арным) предикатом. Язык исчисления предикатов Исчисление предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций, и предикатов. Для описания некоторой предметной области на языке исчисления предикатов (ИП) определяются множества исходных элементов, правила построения формул, система аксиом и множество правил вывода, каждое из которых описывает способ построения новых формул из исходных элементов и уже построенных формул. Исходные элементы ИП конечное множество предметных переменных {Х1,Х2,…Хk}; конечное множество предметных констант {a1,a2,…an}; конечное множество функциональных символов {f1,f2,…fm}; конечное, непустое множество предикатных констант {p1,p2,…pr}; Исходные элементы ИП логические связки: ¬ (отрицание), & (конъюнкция), ∨ (дизъюнкция), ⇒ (импликация); кванторы: ∀ (квантор всеобщности) и ∃ (квантор существования); специальные символы: ( ) + - */ < > . , [ ] : ; знак пустого дизъюнкта , который является тождественно ложной формулой. Построение формул в ИП Формулы состоят из термов, предикатных констант, специальных символов и логических связок. Понятие терма в ИП Определение терма рекурсивно: терм это предметная переменная или предметная константа. если f функциональный символ, и t1,t2, …tn термы, то f(t1,t2,…tn) терм. Понятие элементарной формулы в ИП Предикат вида p(t1,t2,…tn), где p предикатная константа, а t1,t2,…tn термы, является элементарной формулой. Правила построения ППФ в ИП Правила построения ППФ (Правильно Построенных Формул) в исчислении предикатов следующие: всякая элементарная формула есть ППФ; если A и B ППФ, а x предметная переменная, то каждое из выражений ¬ A, A & B, A ∨ B, A ⇒ B, ( ∀ x)A, ( ∃ x)A есть ППФ; других правил построения ППФ нет. Формулы ИП с кванторами Для формул с кванторами справедливо следующее утверждение: формула Q(X1,X2,…,Xn) получена из формулы P(X1,X2,…Xn) посредством присоединения квантора, если Q(X1,X2,…,Xn) = ( ∀ Xi) P(X1,X2,…Xn) или Q(X1,X2,…,Xn) = ( ∃ Xi) P(X1,X2,…Xn). Формулы ИП с кванторами Пусть D={a1 , a2, …, an} есть множество предметных констант, и P(x) предикат, определенный на множестве D, тогда справедливы утверждения: ( ∀ X) P(X) = P(a1) & P(a2) & … & P(an) и ( ∃ X) P(X) = P(a1) ∨ P(a2) ∨ … ∨ P(an). Система аксиом ИП Система аксиом исчисления предикатов включает в себя аксиомы исчисления высказываний А1 А11 и две аксиомы с кванторами А12 и А13. Система аксиом ИП A1) A ⇒ (B ⇒ A) A2) (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)) A3) A & B ⇒ A A4) A & B ⇒ B A5) (A ⇒ B) ⇒ ((A ⇒ C) ⇒ (A ⇒ B & C)) Система аксиом ИП A6) A ⇒ A ∨ B A7) B ⇒ A ∨ B A8) (A ⇒ C) ⇒ ((B ⇒ C) ⇒ (A ∨ B ⇒ C)) A9) (A ⇒ B) ⇒ ( ¬ B ⇒¬ A) A10) A ⇒¬¬ A Система аксиом ИП A11) ¬¬ A ⇒ A A12) ( ∀ X) A(X) ⇒ A(t) A13) A(t) ⇒ ( ∃ X) A(X), A(X) ППФ, t терм, не содержащий X. Все аксиомы тождественно истинны. Правила вывода в ИП Выводом P называется такое линейно упорядоченное множество элементов, что всякий элемент P является либо аксиомой, либо заключением применения некоторого правила вывода. Формула является выводимой, если можно построить вывод, заканчивающийся этой формулой. Правила вывода в ИП 1) Правило аксиом. Все аксиомы выводимы. Правила вывода в ИП 2) Правило подстановки. Подстановка (ti вместо Xi) есть множество θ ={X1=t1,X2=t2,… Xk=tk}, где X1,X2,…,Xk попарно различные переменные , Xi ≠ Xj при i ≠ j , t1,t2,…,tk термы, если Xi=ti, то ti не содержит вхождений Xi. Правило подстановки означает, что если P(X1,X2,…Xk) выводима, то и формула P(t1,t2,…tk) = θ (P(x1,x2,…xk)) выводима. Правила вывода в ИП 3) Правило Modus Ponens (MP). Если А выводимая ППФ и A ⇒ B выводима, то B также будет выводима. Правила вывода в ИП 4) Правило обобщения. Если B ⇒ A(X) выводимая ППФ и B не содержит вхождений X, то формула B ⇒ ( ∀ X)A(X) также будет выводима. Правила вывода в ИП 5) Правило конкретизации. Если выводима формула A(X) ⇒ B и B не содержит вхождений X, то формула ( ∃ X)A(X) ⇒ B также будет выводима. Правила вывода в ИП 6) Правило переименования переменных. Если A выводимая ППФ, имеющая квантор ∃ и (или) ∀ , то одна связанная переменная может быть заменена другой, не меняя истинностного значения формулы. Полученная формула также будет выводима. Стандартные формы ППФ в ИП Приведение логических формул к одной из стандартных (нормальных) форм представления позволяет упростить алгоритм доказательства истинности формул. По тем же причинам язык программирования Пролог является подмножеством языка исчисления предикатов, в Прологе используется только клаузальная форма записи формул исчисления предикатов. Клаузальная форма ППФ в ИП Клаузальной формой (клаузой или предложением) в исчислении предикатов называется формула без кванторов, представляющая собой несколько предикатов или их отрицаний, объединенных знаками дизъюнкции. Клаузальная форма ППФ в ИП В общем случае клаузу можно представить в следующем виде: ¬ A1 ∨¬ A2 ∨ … ∨¬ Ak ∨ B1 ∨ B2 ∨ … ∨ Bn , где элементарные формулы (предикаты) ¬ Ai и Bj называются литерами, причем Bj положительная литера, а ¬ Ai отрицательная литера. Клауза Хорна (Хорновский дизъюнкт) Если k ≥ 1 и n=1, то такая клауза имеет вид ¬ A1 ∨¬ A2 ∨ … ∨¬ Ak ∨ B и называется клаузой Хорна или хорновским дизъюнктом. Хорновский дизъюнкт содержит не более одной положительной литеры. Клауза Хорна (Хорновский дизъюнкт) Дизъюнкты Хорна названы по имени логика Альфреда Хорна, который впервые указал важность таких дизъюнктов в статье "On sentences which are true of direct unions of algebras" (Journal of Symbolic Logic, том 16, 1951, с. 14-21). Преобразование хорновского дизъюнкта Дизъюнкт Хорна можно преобразовать с помощью правила де Моргана ¬A V ¬B = ¬(A&B) и формулы связи между операциями отрицания, дизъюнкции и импликации ¬ AVB = A→B. Преобразование хорновского дизъюнкта Дизъюнкт Хорна можно преобразовать с помощью правила де Моргана: ¬ (A1 & A2 & … & Ak) ∨ B, а эта формула равносильна формуле A1 & A2 & … & Ak → B, что соответствует правилам “Если …,то”. Клаузы Хорна в языке Пролог На языке Пролог дизъюнкт Хорна записывается в другом виде B: A1,A2,…,Ak. При такой записи «,» соответствует знаку конъюнкции & , а знак “: ” соответствует знаку импликации ← Клаузы Хорна в языке Пролог. Правила. В языке Пролог используются только хорновские дизъюнкты, называемые правилами. При этом B называется заголовком правила, а конъюнкция A1,A2,…,Ak называется телом правила. Знак “: ” читается как “Если”. Таким образом, правило является условным предложением языка Пролог. Клаузы Хорна в языке Пролог. Факты. В клаузе Хорна элементарные формулы A1,A2,…,Ak могут отсутствовать, т.е. k=0, n=1. В этом случае правило имеет пустое тело: B: . или B. Это означает, что предикат B истинен всегда, такая конструкция в языке Пролог называется фактом или безусловным предложением . Клаузы Хорна в языке Пролог. Вопросы. Если в хорновском предложении отсутствует заголовок правила, т.е. k ≥ 1, n=0, то правило принимает вид: ? : A1,A2,…,Ak. Такое выражение называется вопросом или запросом, или целевым утверждением, а предикаты A1,A2,…,Ak называются целями. Клаузы Хорна в языке Пролог. Вопросы. Если в хорновском предложении отсутствует заголовок правила, т.е. k ≥ 1, n=0, то правило принимает вид: ? A1,A2,…,Ak. Такое выражение называется вопросом или запросом, или целевым утверждением, а предикаты A1,A2,…,Ak называются целями. Клаузы Хорна в языке Пролог. Пустой дизъюнкт. Если в хорновской клаузе k= n=0 , клауза называется пустым дизъюнктом, имеет обозначение и интерпретируется как тождественно ложная формула. Клаузы Хорна в языке Пролог. Логическая программа. Предложения языка Пролог являются либо правилами, либо фактами, либо запросами. Логическая программа на Прологе это конечная последовательность фактов и правил. |