9) Т. Поста (критерий рекурсивности мн-ва).

Мн-во А – рекурсивное А и (дополнение к А) – рекурсивно перечислимы.

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

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

11) Ф-лы ЛВ:

Атомарная ф-ла: .

Опр.Формулой наз.: а) всякая атомарная ф-ла; б) если слова явл. ф-ми - ф-лы

5 вариант=25вариант=45вариант(наверно)

1. Штрих шеффера

x	y	x|y
0	0	1
0	1	1
1	0	1
1	1	0

2) Теоремы о нормальных формах

О существование СДНФ

Пусть f при этом f . Тогда существует СДНФ от представляющая f причем единственная с точностью до порядка конъюнктов и литер в этих конъюнктах

О существование СKНФ

Пусть f при этом f . Тогда существует СKНФ от представляющая f причем единственная с точностью до порядка дизъюнктов и литер в них

3) Т Поста. о полноте системы булевых ф-ий.

Система булевых ф-ий не содержится полностью ни в одном из классов , , L

4) - правило силлагизма(закон цепных рассуждений);

5) Непротиворечивость и выводимость:

Опр. Выводимость: ф-ла выводится из множества фор-л Г:Г  вывод .Последов называется выводом из множ Г, если кажд. Г (гипот),либо аксиома, либо получ МР из формул , ; j<k<i;

Опр. Множество формул Г называется противоречивым, если сущ.формула φ:Г⊢φ и Г⊢ (φ.) ̅ Если такой не сущ , то Г не противореч.

6) Модели и интерпритация формул данной сигнатуры.

Опр. Структура А(греческая с расслоённым концом) с сигнатурой интерпритация называется моделью предложения , если при данной интерпритации предложение А истинно А

7) Т. о полноте.

Теорема. Геделя(о полноте)

Множество формул не противоречиво  Г имеет модель.

⊢φ⟺⊨φ(теорема тогда и только тогда, когда тавтология)

Теорема Геделя (обобщенная теорема о полноте)

Г -предложение  Г

Логика высказывания и ИВ Гильберта:

Т.(о полноте ИВ Гильбрта)

Т.( обобщен теорема о полноте)

Т. компактности. Мн-во формул Г – выполнимо каждое конечное подмн-во Г выполнимо

Т. об адекватности логики ИВ Гильберта и ЛВ. Пусть Г – мн-во формул, -формула. Тогда следующие утверждения верны: 1. (Т о модели); 2.) ; 3) (обобщенная Т. о полноте ИВ Гильберта); 4) (Т. о полноте)

8) Машина Тьюринга

состоит из след элементов:

1)два конечных мн-ва

A={ - внешний алфавит

Q={ }- внутренний алфавит

2)лента разбитая на ячейки, потенциально бесконечная (в кажд момент времени врем конечно можем дополнить сколь угодно в разные стороны). Каждая ячейка содержит один символ внешнего алфавита.

- символ пустой ячейки.

3) Управляющее устройство (каретка)-В каждый момент времени работает с одной ячейкой. Коретка может прочитать/записать символ в ячейку и переместиться в соседн ячейку.

4) В каждый момент времени машина нах во внутр состоянии И каждое внутреннее состояние об-ся символом алфавита Q.

начальное состояние

конечное состояние

5) программа МТ –конечное мно-во команд вида

В программе не должно быть каманд с одинаковой левой частью.

9) S-m-n Т.

Существует всюду определенная вычислимая ф-ия(о.р.ф.) ( :