Ш.И._Галиев_МЛ_и_ТА_2004

1| "Кто родитель Боба?":

? - родитель (Х,5сб). Система отвеют: Х= оям;Х“гом

2) 'Кто ней родитель?':

f - родитель (X.Y).

Система распечатает «пмпжные значенияX иY.

3) "Кто внукн Тома? " Так кап в системе не введено понятие внуков, то строим сложныйвопрос:

?-ропятсль (том, X), родитель (X, Y).

иия. Составной вопрос интерпретируется: найти Х,У, удовлетворяю­ щие двум требованиям:

родитель(том,Х) продитель(X.Y).

3-ролBTejiufX.Y), рвдати. (гои,Х).

Ответ не зависит от порядка в сипу того, fro система получит для вопросадизъюнкг:

] родтелъ(Х,У)'./|родитель(тпм.Х), который равносилен днзьюнвлу:

1 родитсяь(том,хИ родителях,Y). На вопрос 3) система oiermT

Х =«об У = энв; ХМо<5 Y= паг

Пользователь ПРОЛОГа молят совершенно не знать мечил резолюций. Система сача находитотоегы.

§ 13. Введение и использование правил вПРОЛОГе

В качестве расширения рассмотренной в §12 программы на ПРОЛОГе Введем отношение дети, которое обратно отношению

121

родитель. Можно было бы определить дети тем же сппсобои, чтос родитель, т.е. предстаем»описок:

дета (боб, нам).

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

ДллюехХнУ Yдета X, если

Xявляется родителемY.

Спответстоующмпрологмеко*предаожешис тем же смыслом кмеег

детя (Y,X):- родатель(X,Y).

(3.20)

Приведенное прологовскос предложение (320) называется

Предложение родитель(ток,лм). .

условия К рассмотренной в 112 программе добавим «ше предложение

<3.20). Спросим полученную программу, «вллется ли Лиз отпрыс*ом Точи:

?- дети (лп, том). Предложение(3.20) на ядам логикикчеетвид:

родигелк(Х,У) "э цвти(У,Х). Преобразуем последнее выражение и дизъюнкт

"Iродитель(Х,У)^депцТ,Х). (321)

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

(3.22)

Из (3.21) и(3.22) получим:

! рпцкгвль (том, лш).

Далее, Исчольтуя предложение (дизъюнкт) (3.12), i

§ 14. Рекурсивное змание правил вПРОЛОГе

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

Будем считать, что некоторый X является отдаленным предком неко­ торого Z, если между X и 2 «шествует цгночка люден, евлйнных между собой отношениемроштояьродитель.

Первое правилопростое иегп можносформулироватьтак: Для всехX иZ:

X - предок Z, если X -родитель Z.

ГЬо псремиштеина Пролог в визе предложении |ф«пк(Х,7,):-

родгге.1ЦХ,г)| Второе правило сложнее. Один из способов определения

отдаленные ролсгвенников падать их слелующны множеством пред­ ложений:

123

предок(Х,7.):- родигель(Х^).

предок(Х.£): - роднт«ль(Х,У), ролиг«ль(¥Й .

npenoK(JiZ):- роднтель(Х,У1(, родитель(У1,¥2), ponaiejiK(Yi,Z).

np«H3K(X,Z):-
роди1СЛЬ(Х,У1),
ролвт«льО'1,У2),
pomiTtib(Y2,Y3),
роднтель(УЗ.Я(.
Эта программа ЯДОка и,	что важнее, работает только
а опремдадких прщглгл, Ой»	о6тр>живяа г.рьдааг шхь
до опр«дв.]Вннпй глубиныфамильногодерем.
Существует компактная и корректная формулировка отношения

предок, которая работает ш любую глуошу Клюпсвпя идея для это­ го; определить01ношение предок черекнегосамого, т.е. ввести рекур­ сивное определение, Это определение будет следующим:

ДмиссхХиг

X- предок г, если существуетY, такой, что

(1) X-родитель Y и

(2) V-предокZ.

Предложена ПРОЛОГа, имеющее ют *е синел, залистаете» •в виде;

up«0K(X,Z):- роявтель<Х,У), npe;iOK(Y,Z).

124

Полнм программа для отношении предок содержит оба прави­ ла: одно для ближайших предков и другое для отдаленных предков. В результате имеем:

предоii(X,Z): - рпишель(Х,2).

iipwoicfX.Z):-
роаителЦХЛ),	(323)
предоK(Y,Z).
Отметим, что • рекурсивное задание правил	проводится

например, на следующее

о[кдок(Х,¥); - рпдителЦХ.Г).

прсдок(ХЛ|: - ирсдок(Х,У), прслак(УД).

Воли к рассмотренной в § 12 программе добавить предложение (3.23), то полученную программу можно, иапричер, спросить:

«Кто потомки Пам?» Не ПРОЛОГе этот вопрос запишемовиде:

?-предок(пя«,Х).

Х=пжим Выясним, как получает программа ответ. Предложения (3.23)

К1,ювются о виде: роднтеиь(ХД=>предок(Х,2), роднтоль(Х,У)&прсдок(УД=>предок(Х,2).

125

Преобразовав эти формулы, полунии:
|родитель(Х.2)упрецок{Х2),	(3.24)
1 роди!гль(Х,У)'/1 npeaox(Y,Z)vnpe®JK(X,Z).	(3.25)
Вопрос к системе преобразуетсяквиду
"lnp«OK(mM,X)vANS<X).	(3.26)

Для получения ответа используются предложения (дилыонкты) (3.10)-(3.15) И диаъютпъ! (3.2ДНЗ-26)-

Непосредственная потомок дли Пам выявится, ес.та из (3.24) и

(3.26) получитьбинарную резольвенту:
l p o f l H T e ; i b ( n a M	, Z ) (3v .27)A N

Затем получим ANS(6o6) как бинарную резольвенту из (3.27) и (3.10).

Потомки второго уровня (внуки Пам) выявмся в результат*

полученияследующих резольвент
1родлтоль(пам,У)ЛiipeaotfY,X)'./ANS(X),	¢3.28)
которое получено из (3.25) и(3.26),
1родителях,Y)v",poa;iTftiib(naM,X)vANS(Y),	(3.2¾
полученное из (3.28) и (3.24),
1poairrenb(6o6,Y)vAXS(Y),	(3.30)

полученное из (3.29) и(ЗЛО). Далее имеемANS(3HII) - пилучввдHI П.30) и (3.13), ANS(naT) - получено и*(3.30) и (3.14).

Потомки третьего уровня (правнуки Пам) выявятся в результате следующие преобразований:

1 родктоль(памДуАКS(Z),

(3-31)

получено ж (3-26) и13.24).

1rpeaoK(6o6,X)vANStX),

(3.32)

получено из (3.31) и (3.10),

1 родителb(do6,Y)v| npejnKfY^XjvANSIXj,

(3.33)

получено из [3.32) и(3.25),

продителях,Yjvl родИте.ть(?об,Х)./ANS(Y),

(3.34)

получено из (3.33) и (3.24),

1 po№Te.ni,(naT,y)vANS(Y),

(3-35)

получено из (3.34) и (Э.14). Затем из (3.35) в (3.15) получим: АМЯ(пжим),

OTXICTHM, что в каждом из рассмотренныхслучае» выполняет­ ся следующее:

1} в перво)! выполняемой резолюции используете* днлюнкт, построенный для вопроса;

2) я каждой последующей резолюции должна участвовать резольвента предыдущейрезолюции

Целью данного пособия вс является изложение языка ПРОЛОГ. Эти параграфы только кллшетоируют, как работает логика в многообещающем яэике ПРОЛОГ.

ЯпмкПРОЛОГ находит существенное использование:

-при описании и решении с-адач ка графах:

-в экспортных системах (системы испытаний, медицинская ди­ агностика, нахождение неисправностей втехнических системах);

док.иотельотво теорем, различные игры, шахматы, кубики);

-при созданиисистем переводас одногоязыкападругой;

-в системахуправлении производственными процессами;

-при создании пакетов символьных вычислений для решения уравнений, дифференцирования иинтегрирования;

-при создании специализированных и общих вопросноотчетныхсистем.

Метод резолюций используется не только в языке ПРОЛОГ, до и а некоторых системах управления базами данных и некоторых спе­ циализированных экспертных системах. Программа ни ПРОЛОГе включает:

факты типа: родмель(то!И,бо6). родитедь(6об,лвз).

правила вила: прсдок(Х,У): -

родятель(Х2)| яреаок|1,У).

целлит ?-предо«(Х,том).

Мехают ПРОЛОГв состоит в том, чтобыдоказать истинность цели и (или) найти знамение переменного цели, при котором цель истинна. Вычисления всегда начинаются с цели; рассматриваются возможные вариант нахождения резольвент.

В настоящее время разработаны различные модификации ПРО­ ЛОГа. Существует много работ по связыванию ПРОЛОГа с багами данных. В принципе программу на ПРОЛОГе можно унсе рассматривать как некоторуюбазуданных

Соберисьидейещуй.

Биля ГеКтс

§ 15. Вопросы н темы для самопроиерки

(.Определение логического следствия и-I данной пропорцио­ нальной формы(формулылогики высказываний).

2.Свойствалогическогоследования.

12!

3. Логическое следствие из множества формул логики выека-

4, Проблем» дедукции логики высказываний. Решение проблемы дедукции с использованием противоречивостиспециальной формулы.

5 Литералы, контрарные литералы, дизъюнкты.

6.Бинарные резольвентыдизъюнктовлогикивысказываний.

7.Теорема о полном методарезолюций,

8.Метод резолюция влогике высказываний.

9.Методаасышеим уровня.

!0. Стратегии вычеркивания.

11.Лок-резолюшя. Теорема о полноте метода лок-ремлюций. Зависит ли результат лак-резолюции от изменение индексов литера-

12.Метод резолюцийдля хорновскнх цизыонхтпв.

13.Определение логического следствиядля формуллогики пре­

дикатов.

ли формулы логики предикатов существует сколемовсквя стандартная

15.Единственна ли сколемовская стандартная форма для заданной формулыпотки иредихт-ов?

16.Алюритми натадення сшюмевскихымдяртшх форм. П. Когда формула равносильна своей сколсыпвсхой стандарт­

ной форма?

18.Унификации. Алгоритмы унификации.

19.Метод резолюции в логике предикатов, отличия от метода резолюций в логике высказываний.

Аристотеля.

21.Использование метода резолюций в ПГОЛОГе при работе

22.Для каких задачвводится AHS-преднкат?

23.Приведите примерыведения правка в ПРОЛОГе.

24.Рскурснзнсе задание правил вПРОЛОГе.

129

§16. Уиражиеияя

1.Доказать, что А )= В&.С тогоа и только тогда, ког

\А=>В&С?.

a)	В тогда и только тогда, когда А ^А ъ -А *-1 (=

5)А[ГАъ.,.^4п(=В тогда итолькотогда, когдв

a)AiAb—>Ai^ В тогда и только тогда, «алш А1&А7&....&Л„

К

5. Доказать, что гели A f=С и В f=С тоAvB |=С (доказательство разбором случаев).

4, Доказать, что если А |= В, то для произвольной пролозикионакьной формы Симеег мест А&С^В

5. Доказать, что
а)	А,Л=>КJ:В (правило заключении);
5)A,B\i4&B; в) A.B^A'jB,		f) A fUvfl;
д)/»=>£Г,"1в j>"U (правило отрицания);
е)	А=$В, П^С	(правило силлогизма);
ж)4=58 ^=1в=>14 (правилоконтрапозицнн);
s)	(правило перестанпаки посылок);

и)^=»(В=С) (>.4&JB=»C(правилосоединениялосылпк); к)A&£=iC ^A=PfB=>C) (правилорагьеднкеннч посылок);

м)	,&8t )=В,-дляхалдою i(\£i<k).
Известно, что если пропозициональная форма С представлена
в к.н.ф,	или с.к.н.ф., то каждый ее конъюнктивный член, а также

конъюнкция любого числа конъюнктивных членов является логиче­ ским следствием и! С. Это позюлда нвкодигь езедегш из данных пропозициональных форм. Пусть лапы пропозициональные формы А