Ответы: Экзаменационные варианты

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник

Распознанный текст из изображения:

з

!

лоача т. г, (см ттрн„, нользуа н

оже конст Нсл б У Утлого троить клио«аль няем НОС ЫЕ фУН«

В есноне лени|о.

НЫеил лвил Днанзп, 'чномног~ ' ф~омулул, Ли««ИЫ,, редельны ого членов лскики и„ык к«мяч« точек 3 ослелоиа оя атель

а«каток, кяфаяь адача 2. д послеаон ности р ' Якчкзяу

° кочз 3

онательно кяны олн голл аааннои ф ~сти ркы н зта ф„ РИУла Обяпе ыяснить оомулы ф н ~му жс чик „жк чик

исчу"

Япезначим И ь нрименяя

Зх (Р(х) ' кч"л мки Задача з. тт,„

9(х)) , (З ч'кких тка формУла ~ л заданное фо О(У) м З х Р(х)) Ула общезна ормулы ф в моя нлн нет слить, нрим (аУО(У) .Зхрх мстол резол«

ния, явля Задача 4 Длл

х Р(х)) -+ Зх (Р(х) м лл заданного 3

хР х х чО(х))

лл з роса ~= ° ~(") отсече р ной стратеги ответов. 1числения ( и опрелелить мн ть множество вычи

слимых Я:В « : В(У) < пот(А(т(У)))' В(а) <- А(а) В(Ь) +- А(Ь)'$ А(Ь) ч А(Г(а)) <- В(Ь), '~ А(а) <- Вопрос 5. Какова фо м л формулировка теоремы о логиче

ческом следствии. Вопрос б. Ч

р . Что называется эрбраиовской инте п ета порядка?

й интерпретацией для логики преликатов первого Вопрос 7. Что назыв

аз гвается правильным ответом иа запрос С к логической программе П .

Вопрос 8. Какая стратегия выполнения логических программ называется полиойз

Вопрос 9. Выберите и мотивируйте правильные продолжения следующего утверждеиия Формула (р логики предикатов первого порядка общезначима тогда и только тогда, «огда 1. В любом дереве табличного вывода для исходной таблицы 'Ф любая ветвь

завершается аксиомой, потому что .... 2, В любом дереве табличного вывода для исходной таблицы Т хотя бы одна ветвь завершается аксиомой, потому что ....

исхо ой таблицы Та любая ветвь 3. Хотя бы в одном дереве табличного вывода для исходной таблицы Та лю ая ветвь завершается аксиомой, потому что .... е п одолжений утверждения нев

верно потоку что.... 4. Ни одно из приведенных выше пр д

тво Р' бесконечного семейства ое конечное подмножество

ченвв вз числа Вюарос! О. Известно, что квжд

и обоснуйте правильные зеклк)чен Лиаюнктов Р непротиворечиво. Выберите и о ос

Распознанный текст из изображения:

те"

, .-. ~ г" т

т ае етЕ~

Семейств

2. Се, и пльюнктов В обязатез

пктов гт - б ~улет Ре аер

3. Семей

противоречивым

, потому что

ььпь как пепр,~,~,

~Фечяатятт, та„„

4- Ниоттиоизп

ство аизьюнктов 11

ттрпвеаеппьот вьтпте РетттаеРечйаььт, ает

обязательио будет и

нвй п

пеаеРне, потом,„'ат„

Вопрос 11. Пусть С вЂ” лап к

п

рос к хорновекои лотттчеекой и

рнведениых ниже утверждений

о програмне П- Какие из

справедливы и почему".

Каятдьтй правильный ответ па запрос С

ответом, потому что...

к про кмме

рос янляетел атяяяеляттпм

Кя -"- ычиспимый ответ на запрос С к программе П яв.

ответом, потому что...

ме является арааальаттм

3. Некоторые (но не все) правильные ответы на запрос С к программе П яаляе-.ся

вьтчислимьпмн, потому что...

4. Некоторые (но не все) вычислимые ответы на запрос С к программе П явля=-ея

правильными, потому что...

Вопрос 12. Какие нз приведенных нн'ке утверждений справедливы в почему!

1. Лтобая арифметическая функция, вычнслнмая на машине Тьюрввга. моиет быть

вычислена подходящей хорновской логической программы с использованием

стандартной стратегии вычисления, потому что...

Лтобая арифметическая функция, вычнслнмая на машине Тьюринга, моттет быть

вычислена подходящей логической программой, но лишь с использованием

нестандартной стратетзти вычисления, потому что...

быть

ая на машине Тьюринга, может

3. Любая арифметическая функция, вычислнмая н маппш юр

вычислена подходящей логич ротТтамм

еской и ы с использованием стандартно

стратегии вычисления, но ли р

шь и и добавлении операторов и н в

е Тыорвнта, л;и

, вычислимая на машин

4. Существуют арифметическая функция,

зьФчислсиия которой нет логической программы даже в с.

Оияиаторо

иераторов Ь и ио1, потому что...

Распознанный текст из изображения:

ЭКЗАМЕНАЦИОННА51 КОНТРОЛЬНАЯ РАБОТА

ио курсу

"Математическая логика и логическое про1'р а~мир<>оаш~е"

ВЛ1'ИЛ НТИ

Задача А-1.

Построить формулу логики предикатов заданной сиги луры. соответствук>щук>

«данному математи !ескому утвержд<.ник> (см. приложенн ).

~~си. ф>Дф. ЬГй~с2 ~~~ //~ ~>~~~~ ~! а> >>~~мй->л

.Сл .~

Задача А-2.

(3у- Р(у) -+:Ь:!'1.(х)) — ) Мх31/(Р(х) ~! (>.(1/) )

ЖЗ~(Их) еУ)- (~~1>С~1- ЪЕ1к))

Задача А-З. Ис>1оньзуя ме71>/! 1>азов!Я>ции иссл>дов!>ть пл'п~>1>тив1>~>>."11>в>и'7'ь сл>'ду!>>щ1'.1.',г>.'м>'итво дизь!онктов.

~; — ! ~.1.,) у )l~,,> у ~..1,71...,.;~) Я1,.„,,> У .Я,,а,71,;>;~

Е(а), !'(а). Р(Д:1;)) Ч 5'(1!/.:1>)

Р(х) Ч 'У(>/(1)) Ч ~У(7/), '! (х) ~ ~С(1/))

Задача А-4.

Лля заданной логической программы определить множество ответов.

: > стандартной стратегии вычисления,

вычислимых

'1 < — Р(х):

Р(х) ~ — Л(х), !, Р(1>);

Р(1>)

ЙЯ ( — по~(Р(а)). !;

1ца) е.—

Задача Б-1.

Привести определение понятия

/1.ерево вывода для семантических таблиц.

Задача Б-2,

Привести оп1>едслени» понятия

Предваренная нормальная фо1>ма.

Задача В-З.

.Привести опредсленис понятия

, - ° -~, аг~~

ЯГ.Й-розолк>тинный вывод для х1>р>1овских логических программ.

Задача В-4.

Используя метод семантических т>~Г>лиц. исследовать ин < бщезн1>чимос7ь следук>- > 1ук! формулу логики предикатов.

Распознанный текст из изображения:

° ~'

Р"

36ъ я~ >< с< еь., В ~1< м заклю 1ается д' пу1' 1<>ии(: 5«<<> кк~ ь > хм''ч~ ля% я'.'хы~<с<.'--ъ' цк ц> >с >- с

грамм.

~.~ОД и~' ~~~~ я <.иЧ~~~~

Задача С-1.

Сформулировать теорему Лс)вен>:й) а-Скул<:«1».

Задач 1 С-2.

Сформулировать т<:ор<:му <>6;>рГ;<ап в<:ких 1<111 1 пр «»11иях,

Задача < '-3.

Сформулировать теорему кс>1>рс;лтн< сти для Яцй-1>

гических программ

лн>тивиых вычислений лс>-

Задача С-4.

иычисл<;ния для хорнов<.лих

Сфс)рмулировстгь теорему о не:)<нис<1мости пр;>1>ил;

логических программ.

с''м-к- ~"~« '1'тГ/

Задача 0-1. л ~

Рм, с- о3~~~р~~и~г .

Сушествует ли алгоритм, позвол>11<>ясий п1>о1«:1>;< гь в

мул вида

3

с>«~, р,-<Я)

1н)лнимс>сть ъ1мкнутых 11)<>1>- 3

где М(х1..<:2,.....>:„) -- формула. и. со);<.рж цц<я к>а>г< 1>ов и 11)ункц11<>н <ль11ых имвс>лс>в

13<> ) мс) ж ны<. <)тв<:тЬ1:

11<)т. пс>тому что ...

ТТ

да, и эгог с<лгсрнтм т')х<.1в.

р~рс.~, ~'-~ Ю><'> 1ФДЛ

Задача 0-2.

Сушествует ли логическая про1 рм ма )т така>. ч )ап1>с)<:ы '! — ' Р. Л(;<:) и

— лО«,~.'','. Л1.х,> иж'>с>т ОдкО 'А ";~> ж мкс>ж<'.ст1» Вы ' <1<:лимы х <>тв<''< <>в!

Задач» 1)-3.

й ц.ы О;~; Й''ж1 ЙА.Г < ''к< "Р'Ф Д-~ 4~-ю ~'Й'~ы~'- I

13ерно л . что всякая формула, с>бш.)начимая 1 ин" уиционистс:кой логикс., 1)удс.т т1кжс обш<1~1са <имой в клясс:иве<..)сс»1 лс гик<:

Варианты ответа.

,с),а. верно всегда. потому что ...

Нет. никогда н«вс.рно. пс>тому ч гс> .,

Справедливс>сть этогс> утвс.рждс.пия .>ави<.><т <>т 1<1,1< «ф<>рмулы. М<>жнс> прив«ти л>) «л ду»ших п1>им<.1> »....

Распознанный текст из изображения:

Занача ). )[еппзльз)в констайтныс, фзнкциоих

' пюввльиые и прел!нитные аьчволы язгизии

постРмзть ',[а)ЖМХХтЖ фс»РНЕНУ иоп!ки ицеаикя~ои соо ие ' .. ",... лабазе

иь !ток, согтиетствзло!ияьз стелт'ысае.зз ! .ьсез!„!с,иы

"Вскипи ызззз»зтонио зоывяо!цаи посл»лоьпзиьйосзь лев-тт . -". ! ет *лг!

лы оттаете тьззык чисел извет *ляи

Заяача 2. иля заикиной формзлы ят выяснить, првмсняя»!стол счзипысскиз тн)лззи. яви»с!си ли ф зрыулк о»о[!цел!и!низ!»Тцз

Зх Зь.[Р(х) -+ В[т)) ь (сс) Р[у) ь Зх В(х))

Звлача 3. дия залзнноа форчзлы о выяснить, трпискяя иетол резол!олив. як»хе!си зя з; ииг .;, »»б!псзнзчз!мон нли иез.

Вп Зх [Зз'ь»у ((Р[ьл»Г) -+ В()ль)) А З»»Х!з (В[и,т) -ь В(во В) -ь гу Р[в,!))

а, ди тзиитго загроса сыз. В[з,»),В[к) к зялзииоп лог!»чески!а прогрп«с и иоыпоизь.з Залача . Дия з

» -иов!' стзнлацтио! стол ', '"' с з с

.ттотспи! вычислеинз) [с испол!.Тозоиз!еы оисрятогм отсс»сияя к етр! з из лс)»сво Я Вз-Резал!оп!и.:, "с з

'ьЛы с - лтивньы вычислении и оппелслить ииоьиств! вычисти»!ыз откетоя Впво.-зле б! киь: з,Ь.с,о офозизчяь т х! и слиты

РВ АМ(т),аз»- Е[х). '.. поз[В[я))!

А(с)л)»- Е[я), В[В)!

В[х)»- пот[Е[ТИ:

В(с[)»-;

В(х) 'Е,.):

0(В)»-;

Е(и[х))»- ))[ь),!:

сз и ь

к топи и! выислвясх

!о и!'

"иг,' и'

изт ! б

!

,»Ы.,О ВиеСТН

[о из ты тс»"по" '"'

, чт.

Распознанный текст из изображения:

п и и( «( (.«и( н

ма('(и) — г('(. нн и*'

поо з(*и

иФ

Оки Р( И

оМ

мн н и(*и

из (

нр 'Р """

к«(«мат(,аою у о,,

,2. Влюбомднме бтвмнозв«нкид«я и одно«та«( н т= уеу(з . «м «а м

ивера меяакмммм(,л тому

3(тбоыбмводн мдереябзеб(мено«там« дате ие«од оь б(еа т= (Еу(З ю люе

ррмрмдмоя вн иомоб, пзону' тто

.. б;,."«здзмдедпм«деря е«азмммтоамвз( даян яом( а» бя(н«(р- уе((з««о «б(омм

~!,-~:;;:-З "-' ",

'= '«Ф~фй(б(р«бакур(беар«фин«вр(ма продо«неннб утвари иная н ° рвз но(о «о

Распознанный текст из изображения:

и Х.1а си сии ьсииссииисаис:и ии ис"сии 1 ~., сас~еиы ьи;ы июи ь В ~ ыржи1

цисциы 11. 11иессж . и о вы иср и вской вы и и:кс й и; итыииы П и рйриииьсьой аиырирсеаиив1

и жсыиаиыя и сыисииа '1й111 — 1и ти1ыа1, евс Т,, оиссисир асио.рсыиьсиимо вмиисскио

.ысиылиии. -.ч ир итыииы П микис и~ ории: ыииы; иийс ~ ~исржыььй сираьеи ~аьм а и ~ ~си т

еиюссса исйсиь иро.рйиыы П.,ысои1 ий

1 ис яисиессе ис" ииы ир ирйииы П. 1и иип ыо

У 1 аовсс кйкквятьси. сики исийтксъси и ветвь ир ~1ыииы П ь мьисныосеи йвыйорв1иП,

йотомв

Вопрос 1йй Иьвсстио, ло йисрос ". р1т) к йросрьыис П высит ссисвйиис Я й-рсзойкттввйоо

оаржержсввс. в рейулиткте косоросо ь кв ксиве освети вычисййетсй йос1стевойкв 1х 1 1йу1). 1 вкйй )т1

1писвежввык ййже утзержлеюот оулут вс ьййв сй равелйввы, неййвисвы о от арогрвыыь1 П в йтоыв' Рйх) М

иодейй 1 У Ответ ооосйовв ть.

1. П~ ' Ух Ррх), йотжу по .

2. П ~="'Зх Р(х). потому что...

У . П ~ы' "йу РЩу)); потому йто...

4 'Пты Зу рЩу)),'потсщу что.'.,

5)::Бпоййекйх П)п1вйййппвкт вйп1с, Уйхфпйв11пй'х обп1сы,сйУУ1йй.11в йвР11йи

Распознанный текст из изображения:

» '. >

»

(Н(с) ° ')> )'><,)Н > Цл ( >) Р(л.>) !Цлц

) ч ((з(и'>-'и(' не(.'" и )»ч. мл )ц,,н(,,И

3» >ич> ),.(» » юн» .н>р .> ( Рт Р(з )) н(т) и ю»нн и и >н >с и и >ги>), .>чс и > ю>р>и» ии

и и.с> О» р>ш ч»рл» ни » н>нс >с >нн и и>и' и > и ни>сисис(>и>( ин> синили >рис нии)

>срси .' ( О рс>ни ннюнлз и» >ис >сини ни»р'>с >н'>' ннн:'»и ю»ис» >ни»с> и ((рии* мисс

О> или,>,Ь,сд н >ни мин и >и» и > и

ис г)(г(>')) < — х(с)

( (и) <-:

В(х) +- щс)>

я(д) <-:

Р(Г(з),и) <- ()( ), ), ((К(з))>

Р((),х) < — (у(х).!((И)(

П(х) — . (()(х)П

й(()) +-;

Вопрос 5. Какая семантическая таблица (Г, Л) иазъц>ас>ся выполнимой?

Вопрос Си Сформулиру>жс оорслслсиис слслукнцс>о цинян>я: >рбраноаская интерпретация лля

семейства дизъюнкзон з. Верно ли, что каждая непротиворечивая сис(сма дизъюцктов 8 имеет хозя бы' . ':

ол)гу зрбрановскую модель?

Вопрос 7. Сформулируйте теорему полноты операционной семантики логических (грограмм

относительно декларативной семантики.

Вопрос З..Что'означает алгоритмическая полнота хорновских логических программу

Вопрос 9; Известно, что семантическая таблица (((р),(>))О является невьшолнимои. Какие из

принеденных ниже утверждений всегда верны )ц(я любых замкнутых формул (р и')уз

.(. ' Формула,(р является логическим следствием формулы >)(, потому что..

2,:::-Фо мула))( является логическим следствием формулы (р, потому что..

- 3' ',:.9е>4у)г(еетв>уст успепнгого табличного вывода из семантической т . ' (((р)> цг

орм

й табгп(цьг (А Цзрфвоуому итр> ° ","

;:,,'!':"",:- 4 "' Форс)))у))йф+у является противоречивой, потому что.„

""... -"4я:,')с>)ее:,))У)())>с>деп))лги ввйпе утверждения в об)нем случае неверны.

Распознанный текст из изображения:

у.,~,, ~ж ~ -, .;. ~ .-„, ~,.'а ..: з иуе~щ~к.же в юржвмьаюей фю~рееа., жфщ~в~аа:~~~~ффф"":.';;-;:,':;,"~!-.',~~;

Ф Ю ВЧффКД'~~

'.-*~ 4 м ь' кж см.-"манеж~ "~;з +эры..а~ ~ ~дж~ддр~дущ~~~ц~.ерв„

Вюиарж Г 1,: ".." Г . ". '-. "~а .жм .;~ ж-.-~ж:~же~щюююж. а % — ~~ьр~ мцррдрр ареадуд~щ~,';!~!Ф,

.'*.' '".йи..: М' ~ЖАР~~;.".."':аМжМ" ~ " ' ЖФ".':Ф МЖЭФВ~ МР*'. ~РВМЯФБ4 й. ЙФВЮРЯЭФР КВФДЗ~ФФфФМЙЮЬЮМФ:: **'."::РФ

жж: ~за.кь' й -:. жз Мук Г- у ..:.. ~ ~а ьсь%~л=твсеьвм~ ~..жлаеаеа~п М~~луефе~4аФц~33

фр» ~ ~ .~~ ~ .дк4ж ~ .' ",~ЖЗС'Л~-ВЖЬЛ: ЪЖЯЖ ' 'ЙЭФфМ~ДФВВФ 6$Лф'Й 36ффФДФЩМ41фф1фф

.'Ф Ж'й"" ''

: .~-.~~ ~ ~-., ж~к".*.~» ~ ж~~м~т~з зр".~ж~режюзй адеэвар чаю .

Ф. =а~д~ъ~ ~®;~~~~~=;~~ Ъ ~~" й;:.~~ ~~~й==~~ ~в~ ~~~Ж ~~~~д~д~уд,д,фрр~ффф ~фф.",д:",'Е.',-".':,"~;;;,,':,:,"!'

'..Ж~Юкй .ЪЖйЪЮВФ .'.АЬ Ъ ВйЫ32С.Бай'У"-'й Ж М.ййс.~:Ф '~3бфщщюй~др3ф

Ъ':-гю.бы;;деи,э~а.зомби: а в~=«.се~ Ъ ж жж~~жх ажелвФаааиаФаФ~ФЩфф."

~й едва и~ арах»~жевмх аййв~.." ~~~ф~~~~~~й ~ ~4~й~ ~~а~йФ ~~Ф:ффффф,.

Распознанный текст из изображения:

Вопрос '1О. Известно, что семантичесяая таблниа (1о1,1о1> являетс~ яс. и ляячоа сс!"

приведенных ниже утверждений всегда вернь! лж лыбыя замкчуг!» оор! ул о я „"

.1. Не су цествует успешного табличного вывола нз семанпшесяой . блиаы ",об!ъ и» *;,;,,»; ч!о

' 2, 'Формула !тт является логическим след»твнем форма лы о, г,!гочз чзо

3. Формула !р является логическим следствием формтлы ач попом!:по .

''4.. Формула о!-+ту является противоречиво!!. пото!!з что

5. Все приведенные вы!не утверждения в о»з!иез! слз чае неве, ны.

В 11. 1»ание из приведенны» ниже утверждений озгбт в~рвы н почем! "

опрос . з

1, Д:!я лтооого запроса С и логической пшзгга»!з!ы П. в составе которь есь зиеев-ет

отравив!!я, »утиеств5ет таила верно.сгся л. тч с:,,! з ' !ъс ассе!во»смз

! ' ! я '3го миши»с во вычисти!!ы» о в

программе П совпалает с множес!вом ы слн ы .-;.:; - и,

ер " ' отсе шния и стонами!я! миоже»та~ в ' " ' .'' '! с

программе П не совпадае! с и ич ес;в! сч - о..а

ш !ы ' (Т )=о саяне! *!е, ш !

ч

поч»м

Из системы дизь .л зя

3. Система дизъгонкт» . л и ог

.» я бы один лгыък - " '- и- °

и ! еденных выше»тверж.

5. Ни одно из приведенн

Возможно не удалось распознать кодировку файла