5) Т. О дедукции:

6)

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

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

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

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

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

8) Вычислимость функции на мт

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

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

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

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

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

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

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

10)подставить вместо х 4!!!!

19 Вариант

1)

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

2) Для всякой б.ф. существует СКНФ от переменных причем единственная с точностью до порядка дизъюнктов в коньюкции и переменных в дизъюнкции.

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

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

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

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

4) Ф-лы ЛВ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема о компактности.

Множество предложений имеет модель  каждое его конечное подмножество имеет модель.

9) S-m-n Т.

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