Задачи (Старые варианты экзамена), страница 3

Какая формула ϕ называется логическим следствием множества предложенийΓ? Приведите пример замкнутой формулы ϕ, которая не является логическим следствием множеcтвазамкнутых формул Γ = {∃xP (x), ∀x¬P (x)}?Задача 5 (2 балла). Сформулируйте теорему компактности Мальцева. Следует ли из этой теоремыутверждение: «Если бесконечное множество предложений Γ не имеет модели, то хотя бы однопредложение множества Γ является противоречивым»?Задача 5.

Какая формула ϕ называется логическим следствием множества предложений Γ? Существует ли хотя бы одна такая формула, которая является логическим следствием любого множествапредложений Γ?Êàêîâà ôîðìóëèðîâêà òåîðåìû ïîëíîòû òàáëè÷íîãî âûâîäà äëÿ êëàññè÷åñêîéëîãèêè ïðåäèêàòîâ? ×òî ìîæíî ñêàçàòü î âûïîëíèìîñòè ôîðìóëû ϕ, åñëè èçâåñòíî, ÷òî îáå ñåìàíòè÷åñêèå òàáëèöû h{ϕ}, ∅i è h∅, {ϕ}i íå èìåþò óñïåøíîãî òàáëè÷íîãî âûâîäà?Çàäà÷à 5 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó î ëîãè÷åñêîì ñëåäñòâèè äëÿ êëàññè÷åñêîé ëîãèêèïðåäèêàòîâ.

Âåðíî ëè, ÷òî âñÿêîå ìíîæåñòâî çàìêíóòûõ ôîðìóë èìååò áåñêîíå÷íî ìíîãî ðàçëè÷íûõëîãè÷åñêèõ ñëåäñòâèé?Çàäà÷à 5 (2 áàëëà).Задача 5 (2 балла). Какая формула ϕ называется логическим следствием множества предложенийΓ? Приведите пример замкнутой формулы ϕ, которая не является логическим следствием множеcтвазамкнутых формул Γ = {∃xP (x), ∀x¬P (x)}?Задача 5. Какая семантическая таблица hΓ, ∆i называется выполнимой ? Является ли выполнимой семантическая таблица h{P (x)}, {P (y)}i?Задача 5 (2 балла). Какая формула ϕ называется логическим следствием множества предложенийΓ?Приведите пример замкнутой формулы ϕ, которая не является логическим следствием множеcтва замкнутых формул Γ = {∃xP (x), ∀x¬P (x)}?Задача 5 (2 балла). Сформулируйте теорему компактности Мальцева.

Следует ли из этой теоремыутверждение: «Если бесконечное множество предложений Γ не имеет модели, то хотя бы одно предложениемножества Γ является противоречивым»?Задача 5 (2 балла). Какова формулировка теоремы корректности табличного вывода для классиhΓ, ∀xϕ(x) | ∆iческой логики предикатов? Корректно ли правило табличного вывода?hΓ | ∃x¬ϕ(x), ∆iЗадача 5 (2 балла).

Какая семантическая таблица T = hΓ, ∆i называется выполнимой? Может ливыполнимая таблица содержать только невыполнимые формулы?Задача 6 (2 балла). Какая интерпретация называется эрбрановской интерпретацией для заданнойсигнатуры σ? Сколько существует различных эрбрановских интерпретаций в сигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметной константы c ?Задача 6 (2 балла). Какие формулы логики предикатов называются равносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когда множествологических следствий формулы ϕ совпадает с множеством логических следствий формулы ψ?Задача 6.

Какова формулировка теоремы об эрбрановских интерпретациях? Верно ли, что каждаянепротиворечивая система дизъюнктов имеет хотя бы одну эрбрановскую модель?Ñôîðìóëèðîâàòü îïðåäåëåíèå ýðáðàíîâñêîé èíòåðïðåòàöèè çàäàííîé ñèãíàòóðû σ. Ññêîëüêî èìååòñÿ ðàçëè÷íûõ èíòåðïðåòàöèé ñèãíàòóðû σ, â êîòîðîé Const = {c1, c2}, F unc =∅, P red = {P (2) }?Çàäà÷à 6 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó î ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå? Âåðíî ëè, ÷òîåñëè ôîðìóëà ϕ â ïðåäâàðåííîé íîðìàëüíîé ôîðìå ÿâëÿåòñÿ îáùåçíà÷èìîé ôîðìóëîé, òî è ñîîòâåòñòâóþùàÿ åé ñêîëåìîâñêàÿ ñòàíäàðòíàÿ ôîðìà òàêæå áóäåò îáùåçíà÷èìîé ôîðìóëîé?Çàäà÷à 6 (2 áàëëà).Задача 6 (2 балла).

Что называется эрбрановским универсумом заданной сигнатуры σ? Сколькоразличных элементов содержит эрбрановский универсум сигнатуры σ, состоящей из одного одноместного предикатного символа P , одного одноместного функционального символа f и из одной предметнойконстанты c ?Задача 6. Что такое эрбрановский универсум? Каким условиям должна удовлетворять сигнатура σ длятого, чтобы эрбрановский универсум сигнатуры σ был конечным множеством?Задача 6 (2 балла). Какая интерпретация называется эрбрановской интерпретацией для заданнойсигнатуры σ? Сколько существует различных эрбрановских интерпретаций в сигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметной константы c ?Задача 6 (2 балла). Какие формулы логики предикатов называются равносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когда множество логическихследствий формулы ϕ совпадает с множеством логических следствий формулы ψ?Задача 6 (2 балла).

Как формулируется теорема компактности Мальцева? Следует ли из теоремыкомпактности теорема Эрбрана?Задача 6 (2 балла). Какова формулировка теоремы об эрбрановских интерпретациях? Сколькоэрбрановских моделей в сигнатуре σ = hConst = {c}, F unc = ∅, P red = {P }i имеет формула ϕ =∃xP (x)&¬P (c)?Задача 7 (2 балла). Приведите определение SLD-резолютивного вычисления запроса G,обращенного к хорновской логической программе P. Верно ли, что если P |= ∀xR(x), то запросG =? R(c), R(f (y)), обращенный к хорновской логической программе P имеет хотя бы одно успешноеSLD-резолютивное вычисление?Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логическойпрограмме P, которые не могут быть вычислены?Задача 7.

Какова формулировка теоремы корректности операционной семантики относительно декларативной семантики? Верно ли, что из этой теоремы следует, что для любого атома из наименьшейэрбрановской модели MP программы P запрос ?A, обращенный к программе P имеет успешное вычисление?Çàäà÷à 7 (2 áàëëà). Ñôîðìóëèðóéòå îïðåäåëåíèå SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ çàäàííîãî çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P . Ñóùåñòâóþò ëè òàêèå õîðíîâñêèå ëîãè÷åñêèåïðîãðàììû, êîòîðûå íå èìåþò íè îäíîãî óñïåøíîãî SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ íè äëÿ êàêèõ çàïðîñîâ?Çàäà÷à 7 (2 áàëëà).

Îïèøèòå àëãîðèòì âû÷èñëåíèÿ íàèáîëåå îáùåãî óíèôèêàòîðà äâóõ àòîìîâP (t1 , t2 , . . . , tn ) è P (s1 , s2 , . . . , sn ).Задача 7 (2 балла). Приведите определение SLD-резольвенты запроса G и программного утверждения D. Выпишите все SLD-резольвенты запроса ? P (X, c), P (c, f (X)) и программного утвержденияP (X, X) ← R(X).Задача 7. Какая интерпретация называется эрбрановской моделью для хорновской логической программыP? Верно ли то, что всякая хорновская логическая программа имеет непустую эрбрановскую модель?Задача 7 (2 балла). Сформулируйте теорему об основном правильном ответе на запрос к хорновской логической программе.

Верно ли, что если запрос G(x) к хорновской логической программе имеетхотя бы одно успешное вычисление, то этот запрос имеет хотя бы один основной правильный ответ?Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логической программеP, которые не могут быть вычислены?Задача 7 (2 балла).

Какой ответ на запрос G к хорновской логической программе P называетсяправильным? Сколько правильных ответов может иметь запрос G =?A, обращенный к хорновскойлогической программе P, в том случае, если A — основной атом?Задача 7 (2 балла). Какова формулировка теоремы полноты операционной семантики хорновскихлогических программ относительно декларативной семантики? Верно ли, что из этой теоремы полнотыследует, что для любого основного атома A, являющегося логическим следствием программы P, любоевычисление запроса ?A, обращенного к программе P, является успешным?Задача 8 (2 балла).

Что называется стратегией вычисления логических программ? Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 8 (2 балла). Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?Задача 8. Какова формулировка теоремы Черча о проблеме общезначимости в классической логикепредикатов? Следует ли из этой теоремы, что не существует алгоритма, проверяющего выпонимостьформул логики предикатов?Ñôîðìóëèðóéòå òåîðåìó ñèëüíîé ïîëíîòû äëÿ õîðîíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì? Ñîõðàíÿåò ëè ýòà òåîðåìà ñïðàâåäëèâîñòü äëÿ ëîãè÷åñêèõ ïðîãðàìì, ñîäåðæàùèõ îïåðàòîðnot?Çàäà÷à 8 (2 áàëëà). ×òî íàçûâàåòñÿ äåðåâîì SLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P ? Çàâèñèò ëè óñòðîéñòâî äåðåâà SLD-ðåçîëþòèâíûõ âû÷èñëåíèé îò ïðàâèëà âûáîðà ïîäöåëåé?Çàäà÷à 8 (2 áàëëà).Задача 8 (2 балла).

Что называется стратегией вычисления логических программ? Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 8. Сформулируйте правило SLDNF-резолюции. Какой ответ будет получен на запрос ?not(P (x))к программе P = {P (c) ← R(c)}?Задача 8 (2 балла).

Что называется стратегией вычисления логических программ? Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 8 (2 балла). Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?Задача 8 (2 балла). Что означает алгоритмическая универсальность хорновского логического программирования? Верно ли, что для любой логической программы с операторами отсечения и отрицаниясуществует такая хорновская логическая программа (без отсечений и отрицаний), которая вычисляетточно такое же множество ответов?Задача 8 (2 балла). Какова формулировка теоремы Черча о проблеме общезначимости в классической логике предикатов? Существует ли алгоритм, проверяющий противоречивость конечных множеств замкнутых формул логики предикатов?Задача 9 (2 балла).