Тема 2. Модели представления знаний

Одна из ключевых проблем, возникающих при построении ИИС состоит в необходимости выбора и реализации способа представления знаний. Важность данной задачи обуславливается тем, что именно представление знаний в конечном итоге определяет характеристики системы. Используемый метод представления знаний оказывает влияние на решение таких вопросов инженерии знаний извлечение знаний из различных источников. Приобретение знаний от экспертов, интеграция и согласование знаний и т.д. Модель представления знаний это основной тип моделей искусственного интеллекта. Конкретная реализация интеллектуальных систем происходит в рамках одной из моделей представлений знаний или языков представления знаний. Реальные системы редко основываются на одной из моделей ПЗ. Чаще всего реальные системы представляют собой гибрид из классических моделей со значительной долей собственных ограничений, догадок и условностей. Часть из них называют эвристиками. В настоящий момент применяются следующие модели:

• Классические (символьные): подражают мышлению и структуре памяти человека

  • Логическая

    • логика высказываний

    • логика предикатов

    • нечеткая логика

  • Продукционная

  • Фреймовая

  • Сетевая

    • семантическая сеть

    • онтология

  • Объектно-ориентированная

  • Специальная

• «Новые модели

…

Тема 3.

Логическая модель ПЗ

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

Введем понятие логической формулы:

• атом является логической формулой;

• если G – это логическая формула, то отрицание G - тоже лог формула;

• если G и H – логические формулы, то GH, GH тоже лог формулы.

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

G	H	GH	GH
0	0	1	1
0	1	1	0
1	0	0	0
1	1	1	1

 (GH)

 (GH)

 (GH)

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

Ранги лог связок в убывающем порядке располагаются следующим образом: 

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

2. Логика предикатов первого порядка

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

Пусть М – непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М.

Примеры.

Пусть М есть множество натуральных числе N.

Тогда выражение «х – простое число», «х – четное число», «х – больше 10» являются одноместными предикатами. При подстановке вместо х натуральных числе получаются высказывания: «2 – простое число» и т.д.

Пример 2-местных предикатов:

x>y

x делит нацело у

x+y=2

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

Предикат с заменяемыми переменными х1 … хn будем обозначать заглавной латинской буквой. После которй в скобках указаны эти переменные. Например, Р(х1,х2).

В логике предикатов дополнительно вводятся 2 новые операции:

1.  - квантор общности

2.  - квантор существования

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

Если обозначить предикат «х+у=10» через S(x,y) (предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x,y)»

В этом случае говорят, что предикат Р(у) получен из предиката S(x,y) навешиванием квантора существования.

Пример 2. Выражение «для всех х справедливо, что y>-x^2 определяет на множестве целых чисел одноместный предикат Q(y).

Если y>-x^2 обозначить Т(х,у) то можно записать так: Q(y)=(x)T(x,y).

Формулы логики предикатов

Термом называется:

1) переменная или константа

2) выражение вида f(t1,…,tn), t1…tn – термы, а f – n местный функциональный символ.

Терм – выражение, полученное из переменных и констант с помощью символов функций.

Атомарной формулой называется выражение вида r(t1…tn) где t1…tn – термы, r – символ н-местного предиката.

Формулой логики предикатов первого порядка – называется:

1) Атомарная формула

2) выражение вида (F)(G), (F1)(G), (F), (F)(G), (F)(G) где F and G – формулы логики предикатов.

(y)(F), (x)(F), y, x – пременные.

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

F=t(x)(y) [ S(x,y)(x)(r(x,y)t(y) )]

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

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

1) константе ставит в соответствие элемент множества М

2) символу н-местной функции ставит в соответствии н-местную функцию заданную на множестве М

3) Символу н-местного предиката ставит соответствии н-местный предикат заданный на множестве М.

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

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

1. Тот, кто посещает занятия, сдает экзамены на хорошо и отлично.

2. Тот, кто много знает, получает на экзамене хорошие отличные оценки.

3. Не существует того кто посещает занятия и не тратит много времени на учебу.

4. Каждый не тратит много времени на учебу или много знает.

Предикаты:

• Р(х) – х посещает занятие

• С(х) – х сдает экзамены на хорошо и отлично

• М(х) – х много знает

• Т(х) – х тратит много времени на учебу

Формулы логики предикатов:

(x)[P(x)C(x)]

(x)[M(x)C(x)]

(x)[P(x)T(x)]

(x)[T(x)M(x)]

Задание. Представить утверждения в виде формул логики предикатов

1. Любой отличник сможет стать президентом

2. Отличники всегда посещают лекции

3. Каждый, кто не узнает много интересного, не посещает лекции

4. Не существует того, кто узнает много интересного и мало знает

5. Каждый или мало знает или сможет стать президентом.

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

Формулы F(x1…xn) и G(x1…xn) называются равносильными, если для любой инерпретации фи с областью М высказывания (фиF)(х1..хn) и (фиG)(х1..хn) при любых х1..хn из М одновременно истинны или одновременно ложны.

Законы логики предикатов:

1. HG = (HG)(GH) – исключение эквивалентностей

2. HG=HG - исключение импликации

3. HG=GH - законы коммутативности

4. HG=GH

5. (HG)S=H(GS) - ассоциативности

6. (HG)S=H(GS)

7. H(GS)=(HG)(HS) - дистрибутивности

8. H(GS)=(HG)(HS)

9. H1=1

10. H0=H

11. H1=H

12. H0=0

13. HH=1 - исключенного третьего

14. HH=0 - противоречия

15. (H)=H - двойного отрицания

16. (HG)=HG - Де Моргана

17.(HG)=HG

18. (HG)(HG)=H - склеивания

19. (HG)(HG)=H

20. H(HG)=H - поглощения

21. H(HG)=H

22. HH=H - иденпотенции

23. HH=H

24. HG=GH - контрапозиции

25. (x)(H(x)G(x))=(x)H(x)(x)G(x)

26. (x)(H(x)G(x))=(x)H(x)(x)G(x)

27. (x)(y)H(x,y)=(y)(x)H(x,y)

28. (x)(y)H(x,y)=(y)(x)H(x,y)

29. (x)H(x)=(x)H(x)

30. (x)H(x)=(x)H(x)

31. (x)(H(x)G)=(x)H(x)G

32. (x)(H(x)G)=(x)H(x)G, G не содержит х

33. (Q1x)(Q2z)(H(x)G(z))=(Q1x)H(x)(Q2z)G(z)

34. (Q1x)(Q2u)(H(x)G(u))=(Q1x)H(x)(Q2u)G(u), где Q1, Q2 кванторы  или , u не входит Н(х), а х не входит в G(u).

35. (x)H(x)=(z)H(z)

36. (x)H(x)=(z)H(z)

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

Пример. Доказать равносильность формул F и G.

F=(x)(y)[S(x)P(x,y)(z)(T(z)P(x,z))]

G=(x)(y)[S(x)P(x,y)(z)(T(z)P(x,z))]

1. Исключение импликации

F=(x)(y)[(S(x)P(x,y))(z)(T(z)P(x,z))]

2. F=(x)(y)[(S(x)P(x,y))(z)(T(z)P(x,z))]

3. F=(x)(y)[ (S(x)P(x,y))(z)(T(z)P(x,z))]

4. F=(x)(y)[S(x)P(x,y)(z)(T(z)P(x,z))] = G

Еще пример. Доказать равносильность формул F и G.

F=(x)P(x)[(x)(y)(H(x,y)S(x)) (y)(Q(x,y)P(y))]

G=(x)P(x)[(x)(y)(H(x,y)S(x))(y)[Q(x,y)P(y))]

1. HG=HG - исключение импликации

F=(x)P(x)[ (x)(y)(H(x,y)S(x)) ( y)(Q(x,y)P(y)) ]

2. (HG)=HG

F=(x)P(x)[ (x)(y)(H(x,y)S(x))  (y)(Q(x,y)P(y))]

3. F=(x)P(x)[ (x)(y)(H(x,y)S(x))  (y)(Q(x,y)P(y))]

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

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

z  P1,p2,…Pk

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

z P1P2 … Pk

Если клаузы выглядят так P1P2 … Pk, то это заведомая ложь.

А если так: z  , то это факт.

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

M(x,y) = x mother of y

O(x,y) = x father of y

D(x,y) = x dad of y

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

D(x,y)O(x,z), M(z,y)

D(x,y)O(x,z), O(z,y)

Алгоритм приведения к виду Хорна.

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

1) Исключение знака импликации  и эквивалентности . (Законы 1 и 2)

2) Продвижение знака отрицания до атома (предиката) или атомарной формулы (законы 15, 16, 17, 29, 30)

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

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

5) Избавление от кванторов существования по следующим правилам:

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

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

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

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

A(BC)=(AB)(AC)

A(BC) = ABC

A(BC)=ABC

A1A2A3(B1B2B3) = (A1A2A3B1)(A1A2A3B2)(A1A2A3B3)

8) Запись в виде множества дизъюнктивов S={D1,D2..Dn)

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

AB=AB

ABC=CAB