1вариант.= 21вариант=41вариант

1)таблица истинности для импликации

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

2) лемма о несамодвойственности функции

. Тогда (содержат «0» и «1»)

3) теорема о замене

1. — ф-ла, – ее подформула, - ф-лы, причем => .

2. - ф-лы, причем , x – символ переменной, - ф-лы причем . Тогда .

4) Семантическое дерево

– это корневое бинарное дерево, каждое ребро которого помечено некоторой литерой(симвалы из х или их отрицаниями), причем ребра выходящие из одной вершины помечаются переменной и ее отрицанием, и каждая ветвь, идущая от корня каждую переменную содержит не более одного раза.(одновременно х или не может быть)

5)Определение теории и разрешимость теории

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

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

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

6)элементарная эквивалентность моделей

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

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

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

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

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

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

7)постоить эрбранову область

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

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

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

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

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

Н={c,f(c),f(f(c)),…}

8) Т. о графике:

Опр.пусть f : , определим множество функции f,

Теорема о графике. Пусть тогда верны утверждения:

1) ч.р. фун  рек. Пер. множ.

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

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

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

F= S(

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

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

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

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

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

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

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

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

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

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

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

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

2.вариант=42вариант=(22наверно)

1)Таблица для коньюкции

x	y	xɅy
0	0	0
0	1	0
1	0	0
1	1	1

2) Кол-во булевых ф-ций.

Т. Число n-местных булевых ф-ций равно

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

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

4) Аксиомы ИВ:

A1) ,

A2) ,

A3) ( .

Правило вывода ИВ: .(MP-modus ponens правило отделения)

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

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

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

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

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

6) Терм

1)Свободные переменные

2)Константные символы

3) Если функцианал символ –терм ,то f( - терм.

7) Т. о дедукции:

8) Т. о графике:

Опр. Пусть f : , определим множество функции f,

Теорема о графике. Пусть тогда верны утверждения:

1) : N→N ч.р. фун  рек. Пер.

2)Если функция всюду определена f: N→N(f-o.р.ф.)  рекурсив. Множ.

9) Простейшие функции:

Опр. След функц называются элементарными:

S(x)=x+1;

(x)=0;

(проэкция)

10) Т.О полноте

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

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

3 вариант.=23вариант=43вариант

1)Дизъюнкция

x	y	x˅y
0	0	0
0	1	1
1	0	1
1	1	1

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

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

Следствие.

Опр.

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

Теорема.

для любых формул и любой интерпретации функций с

3) Лемма о немонотонной ф-ии

F M => [{f,0,1}](замыкание системы ф-ий из «0» «1» содержит отрицание)

4) - закон modus ponens

- закон modus tollens;

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

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