Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 10
Текст из файла (страница 10)
. . , t )Pатомарная, если P (m) 2 Pred, {t1 , t2 , . . . , tm } ✓ Term;формула1 2mP (m) (t1 , t2 , . . . , tm ), если P (m) 2 Pred, {t1 , t2 , . . . , tm } ✓ Term; составная формула('&)составнаяформула , если ', � формулы;('('&_ )), если ', � формулы;('('!_ ))(¬')(' ! ) (¬')(8x'), если x 2 Var , ' � формула.(9x')(8x'), если x 2 Var , ' � формула.(9x')('&, если ', � формулы;(' _) )('_)СИНТАКСИС:ТЕРМЫ И ФОРМУЛЫ(' ! )СИНТАКСИС:ТЕРМЫ И ФОРМУЛЫ('(¬')! )СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫ(¬')(8x'), если x 2 Var , ' � формула.(8x'),еслиx 2 Var , ' � формула.(9x')Свободныеи связанные переменные.(9x')Свободныеисвязанныепеременные.Свободные и связанные переменные.Свободные и связанные переменные.
Кванторсвязывает тупеременную,которая алфавита.следует за ним.Form � множествовсехформул заданногоКванторсвязываетту переменную,переменную,котораяследует заза ним.ним.КванторсвязываеттукотораяследуетForm�множествовсехформулзаданногоалфавита.Кванторсвязываеттупеременную,котораяследуетза ним. Вхождениепеременнойвобластидействияквантора,СИНТАКСИС:ТЕРМЫИ действияФОРМУЛЫВхождение переменнойпеременнойобластидействияквантора,Вхождениеввв областиквантора,связывающегоэтупеременную,называетсясвязанным.Вхождениепеременнойобластидействияквантора,СИНТАКСИС:ТЕРМЫИФОРМУЛЫсвязывающего этуэту переменную,переменную, называетсяназывается связаннымсвязанным ..связывающегоСИНТАКСИС:ИназываетсяФОРМУЛЫсвязывающегоэтуТЕРМЫпеременную,связанным.
Вхождениепеременнойв формулу,не являющеесясвязанным,Вхождениепеременнойвформулу,неявляющеесясвязанным,Свободныеи связанныепеременные.Вхождениепеременнойв.в формулу,неназываетсяВхождение свободнымпеременнойформулу,не являющеесяявляющееся связанным,связанным,называется свободнымсвободным. Свободныеисвязанныепеременные.называется.называетсясвободным.Переменнаяназываетсясвободной,еслионаимеетсвободноеСвободныеи связанныепеременные.Varсвободныхпеременных' � множествоПеременнаяназываетсясвободнойеслиформулыона имеетимеет'.свободноесвободноеПеременнаяназываетсясвободной,,,Sеслионавхождениевформулу.ПеременнаяназываетсясвободнойеслионаимеетmVar�множествосвободныхпеременныхформулы'. свободное 'вхождениевформулу.(m)' '=�Pмножество(t, t2 , .
свободных. . , tm ) Varпеременныхвхождениевв 1формулу.' = m Varформулыti ;Var'.вхождениеформулу.S(m)i=1' = P (t1 , t2 , . . . , tm ) Var' = Sm Varti ;' = P (m) (t1 , t2 , . . . , tm ) Var' = i=1 Varti ;' = ( 1& 2)Var' = Vari=1 1 [ Var 2 ; '' == (( 11&_ 2 )2 )Var' = Var 1 [ Var 2 ;' === ((( 111_&Var' = Var 1 [ Var 2 ;! 22))2 )'''=(_)' = ( 1 1! 22 ) ' == (¬( 1 )! 2 )'Var' = Var ;СИС: ТЕРМЫ' = И(¬ФОРМУЛЫ)Var' = Var ;СИНТАКСИС:ТЕРМЫ(¬ ))' = (8xVar'' И= ФОРМУЛЫVar ;\ {x}..
. , xn ) � запись, обозначающаяформулу',укоторой'=(9x)' = (8x )Var' = Var \ {x}. Var' = Var \формулу{x}.Var' ✓ {x', x=, .x(9x.2(8x., ,. x. n.)}.'(x,)xn ) � запись, обозначающая', у которой1'21='=(9x)Var✓{x,x,...,x}.'12n' = ;, то формула ' называетсязамкнутой формулойили.Если Var', =;, предложениемто формула ' называетсязамкнутой формулой , или предложением .множество всех замкнутых формул.CForm � множество всех замкнутых формул.ение о приоритетелогических операцийСоглашениео приоритете логических операцийе убывания приоритетасвязки и кванторыаются так:В порядке убывания приоритета связки и кванторырасполагаются так:¬, 8, 9¬, 8, 9& &_СЕМАНТИКА:СЕМАНТИКА:ИНТЕРПРЕТАЦИИИНТЕРПРЕТАЦИИ_! ИнтерпретациясигнатурыhConst,Func, Predi � этоИнтерпретациясигнатурыhConst,! Func, Predi � этоалгебраическаясистемаI=hD,Const,Func,Predi,гдегдеI I , Const,алгебраическая система I = hDFunc,Predi, IIDID�непустое множество, которое называется областьюI � непустое множество, которое называется областьюинтерпретации, предметнойобластью, илиуниверсумом; ;интерпретации, предметнойобластью, илиуниверсумомConst!D�оценкаконстант,: Const ! IDI � оценка констант ,сопоставляющаякаждойконстантеc элемент(предмет)c̄ c̄сопоставляющаякаждойконстантеc элемент(предмет)изизобластиинтерпретации; областиинтерпретации;(n)(n)! (D n n! D ) � оценкаIIFunc:FuncI I ! IDI ) � оценкаFunc : Func! (Dфункциональныхсимволов, сопоставляющаякаждомуфункциональных символов, сопоставляющаякаждому(n) местности n всюдуфункциональномусимволуf(n)функциональному символу fместности n всюдуопределеннуюn-местнуюфункциюf̄ (n)нанаобластиопределеннуюn-местнуюфункциюf̄ (n)областиинтерпретации; интерпретации;(m)(m)(m)! (D mm m! {true, false}) � оценкаIPred:PredIIIIPred : Pred! (D! {true, false}) � оценкаIпредикатныхсимволов,сопоставляющаякаждомупредикатных символов (m), сопоставляющаякаждому(m)предикатномусимволуP P (m)местностиmmвсюдупредикатномусимволуместностивсюду(m) на областиопределенноеm-местноеотношениеP̄определенноеm-местноеотношениеP̄(m)областиопределенноеm-местноеотношениеP̄(m)нанаобластиинтерпретации.интерпретации.интерпретации.IIConstConst:Func : Func! (DI ! DI ) � оценкафункциональных символов , сопоставляющая каждомуфункциональному символу f (n) местности n всюдуопределенную n-местную функцию f̄ (n) на областиинтерпретации;I Pred : Pred (m) ! (D m ! {true, false}) � оценкаIСЕМАНТИКА:ИНТЕРПРЕТАЦИИСЕМАНТИКА:ИНТЕРПРЕТАЦИИСЕМАНТИКА:ИНТЕРПРЕТАЦИИпредикатных символов, сопоставляющая каждомупредикатному символу P (m) местности m всюдуЗначениетермаm-местное отношение P̄(m) на областиопределенноеЗначениетермаЗначениетермаинтерпретации.
Пусть заданы интерпретация I = hDI , Const, Func, Predi, термПустьзаданыинтерпретацияI=hD,Const,Func,Predi,Iзаданы интерпретация I = hDI , Const, Func,Predi, термтермt(xПусть(предметов)из1 , x2 , . . . , xn ) и набор d1 , d2 , . . . , dn элементовt(x,x,...,x)инаборd,d,...,dэлементов(предметов)из12n12nt(x,x,...,x)инаборd,d,...,dэлементов(предметов)из12n12nобласти интерпретации DI .областиинтерпретацииD.области интерпретации DII . Значение t(x1 , x2 , . .
. , xn )[d1 , d2 , . . . , dn ] терма t(x1 , x2 , . . . , xn )Значениеt(x,x,...,x)[d,d,...,d]термаt(x,x,...,x)12n12n12nxn )[d1 , d2 , . . . ,рекурсивно.dn ] терма t(x1 , x2 , . . . , xn )наЗначениенаборе d1t(x, d21,, .x.2., ,. d. .n , определяетсяна на наборенаборе dd11,, dd22,, ..
.. .. ,, ddnn определяетсяопределяется рекурсивно.рекурсивно.I Если t(x1 , x2 , . . . , xn ) = xi , тоI Если t(x1 , x2 , . . . , xn ) = xi , тоI Если t(x1 , x2 , . . . , xn ) = xi , тоt(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] = di ;t(xt(x1 ,, xx2 ,, .. ..
.. ,, xxn )[d)[d1 ,, dd22,, .. .. .. ,, ddnn]] == ddii ;;I Если t(x1 ,1x2 ,2. . . , xn )n = 1c, тоI Если t(x1 , x2 , . . . , xn ) = c, тоСЕМАНТИКА:ФОРМУЛI Если t(x1 , x2 , ВЫПОЛНИМОСТЬxn1), =t(x1 , x2 , . . . ,. x. n. ,)[dd2 ,c,. . то. , dn ] = c̄;t(x,x,...,x)[d,d,...,d]=c̄;12n12nСЕМАНТИКА:ВЫПОЛНИМОСТЬФОРМУЛt(x , x , .
. . , xn )[d1 , d2 , . . . , dn ] = c̄;СЕМАНТИКА:ФОРМУЛI Если t(x1 ,1x2 ,2. . . , ВЫПОЛНИМОСТЬx ) = f (t , . . . , t ), тоI Если t(x1 , x2 , . . . ,nxn ) = f 1(t1 , . . . k, tk ), тоОтношениеI Если t(x1выполнимостиxn1), =.d.n.] ,=tk ), тоt(x1 , x2 ,, .x.2., ,. x. n. ,)[dd2 ,f .(t. .1 ,,формулt(xxxвыполнимости,, .. .. .. ,, xxn )[d,формулddn ]] =2выполнимости1 ,, d2 ,, .. ..
..формулОтношениеОтношениеt(x11,, f̄(t)[dd,=1 , d2 , . . . , dn ]).2 1 [d1 , dn2 , . .1. , d2n ], . . . , ntk, [d[d,d,...,d],...t.. .. ,, ddпомощи112nn ]). Значение формулf̄(tвинтерпретацииопределяетсяf̄(t1 [d1 , d2 , . . . , dn ], . . . , tkk [d[d11,, dd22,, ..приn ]).Значениеопределяетсяотношениявыполнимости|=.Значение формулформул вв интерпретацииинтерпретацииопределяется припри помощипомощиотношенияотношениявыполнимости|=.Пустьзаданывыполнимостиинтерпретация|=.I = hDI , Const, Func, Predi, ПустьII =Predi,формула'(x1 , xинтерпретация, . .
. , xn ) и набор, dIII,2,Const,,Const,. . . , dnFunc,элементов2интерпретация1hDПусть заданызаданы=dhDFunc,Predi,формулаxx222,,......,,xxинтерпретации, . . . , d элементов(предметов)из111,,областиформула '(x'(xнабор dd111,,dd2Dnnn)) ии набор22 ,I .. . . , dnnn элементов(предметов)из(предметов)из областиобласти интерпретацииинтерпретацииDОтношениевыполнимостиI |= '(x1 , x2 , . .D. ,I I.x. n )[d1 , d2 , . . . , dn ] Отношениеxx2nn,)[dформулы' ввыполнимостиинтерпретацииIII|=на'(xнаборе. .
1.1,,dd2n2,,......,,ddnn]]11,,xx22,,..d..1..,,,dОтношениевыполнимости|='(x)[dформулыопределяетсяформулы '' врекурсивно.в интерпретацииинтерпретации II нана наборенаборе dd11,,dd22,,......,,ddnnопределяется определяется рекурсивно.рекурсивно.СЕМАНТИКА:ВЫПОЛНИМОСТЬ ФОРМУЛI Если '(x1 , x2 , . . . , xn ) = P(t1 , . . . , tm ), тоI'(x, . . .
, xn ) =тоI Если11,,xx,22x1 , . . . , tm ),Если'(x= P(tP(tI |='(x1 ,2.,....,.x,nx)n )[d1 , d12, . . . , tdmn ]), тоdd22,,......,,ddnn]]() II |=|= '(x'(x11,,xx22,,......,,xxnn)[d)[d11,,формулОтношениевыполнимости()P̄(t1 [d1 , d2 , . . . , dn ], . . . , tm [d1 , d2 , . . . , dn ]) = true; ()P̄(tP̄(t1 [d[d1 ,,dd2 ,,......,,ddnn],],......,,ttmm[d[d11,,dd22,,......,,ddnn])]) == true;true;I Если '(x11, x21, . .2. , xn ) =1 & 2 , тоII |= '(x1 , x2 , .
. . , xn )[d1 , d2 , . . . , dn ]()⇢I |= 1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]I |= 2 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]Если '(x1 , x2 , . . . , xn ) = 1 _ 2 , тоСЕМАНТИКА:ВЫПОЛНИМОСТЬ ФОРМУЛI |= '(x , x , . . . , x )[d , d , . . . , d ]1()I |=2n12n1 (x1 , x2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
