Задачи по комбинаторике
Задание по КР № 1.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (3)»
(Мендельсон: с. 151 — )
Задание по КР № 2.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (4)»
(Мендельсон: с. 151 — )
Задание по КР № 3.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (5)»
(М.: с 151 -)
Задание по КР № 4.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (6)»
(Мендельсон: с. 151 — )
Задание по КР № 5.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (7)»
(Мендельсон: с. 151 — )
Задание по КР № 6.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (8)»
(Мендельсон: с. 151 — )
Задание по КР № 7.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (10)»
(Мендельсон: с. 151 — )
Задание по КР № 8.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (11)»
(Мендельсон: с. 151 — )
Задание по КР № 9.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (14)»
(Мендельсон: с. 151 — )
Задание по КР № 10.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (13)»
(Мендельсон: с. 151 — )
Задание по КР № 11.
Теория К1 –теория первого порядка без функциональных букв и предметных констант, единственная предикатная буква – « = ». Собственные аксиомы К1:
Доказать, что К1 — теория первого порядка с равенством.(М.: с. 88)
Задание по КР № 12.
К2 –теория первого порядка без функциональных букв и предметных констант, с двумя предикатными буквами – « = », и « < ». Собственные аксиомы К2 – элементарной теории плотно упорядоченных множеств без первого и последнего элементов – см. в книге: «Э. Мендельсон. Введение в математическую логику. М., 1971 – с. 89, упр.2».
Доказать, что К2 — теория первого порядка с равенством.
Задание по КР № 13.
Доказать разрешимость теория первого порядка с равенством К2 – элементарной теории плотно упорядоченных множеств без первого и последнего элементов. Описание К2 –– см. в книге: «Э. Мендельсон. Введение в математическую логику. М., 1971 – с. 89, упр.2». (М.: с. 104 — 108)
Задание по КР № 14.
Доказать разрешимость теория первого порядка с равенством К1 – элементарной теории равенства. Описание К1 –– см. в книге: «Э. Мендельсон. Введение в математическую логику. М., 1971 – с. 88, упр.1». (М.: с. 104 — 108)
Задание по КР № 15.
Доказать, что теория S – формальная арифметика – является теорией первого порядка с равенством. (Мендельсон.: Гл.3).
Задание по КР № 16.
Показать, что принцип мат. индукции, будучи аксиомой теории S – формальной арифметики, – не зависит от остальных аксиом этой теории. (Мендельсон.: С.131, упр. 1).
Задание по КР № 17.
Построить машину Тьюринга копирующую слова, т. е. перерабатывающую слово А в А•А. Начертить диаграмму.
Задание по КР № 18.
Построить машину Тьюринга складывающую числа х и у . Начертить диаграмму. Доказать, что функция f(x,y) = x + y – примитивно рекурсивна.
Задание по КР 19.
Построить машину Тьюринга вычисляющую функцию f(x) = 2x. Начертить диаграмму. Доказать, что функция f(x) = 2x – примитивно рекурсивна.
Задание по КР № 20.
Построить машину Тьюринга умножающую числа х и у . Начертить диаграмму. Доказать, что функция f(x,y) = x ∙ y – примитивно рекурсивна.
Задание по КР № 21.
В теории S – формальной арифметики, – обозначим термы 0, 0′, 0″, 0‴, …соответственно: [0], [1], [2], [3], … . Доказать для S следующие утверждения:
1. если m ≠ n, то ˫ [m] ≠ [n];
2. ˫ [m+n]=[m] + [n];
3. ˫ [m ∙ n]=[m] ∙ [n];
4. всякая модель S – бесконечна;
5. для любого кардинального числа אβ S имеет модель мощности אβ.
(Мендельсон.: С.124).
Задание по КР № 22.
Доказать теоремы теории S: для любых термов t, r, s:
1. ˫ t∙(r+s) = t∙r + t∙s;
2. ˫ (r+s)∙t = r∙t + s∙t;
3. ˫ (t∙r)∙s = t∙(r∙s).
(Мендельсон.: С.121).
Задание по КР № 23.
Построить машину Тьюринга вычисляющую предикат « х < у » . Начертить диаграмму. Доказать, что предикат « х < у » – примитивно рекурсивен.
Задание по КР № 24.
Показать, что чистое исчисление предикатов, содержащее только одноместные предикатные буквы эффективно разрешимо. (Мендельсон.: С.174).
Задание по КР № 25.
Доказать, что множество Tr геделевых номеров всех формул теории S (формальной арифметики), истинных в стандартной модели, не рекурсивно. (Мендельсон.: С.164).
Задание по КР № 26.
Теорема (де Брейн, Эрдеш). Если множество вершин графа G может быть вполне упорядочено, а всякий его подграф k-хроматический, то и сам граф G — k-хроматический.
Доказать, построив теории I порядка с равенством (см. Э. Мендельсон. Введение в мат. лог. М., 1971.: гл.2 «Теории I порядка»; § 12 ; с. 109). Привести обычное мат. доказательство (см. О. Оре. Теория графов. М. 2009.: Гл. 14 «Хроматические графы»; Теорема 14.1.3.; с. 294).
Задание по КР № 27.
Доказать теорему теории S – формальной арифметики:
(Мендельсон.: С.128).
Задание по КР № 28.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы аксиом S(9)» ,
где S(9) – номер собственной аксиомы формальной арифметики в нумерации: Э. Мендельсон. Введение в мат. лог. М., 1971.: гл.3 «Формальная арифметика»; § 1; с. 116.
(Мендельсон.: С.151-).
Задание по КР № 29.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер аксиом S(i)» ,
где S(i) – номер собственной аксиомы формальной арифметики в нумерации: Э. Мендельсон. Введение в мат. лог. М., 1971.: гл.3 «Формальная арифметика»; § 1; с. 116. i = 1; 2; 3; 4.
(Мендельсон.: С.151-).
Задание по КР № 30.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер аксиом S(i)» ,
где S(i) – номер собственной аксиомы формальной арифметики в нумерации: Э. Мендельсон. Введение в мат. лог. М., 1971.: гл.3 «Формальная арифметика»; § 1; с. 116. i = 5; 6; 7; 8.
(Мендельсон.: С.151-).
Задание по КР № 31.
Доказать методом резолюций теорему формальной теории групп:
где е – единица группы. Дать неформальное доказательство. (Ч. Чень, Р. Ли. Математическая логика и автоматическое доказательство теорем. М., 1983: Гл. 4 (с.57)).
Задание по КР № 32.
Доказать что принцип полной индукции является теоремой формальной арифметики.
(М.: Гл. 3, § 1)
Задание по КР № 33.
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (12)»
(Мендельсон: с. 151 — )
Задание по КР № 34.
Доказать, что прообраз рекурсивно перечислимого множества при отображении рекурсивной функцией рекурсивно перечислим.
(М.: Гл. 5, § 3)
Задание по КР № 35.
Доказать, что прообраз рекурсивного множества при отображении рекурсивной функцией рекурсивен.
(М.: Гл. 5, § 3)
Задание по КР № 36.
Доказать, что образ рекурсивно перечислимого множества при отображении рекурсивной функцией рекурсивно перечислим.
(М.: Гл. 5, § 3)
Задание по КР № 37.
Доказать, что образ рекурсивного множества при отображении рекурсивной функцией не обязательно рекурсивен.
(М.: Гл. 5, § 3)
Задание по КР № 38.
Доказать, что бесконечное множество рекурсивно тогда и только тогда, когда оно есть область значений строго возрастающей рекурсивной функции.
(М.: Гл. 5, § 3)
Задание по КР № 39.
Доказать, что бесконечное множество рекурсивно перечислимо тогда и только тогда, когда оно есть область значений взаимно однозначной рекурсивной функции.
(М.: Гл. 5, § 3)
Задание по КР № 40.
Доказать, что всякое бесконечное рекурсивно перечислимое множество содержит бесконечное рекурсивное подмножество.
(М.: Гл. 5, § 3)
Задание по КР № 41.
Доказать, что если множества А и В рекурсивно перечислимы, то рекурсивно перечислимы и их объединение и пересечение.
(М.: Гл. 5, § 3)
Задание по КР № 42.
Доказать, что существует такое рекурсивно перечислимое множество А, что ω – А не является рекурсивно перечислимым множеством.
(М.: Гл. 5, § 3)
Задание по КР № 43.
Доказать, что предикат FL(x) является (или не является) (примитивно) рекурсивным, FL(x):
«х есть геделев номер функциональной буквы».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 44.
Доказать, что предикат EVbl(x) является (или не является) (примитивно) рекурсивным, EVbl (x):
«х есть геделев номер выражения, состоящего из переменной».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 45.
Доказать, что предикат EFL(x) является (или не является) (примитивно) рекурсивным, EFL(x):
«х есть геделев номер выражения, состоящего из функциональной буквы».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 46.
Доказать, что предикат NU(x) является (или не является) (примитивно) рекурсивным, NU(x):
«х есть геделев номер цифры».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 47.
Доказать, что предикат Trm(x) является (или не является) (примитивно) рекурсивным, Trm(x):
«х есть геделев номер терма».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 48.
Доказать, что предикат Atfml(x) является (или не является) (примитивно) рекурсивным, Atfml(x):
«х есть геделев номер элементарной формулы».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 49.
Доказать, что функция Num(x) примитивно рекурсивна, Num(x) = геделеву номеру цифры ̅х.
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 50.
Доказать, что функция Argf (x) примитивно рекурсивна, Argf (x) = числу аргументов функциональной буквы f, если х — геделев номер f.
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 51.
А – мн-во натуральных чисел. А*={u│u= γ(C(x1)) & γ(C ( ̅u)) ϵ A}, где: C(x1) – некоторая формула, γ(C(x1)) геделев номер формулы C(x1), ̅х – цифра. Доказать: если А – рекурсивно, то и А* — рекурсивно.
(М.: Гл. 5, § 3)
Задание по КР № 52.
ТК – мн-во геделевых номеров всех теорем непротиворечивой теории 1-ого порядка К. Доказать: ( ̅ТК)* невыразимо в К. Где: ̅ТК – дополнение мн-ва ТК, а мн-ва А и А* связаны следующим образом: А*={u│u= γ(C(x1)) & γ(C ( ̅u)) ϵ A}, C(x1) – некоторая формула, γ(C(x1)) геделев номер формулы C(x1), ̅х – цифра.
(М.: Гл. 5, § 3)
Задание по КР № 53.
Доказать, что если всякое рекурсивное мн-во выразимо в теории К, то эта теория существенно рекурсивно неразрешима.
(М.: Гл. 5, § 3)
Задание по КР № 54.
ζn – область определения частично рекурсивной функции U(μy T1(n, x, y)). Мн-во В называется креативным, если оно рекурсивно перечислимо и существует такая частично рекурсивная функция φ, что для любого n, если ζn – подмножество дополнения В, то значение φ (n) определено и φ (n) ϵ ̅В ζn . Доказать, что мн-во
креативно, а всякое креативное мн-во не рекурсивно.
(М.: Гл. 5, § 3)
Задание по КР № 55.
Частично рекурсивная функция φ называется потенциально рекурсивной, если существует такая рекурсивная ф-ция f, что φ (x1, x2, …, xn) = f (x1, x2, …, xn) всякия раз, когда значение φ (x1, x2, …, xn) определено. Доказать, что функция μyT1(х, x, y) не является потенциально рекурсивной.
(М.: Гл. 5, § 3)
Задание по КР № 56.
Доказать, что функция х • у примитивно рекурсивна, х • у = геделеву номеру выражения АВ, если х — геделев номер выражения А, а у — геделев номер выражения В.
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 57.
Доказать, что предикат Subst (a,b, u,v) примитивно рекурсивен. Subst(a,b, u,v): «v есть геделев номер некоторой переменной xi, u — геделев номер некоторого терма t, b — геделев номер некоторого выражения А, а — геделев номер результата подстановки t вместо всех вхождений xi в выражение А».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 58.
Доказать, что предикат Eqt (x) примитивно рекурсивен. Eqt (x): « x есть геделев номер равенства».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 59.
Доказать, что предикат Syst (x) примитивно рекурсивен. Syst (x): « x есть геделев номер системы равенств».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 60.
Доказать, что предикат Осс (u, v) примитивно рекурсивен. Осс (u, v): «u — геделев номер некоторого терма t или некоторого равенства В, v есть геделев номер терма, входящего в t или В».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 61.
Доказать, что предикат Cons1 (u, v) примитивно рекурсивен. Cons1 (u, v): « cуществуют такие равенства е1 и е2, что u — геделев номер е1, а v есть геделев номер е2 и е2 есть следствие е1 по правилу R1».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 62.
Доказать, что предикат Cons2 (u, z, v) примитивно рекурсивен. Cons2 (u, z,v): «cуществуют такие равенства е1, е2 и е 3, что u, z, v – являются соответственно их геделевыми номерами и е3 есть следствие е1 и е2 по правилу R2».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 63.
Доказать, что предикат Ded (u, v) примитивно рекурсивен. Ded (u, v): «u — геделев номер некоторой системы равенств Е, v есть геделев номер некоторого вывода из Е».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 64.
Доказать, что предикат Sn (u, x1, x2, …, xn, z) примитивно рекурсивен. Sn(u, x1, x2, …, xn, z): «u — геделев номер некоторой системы равенств Е, c главной буквой fj n, z есть геделев номер некоторого вывода из Е равенства fjn(x1,x2,…,xn)=р».
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 65.
Доказать, что функция U(x) (если х — геделев номер вывода равенства r= ̅p, то U(x) = p) примитивно рекурсивна: U(x)=μy(y<x)(Num(x)=((x)lh(x)﬩1) lh(z)﬩1), где z= (x)lh(x)﬩1.
(М.: Гл. 3, § 4, Гл. 5, § 3)
Задание по КР № 66.
Доказать, что всякая частично рекурсивная функция вычислима по Эрбрану-Геделю.
(М.: Гл. 5, § 3)
Задание по КР № 67.
Доказать, что всякая функция, вычислимая по Эрбрану-Геделю, является частично рекурсивной функцией.
(М.: Гл. 5, § 3)
Задание по КР № 68.
Доказать, что если n>0, то для любого рекурсивного предиката R(x1, x2, …, xn, z, y) cуществуют такие натуральные числа а и в , что
и
(М.: Гл. 5, § 3)
Задание по КР № 69.
Доказать, что множество рекурсивно тогда и только тогда, когда оно само и его дополнение рекурсивно перечислимы.
(М.: Гл. 5, § 3)
Задание по КР № 70.
Доказать, что множество рекурсивно перечислимо, но нерекурсивно.
(М.: Гл. 5, § 3)