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

Задача 0 (6 баллов). Слово — это конечный непустой список букв фиксированного конечногоалфавита. Текст — это конечный непустой список слов. Построить логическую программу, котораядля заданного текста L вычисляет кратчайшее по длине слово X, содержащееся в тексте L, котороеимеет с каждым словом текста L хотя бы одну общую букву. Запрос к программе должен иметь вид? G(L, X).Задача 0 (6 баллов). Слово — это конечный непустой список букв фиксированного конечногоалфавита.

Словарь — это конечный непустой список попарно различных слов. Построить логическуюпрограмму, которая для заданного словаря L разбивает множество слов L на два такихнепересекающихся словаря X и Y = L \ X, что никакие два слова w1 ∈ X и w2 ∈ Y не имеют ниодной общей буквы. Запрос к программе должен иметь вид ? G(L, X, Y ).Задача 0. Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст— это конечный непустой список слов.

Построить логическую программу, которая для двух заданныхтекстов L1 и L2 вычисляет бесповторный список X, состоящий из всех тех слов текста L1 , в которыхесть хотя бы одна буква, не встречающаяся ни в одном слове текста L2 . Запрос к программе должениметь вид ? G(L1 , L2 , X).Ïîñòðîèòü ëîãè÷åñêóþ ïðîãðàììó, êîòîðàÿ äëÿ çàäàííîãî êîíå÷íîãî ìíîæåñòâà íàòóðàëüíûõ ÷èñåë, ïðåäñòàâëåííîãî ñïèñêîì L, âû÷èñëÿåò ìàêñèìàëüíîå ïî ÷èñëó ýëåìåíòîâïîäìíîæåñòâî ÷èñåë X , êðàòíûõ îäíîìó è òîìó æå ÷èñëó èç ýòîãî æå ïîäìíîæåñòâà X . Çàïðîñ êïðîãðàììå äîëæåí èìåòü âèä ? G(L, X).Çàäà÷à 0 (6 áàëëîâ).

Ñëîâî ýòî êîíå÷íûé íåïóñòîé ñïèñîê áóêâ ôèêñèðîâàííîãî êîíå÷íîãî àëôàâèòà. Òåêñò ýòî êîíå÷íûé íåïóñòîé ñïèñîê ñëîâ. Ñëîâî W íàçûâàåòñÿ ñìåñüþ ñëîâ U è V , åñëèU = U1 U2 äëÿ íåêîòîðûõ ñëîâ U1 è U2 , V = V1 V2 äëÿ íåêîòîðûõ ñëîâ V1 è V2 , è W = U1 V1 U2 V2 . Íàïðèìåð, ñëîâî ¾ëåãåíäà¿ ÿâëÿåòñÿ ñìåñüþ ïàðû ñëîâ ¾ëåä¿ è ¾ãåíà¿. Ïîñòðîèòü ëîãè÷åñêóþ ïðîãðàììó,êîòîðàÿ äëÿ çàäàííîãî òåêñòà L âû÷èñëÿåò áåñïîâòîðíûé ñïèñîê X âñåõ ñëîâ òåêñòà L, íå ÿâëÿþùèõñÿñìåñüþ íèêàêîé ïàðû ñëîâ òåêñòà L. Çàïðîñ ê ïðîãðàììå äîëæåí èìåòü âèä ?G(L, X).Çàäà÷à 0 (6 áàëëîâ).Задача 0 (6 баллов). Точка на плоскости задается списком из двух действительных чисел. Всякаятройка точек, не лежащих на одной прямой, образует треугольник. Построить логическую программу,которая для заданного бесповторного списка L точек на плоскости вычисляет список X всех троекточек из списка L, образующих треугольники.

Запрос к программе должен иметь вид ?G(L, X).Задача 0. Точка на плоскости задается списком из двух действительных чисел. Построить логическуюпрограмму, которая для заданного бесповторного списка L точек на плоскости вычисляет список X всех парточек из списка L, наиболее удаленных друг от друга. Запрос к программе должен иметь вид ?G(L, X).Задача 0 (6 баллов). Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст — это конечный непустой список слов.

Построить логическую программу, которая длязаданного текста L вычисляет кратчайшее по длине слово X, содержащееся в тексте L, которое имеет скаждым словом текста L хотя бы одну общую букву. Запрос к программе должен иметь вид ? G(L, X).Задача 0 (6 баллов). Слово — это конечный непустой список букв фиксированного конечногоалфавита. Словарь — это конечный непустой список попарно различных слов. Построить логическуюпрограмму, которая для заданного словаря L разбивает множество слов L на два таких непересекающихсясловаря X и Y = L \ X, что никакие два слова w1 ∈ X и w2 ∈ Y не имеют ни одной общей буквы.Запрос к программе должен иметь вид ? G(L, X, Y ).Задача 0 (6 баллов).

Множество целых чисел называется свободным от сумм, если сумма любых двух чисел из этого множества не принадлежит указанному множеству. Построить логическуюпрограмму, которая для заданного конечного множества целых чисел, представленного списком L, вычисляет максимальное по числу элементов подмножество X, свободное от сумм.

Запрос к программедолжен иметь вид ? G(L, X).Задача 0 (6 баллов). Построить логическую программу, которая для заданного конечного множества целых чисел, представленного бесповторным списком L, и заданного целого числа N вычисляетмаксимальное по числу элементов подмножество X, сумма чисел которого превосходит N . Запрос кпрограмме должен иметь вид ? G(L, N, X).Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Ни одна последовательность положительных действительных чисел не имеет ни однойотрицательной предельной точки»Задача 1 (3 балла).

Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Всякая неограниченная сверху последовательность действительных чисел не имеет предела.»Задача 1. Используя константные, функциональные и предикатные символы алфавита (см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению.«Ни одна расходящаяся последовательность действительных чисел не является ограниченной»Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû àëôàâèòà(ñì.

Ïðèëîæåíèå 1), ïîñòðîèòü çàìêíóòóþ ôîðìóëó ëîãèêè ïðåäèêàòîâ, ñîîòâåòñòâóþùóþ ñëåäóþùåìóóòâåðæäåíèþ.¾Íå âñÿêàÿ ïðåäåëüíàÿ òî÷êà ïðîèçâîëüíîé ñõîäÿùåéñÿ ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåëÿâëÿåòñÿ ïðåäåëîì ýòîé ïîñëåäîâàòåëüíîñòè¿.Çàäà÷à 1 (3 áàëëà). Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû àëôàâèòà(ñì. Ïðèëîæåíèå 1), ïîñòðîèòü çàìêíóòóþ ôîðìóëó ëîãèêè ïðåäèêàòîâ, ñîîòâåòñòâóþùóþ ñëåäóþùåìóóòâåðæäåíèþ.¾Âñÿêàÿ ñõîäÿùàÿñÿ ïîñëåäîâàòåëüíîñòü ïîëîæèòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë ìîíîòîííî âîçðàñòàåò¿Çàäà÷à 1 (3 áàëëà).Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Ни одну сходящуюся последовательность действительных чисел нельзя представить в виде суммыдвух сходящихся последовательностей действительных чисел»Задача 1.

Используя константные, функциональные и предикатные символы алфавита (см. Приложение1), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению.«Сумма любых двух сходящихся последовательностей действительных чисел также является сходящейсяпоследовательностью действительных чисел»Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см.

Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Ни одна последовательность положительных действительных чисел не имеет ни одной отрицательной предельной точки»Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Всякая неограниченная сверху последовательность действительных чисел не имеет предела.»Задача 1 (3 балла).

Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Никакая монотонно убывающая последовательность действительных чисел не имеет двух различных предельных точек.»Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Ни одна расходящаяся последовательность действительных чисел не является ограниченной»Задача 2 (3 балла).

Для заданной формулы ϕ выяснить, применяя метод семантических таблиц,является ли эта формула общезначимой.ϕ = ∃y(∀xP (y, f (x)) → ∀xR(x)) → ∀x(¬∃yP (y, f (x)) ∨ R(x))Задача 2 (3 балла). Для заданной формулы ϕ выяснить, применяя метод семантических таблиц,является ли эта формула общезначимой.ϕ = ∃y(∃xP (y, x) → ∀xR(x)) → ∀x(¬∀yP (y, f (x)) ∨ R(x))Задача 2. Для заданной формулы ϕ выяснить, применяя метод семантических таблиц, является лиэта формула общезначимой.∀x((∃x¬P (x) → ∃xR(x)) → ∃y(P (x) ∨ R(y)))Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ñåìàíòè÷åñêèõ òàáëèö,ÿâëÿåòñÿ ëè ýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 2 (3 áàëëà).ϕ = ∀x(¬∃yP (x, y) ∨ R(x)) → ∃x∃y(P (x, y) → R(x))Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ñåìàíòè÷åñêèõ òàáëèö,ÿâëÿåòñÿ ëè ýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 2 (3 áàëëà).ϕ = ∀x(P (x, x) → ∀x(R(x) → ∃x(∃xP (x, x) & R(x))))Задача 2 (3 балла).