Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 11
Текст из файла (страница 11)
. , xn )[d1 , d2 , . . . , dn ]Отношение иливыполнимости формулIII |= 2 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]Если '(x1 , x2 , . . . , xn ) = 1 ! 2 , тоI |= '(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]()I 6|= 1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]илиI |= 2 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] Если '(x1 , x2 , . . . , xn ) = ¬ , тоI |= '(x1 , x2 , . . . , xn )[d1 , d2 , . .
. , dn ]()I 6|= (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] 12n12n()I 6|=1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]илиI |= 2 (x1 ,ВЫПОЛНИМОСТЬx2 , . . . , xn )[d1 , d2 , . . . , dn ]СЕМАНТИКА:ФОРМУЛI Если '(x1 , x2 , . . .ВЫПОЛНИМОСТЬСЕМАНТИКА:ФОРМУЛ, xn ) = ¬ , тоI |= '(x1 , x2 , .
. . , xn )[d1 , d2 , . . . , dn ]Отношениевыполнимости формул()Отношениевыполнимости формулI 6|= (x , x , . . . , x )[d , d , . . . , d ]II12n12n12n12nЕсли '(x1 , x2 , . . . , xn ) = 8x0 (x0 , x1 , x2 , . . . , xn ), тоI Если '(x1 , x2 , . . . , xn ) = 8x0 (x0 , x1 , x2 , . . . , xn ), тоI |= '(x , x , . . . , x )[d , d , . . .
, d ]() I |= '(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]()для любого элемента d0 , d0 2 DI , имеет местодля (xлюбогоI |=, . . . , xn )[dd00, ,d1d,0d2. .I ., ,имеетdn ] место0 , x1 , x2элемента2, DI |= (x0 , x1 , x2 , . . . , xn )[d0 , d1 , d2 , . . .
, dn ] Если '(x1 , x2 , . . . , xn ) = 9x0 (x0 , x1 , x2 , . . . , xn ), тоЕсли1 , x,2x, .,....,.x,nx) =I |='(x'(x)[d9x, 0d , .(x. 0. ,, xd1 ,]x2 , . . . , xn ), тоI1 21 2nВЫПОЛНИМЫЕИОБЩЕЗНАЧИМЫЕВЫПОЛНИМЫЕИn ОБЩЕЗНАЧИМЫЕОБЩЕЗНАЧИМЫЕВЫПОЛНИМЫЕ. , xОБЩЕЗНАЧИМЫЕВЫПОЛНИМЫЕИ() I |= '(x1 , x2 , . .Иn )[d1 , d2 , . . . , dn ]ФОРМУЛЫФОРМУЛЫ()ФОРМУЛЫдля некоторого элемента d0 , d0 2 DI , имеет местоФОРМУЛЫдля (xнекоторогоI |=, xn )[d0 , d1d, 0d,2 d, .0.
2. ,DdnI ], имеет место0 , x1 , x2 , . . . элемента Формула'(x. . .,,xx ,)x2называется|= 11,,(x, . . . , xn )[d0 ,выполнимойd1 , d2 , . . . , dnвв] интерпретацииФормулаI'(x'(xназываетсявыполнимойинтерпретацииФормула,,,........0....,,,,xxxx1nnnn)))) называетсявыполнимойвв интерпретации1Формула'(xназываетсявыполнимойинтерпретацииФормула'(xназываетсявыполнимой11nI , еслитакойнаборэлементов2если существуетсуществуеттакойнабор элементовэлементов ddd11,,,.........,,,dddnn 22DDI ,, длядляIIII,,,, еслитакойнаборnn 2 Dеслисуществуеттакойнаборэлементовd.111., ..
,. d. , dDIIII,, длядляесли существуетсуществуеттакойнаборэлементовnкоторогоимеетместоI|='(x,...,x)[d,].11 , . . . , xnn )[d11 , . . . , dnn ].которогоимеетместоI|='(xкоторогокоторогоимеетместо|='(x)[d111,, .. .. .. ,, ddnnn].].которого имеетимеет местоместо III |=|= '(x'(x111,,,.........,,,xxxnnn)[dФормула'(x,...,x)называетсяистиннойI , 11 , . . . , xnn ) называется истинной вв интерпретацииФормула'(xинтерпретацииФормула'(x,,,.........,,,xxxnn ))) называетсяистиннойвв интерпретацииIII,,,1Формула'(xназываетсяистиннойинтерпретацииФормула'(xназываетсяистинной11nеслидлянабораэлементов2если длядля любоголюбого наборанабора элементовэлементов ddd111,,,.........,,,dddnnn 22DDI имеетимеет местоместоеслиеслидлялюбогонабораэлементовdd11,, .
. . , dnn 2 DDIIII имеетимеет местоместодля1любоголюбогонабораэлементовIесли|='(x,...,x)[d,...,d].n1n|= '(x11,,......,,xxnn)[d)[d1 , . . . , dn ].IIII |=|='(x].].|= '(x'(x11,, .. .. .. ,, xxnn)[d)[d111,,,.........,,,dddnnn]. Формула'(x,...,x)называетсявыполнимойеслиесть1nФормула '(x'(x11,,......,,xxnn)) называетсяназывается выполнимойвыполнимой ,,, еслиесли естьестьФормулаФормулавыполнимой, если естьФормула '(x'(x11,, ..I..,..в,, xxкоторойназываетсявыполнимойnn)) называетсяинтерпретацияэтаформулавыполнима.интерпретацияI,, вв которойкоторойэта формулаформула выполнима.выполнима.интерпретацияIэтаинтерпретацияинтерпретация II,, вв которойкоторой этаэта формулаформула выполнима.
Формула'(xобщезначимой(или11,,......,,xxnn)) называетсяФормула'(xназываетсяобщезначимой(илиФормула.........,,,xxxnn ))) называетсяобщезначимой(илиФормула'(xобщезначимой(или любойФормула '(x'(x11,,,истиннойназываетсяобщезначимойn называетсятождественно),), еслиэтаформулаистиннатождественно1ЛОГИЧЕСКОЕистиннойесли этаэта формулаформулаистинна ввв любойлюбойМОДЕЛИ.СЛЕДСТВИЕтождественноистинной),еслиистиннатождественнотождественно истиннойистинной ),), еслиесли этаэта формулаформула истинна в любойинтерпретации.интерпретации.
МОДЕЛИ.ЛОГИЧЕСКОЕ СЛЕДСТВИЕСЛЕДСТВИЕинтерпретации.МОДЕЛИ.ЛОГИЧЕСКОЕинтерпретации.интерпретации.ОпределениеФормула'(xназываетсяпротиворечивой(илиФормула'(x111,,,.........,,,xxxnnn))) называетсяназывается противоречивойпротиворечивой (или(илиОпределениеФормула'(xФормула'(x.. ..если,, xxnn))множествоназываетсяпротиворечивой(или✓ CForm.ОпределениеФормула'(xназываетсяпротиворечивой11,, ..),Пусть�некотороезамкнутыхформул,невыполнимойонанеявляетсявыполнимой.невыполнимой ),), еслиесли онаона не являетсяявляется выполнимой.выполнимой. невыполнимойневыполнимой),онаневыполнимой.невыполнимой), еслиеслимножествоона нене являетсяявляетсяПусть каждаянекотороеформул, ✓✓CForm.CForm.ТогдаинтерпретацияI , замкнутыхвзамкнутыхкоторойвыполняютсявсеПусть��некотороемножествоформул,ТогдакаждаяинтерпретацияI,вкоторойвыполняютсявсеформулымножества, называетсямодельюдля множестваТогдакаждаяинтерпретацияI , в которойвыполняютсявсе .формулымножества,называетсямодельюдлямножестваформулы множества , называется моделью для множества .
.Пусть � некоторое множество замкнутых формул, и ' � Пусть�некотороемножествозамкнутыхформул,и'�замкнутаяформула.Формула'называетсялогическимПусть � некоторое множество замкнутых формул, и ' �замкнутая формула.Формула' называетсялогическимследствиеммножествапредложений(базы знаний), еслизамкнутаяформула.Формула' называетсялогическимследствиеммножествапредложений(базыявляетсязнаний)моделью, есликаждаямодельдлямножестваформулследствием множества предложений (базы знаний) , есликаждаямодельдлямножестваформулявляетсямодельюдля формулыт.
е.для любойинтерпретацииI вернокаждаямодель',длямножестваформулявляетсямодельюдля формулы ', т. е. для любой интерпретации I вернодля формулы ', т. е. для любой интерпретации I верноI |=() I |= 'I |=() I |= 'I |=() I |= ' Запись |= ' обозначает, что ' � логическое следствие .Запись |= ' обозначает, что ' � СЛЕДСТВИЕлогическое следствие .МОДЕЛИ.Запись |= ЛОГИЧЕСКОЕ' обозначает, что ' � логическое следствие .Для обозначения общезначимости формулы ' будемДля обозначенияобщезначимостиформулы ' будемиспользоватьзапись|= ' . формулы Дляобозначенияобщезначимости' будемиспользоватьзапись|=следствии'.Теоремаологическомиспользовать запись|= ' .Пусть={n } ✓ CForm, ' 2 CForm.
Тогда|= ' () |= 1 & . . . & n ! '. 1, . . . ,Доказательство. ) Пусть I � произвольная интерпретация.Если I 6|=Если I |=1& . . . & n,1& . . . & n,то I |=то I |=1& . . . & ni,! '.1 i n, т. е. I � модельПусть={✓ CForm, ' 2 CForm. Тогда|= ' () |= 1 & . . . & n ! '.1, . . . ,n}Доказательство. ) Пусть I � произвольная интерпретация.Если I 6|= 1 &. . . & n , то I |= 1 & . .СЛЕДСТВИЕ. & n ! '.МОДЕЛИ.ЛОГИЧЕСКОЕЕсли I |= 1 & . . . & n , то I |= i , 1 i n, т.
е. I � модельдля . Поскольку|= ', получаемI |= '.Теоремао логическомследствииЗначит, I |= 1 & . . . & n ! '.Пусть= { 1 , . .для. , любой' 2 CForm.ТогдаместоТаким образом,интерпретацииI имеетn } ✓ CForm,|='()|=&...&!'.I |= 1 & . . .
& n ! '.1nЗначит, 1 & . . . & n ! ' � общезначимая формула.Доказательство. ( Пусть I � модель для множествапредложений , т. е. I |= i , 1 i n.Тогда I |= 1& . . . & n.Так как 1 & . . . & n ! ' � общезначимая формула, имеетместо I |= 1 & . . . & n ! '.Значит, I |= '.ПРОБЛЕМАПРОБЛЕМА ОБЩЕЗНАЧИМОСТИОБЩЕЗНАЧИМОСТИ ФОРМУЛФОРМУЛТаккакI�произвольнаямодель для , приходим кФОРМУЛПРОБЛЕМА ОБЩЕЗНАЧИМОСТИзаключению |= '. ОбщезначимыеОбщезначимыеформулыформулы��этоэтоканалыканалыпричинно-следственнойпричинно-следственной⇤Общезначимыеформулы� этознания,каналыпредставленныепричинно-следственнойсвязи,попередаютсявввидесвязи,покоторымкоторымпередаютсязнания,представленныевидесвязи, по которымзнания,представленныев виделогическихформул,преобразуясьприизввлогическихформул,передаютсяпреобразуясьприэтомэтомизоднойоднойформыформылогическихформул,преобразуясьприэтомизоднойформывдругую.другую.другую.
ПрактическиПрактическиважноважноуметьуметьопределятьопределятьэтиэтиканалыканалыиинастраиватьнанужныхПрактическиихважноуметь определятьэтиканалы инастраиватьихнаизвлечениеизвлечениенужныхзнаний.знаний.настраиватьихнаизвлечениенужныхзнаний.II БазаБазазнанийзнаний��множествомножествопредложенийпредложений ; ;I База знаний � множество предложений ;IIЗапросЗапросккбазебазезнанийзнаний��предложениепредложение';';IЗапроскбазезнаний�предложение';логическогоII ПолучениеПолучениеответаответананазапросзапрос��проверкапроверкалогическогоI следствия|=Получение ответаследствия|='.'.