4) Лемма о нелинейной ф-ии:
. Тогда
5) Опр. Атомарные формулы сигнатуры -это слова двух видов:
1)
=
,
где
и
-термы сигн
2)
Р(t1,
…, tn),где
- предик. символ; t1,
…, tn
– термы
5) Определение формулы в лп
Опр.формула сигнатурой это слово, построенное по правилам:
1)атомарн формулы есть формулы
2)
если
-формулы
,то и
,
,
,
,
,
-тоже формулы
3)
Если
-формулы , х переменные , то слова
формулы.
6) Основные эквивалентности ЛП:
Все эквивалентности, пришедшие из ЛВ.
Если формула не содержит связанную переменную у
Если
не содержит переменную (ые) y,z,x
– свободная переменная
ψ
Ψ – не содержит у
Квантор всеобщности можно заменить на квантор существования и наоборот.
ψ(у))
)
)
7) Понятие теории, полные разрешимые, категоричные теории
Теория Т-любое мн-во предложений.
Теория называется полной , если любые предложения , либо Т либо T
Теория Т называется разрешимой, если алгоритм, кот за конечное число шагов получит ответ на вопрос «выводиться ли из Т или нет?»
Теория Т называется категоричной мощности , если Т существует единственная модель мощности с точностью до дизъюнкта.
2
способа задания теории: 1. синтаксический:
– аксиомы; 2. семантический: Th
(𝕰)=
Св-ва
теорий: 1.
Непротиворечивость (противоречивость
Т
,
Т
);
2. Полнота (
или Т
);
3. Аксиоматизируемость (конечная,
счетная); 4. Разрешимость (
алгоритм
имеем ответ Г
или Г
);
5. Категоричная мощность
(
модель: 𝕰
,
|𝕰|=|
𝕰-
)
8) Тезис Чёрча.
Класс интуитивно вычислимых ф-ий совпадает с классом ф-ий вычислимых по Тьюрингу.
9) S-m-n Т.Существует всюду определенная вычислимая ф-ия(о.р.ф.) ( :
10) Высчитать ф(2,3) оператором примитивной рекурсии, если ж(х) =х^2+х+ аш (x,y,z)= max(x,y,z)
ф(2,0)=ж(2)
ф(2,1)=аш(2,0,ф(2,0))
ф(2,2)=аш(2,1,ф(2,1))
ф(2,3)=аш(2,2,ф(2,2))
8)Вариант
1
а |
б |
a->б |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
2) . Рекурсивно перечислимымые множества
Мн-во А наз. рекурсивно перечислимым,
1)
если либо
,
либо существует f(x):A
,
где f
– общая рекурсивная ф-ия.
2)мн-во А рекурсивно перечислимо если его характ. функция
3) Аксиомы ив Генцена.
Алфавит—Алфавит ЛВ без
Секвенция – упорядоченная пара мн-в формул Г, Г знак секвенции
Аксиома: Г, где
Правила вывода ИВ Генцена: .
& |
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г |
Г, |
Г |
|
|
Г, |
Г, |
Г, |
Г |
|
̚ |
Г |
Г, |
Г , ̚ |
Г |