Ш.И._Галиев_МЛ_и_ТА_2004
.pdf1| "Кто родитель Боба?":
? - родитель (Х,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). |
Известно, что если пропозициональная форма С представлена |
|
в к.н.ф, |
или с.к.н.ф., то каждый ее конъюнктивный член, а также |
конъюнкция любого числа конъюнктивных членов является логиче ским следствием и! С. Это позюлда нвкодигь езедегш из данных пропозициональных форм. Пусть лапы пропозициональные формы А