20xx - коллок ответы (1162116)
Текст из файла
Задача 5 (2 балла). Какая формула ϕ называется логическим следствием множества предложенийΓ? Приведите пример замкнутой формулы ϕ, которая не является логическим следствием множеcтвазамкнутых формул Γ = {∃xP (x), ∀x¬P (x)}? - противоречивое ⇒ ∀ϕ∈СForm явл. лог. следств.Задача 5 (2 балла). Сформулируйте теорему компактности Мальцева. Следует ли из этой теоремыутверждение: «Если бесконечное множество предложений Γ не имеет модели, то хотя бы однопредложение множества Γ является противоречивым»? НЕТЗадача 5.
Какая формула ϕ называется логическим следствием множества предложений Γ? Существует ли хотя бы одна такая формула, которая является логическим следствием любого множествапредложений Γ? ОБЩЕЗНАЧ.Êàêîâà ôîðìóëèðîâêà òåîðåìû ïîëíîòû òàáëè÷íîãî âûâîäà äëÿ êëàññè÷åñêîéëîãèêè ïðåäèêàòîâ? ×òî ìîæíî ñêàçàòü î âûïîëíèìîñòè ôîðìóëû ϕ, åñëè èçâåñòíî, ÷òî îáå ñåìàíòè÷åñêèå òàáëèöû h{ϕ}, ∅i è h∅, {ϕ}i íå èìåþò óñïåøíîãî òàáëè÷íîãî âûâîäà? ВЫПОЛНИМ.Çàäà÷à 5 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó î ëîãè÷åñêîì ñëåäñòâèè äëÿ êëàññè÷åñêîé ëîãèêèïðåäèêàòîâ.
Âåðíî ëè, ÷òî âñÿêîå ìíîæåñòâî çàìêíóòûõ ôîðìóë èìååò áåñêîíå÷íî ìíîãî ðàçëè÷íûõëîãè÷åñêèõ ñëåäñòâèé? ДА (ОБЩЕЗНАЧ.)Çàäà÷à 5 (2 áàëëà).Задача 5. Какая семантическая таблица hΓ, ∆i называется выполнимой ? Является ли выполнимой семантическая таблица h{P (x)}, {P (y)}i?ДА <- АТОМАРНАЯ, НЕ ЗАКРЫТАЯЗадача 5 (2 балла). Какова формулировка теоремы корректности табличного вывода для классиhΓ, ∀xϕ(x) | ∆iческой логики предикатов? Корректно ли правило табличного вывода? ДАhΓ | ∃x¬ϕ(x), ∆iЗадача 5 (2 балла).
Какая семантическая таблица T = hΓ, ∆i называется выполнимой? Может ливыполнимая таблица содержать только невыполнимые формулы? Г = ∅Задача 6 (2 балла). Какая интерпретация называется эрбрановской интерпретацией для заданнойсигнатуры σ? Сколько существует различных эрбрановских интерпретаций в сигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметной константы c ? 2Задача 6 (2 балла). Какие формулы логики предикатов называются равносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когда множествологических следствий формулы ϕ совпадает с множеством логических следствий формулы ψ?ϕ|=Q, ψ|=Q, ϕ∈Q, ψ∈Q ⇒ |=(ϕ→ψ)&(ψ→ϕ)Задача 6.
Какова формулировка теоремы об эрбрановских интерпретациях? Верно ли, что каждаянепротиворечивая система дизъюнктов имеет хотя бы одну эрбрановскую модель? ДА (по Т об эрб. инт)Ñôîðìóëèðîâàòü îïðåäåëåíèå ýðáðàíîâñêîé èíòåðïðåòàöèè çàäàííîé ñèãíàòóðû σ. Ññêîëüêî èìååòñÿ ðàçëè÷íûõ èíòåðïðåòàöèé ñèãíàòóðû σ, â êîòîðîé Const = {c1, c2}, F unc =∅, P red = {P (2) }? 2^4 //P(c1,c1), P(c2, c2), P(c1,c2), P(c2,c1), принимают 0 или 1Çàäà÷à 6 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó î ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå? Âåðíî ëè, ÷òîåñëè ôîðìóëà ϕ â ïðåäâàðåííîé íîðìàëüíîé ôîðìå ÿâëÿåòñÿ îáùåçíà÷èìîé ôîðìóëîé, òî è ñîîòâåòñòâóþùàÿ åé ñêîëåìîâñêàÿ ñòàíäàðòíàÿ ôîðìà òàêæå áóäåò îáùåçíà÷èìîé ôîðìóëîé? НЕТÇàäà÷à 6 (2 áàëëà).Задача 6 (2 балла).
Что называется эрбрановским универсумом заданной сигнатуры σ? Сколькоразличных элементов содержит эрбрановский универсум сигнатуры σ, состоящей из одного одноместного предикатного символа P , одного одноместного функционального символа f и из одной предметнойконстанты c ? H0 = c, H1 = f(c), H2 = f(f(c)), ..., т.е. ∞Задача 6. Что такое эрбрановский универсум? Каким условиям должна удовлетворять сигнатура σ длятого, чтобы эрбрановский универсум сигнатуры σ был конечным множеством?Const - конечное; не содержит функ.
символовЗадача 6 (2 балла). Как формулируется теорема компактности Мальцева? Следует ли из теоремыкомпактности теорема Эрбрана?ДА, мн-во Т∈CForm имеет модель ⇔ ∀конечно Т'⊆Т имеет модель⇒мн-во осн. примеров противор. ⇔∃конечное противор. мн-во.Задача 6 (2 балла). Какова формулировка теоремы об эрбрановских интерпретациях? Сколькоэрбрановских моделей в сигнатуре σ = hConst = {c}, F unc = ∅, P red = {P }i имеет формула ϕ =∃xP (x)&¬P (c)?2 интерпретации, 0 моделейЗадача 7 (2 балла).
Приведите определение SLD-резолютивного вычисления запроса G,обращенного к хорновской логической программе P. Верно ли, что если P |= ∀xR(x), то запросG =? R(c), R(f (y)), обращенный к хорновской логической программе P имеет хотя бы одно успешноеSLD-резолютивное вычисление? ДАЗадача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логическойНЕТпрограмме P, которые не могут быть вычислены?Ñôîðìóëèðóéòå îïðåäåëåíèå SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ çàäàííîãî çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P . Ñóùåñòâóþò ëè òàêèå õîðíîâñêèå ëîãè÷åñêèåïðîãðàììû, êîòîðûå íå èìåþò íè îäíîãî óñïåøíîãî SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ íè äëÿ êàêèõ çàïðîñîâ? ∅ ??? P(X)→P(X)Çàäà÷à 7 (2 áàëëà).Задача 7 (2 балла). Приведите определение SLD-резольвенты запроса G и программного утверждения D.
Выпишите все SLD-резольвенты запроса ? P (X, c), P (c, f (X)) и программного утвержденияP (X, X) ← R(X). θ{X/c}→?R(X), P(c,f(X))ДАЗадача 7. Какая интерпретация называется эрбрановской моделью для хорновской логической программыP? Верно ли то, что всякая хорновская логическая программа имеет непустую эрбрановскую модель?Задача 7 (2 балла). Сформулируйте теорему об основном правильном ответе на запрос к хорновской логической программе.
Верно ли, что если запрос G(x) к хорновской логической программе имеетхотя бы одно успешное вычисление, то этот запрос имеет хотя бы один основной правильный ответ?ДАЗадача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логической программеP, которые не могут быть вычислены? не существует по теореме полнотыЗадача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсяправильным? Сколько правильных ответов может иметь запрос G =?A, обращенный к хорновскойлогической программе P, в том случае, если A — основной атом? 0 или 1 (если есть вывод)Задача 7 (2 балла).
Какова формулировка теоремы полноты операционной семантики хорновскихлогических программ относительно декларативной семантики? Верно ли, что из этой теоремы полнотыследует, что для любого основного атома A, являющегося логическим следствием программы P, любоевычисление запроса ?A, обращенного к программе P, является успешным?нет, не при любом алгоритмеЗадача 8 (2 балла). Что называется стратегией вычисления логических программ? Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется? ДАЗадача 8 (2 балла).
Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?да , т.к. ϕ не следуетЗадача 8. Какова формулировка теоремы Черча о проблеме общезначимости в классической логикепредикатов? Следует ли из этой теоремы, что не существует алгоритма, проверяющего выпонимостьформул логики предикатов? Нет, выполнимость ϕ ⇔ общезн ¬ϕÇàäà÷à 8 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó ñèëüíîé ïîëíîòû äëÿ õîðîíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì? Ñîõðàíÿåò ëè ýòà òåîðåìà ñïðàâåäëèâîñòü äëÿ ëîãè÷åñêèõ ïðîãðàìì, ñîäåðæàùèõ îïåðàòîðnot? Не сохраняет (для ! тоже)Çàäà÷à 8 (2 áàëëà). ×òî íàçûâàåòñÿ äåðåâîì SLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P ? Çàâèñèò ëè óñòðîéñòâî äåðåâà SLD-ðåçîëþòèâíûõ âû÷èñëåíèé îò ïðàâèëà âûáîðà ïîäöåëåé? Скорее ДАЗадача 8.
Сформулируйте правило SLDNF-резолюции. Какой ответ будет получен на запрос ?not(P (x))к программе P = {P (c) ← R(c)}? □, т.к. ? R(c) - failЗадача 8 (2 балла). Что означает алгоритмическая универсальность хорновского логического программирования? Верно ли, что для любой логической программы с операторами отсечения и отрицаниясуществует такая хорновская логическая программа (без отсечений и отрицаний), которая вычисляетточно такое же множество ответов? ДА (Т. Полноты)Задача 8 (2 балла).
Какова формулировка теоремы Черча о проблеме общезначимости в классической логике предикатов? Существует ли алгоритм, проверяющий противоречивость конечных множеств замкнутых формул логики предикатов? ДАЗадача 9 (2 балла). Как определяется частичная корректность программы π относительнопредусловия ϕ и постусловия ψ в интерпретации I?Является ли программа while X > 0 do X + + od частично корректной относительно предусловияϕ = (X > 0) и постусловия ψ = (X < 0) в стандартной интерпретации арифметики целых чисел? ДАЗадача 9 (2 балла).
Как определяется отношение выполнимости I, s0 |= ϕUψ в темпоральнойлогике PLTL? Являются ли формулы ϕU(ψ1 &ψ2 ) и ϕUψ1 & ϕUψ2 равносильными? НЕТЗадача 9. Как формулируется задача верификации моделей программ (model checking)? К какимзадачам теории графов сводится задача model-checking для темпоральной логики PLTL?Çàäà÷à 9 (2 áàëëà).I, w |=ϕ→ψp ∨ ¬p p → pÊàê â èíòóèöèîíèñòñêîé ëîãèêå îïðåäåëÿåòñÿ îòíîøåíèå âûïîëíèìîñòèèÿâëÿþòñÿ îáùåçíà÷èäëÿ èìïëèêàòèâíîé ôîðìóëû? Óêàæèòå, êàêèå èç ôîðìóëНЕТДАìûìè ôîðìóëàìè èíòóèöèîíèñòñêîé ëîãèêè?Çàäà÷à 9 (2 áàëëà).
Êàê îïðåäåëÿåòñÿ îòíîøåíèå âûïîëíèìîñòè I, t |= ϕUψ â òåìïîðàëüíîé ëîãèêåPLTL? Âåðíî ëè, ÷òî ôîðìóëû ϕU(ψ1 ∨ ψ2) è (ϕUψ1) ∨ (ϕUψ2) ÿâëÿþòñÿ ðàâíîñèëüíûìè ôîðìóëàìèëîãèêè PLTL?Задача 9 (2 балла). Как определяется интерпретация интуиционистской логики высказываний?Является ли формула p → ¬¬p общезначимой в интуиционистской логике высказываний? ДАЗадача 9. Как определяется интерпретация темпоральной логики линейного времени PLTL ? Являютсяли равносильными PLTL формулы Fp и (p ∨ ¬p)Up?Задача 9 (2 балла). Как определяется отношение выполнимости I, w |= ϕ в модальной логике?Верно ли, что для любой модели Крипке I и для любого состояния w если I, w 6|= ¬p, то I, w |= ♦p ?Задача 9 (2 балла). Как определяется отношение выполнимости I, s0 |= Fψ в темпоральной логикеPLTL? Являются ли формулы F(ψ1 &ψ2 ) и Fψ1 & Fψ2 равносильными?Задача 10 (3 балла).
Известно, что некоторая модель для формулы ϕ не является моделью дляформулы ψ. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул ϕи ψ ? 4. Не существует успешного табличного вывода из таблицы T = h{ϕ}, {ψ}i, потому что...есть интерпретация в которой выполнимаЗадача 10 (3 балла). Известно, что для семантической таблицы T = h{ϕ}, {ψ}i нельзя построитьни одного успешного табличного вывода. Какие из приведенных ниже утверждений всегда верны длялюбых замкнутых формул ϕ и ψ ?ϕ→ψ, ϕ→ общезначима4.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
