Математическая логика и теория алгоритмов. Стенюшкина В.А. - 112 стр.

бит, после чего написанная им же программа восстановления сможет восстано-
вить исходный файл. Почему он неправ?
      48 Пусть S – конечное множество, k – натуральное число, Ik – семейство
всех подмножеств S, содержащих не более k элементов. Покажите, что (S, Ik) –
матроид.
      49 Покажите, что отношение ≤ p транзитивно, то есть из L1≤ pL2 и L2≤ pL3
следует L1≤ pL3.
      50 Множество вершин V′⊂V графа G=(V, E) называется независимым,
если никакие две его вершины не соединены ребром. Задача о независимом
множестве состоит в отыскании в данном графе независимого множества мак-
симального размера. Сформулируйте соответствующую задачу разрешения и
докажите её - полноту.
      51 Показать, что в алгебре  число 2 порождает множество всех по-
ложительных чисел, число 1 – положительных чисел, а совокупность {0;1} по-
рождает всю алгебру.
      52 Выяснить, что все подалгебры алгебры  исчерпываются следу-
ющими: 1) подалгебра, порожденная нулем и состоящая из него; 2) подалгебра,
порожденная числом 1 и совпадающая с самой алгеброй; 3) подалгебра, порож-
денная произвольным числом a>1 и состоящая из чисел 0, а, 2а, 3а,…
      53 Каждая подалгебра алгебры  состоит из всевозможных кратных
подходящего числа а, за исключением, быть может, конечного числа таковых.
Доказать.
      54 Рассмолтрим алгебру  , где “-“ – частичная операция:
          x − y, x ≥ y,
x −& y =                Какие функции представляются термами: 0(x-(x+1)), (x-y)+y,
         ∃, x < y.
(x+y)-y? Показать, что функция 2-х переменных не может быть представлена
термом в указанной алгебре (т.е. термом, записанным в алфавите {x, +, *, -}).
       55 Операция подстановки одноместной функции в одноместную функ-
цию дает снова одноместную функцию. Эту операцию обозначим *. Таким
образом, по определению f * g = S (f,g), (f * g)(x) =f (g(x))
       Операция * ассоциативна, но не коммутативна: f * (g*h)= (f*g) * h, s * sg
= sg * s
       Показать, что для любой одноместной функции f I11*f=f*I11, f-1*f*f-1=f-1.
       Если f-1 всюду определена, то (f* f-1)(x)=x.
       Показать, что существуют одноместные функции f, для которых f-1 всюду
определена и в то же время f-1f≠I11.
       56 Для двуместных функций введем операцию τ полагая fτ(x,y)=f(x,y).
       Операция τ удовлетворяет следующим соотношениям: fτ=S3(f,I22,I12),
µx(f(x,y)=z)=(Mfτ)(y,z).
       57 Если x-вещественное число, то символом [x] обозначим целую часть x,
т.е. наибольшее целое число, не превосходящее x . Показать, что функция
q(x)=x-[√ x]2 удовлетворяет соотношениям q-1(2x)=x2+2x, q-1(2x+1)=x2+4x+2.
       58 Пусть F-множество всех частичных функций на N от любого числа
переменных. . Основное определение частичной рекурсивнос-