7)Вычисл функции

Пусть функция f:

Опр. функция f вычислима на Маш. Тью. М ó для любого набора машина М : W втом, и только том, случае , когда f(

Теорема. Всякая МТ вычисляет некоторую n-местную функцию.

Теорема . существ функции не вычислимые на МТ .Функции вычислимые на МТ называется вычислимыми.

МТ вычисляет ф-ию f набора ( ) M: , если определено, иначе (если не определено) М работает бесконечно. Всякая ф-ия, для которой можно построить МТ наз. вычислимой по Тьюрингу.

8) Оператор суперпозиции:

Суперпозиция функций f ) и ( -это функция

F= S(

Другой вариант:

9) S-m-n Т.

S-m-n Т. общая рекурсивная ф-ия (m+1)-местная (z,

10)ответ (с1,с2,с3)

Вариант 15=35=55

1) Булевые ф-ции одной переменной

Перечислим вначале все булевы функции от 1-ой переменной  . Как мы знаем, их всего четыре.

1.  - константа 0;

2.  - константа 1;

3.  - тождественная функция;

4.  Эта функция называется отрицанием   и обозначается   (используется также обозначение  , а в языках программирования эта функция часто обозначается как  ).

2) Принцип двойственности

Опр. - n-местная булева ф-ия. Двойственной к n наз. n-местная булева ф-ия , определяемая условием для любого набора булевых величин ,где

– интерпретация функциональных символов, тогда -двойственная к .

Теорема. Принцип двойственности

Тогда

3) Класс А называется полным , если [A]=B.

Опр.Система б.ф . (или полна в классе К ) , если её [K]=B, ([ =K)

Опр. Базиса: Система (Базис класса К), если (полна в классе К) и любая другая подсистема ⊂ не полна в классе К.

4) - закон контрпозиции;

5)

	Г,	Г,
	Г,	Г

6)правила вывода

1.) - закон modus ponens

2) - закон modus tollens;

7) Понятие теории, полные разрешимые , категоричные теории

Теория Т-любое мн-во предложений.

Теория называется полной , если любые предложения , либо Т либо T

Теория Т называется разрешимой, если алгоритм, кот за конечное число шагов получит ответ на вопрос «выводиться ли из Т или нет?»

Теория Т называется категоричной мощности , если Т существует единственная модель мощности с точностью до дизъюнкта.

2 способа задания теории: 1. синтаксический: – аксиомы; 2. семантический: Th (𝕰)=

Св-ва теорий: 1. Непротиворечивость (противоречивость Т , Т ); 2. Полнота ( или Т ); 3. Аксиоматизируемость (конечная, счетная); 4. Разрешимость ( алгоритм имеем ответ Г или Г ); 5. Категоричная мощность ( модель: 𝕰 , |𝕰|=| 𝕰- )

8) Оператор примитивной рекурсии

;

Функция получается примитивной рекурсией из функций и если выполнены след условия:

;

3)F(y+1)=h(y,f(y));(f=R(g,h))

9) Т. О неподвижной точке:

неподжвижная точка – - обще рекурсивная ф-ия. Тогда .

10) Эрбранова область

Эрбранова область строится так : - область:

1. Если в формуле есть константный символ с, то ;

2. Если нет константных символов,=> новый ;

3. - n-местный функциональный символ

Если не содержит функциональных символов , то Эмбр обл конечно, иначе бесконечна.

16вариант=36

1)коньюкция

A	B	a/\b
0	0	0
0	1	0
1	0	0
1	1	1