4) Понятие прямой теоремы и произвольных от неё высказываний

Прямая теорема – высказывание вида A . Производное высказывание от прямой теоремы

Опр. А наз антецедей , В называется консеквент, а само утверждение наз.прямой теоремой; условие В необходимо для А , условие А достаточнодля В.

Расм.также B .

Опр. B -обратное , -против высказывание, теорема обратная противоположной

5) . Алфавит: а) счетное мн-во переменных;(x,y,z,t,..) б) символы логических операций; в) вспомогательные символы(

6)Т о дедукции

7) Опр. Функция F называется рекурсивной (ч.р.ф) , если F- элемент , или получен из элемента с помощью операций суперпозиции, примитивной рекурсии и минимизации.

Опр. Функция f – обще рекурсивная функция если f- частично рекурсивна и всюду определена.

Дополнение:

Ф-ия f наз. частично рекурсивной ф-ией, если такая последовательность ф-ий , что каждая - простейшая, либо получена из предыдущих с помощью одного из операторов.

8)Вывод генсена

&	Г,	Г
	Г,	Г
	Г,	Г
	Г,	Г

9) Т. О проекции:

Опр.Если рассматривается некоторое мн-во А, то проекцией этого множества А по j-ой координате называется

={ ,…, | }, если N⊇A, то его проекция

Теорема о проекции:

1.Мн-во А рек. Пер.  А –проекция рек мн.

2.Если А р.п => всякая проекция р.п. множество.

10) ответ на задачу не вычиляется Т как нет действительных корней уравнения

Вариант 11=21=41(четко)

1)

x	y	x↑y
0	0	1
0	1	0
1	0	0
1	1	0

2)х->y= V y

3) Теорема о существовании единственной сднф

Для всякой б.ф. Существует СДНФ от переменных причем единственная.

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

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

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

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

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

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

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

4) Понятие прямой теоремы и произвольных от неё высказываний

Прямая теорема – высказывание вида A . Производное высказывание от прямой теоремы

Опр. А наз антецедей , В называется консеквент, а само утверждение наз.прямой теоремой; условие В необходимо для А , условие А достаточнодля В.

Расм.также B .

Опр. B -обратное , -против высказывание, теорема обратная противоположной

5)генсена

	Г,	Г,
	Г,	Г

6) Понятие предиката

Опр. n- местный предикатом на мн-ве М называется функция P: Чтобы задать предикат надо:

1)задать местность

2)задать множество

3)значение.

А – мн-во; - предикат символов ставит в соответствие конкретный предикат на А.

на А; , получили структуру сигнатуры ; - интерпретация сигнатуры (каждая структура имеет свою четкую сигнатуру, обратно неверно).

7)Т. компактности.

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

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

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

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

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

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

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

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