Задачи по комбинаторике

Задание по КР № 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)