Ответы: Коллоквиум

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

,-~~"~~ 'фДу~~,~.,Д~ ~ ~ ф~(к~~',;~ДЮфЕ1.: !"Д~~Ф~~ )Ду„' рй1)$ «Ъхайй~ ~~~ Р~~Л ' ~; ~-4

~~з~ Ик~„д~,,~~ Д ~ ~.- ~'И ' ФК.ъ ~~ ., ', '3~ф~М~~ ~ 1Ри~>сна > ~ 1.!?'~Й У ~'" +~~ ~ ~ Р~:,, ~ ы к ~~ ~,~ ф,,":», ~ .~

ф ~,Ь ~'ц ) ~,~ й й . ) ~=~,-, ~Щ,-,- ~Ь,, Л,.~,

;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- такой резольвенты вывести из системы дизъюнктОВ Я неВозможнО

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

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