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

Литера называется позитивной, если она не содержит отриид-

Дизъюнкт D называется хорновекли, если он содержи не более оддой позитивной литеры. Примеры хорпооских дигьюнк-

TOV. Л,	В, \i, 1 S,	Tiv I CvB, 1 Av \ 8,	ylvlcV CvD.	В общем
случае	хорновский	дизъюнкт мо«но	представить	а виде

"U]v”kiv..,v"k,ivtf или 1jiivl ,4iv...v"li4„. nil, кли А. При этом дигь-

шнкт	1	X]v| Atv...v A„vB назыпают точным,	дгаыомкг
\Л'У		]Л,~ негативным, едизъюнктА - унитарным патчив-
ит дизъюнктом.
	Рассмотрим множество Л' хоркокких дазьюнктоп бет iанало­
гий	Невыполнимость можно проверить г помощью следующего
алгоритма.
	:. Полагаем; чтоS^=S
	2.Пусть S*'1, >el, построено. Дл* построения S''		выбираем
н5Х“'лизъюнх1ыД1и£>1та«ие,что:
	О, - унитарный позитивныйдизъюнкт, пусть, напримгр, Di=P;
	Di - дизыанШ1, содержащий литеру 1 Р.
	Вычисляем резольвенту R для дизьюнетов О, и Oj и полагаем,
что S" =		£>з})и{Д(. Эту процедуру повторяем до тех пор, пом

не получим пустой дкгмоист О либо пока не окажется, что в S несуществует датькжктоаД и Ojуказанны» видов,

пустого дизыонетаозначает, что множествоS хорнопски»дизъюнктов невыполнимо. Если же окажется, что S”1 не содержит дязыонктов Oi и Dt указанных видов, то исходное множено S хоркояских ди'льюнктоь выполнимо.

Реализацию этогоалгоритма проще проводить с помадьш таблицы. Продемонстрируем это на примере. Пусть имеем множество хорнпвеких дитаоншов; S={Pvl Qvl В, Г, g iivl АЛ gvl U, Sv] Т, 1 fv l gvl Z}. Вапишем шуыимпи ю - S в ячейки нулевой строки приводимой далее таблицы. Каждая п-я строка содержи! дизъюнкты из S", п 2 0.

Дизъюнкты

л1л/1еЛь IЯ\Лт ’Pv'fivl

пупойд«зккшкт П, следовательно, множество Sхорноаскяхдкгьюниов

§ 8. Преобразование формул логики предикатов. Сколомовская стандартам форма

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

т.е. о виде; QiQi-.Q.JI, raeQ-.,Q^ ,Q„- некоторая совокупног-гькван­ торов. а формулаВ несодержи?кван/оров.

102

Для формула А ~ Q<Qi..Q£ совокупность квантора» QiQ:, . ,у.| считаете? префиксов формулы-4. а формулаflматрицей фирмулы А. Будем дополнительно считать, чго чаг-рищ приведена к

конъюнктивнойнормальной форме.
Очевидно,	что формула	А является противоречивы тогда
и только тогда,	когда 1 А	явлистся логически общезначимой.

Из снойствформул (см. § 5 га. 2) следует, что формулаВ является ло- I «чески общезначимой тогда и только тогда, когда логически обще­ значимо замыкание Ji* формуда в. Кек известно, замывание В* фор­ мулы В получается приписыванием к й кванторов вссо5шноети по псем ее свободным переменным

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

Осуществим следующие преобразования формул логики преди­ катов(формулызаписаны с использованиемсвязок1,=>):

2)лобьемся того, чтобы 1 относилась только к элсмеи-гарныи формулам: это можно сделать, используя Правила перенесения отрицания nepei кванторы ияакиныде Моргана;

3)проведем стандартизацию (переименование) переменных для

4)вынесем кванторы зо скобки, т.е, получим предваренную нормальную форму:

Л - Q\X\ Q&2- QrfJf, здеоь В - матрица формулы, a QiXiQiXi.-Q^,,- пре^ткс (совокупность кванторов). Будем считать, чтоматрица приведена к коньюнктивкой нормальной форме;

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

сколемооеюк функций (SkoltmТ).
Осуществим	это	следующим	образом.	Пусть

л w Q\*I, Qff-ъ- ; УА-9, где 2|Х|,б»*г,-.бл*п ~ кванторы всеобщно­ сти или существования. Положим, что фс, - квантор существования

1	1	I	3	«й квантор всеобщ-
кости не стоит е префиксепемг Q,x, то выбкраеь1новую предметную
постоянную с,	отличную	от вмх предметны»: постоянных в В.

н заменам все х„ встречающиеся в г, «а с и аычвркиваеч fl* из префикса. Покажем это на примере. Пусть имеем формулу 3*Чу(Р?(;дО=»0?(х,в)). Тогда для TOMIIOTEмня квантора Зх введем постоянную с. В ргаультате tюлучим формулу:

Рассмотрим другой пример Пусть имеем формулу 3«3yVj(Pf(4 .,x)=je|(fl,6,v№ Тогда исключая ""ангоры существоаания. получим:Vz(Pj(c,rfj)=> Q‘ (a.b.c.d)).

«тречак-идихс*пенсекмнкра cyupenonnuQjt,f 1< si< 5i<... < j„< n, то выберем новую ет-местную функциомльную букву/", откичную

от других функциональных 6)16,		аз Л, и шмпхч все J, в В
на /"(« 1Гс ,	ивычеркнем близ префикса.
Пример. Пусть имеем форму		Ввей»
Vx(\/\x,Mx))vQlfM,fmy		'
Пример.	Пусть ниим	формулу: 'ix'Vy2z(P(xj'j=/

(х)^гй(г)))), Вводи необходимую функцию и исключая импли­

кацию, получим: VJ VJO ^ K ад^)/М ЛШ *,У)))])- Проводим описанную процедурудо тех пор, пока пе исключим

ке хмнторы существования. Полученная в результате формула есть

сшековская стандартная ферма, я а краткости стандартное форма формулыА. Константа и функции, используемые для замены переменных кваеторя существования, называются лгалсдимошш

Праиер Пустьимеем формулу 5*w)). Приведем матрицу формулы к к.н.ф.:УгЭуЭй1 и^)'/5(х^л))&(Л(х;) vS(xyj)). Затеи введем функцииЛ*Х&Y

лО ^Д г)К Полученная формула является стандартной формой неходкой

формулы.

(ятерт) чакте првдшгатое.

Дизъюнктом «логике предикатив вазьшаютдизъюнкцию лите-

Иногда цгпгралы или датюкеты нгныааюг ыоукши (clause -

Пусть формула А приведено в предареиную нормальную фор­ му, а и матрица представлена I к.я.ф., т.е. -<=<6

{Q)X,Qibi...Q^n)Di&Di&...&D*, гдб (Q#XQ£*I-Q J , \ - префикс фор­ мулы А, 1 Д А ..-Д . -аюыонкты Попоиии, чгосгандаргнля форма дня А равна ArtQ^tQtXT £а)'С,&С,&...&С„, где в префиксе опутана кканторысущсствопаим, а С, полненыщ D,(!<]<«) вееде-

Отшгич, что стандартная форма А, формулы Л определяете» не единственным «Сразим, ибосколемово'иефункцииможно плодить

Имеетместоследующаятеорема.

Пустьимеетсятолькоодин кванторсуществование Qj:;.

/4—Wc>...VXAO3*,Кс„	|... J^»2. . A )
Положим Л "* :	.....
*ж!--лО,ГдеД*!,*ь...Л!)-™олеиовбкал функция.
Покажгы, чтоА лрвтнюрсчивятогяа и только тогда, kgiаипро-

Пусть А - протаворечис. Допустим, что А, не противоречие, следовательно, существуй интерпретация, в которой А, выполнима, т.й для V,f,,V*2,... ,W,-I Jl, =.Дх|Л.... *.l). ’ ТО при VXh-i,.. ,Vx, фор­ мул* В принимает эначмше "И", а это противоречит тому, что Л - противоречие. Окдовагелыю,А,-противоречие.

Обратно, пусп. Ai - противоречие. Допустим, что А - непроти­ воречив, т.в. существует интерпретация:, и которой А - выполнимо.

Следовательно,		дл*	^i,Vr2;...,Vxr., найдетгв				х,	такое,	что при
Vr,ii,...,Vr„	формула		В примет		значепне	И	Введем		функцию
Д*|....,х№0 = *г Тогда ясно,				что А,■■■■Я, что		противоречш			условию
As - противоречие.
Если	в	префиксе		имеется	т кванторои			существовании,
to доказательство провоартсяаналогично.
Смданш II. ЕслиА- противоречиеи-4,=©								OjCi&Cifk.
т А -С Ж г й		&Q,.							I
Следом!и 5.2,			ГСуси. А, - стандартная ^орча формулы А н!
пустьА -противоречие. Ти-даД, ~/t.									I

Отметим, иго если А не явллегса противоречием, то может быть, что А ие рммосичыш А,. Например, пусть А - ЗдД-с). Тогда

А,=Р{а). Построим интерпретацию. Пусть область интерпретации УЛ=\\2). Положим, чтоо=1, a Ил) обозначает предики <« - чгтное

1D6

число». ТогдаА=Р(Г) обозначает. «1 - четноечисло)! Следовательно, формулаА, ложка в этой интерпретации. Формула/! вэтой интерпре­ тации предгвв.иет истинное высказывание. 3rf<u - четное число»). Таким образом,дл>даннойформулыЛ форотлыЛuAs неравносильны.

§ 9. Унификация

Процесс унификации является

ш резольвент(длямещдарезолюций). Пусть задано множество дизъюнктов. Калцый

Пример. Пусть имеемследующее мно:кестоодизъюнктов:

Дизмликт Дизъюнкт

Термы литерала могут быть переменными, нопоянныки клн выражениями, состоящими из функциональны): буке н термов. Например. Дл» литерала PU. {!у): Ь) имеем, что t - переменна»,

Подананозоиный частный иртой мтраяа получается при подстановке в лотералытермов«место переменных. Пусть имеем ли* «рал fluffy). Ь).Кгочастнымислучаями5удут:

Л -Л * м .» ). Pj = Р(х,Лм 4),

Р*-* Р{с,Яо), Ь)- константныйчсктшыаагучайяшперма

Подстановки, примененные 8 рассматриваемом примере, можно обо­ значитьследующимобразом:

9, " {г/дш'у}, здесьг подставляетсявместох, aw вмкто.у, 9,-<«(>};

3j - {^ф:, Ыу)\ 9, - {eftc а!у\.

Применение подстановки 0 к литералу Р обозначаем Д, Тогда

вм“ м	А>,“ Л.	А, = \
	Рь -Р г,	PS)- ft.

Вели6 - подстановка и она применяется к каждому из литера­ лов £/,то полученныечастные случаиобозначаются через {A}s

Последовательное применение двух подстановок 0[ и 6j даст новую подстановку93, которуюобозначаем0. - Я, •9;.

Множество {!,( литералов называется унифицируемым, если существуеттакая подстановка0, что

№,)в-(У .-

Вэтом случи подстаноекуО называютунифтапором iwt {£>).

Пусть инеем множество литералов (Да, fy). b). Р{х- Л*). &)}. где£, =Р(х, fly), b), Li =P{a,ftb), 4), Подстановкаб = {ст/х, Ыу) явля­ ется, очевидно, унификаторомдля этогомножествалитералов.

Унификатор о дл* множества выражения {£i,i^....£>) называ­ ете» наиболее общимунификатором Тогда к только тогда, когда для каждого унификатора 0 дня иого множества существует тагая под-

Сусцествует алгоритм, называемый алгоритмом унификации, который приводит к наиболее общему унификатору для унифицируе­ мого множества литералов {£,} и сообщает о неудаче, если это мно­ жествоне унифицируемо.

Алгоритм унификации: Алгоритм начинает работу с пустой подстановки н шаг зашагомстроитнаиболееобщийунификатор, если

Ш

таковой cyioecreycr. Предположим, что нак-и шаге получена подстпновка 0» Если все литералы из (£,,) о речупьтате. становятся идентич­ ными. то 0 = 0* и есть наиболее общийуЕТнфикатир. Q противном слу­ чае каждый ич пстгералов в (£i}g, рассматривается как цепочка символоп и наделяется позиция первого символа, в которой не все из лтсралав игйсш'1 одинаковый символ. Рассмотрим пример tttyx лите­ ралов. Стрелками пометки позиции, где появились различные симво­ лы (при просмотре слева направо):

{Р(а, На, ё(г)|, Ш)), Pl.aJ.a, Ч ?(w))) .

1 _• >

Затем конструируете.» множество рассогласования W, содержа­ щее правильно построенные выражения из каждого литерала, которые начинаются с позиции рассогласования (правильно построенное ныражение представляет ообоЯ либо терм, либо литерал). Так. для рассмотренного примера множеством рассогласования будет

Далее модифицируем (еспн можно) подстановку 9|, чтобы уст­ ранив это рассогласование. Пусть существуют такие элементы и и (

вмножестве рассогласования W, что и - переменим, не входящая

вэлемент (терм) I. В таком случае заменяем в литералах перемен­ ную и глеметом (термам) t из W. Если множество рассогласования W не содержит элементов с указанным свойством, то множество литера-

Можнодоказать, следующуютеорему.

I Теорема 3.9 (теорема Робинсона). Описанный алгоритм нахпндит наиболее общий унификатор для множества унифицируемых (литералов н сообщает о неудаче, если литералы неунифицвруемы.

Рассмотрим пример. Пусть S = {Р(а, х, Ш у))), Р[г.А*),М)1- Найдем общийунификашр.

109

1. Пустая подстановкае :

So “ S - не единичный дизъюнкт, следовательно, не получили наиболее обшибунифиютр

2.Множестворассогласованииразно: H'o-fa.*],

следовательно, 6, = е° {я/г}. тогда^ -Je, - {Р(а. x.j[&))), P(a,J{u).

/00)!. " не-единичныйяюъюнкг.

3. Множество рассогласованийдляSi равно.

тогда 0,-8,» {/(«У*} - {a/i.Л ф ), и S, - 5¼ - {П я,А *)\Ш ). Р(а,Да),Дн))}. Sj - не единичныйдизъюнкт.

4.Множество рассогласованийдля& разно: *» = {g<у\и).

тогда вновь строим: 9, = 82« (gOy*) ~ {ate,j{a)/x,g(y)lu} и

S i - \ m №	M l- М у)). /*(«.Я°1 М Ш \ “	№ . Д°)>М М )-
Si - единичной	дизъюнкт, следовательно, 9i	наиболее общий
унификатор.
Рассмотрим еще пример. Пусть S - {£№). g(i)), Q(y, у)). Пус­

та» подстановки б; So = S - не единичный дизъюнкт и №ц = {/(а), у), Si = t ' У Ш = № W . S, = SB| » {QfM. т . Q M Да))}, Sj - не едвииоиыйдюиоткт; Г, = Ш Ш

Следовательно, алгоритм унификации завершается, делавм заключе­ ние, чтоS неунифицируемо

Нясшы®> могусудить, зтоодинюпегнескжных оучлеа, ктврш «рвмишйжетрудны {ШерлокХоемс).

Д1Д«1|.

§10. Метод революций в логике иреллкатои

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