Ответы: Задания прошлых лет

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

Досрочный экзамен по математической логике 25 декабря 2004 года

время на выполнение работы: 2,5 часа

Условия задач:

nb: в oper'е замечена проблема с шрифтом symbol

Текст – это конечный список слов. Слово – это конечный список литер. Написать программу, ищущую самое короткое слово Х из самых часто встречающихся в тексте l слов. Запрос ? g(l, x)

Выразить на языке логики предикатов следующее утверждение в виде замкнутой формулы: "Если почти все элементы последовательности действительных чисел y равны между собой, то и предел последовательности равен этому же числу".

доступные константы:

0 – константа 0

доступные функциональные символы

|x| - абсолютное значение х

(-х) - смена знака х

x+y, x-y, x*y, x/y - арифметические операции

доступные предикаты:

r(x) - вещественное число

n(x) - натуральное число

s(y) - y - последовательность действительных чисел

e(x,n,y) - x - элемент y с номером n

l(p,y) - p - предел последовательности y

x < y, x > y, x = y – сравнение и равенство

С помощью метода семантических таблиц исследовать общезначимость данной формулы:

($y ¬p(x) > $x r(x)) > ("x $y (¬p(x) > r(y)))

С помощью метода резолюций исследовать общезначимость данной формулы:

($y ¬p(x) > $x r(x)) > ("x $y (¬p(x) > r(y)))

Изобразить дерево sld-резолютивных вычислений и дать все вычислимые ответы для следующей программы:

? p(x), r(x)

p(b) < ;

p(f(b)) < r(b), !;

p(c) < ;

r(f(x)) < p(x);

r(x) < p(x);

Дать определение противоречивого множества замкнутых формул

Дать определение sld-резолютивного опровержения

Дать определение эрбрановской интепретации формулы j

Операционная семантика оператора not в логическом программировании

Таблица aГ; dn состоит из замкнутых формул и не имеет успешных вычислений. Какие утверждения верны всегда и почему?

Г имеет хотя бы одну модель

d имеет хотя бы одну модель

ни одна из ?id не является общезначимой

ни одно из утверждений a-c не верно

Пусть s – множество дизъюнктов. Пусть s' – множество всех резольвент, получаемых из s. Какие из следующих утверждений несправедливы и почему?

если s – непротиворечивое множество, то s' – непротиворечивое множество

если s – противоречивое множество, то s' – противоречивое множество

если s' – непротиворечивое множество, то s – непротиворечивое множество

если s’ – противоречивое множество, то s – противоречивое множество

среди a-d есть неверное утверждение, но его номер зависит от s

Пусть i – эрбрановская интерпретация логической программы П такая, что tП(i) c i = tП(i) ? i (tП - оператор непосредственного следования). Какие из следующих утверждений верны независимо от i и П и почему?

succП i i

succП i i

succП = i

succП e i

succП e i

ни одно из a-e неверно в общем случае

Ответы:

программа, работающая на pdc-prolog пример оформления этой задачи

domains

word = char*

text = word*

predicates

g(text, word)

is_most_often(text, word)

exists_more_often(text, word)

occur(text, word, integer)

elem(text, word)

length(word, integer)

exists_more_short(text, word)

clauses

g(l, x) :-

elem(l, x),

is_most_often(l, x),

not(exists_more_short(l, x)), !.

is_most_often(l, x) :-

not(exists_more_often(l, x)).

exists_more_often(l, x) :-

elem(l, y),

not(y = x),

occur(l, x, k),

occur(l, y, k1),

k1 > k, !.

elem([x|_], x).

elem([_|l], x) :- elem(l, x).

occur([], _, 0).

occur([x|l], x, k1) :-

!, occur(l, x, k),

k1 = k+1.

occur([_|l], x, k1) :- occur(l, x, k1).

exists_more_short(l, x) :-

elem(l, y),

is_most_often(l, y),

length(x, lx),

length(y, ly),

lx > ly.

length([], 0).

length([_|l], k1) :-

length(l, k), k1 = k+1. g(l, x) <

elem(l, x),

is_most_often(l, x),

not(exists_more_short(l, x)),

!;

is_most_often(l, x) <

not(exists_more_often(l, x));

exists_more_often(l, x) <

elem(l, y),

not(y = x),

occur(l, x, k),

occur(l, y, k1),

k1 > k, !;

occur(nil, x, 0) < ;

occur(x.l, x, k1) <

!, occur(l, x, k),

k1 is k+1;

occur(y.l, x, k1) <

occur(l, x, k1);

exists_more_short(l, x) <

elem(l, y),

is_most_often(l, y),

length(x, lx),

length(y, ly),

lx > ly;

length(nil, 0) < ;

length(y.l, k1) <

length(l, k),

k1 is k+1;

"y ( s(y) >

"l ( r(l) >

(

( $n ( n(n) &

"m ( n(m) & m > n >

$x ( r(x) & e(x, m, y) & l = x )

)

)

>

$lim ( r(lim) & l(lim, y) & l = lim )

)

)

)

общезначима

общезначима

{x / b}, {x / f(b)}

- 9. - см. лекции

ответ: a, c

верно, т.к. иначе бы по определению выполнимости таблицы таблица имела успешный вывод

неверно. контпример: < | p(a) & ¬p(a) >

верно, т.к. иначе бы таблица по теореме Геделя имела успешный вывод

неверно, т.к. верно а

ответ: b, c, e

всегда верно по лемме о резолюции к теореме о корректности метода резолюций

несправедливо: контпример = { p(x) \/ p(y), ¬p(x) \/ ¬p(y) }

несправедливо, см. контпример пункта b

всегда верно по лемме о резолюции к теореме о корректности метода резолюций

несправедливо: контрпример = { p, ¬p }

ответ: a, b

верно,

т.к. i e tП(i) => i etП(i) => tП(i)e tП(tП(i)) = tП2(i) => i e tП(i) e tП2(i) e tП3(i) e ... . Есть 2 варианта завершения:

цепочка сойдется. Тогда мы придем к lfpП = succП, поскольку наименьшая неподвижная точка единственна. Но тогда смотрим начало и конец цепочки: i e succП, что доказывает начальное утверждение.

цепочка будет уменьшаться до ?. Но что с ней произойдет потом? Пусть мы получили пустое множество на шаге k, т.е. tПk(i) = ?, но tПk(i) e tПk+1(i), т.е. ? e tП(?), но для любого ОНС верно и то, что ? i tП(?) (пустое множество вложено в любое множество). Т.е. ? = tП(?). Т.е. если цепочка дошла до пустого множества, то и наименьшая неподвижная точка равна пустому множеству (она же единственна). Но тогда i e tП(i) e ? = lfpП = succП, т.е. i e succП, что также доказывает начальное утверждение

верно, т.к. верно b

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

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

$Ф.

Мв 6 Иостроить логическую программу которая для заданной конечной ~;::=:последовательности натуральнык чисел, представленной списком Е, вычисляет список ",Х всек тек ее злементов, которые являвзтся простыми числами ~наименьшее простое 4ислО» 2).

Ядщюс к программе должен иметь Вид ? Щ Щ

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

%Ф»:.Ф;~й йййИ;

~ '~~~'-~~~'*'~ММ 3'' "Ж% . ФФ~", яд, "у ~~~~~"' "ы~ ' ~ ФЧУ'т Г ймь~И ч~~~к,йм

ФФ' Ф'"~" фМ 7Фф*;Ж' Ф~; ЖММ,";~Ж"ФФЗЖ% 3ФФ~"' ф5ФУ М ' йМ ам:мъ 'у вю" ~ Ю~~ фон ОЧедЧ ыМВ'!Ь '

ФФФйфРЮК Ф Ь ВЬЮТ,."; ф,"."Юа.ВФФ жФ мреЗЖ".,

'ВФФ ЖФМФЖЖ" *% ЛАФА.", Ю~ . ~"-~Ф„ФЪФ;ФВфйФЖ1. ~ЖюФ1,БОВУА 4!Е>М1фНО1 фО)ЭМУ'!

~4~ 4"~' ''4' и а':""мж'жми ф. ~м~ю' м а;,~«ри~ ам~и ~ а ~~ ч~к~с'ги МНИ Ю4~Ф~~~~~

'~ *г"':~Ф .вафа Ь.,Ф,::%"

» р:„„.„:,~~>аи-к ~~ к*гиажк"й 'Ф'~~Р~"~~" ~

д„дуч~нив. аФ~

!

~,д,ю гивМ

рц,ц-~ай,~ьйй

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

~ФМММффф~ ~уф ~~ ®еж ~~

~~ ф;~.,„„,,.. '~~~~„~„ 43~Мйпщ.

" ~'Р~кт~ьж-„„„,„,, Иопиь ирмщд„,,„ ~Ъ ПфОН~ф„„„~ ~4~Ъ йСЯр~~уц~, ' "~~-'~Ъ'~' ~':,.;~~

5 йЖуьу,у~,~.

,7:-~~!фЧВ~ф)$Ффф~ФФФу ~Пф ЯЦЕК~~ Ф ф(

~ ~."-"'~~,',:,:.):,"-.;~.",:;:."4~3~31,Ффф ФВЖщу щ,. ъ ~~~,'.~"",:Ф"',.В~~Ь Щ~ф еещму "де,

,, ~-;.'.;-;:-;.~''."..Фф~!МЩ~ф, ВМамыщ, У~Э

ЖМИИ М3::ФфИВФЛФВКЪ|Х КИЖе утэсрз~жмМ 6~ л~ ~ жрат м *~ а„м~ ,;!~,"-.":."!,":;;:!'-,',.:,'.„, Я~ ЖЩ~~СЙ Ь» й:~~й~М~~Й ~~~ ~~~~й~ Л, ~;.~:",~~~ ~;-; ~;Ф л.~ .~;:г -г~. ° ~~ю~ в «ЩМЩМЙ$$, СЪЕЛИ% ХФЪФ~ ГВМУ ЪО~МК~'Ф~ЪАМ 'Х~1%'4с~ь,ы,;ртРамма; ж Ф, *э..ь:юру ФПЩМФЗ~М ФЗФВЧФФМ М ~ОТ$%ЦФЖЙМ ЯУ~~ МЖ'.ЪЮ:ГВС ЬЪ'~3й: .ЮМ ~ ° *"Ж,".'Ь ~ Я*"'Як~ 4~ ~фЩФМФ П ~ ЮВ64ЖТ ь' МЙМЖГЭОМ $Ы%М. ММЪ Р.'Ж~;Ф Ф4 Ж7М 6 ~ ~',~м":вмм ' '-,';.:.!;:,:.::.:!:: 4 СМФМЖМ~~Ф7 ~й~ФВ ~йй~~~ ~~ ~ ~~~~~:~~.~~~~~~~ ~~ ~~~ъв~ Ь. ~;.~. л~ «; '.~,'~.й ь:.~ .ъъ~~~~~~ ФЙФИММФ М ФЯМйвййа, чж ни .ъл «аюФ ъ,~е..~км й в.жжем'а щ~.рыжм Й':.ж Цсюаауьмцей Щщчм4 О~жченм Ц ~~$7важам Вкж; 3 М Эм ~ жм Ъ::ж;:М м ФФМ 6Ф ЧФ4ДФММ~ П МФ сОВаИа~~ ~ м~мажлюм емок юмьь;*.жми м ж.р . ~.' ~ ~лзюовм-Р

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

ФАМИЛИЯ И.О.:

ГРУППА:

ВАРИАНТ

Задача 1, Используя только приведенные ниже предикаты

° С(х) — ~х -- квадрате;

° Ь'(х) — ~х — пээцээ;

° В(х) — эх — че1эньэй предмет~,"

° И:"(х) — эх -- белый прелметэ:

е 7..(х, у) -- ~предмет т. лежит левее предмета рэ.

е Г(х. 1э) — епээедмет х лежит виже предмета уэ.

запишите формулу логики преликатов, выражакипую следующее высказывание: Нет такого белого шара. слева от которого лежат только квадраты и при зтом обоих цветовэ,

Задача 2. Докажите обще:эиачимсэсть приведенной ниже формулы, построив успешиьэй табличиый вьэвод д,хеи соответствэ1кэщих семантических таблиц.

Зх ((Р(х) --э -Л(х)) --э - (Зх Р(х) Й Чх Л(х))).

Задача 3. Докажите общезначимость приведенной ниже формулы, используя метод резолюций.

(Зх Р(х) э~ =х Л(х)) -э 3х (Р(х) ~В(х)).

Задача 4. Известно, что множество замкнутых формул ~у„ф) не имеет модели. Какие'из четырех

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

1; ~р -+ ф — общезначимая формула.

2. ф -+ у — общезначимая формула,

3. у -э ф — общезначимая формула.

4 ф -+ -ър — общезначимая формула.

Задача 5. Верно, что существует такое конечное множество предложений Г = фр1, ~рэ,..., уу),

логическим следствием которого

')~1. является формула - мр1.

)» 2. являются всевозможные замкнутые формулы

)» 3. является бесконечное множество замкнутых формул

Задача 6. Какие из трех'формул Р(х), Р(ц),.~ЬР(х) являются р 2. Р(х) и МхР(х). 3. эЗсе три формулы:попарно равносильны. друг'другу,

ввносильными.

(.) )

' "" .к:".~ч":-'.Р *

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

Задача 7. Какие нз приведенных ниже утверждений справедливы для предваренной нормальной формы,й и соответствующей ей сколемовской стандартной формы Ф"

ФОрмулы ~» и 1ь равносильны. 2. Формула ~Р -Ф 11'. 061цезначима.

Если фОрмула ~' противоречива, ТО и фОрмула ф9 противоречива.

4, Ес;1и Формула Ф' 11ротиворечивас то и формула Р противоречива. Задача 8. Предположим, что из непустой конечной системы дизъюнктов Я резолютивно выводимо бесконечно много различных дизъюнктов. Какие из приведенных ниже утверж й ?

верждени верны. 1. Сиги..ма дизьюнктов 5 противоречива. 2..''Система дитьюнктов Ь непротиворечива. ® 3. Такой системы дизьюнктов Ь' не существует Задача 9. Какие из двух формул;р = Чх Чр (Р(х) -~ - Р(р)) и ф = 3х 3р (Р(т) -~ - Р(р)) являются невыполнимымн? 2. "Бх!ько фОРмУла ~Р. 3, и одна из этих двух формул. 4. Обе формулы. Задача Х0. Известно, что семантическая таблица ЦД; 6) имеет конечный табличный вывод, некоторые ветви которого не завершаются закрытой таблицей. Какое из трех утверждений верно для любОЙ формулы,Р. 1. — Общезпачимая формула. 2 ~ — выполнимая формула. Задача 11. Известно, что любая пара дизъ1онктов из множества дизъюнктов 8 имеет модель. Какие из приведенных ниже утверждений будут всегда вернь| для любой системы дизъюнктов Я, — .2.: Никакие два дизъюнкта системы Я не имеют резольвенты. -.;::. 3, .Из системы дизъюнктов. Я нельзя резолютивно вывести пустой дизъюнкт, Задача ХЗ» Известно„.что:дизъюнкт Юа является ре~ольвентой дизъюиктов Юь и Юз. Какйе.йз

ф

ф'

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

ФАМИЛИЯ И.О.: ГРУППА: Зв,цача 1. и ц а Ис1тользун тОлькО приве "1енныс ннж1' 1цх '.1нка'1 а С(х) — ~х -- кващ1ат~; Ф Я~х) — 1х — ц1ар$;

Д~ т) — ~1д — '11"рн1*1й нре чмг'г~ ' е Ц: ~х) — 1х — белый т1редмет~:

Т 1х у) — предмет х лежнт лене~ нредме1н у»,

в Ь1х. Ч) — - ~1тредмет х леж1гг ннж» нр1г1м1 гн 11 . запи1иите ФормУду логики преднкаг.ов. ныражакнцую следуюн1се 1Н.1ск11111.1н1нн1е: ~Никако11 черный квадр~т 1ц лежит нн 1н1д 1.1ннк1 1ерн1,1м ша)к1К1. "н н11 О1 к т1 Ор1нх1 р111 но;нн а11тг1111

все бель1е шары~. Зада'4а 2* Докажите общезнач1тмост1 нр1111с;1енн11й ннже Формулы. Нос гр~н1н уснен1нь1й табличный вывод для соответствующих семан.п1чс1.кнх таблиц. Задача 3. Докажите общезначимость прнведешюй ниже форм~ды, исночьз~'я метод резолюций.

Ь| ((Чх Р1х) 1~ Л(у)) — 1 7х (Р~х) ч' Л~р))), > Задача 4. Известно. 11то н11 множссг11а ~ Ь1 всех 1к новнь1К прнмероа дн.п.кн1кго11 системы Ч' мож1н1 вывести пустой днзъю11кг. н прн этом кратчайший вывод днзъюнкта гЛ имеет длину н. )~акн1 1Н1 приведенных ниже утверждений верны для любой системы днзъюнктси1 .'1, удовлстворнннцей этому ~ словию'1

Днзъюнкт: ' резолютнвно ~~~~дим из 5' н длина крат 1а111нег11 вывоза е1 О )1авна н, 2. Дизьюнкт 1 3 ре'1одютивно выводим из Я, и длина кра*чййнтегО вывода его 1ье превосх1щит н. 3. Дизъюнкт 1 резодютивно выводим из о'. и длина кратчайшего вывода его не меньше в. +-

4. Днзьюнкт Е) не Обизан резолютнвно вывод1пъси из Ь'.

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

Задача 7. Какие из двух формул;р =- Кг =эр~ (р(ч) ~ Р(.,)) и.~ д, ~ (Р(, ) ОО|пезначимьгми:

"11иц |хэ формула;р. 2. Ч|х'|ько формула ~". 3. Ни одна из этих двух формул.

Обе фор~р п| Задача 8. Какие из трех приведенных ниже формул представлены в сколемовской стандартной форме (символы т.. р обозначают переменные, а с, е — константы)? 1. ~|л' 3р (Р(.г, |'(х)) ээ Р(р, эу)) 2. '".'Зэ (Р(2',,~'(|г)) ''Чр Р(р,у)) ЯР,'с, ~(с)') ч Р(с.е). Задача 9. Известно, что из системы дизьюнктов 5 резолютивно выводим пустой дизькэнкт. Какие эгз приведенных ниже угвержленпй верны? ~Р'--

э истема дизыОнк|'ов Ь не имеет эрбранОвских моделей. 2. Система дизъюнктов 5' не имеет конечного противоречивого множество Основных п1эимеров. 3. Система лпзьюнктов 5' непротиворечива. + 4. Лкэбая замкнутая формула является логическим следствием системы дэгтькэикт|эв Ы,

Задача 10. Верно, что существует такое предложение,р, логическим следствием которого +. 1. является любая замкнутая формула. ф не является ни одна замкнутая формула.

3. является тсиько конечное число замкнутых формул Задача 11, Известно, что замкнутая формула э|э равносильна формуле ф. Какие нз приведенных ниже утверждений верны?

1 Всякое логическое следствие формулы,р является логическим следствием формулы ф. О !ф Всякая модель формулы,р является моделью формулы ф. 3, Формулы 1|э н э имеют одинаковую предваренную нормальную форму. 4. Формула:р общезначима тогда н только тогда, когда общезна |има формула ф. Задача 12. Предположим, что нз системы дизъюнктов Я можно резолютивно вывести днзъюнкт Р э" - Р. Какие из приведенных ниже утверждений будут всегда верны.

? 1. В системе дизъюнктов Ь' есть противоречивый днзъюнкт 2. Система дизъюнктов Ь'.непротиворе |ива '3. Система дпзъюнктов Б противоречива 4- такой резольвенты вывести из системы дизъюнктОВ Я неВозможнО