10) Эрбранова область

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

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

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

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

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

6 вариант=26=46(наверно)

1)эквивал.

а	б	=
0	0	1
0	1	0
1	0	0
1	1	1

2) Формулы ив:

А) атомарные формулы

Б) -фор-лы => ,( формулы.

Нет понятия истености и ложн, есть сущест и не существ.

3) Класс монотонных функций

Опр. 

Функция называется монотонной, если есть порядок.

Т.е f- монотонна , если

M ={f | f- монотон} класс монот функций.

4) Опр.Класс предполный

, если [M] , где f[M].

Класс А называется предполным , если

1)[A]⊂B

2)[A =B,

Класс А называется полным , если [A]=B.

5) Правило вывода: 1. МР: ;

2. Gen ( - не содержит переменную y)

Опр.пусть -конечное множество фор-л , Гт- конечное множество свободных переменных кот встречаются в формулах ; послед. формул называется выводом из , Если для любого либо аксиома либо гипотеза (т.е принадл , либо получена из предыдущих по одному из правил вывода , причем , если тогда х непринадлежит Гт.

Предложение

1. Если

2. Если Г Г

3. Если Г , Г⊂ =>

4. Правило Силогизма Если Г

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

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

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

7) Опр. рекурсивной функции

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

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

8) Т. о неподвижной точке:

неподжвижная точка – - обще рекурсивная ф-ия. Тогда .

9) Оператор минимизации

Опр. пусть

=0 (1)

Наим. Корень уравнения (1)

определенно чтобы машина не зациклилась.

Опр.Функция получена минимизацией из функций , если =

10) Теорема о теории модели

1. (Т о модели); 2.)

7вариант=27=47

1.таблица сложения

x	y	х+y
0	0	1
0	1	0
1	0	0
1	1	0

2.двойств и самодв

Опр.Двойственная (сопряженная) к f функция – это

Опр. F самодвойств( самосопряженная) , если она двойственна сама себе.

(класс самодвойственных ф-ии)

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

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

Следствие.

Опр.

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

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