- •10) Понятие прямой теоремы и произвольных от неё высказываний
- •11) Т. О проекции:
- •1)Таблица для коньюкции
- •6) Терм
- •10) Т.О полноте
- •1)Дизъюнкция
- •3) Лемма о немонотонной ф-ии
- •6) . Основная т. О рекурсивно перечислимых мн-вах:
- •7) Проблемма остановки
- •8) Оператор примитивной рекурсии
- •9)Изоморфизм моделей
- •2) О существование скнф
- •3) Лемма о немонотонной ф-ии
- •6) Оператор минимизации
- •7) Понятие теории, полные разрешимые , категоричные теории
- •9) Т. Поста (критерий рекурсивности мн-ва).
- •10) . Тезис Чёрча.
- •Штрих шеффера
- •2) Теоремы о нормальных формах
- •8) Машина Тьюринга
- •10) Эрбранова область
- •1. Если в формуле есть константный символ с, то ;
- •2) Формулы ив:
- •3) Класс монотонных функций
- •4) Опр.Класс предполный
- •6)Т. Компактности.
- •10) Теорема о теории модели
- •4) Лемма о нелинейной ф-ии:
- •5) Определение формулы в лп
- •8) Тезис Чёрча.
- •8)Вариант
- •2) . Рекурсивно перечислимымые множества
- •3) Аксиомы ив Генцена.
- •4) . Т. О графике:
- •1) Ч.Р. Фун рек. Пер. Множ.
- •5) Т Поста. О полноте системы булевых ф-ий.
- •6)Т. Компактности.
- •7) Полином Жигалкина
- •8)Ответ
- •9 Вариант
- •3) ) Лемма о немонотонной ф-ии
- •4) Понятие прямой теоремы и произвольных от неё высказываний
- •5)Правило вывода Ив генсена
- •7) Т.(о полноте ив Гильбрта)
- •9) Т. Поста (критерий рекурсивности мн-ва).
- •1)Дизъюнкция
- •2) Фиктивные и существенные переменные.
- •3) Теоремма о разложении булл функции
- •4) Понятие прямой теоремы и произвольных от неё высказываний
- •6)Т о дедукции
- •8)Вывод генсена
- •9) Т. О проекции:
- •3) Теорема о существовании единственной сднф
- •9) Основная т. О рекурсивно перечислимых мн-вах:
- •10) Т. О проекции:
- •2)Кнф и скнф
- •5) Т. О неподвижной точке:
- •Предложение
- •1) Ч.Р. Фун рек. Пер. Множ.
- •Все эквивалентности лв.
- •Если фор-ла , не содержит связную переменную у : ;
- •Если не содержит переменных y,z ; X-свобод
- •9)Наитии Эрбран область
- •10) Два класса префиксов:
- •14Вариант
- •3) Теоремма о разложении булл функции
- •7)Вычисл функции
- •8) Оператор суперпозиции:
- •1) Булевые ф-ции одной переменной
- •2) Принцип двойственности
- •7) Понятие теории, полные разрешимые , категоричные теории
- •8) Оператор примитивной рекурсии
- •9) Т. О неподвижной точке:
- •10) Эрбранова область
- •1. Если в формуле есть константный символ с, то ;
- •2) Т. О замене
- •3) Понятие прямой теоремы и произвольных от неё высказываний
- •5) Не противоречивость множ-ва формул и выводимости
- •6) Два класса префиксов:
- •8) Вычислимость функции на мт
- •5) Т. О дедукции:
- •7) Понятие теории, полные разрешимые , категоричные теории
- •8) Вычислимость функции на мт
- •9) Т. Поста (критерий рекурсивности мн-ва).
- •19 Вариант
- •3) Теоремма о разложении булл функции
- •20 Вариант
- •2) Т. О дедукции.
- •5) Тезис Чёрча.
- •6) Т. О неподвижной точке:
- •7) Оператор суперпозиции:
- •8) Т. Компактности.
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) Аксиомы ИВ Генцена.
Алфавит—Алфавит ЛВ без
Секвенция – упорядоченная пара мн-в формул Г, Г знак секвенции
Аксиома: Г, где
Правила вывода ИВ Генцена: .
& |
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г, |
Г, |
Г |
|
̚ |
Г |
Г, |
Г , ̚ |
Г |