2) Т. О замене
Т. о замене:
1. — ф-ла, - ее подформула или символ переменной, - ф-лы, причем => .
2.
-
ф-лы, причем
,
x – переменная входящая
в
,
- ф-лы причем
.
Тогда
.
3) Понятие прямой теоремы и произвольных от неё высказываний
Прямая теорема – высказывание вида A . Производное высказывание от прямой теоремы
Опр. А наз антецедей , В называется консеквент, а само утверждение наз.прямой теоремой; условие В необходимо для А , условие А достаточнодля В.
Расм.также B .
Опр. B -обратное , -против высказывание, теорема обратная противоположной
4) Опр.Класс М предполный , если [M] , где f[M].
Класс А называется предполным , если
1)[A]⊂B
2)[A =B, где
. Предполный класс – это неполный класс, но при добавлении в него любой ф-ии, не принадлежащей его замыканию, он становится полным.
5) Не противоречивость множ-ва формул и выводимости
Опр. Множество формул
Г называется противоречивым, если
сущ.формула
Если такой не сущ , то Г не противореч.
Опр. Ф-ла -выводиться из неё Г(Г ) , если вывод из
Г :
Непротиворечивость и выводимость:
Опр. Выводимость: ф-ла выводится из множества фор-л Г:Г вывод .Последов называется выводом из множ Г, если кажд. Г (гипот), либо получ МР из формул , ; j<k<i;
1)Г
Г
2) Г
Г,
;
3)Г
Г,
4)Г => Г
5)если Г
,
Г,
6)
7)
6) Два класса префиксов:
для ПНФ, которая начинается с ,
2) n-1(n )перемена кванторов
для ПНФ, которая начинается с ,
2) n-1(n )
7) Т. об адекватности логики ИВ Гильберта и ЛВ. Пусть Г – мн-во формул, -формула. Тогда следующие утверждения верны: 1. (Т о модели); 2.) ; 3) (обобщенная Т. о полноте ИВ Гильберта); 4) (Т. о полноте)
8) Вычислимость функции на мт
Пусть функция f:
Опр. функция f вычислима на Маш. Тью. М ó для любого набора машина М : W втом, и только том, случае , когда f(
Теорема. Всякая МТ вычисляет некоторую n-местную функцию.
Теорема . существ функции не вычислимые на МТ .Функции вычислимые на МТ называется вычислимыми.
МТ вычисляет ф-ию f набора ( ) M: , если определено, иначе (если не определено) М работает бесконечно. Всякая ф-ия, для которой можно построить МТ наз. вычислимой по Тьюрингу.
9) Т. о проекции:
Опр.Если рассматривается некоторое мн-во А, то проекцией этого множества А по j-ой координате называется
={ ,…, | }, если N⊇A, то его проекция
Теорема о проекции:
1.Мн-во А рек. Пер. А –проекция рек мн.
2.Если А р.п => всякая проекция р.п. множество.
18 вариант
1)
x |
y |
x↑y |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
2)
Принцип двойственности
Опр. - n-местная булева ф-ия. Двойственной к n наз. n-местная булева ф-ия , определяемая условием для любого набора булевых величин ,где
– интерпретация функциональных символов, тогда -двойственная к .
Теорема. Принцип двойственности
Тогда
3) Лемма о немонотонной ф-ии
. Тогда ф-я отрицания
2вар., F M=> [{f,0,1}]
4) Аксиомы ИВ Генцена.
Алфавит—Алфавит ЛВ без
Секвенция – упорядоченная пара мн-в формул Г, Г знак секвенции
Аксиома: Г, где
Правила вывода ИВ Генцена: .
& |
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г, |
Г, |
Г |
|
̚ |
Г |
Г, |
Г , ̚ |
Г |