Студопедия — A®B; B®C; C 8 страница
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

A®B; B®C; C 8 страница






· Выписать множество дизъюнктов:

K= {(ùP3(x)ÚP1 (x)ÚP5(f(x))); (ùP3(x)ÚP1 (x)Ú P24 (x; f(x))); P2(a); P3(a);

(ùP24 (a; y)ÚP2(y)); (ùP1(x)ÚùP2(x)); (ùP5(x)ÚùP2(x))};

 

· Выполнить унификацию и формирование резольвент

ùP2(a)
1) xòa (ùP1(x)ÚùP2(x)) Ú P2(a)= ùP1(a)Ú = ùP1(a);

ùP1(a)
2)ùP1(a)Úxòa(ùP3(x)ÚP1 (x)ÚP24 (x; f(x)))= ÚùP3(a)Ú P24 (a; f(a));

ùP1(a) 1(a)
3) ÚùP3(a) Ú P24 (a; f(a))Ú yòf(a) (ùP24 (a; y)ÚP2(y))=

P24 (a; f(a))
ùP1(a)
ÚùP3(a)Ú Ú P2(f(a));

P24 (a; f(a))
ùP1(a)
4) ÚùP3(a)Ú Ú P2(f(a)) Úxòf(a)(ùP5(x)ÚùP2(x))=

P24 (a; f(a))
P2(f(a))
ùP1(a)
ÚùP3(a)Ú Ú ÚùP5(f(a));

P24 (a; f(a))
P2(f(a))
ùP1(a)
5) ÚùP3(a)Ú Ú ÚùP5(f(a)) Ú

P2(f(a))
ùP5(f(a))
P24 (a; f(a))
ùP1(a)
xòa(ùP3(x)ÚP1 (x)ÚP5(f(x)))= ÚùP3(a)Ú Ú Ú Ú P1 (a);

P24 (a; f(a))
ùP1(a)
P2(f(a))
ùP5(f(a))
6) ÚùP3(a)Ú Ú Ú Ú P1 (a)ÚùP1(a)=

ùP5(f(a))
P2(f(a))
P24 (a; f(a))
P1(a)
ùP1(a)
ÚùP3(a)Ú Ú Ú Ú =

ùP1(a)
ÚùP3(a);

ùP3(a)
ùP1(a)
ùP1(a)
7) ÚùP3(a) Ú P3(a)= Ú = .

 

На рис. 14 дан граф линейной унификации этого примера.

 

ùP1(x)ÚùP2(x)

ùP1(a) P2(a)

ùP1(a)
ÚùP3(a)Ú P24 (a; f(a)) ùP3(x)ÚP1 (x)ÚP24 (x; f(x))

ùP1(a)
P24 (a; f(a))
ÚùP3(a)Ú Ú P2(f(a)) ùP24 (a; y)ÚP2(y)

ùP1(a)
P24 (a; f(a))
P2(f(a))
ÚùP3(a) Ú Ú Ú ùP5(x)ÚùP2(x)

ùP1(a)
P24 (a; f(a))
P2(f(a))
ÚùP5(f(a))

ÚùP3(a)Ú Ú Ú ùP3(x)ÚP1 (x)ÚP5(f(x))

ùP1(a)
ùP5(f(a))
Ú ÚP1 (x)

ÚùP3(a) ùP1(a)

 P3(a)

Рис. 14. Граф линейной унификации

 

Пример: Существуют студенты, которые любят всех преподавателей. Ни один из студентов не любит невежд. Следовательно, ни один из преподавателей не является невеждой. [1]

Пусть P1(x):=” x – студент”, P2(y):=”y – преподаватель”, P23(x, y):=”x любит y”, P4(y):=”y - невежда”.

Формулы этого суждение имеют вид:

$x(P1(x)&"y(P2 (y)®P23(x; y)));


"x(P1(x) ®"y(P4 (y)®ùP23(x; y)));

"y(P2 (y)®ùP4(y));

· Преобразовать посылки и отрицание заключения в ССФ:

1) F1=$x(P1(x)&"y(P2 (y)®P23(x; y)))= $x"y(P1(x)& (P2 (y)®P23(x; y)))= "y(P1(a)& (P2 (y)®P23(a; y)))= "y(P1(a)& (ùP2 (y)ÚP23(a; y)));

M1= P1(a)&(ùP2 (y)ÚP23(a; y));

2) F2="x(P1(x) ®"y(P4 (y)®ùP23(x; y)))=

"x"y (P1(x) ® (P4 (y)®ùP23(x; y)))= "x"y (ùP1(x)ÚùP4 (y)ÚùP23(x; y)));

M2=(ùP1(x)ÚùP4 (y)ÚùP23(x; y));

3) F3=ù"y(P2 (y)®ùP4(y))= $y(ù(ùP2(y)ÚùP4(y))= $y(P2(y) &P4(y))=

P2(b)&P4(b);

M3=P2(b)&P4(b).

· Выписать множество дизъюнктов:

K={P1(a); (ùP2 (y)ÚP23(a; y)); (ùP1(x)ÚùP4 (y)ÚùP23(x; y)); P2(b); P4(b)};

· Выполнить унификацию и формирование резольвент:

 

P2(b)
1) P2(b) Ú xòb(ùP2 (y)ÚP23(a; y))= ÚP23(a; b);

P2(b)
2) ÚP23(a; b)Úyòb (ùP1(x)ÚùP4 (y)ÚùP23(x; y))=

P2(b)
ÚP23(a; b)Ú(ùP1(x)ÚùP4 (b)ÚùP23(x; b));

P2(b)
3) ÚP23(a; b)Úxòa(ùP1(x)ÚùP4 (b)ÚùP23(x; b))=

Ú
P23(a; b)
P2(b)
ÚùP1(a)ÚùP4 (b);

P2(b)
P23(a; b)
4) Ú ÚùP1(a)ÚùP4 (b) ÚP1(a)=

P2(b)
P23(a; b)
ùP1(a)
Ú Ú ÚùP4 (b);

ùP1(a)
P23(a; b)
P2(b)
5) Ú Ú ÚùP4 (b) ÚP4(b)=

ùP4 (b)
ùP1(a)
P23(a; b)
P2(b)
Ú Ú Ú = .

 

На рис. 15 приведен граф линейной унификации для этого примера.

P2(b)

P2(b)
P2(b)
ÚP23(a; b) ùP2 (y)ÚP23(a; y)

ÚP23(a; b)Ú (ùP1(x)ÚùP4 (b)Ú ùP1(x)ÚùP4 (y)ÚùP23(x; y)

P23(a; b)
P2(b)
ÚùP23(x; b))

ùP1(a)
Ú ÚùP1(a) ÚùP4 (b) ùP1(x)ÚùP4 (b)ÚùP23(x; b))

P23(a; b)
P2(b)
Ú Ú ÚùP4 (b) P1(a)

 P4(b)

 

Рис. 15. Граф линейной унификации

 

2.3 Проблемы в исчислении предикатов

Для обоснования исчисления предикатов, как для любой аксиоматической теории, необходимо рассмотреть проблемы разрешимости и непротиворечивости.

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

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

 

2.4 Логическое программирование

Типичным представителем языка программирования для описания последовательности действий в процессе логического вывода является Prolog.

Пролог-программа состоит из предложений, которые бывают трех типов: факты, правила и вопросы.

· Факты есть повествовательные предложения, имеющие значение только “истина” (см. 1.5). Множество фактов формирует так называемую экстенсиональную базу знаний о предметной области. Правила это условные предложения, истинность заключения которых зависит от истинности условий, поэтому в структуру правила включены предметные переменные, имена которых начинаются с прописной буквы и предметные постоянные, имена которых начинаются со строчной буквы. Множество правил формирует интенсиональную базу знаний о предметной области и определяет механизм достижения цели при заданных условиях.

Левая часть правила - <голова> - есть формализованное описание заключения, а правая часть правила – <тело> - формализованное описание условий, определяющих истинность вывода заключения, т.е.

<голова>:-<тело>”.”

Символ “:-“ соответствует символу обратной импликации ””.

Если множество условий имеют между собой конъюнктивную связь, то между ними ставится запятая, т.е.

<заключение>:-<условие>{“,”<условие>}”.”.

Если условия имеют между собой дизъюнктивную связь, то между ними ставится точка с запятой, т.е.

<заключение>:-<условие>{“;”<условие>}”.”.

На языке Prolog эти правила записывают так:

<заключение>:-

<условие_1>”,”

<условие_2>”;”

<условие_3>”.”

Голова предложения при написании программы всегда сдвинута влево относительно перечня условий. Каждое условие начинается с новой строки.

Смысл этого правила таков:“если истинны условия 1 и 2 или 3, то истинно и заключение ”.

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

Если тело пусто, то голова есть истинное утверждение или аксиома. Факты –это предложения, имеющие пустое тело.

<заключение>”.”.

Если голова пуста, то тело продставляет вопрос, т.е.

? - <тело>”.”.

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

Например, множество правил для определения степени родства:

дед(X, Y):-

родитель(X, Z),

родитель(Z, Y).

брат(X, Y):-

родитель(Z, X),

потомок(X; U; Z, Y):-

родитель(Y, Z),

родитель(Z, U),

родитель(U, X).

родитель(Z, Y).

можно применить к родословной русских князей X века:

отец(игорь, святослав).

отец(святослав,владимир).

отец(владимир, борис).

отец(владимир,глеб).

?-дед(святослав, Y).

Y=борис.

Y=глеб.

?-брат(X, Y).

X=борис.

Y=глеб.

?-потомок(X; Y; Z, игорь).

Z=святослав.

U=владимир.

X=борис.

X=глеб.

Предметные переменные заключения, как правило, связаны квантором общности, а для условий - квантором существования. Например, правило “дед(X, Y):- родитель(X, Z), родитель(Z, Y)” утверждает, что если для всех X и Y существует Z, то X -дед для Y.

Правило “брат(X, Y):-родитель(Z, X), родитель(Z, Y)” утверждает, что если для всякого X и Y существует общий Z, то X брат Y.

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

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


Литература

1. Вагин В.Н. Дедукция и обобщение в системах принятия решений.- М.: Наука, 1988г. – 384 с.

2. Войшвилло Е.К., Дектярев М.Г. Логика как часть теории познания и научной методологии. кн.1. Учебное пособие. –М.: Наука, 1994г. –312с.

3. Зегет В. Элементарная логика. - М.: Высшая школа, 1985г..- 256 с.

4. Кириллов В.И., Старченко А.А. Логика. - М.: Высшая школа, 1987г.– 271с.

5. Kузнецов О.П., Андельсон-Вельский Г.М. Дискретная матема­тика. для инженера.- М.: Энергоатомиздат, 1988г.—480 с.

6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, матeмaтичecкoй логике и теории алгоритмов 240с.

7. ЛихтарниковЛ.М., Сукачева Т.Г. Математическая логика /курс лекций/ - СПб.: “Лань”, 1998г..-288с.

8. Першиков В.И., Савинков В.М. Толковый словарь по информатике – М.: Финансы и статистика, 1991г. –543с.

9. Пономарев В.Ф. Математические методы и модели в обработке информации и управлении. Методические разработки по разделу “Формальные системы”- Калининград: КГТУ, 1992г..

10. Роберт P. Столл. Множества. Логика. Аксиоматические теории.- М.: Просвещение, 1968. – 231 с.

 

Предметный указатель

Аксиомы исчисления высказываний, 45, 49

Алгебра высказываний, 7

Алгебра предикатов, 92







Дата добавления: 2015-09-15; просмотров: 358. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

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

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

СИНТАКСИЧЕСКАЯ РАБОТА В СИСТЕМЕ РАЗВИТИЯ РЕЧИ УЧАЩИХСЯ В языке различаются уровни — уровень слова (лексический), уровень словосочетания и предложения (синтаксический) и уровень Словосочетание в этом смысле может рассматриваться как переходное звено от лексического уровня к синтаксическому...

Плейотропное действие генов. Примеры. Плейотропное действие генов - это зависимость нескольких признаков от одного гена, то есть множественное действие одного гена...

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

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

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

Studopedia.info - Студопедия - 2014-2024 год . (0.014 сек.) русская версия | украинская версия