1) Ч.Р. Фун  рек. Пер. Множ.

2)Если функция всюду определена => f о.р ф.  рекурсив. Множ.

7) Тезис Чёрча.

Класс интуитивно вычислимых ф-ий совпадает с классом ф-ий вычислимых по Тьюрингу.

8) Изоморфизм моделей , элементарная эквивалентность.

Опр. пусть даны две АС одинаковой сигнатуры А(греческая с раздвоённым концом) , А=<a, , B = < b, .Изаморфизм системы A(Гр) на сис-му B –это биекция со свой ствами:

1. константы (константы переводят в константы);

2. n-местног предиката (сохраняется истина предикат).

3) функцианал символа

Системы если существ изаморфизм

Опр. Две формулы наз эквивалентными 

Теорема. (об основных эквивалентностях)

4. Все эквивалентности лв.

5. Если фор-ла , не содержит связную переменную у : ;

6. Если не содержит переменных y,z ; X-свобод

–элементарная эквивалентность  любое предложение  ( истинно на  истинно на

9)Наитии Эрбран область

Ответ очевиден)))) с,f(c),f(f(c)),….

10) Два класса префиксов:

1. для ПНФ, которая начинается с ,

2) n-1(n )перемена кванторов

2. для ПНФ, которая начинается с ,

2) n-1(n )

3. 

14Вариант

1)

а	б	+
0	0	0
0	1	1
1	0	1
1	1	0

2) Дизъюнкт ( ) – это дизъюнкция переменных, либо их отрицаний. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конъюнктов. Совершенная ДНФ (СДНФ) – ДНФ, в которой каждый конъюнкт зависит от всех переменных.

ДНФ от переменных х₁, …, х_nназывается формула вида v v…..v ,где - конъюнкты от х₁, …, х_n.

СДНФ от х₁, …, х_n – формула вида v v…..v ,где , ,….., - совершенные конъюнкты, попарно неэквивалентные от х₁, …, х_{n .}

Опр. ДНФ и СДНФ – дизъюнктивная нормальная форма – это формула вида конъюнкт от переменных . СДНФ от переменных наз.:

1) ДНФ от этих переменных;

2) все совершенные конъюнкты от переменных ;

3) нет конъюнктов отличающихся порядком переменных.

3) Теоремма о разложении булл функции

Теорема о разложении булевой функции – каждую n-местную булеву функцию при любом m ( ) можно представить в форме , где дизъюнкция берётся по всевозможным наборам значений переменных .

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

Т о разложении булевой ф-ии: n-местной булевой ф-ии f и набор индексов. Ф-ия f представима:

4) Алфавит—Алфавит ЛВ без

Секвенция – упорядоченная пара мн-в формул Г, Г знак секвенции

Аксиома: Г, где

Правила вывода ИВ Генцена: .

&	Г,	Г
	Г,	Г
	Г,	Г
	Г,	Г
	Г,	Г,
	Г,	Г
̚	Г	Г,
	Г , ̚	Г

5) Теор о полноте МР: пусть S- множество дизъюнктов , S  из S по правилу резолюций можно получить пустой дизъюнкт.

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

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

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