9) Основная т. О рекурсивно перечислимых мн-вах:
Следующие 3 утверждения равносильны:
1) А - рекурсивно перечислимая ф-ия; или , где f – обще рекурсивная ф-ия.
2.
,
где f – частично рекурсивная
ф-ия.
3. A=dom (h), где h – частично рекурсивная в-ия.
10) Т. О проекции:
Опр.Если рассматривается некоторое мн-во А, то проекцией этого множества А по j-ой координате называется
={ ,…, | }, если N⊇A, то его проекция
Теорема о проекции:
1.Мн-во А рек. Пер. А –проекция рек мн.
2.Если А р.п => всякая проекция р.п. множество.
11)ответ на эрбранову область H={c,f(c),f(f(c),….,}
12)вариант=32=52(наверно)
1)
x |
y |
x|y |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
2)Кнф и скнф
Опр.КНФ
и СКНФ – конъюнктивная
нормальная форма – это формула вида
дизъюнкт
от переменных
.
СКНФ от переменных наз.: 1) КНФ от этих переменных;
2) все совершенные дизъюнкты от переменных ;
3) нет дизъюнктов отличающихся порядком переменных.
Другой вариант:
Конъюнкт
(
)
– это конъюнкция переменных, либо их
отрицаний. Конъюнктивная форма (КНФ) –
конъюнкция дизъюнктов. Совершенная КНФ
(СКНФ) – КНФ, в которой все дизъюнкты
зависят от всех переменных
3) Ф-лы ЛВ:
Атомарная ф-ла: .
Опр.Формулой наз.: а) всякая атомарная ф-ла; б) если слова явл. ф-ми - ф-лы
4) Т. об адекватности логики ИВ Гильберта и ЛВ. Пусть Г – мн-во формул, -формула. Тогда следующие утверждения верны: 1. (Т о модели); 2.) ; 3) (обобщенная Т. о полноте ИВ Гильберта); 4) (Т. о полноте)
5) Т. О неподвижной точке:
неподжвижная точка – - обще рекурсивная ф-ия. Тогда .
6) Правило вывода: 1. МР: ;
2. Gen ( - не содержит переменную y)
Опр.пусть -конечное множество фор-л , Гт- конечное множество свободных переменных кот встречаются в формулах ; послед. формул называется выводом из , Если для любого либо аксиома либо гипотеза (т.е принадл , либо получена из предыдущих по одному из правил вывода , причем , если тогда х непринадлежит Гт.
Опр.
вывод из Г(Г
,если
конечное подмножество
Г и вывод
из
.
Вывод из наз. Доказательством , а формула называется теорией.
Предложение
Если
Если Г Г
Если Г , Г⊂ =>
Правило Силогизма Если Г
13 вариант=33=53
1)эквивал.
а |
б |
= |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
2) Опр. ДНФ и СДНФ – дизъюнктивная нормальная форма – это формула вида конъюнкт от переменных . СДНФ от переменных наз.:
1) ДНФ от этих переменных;
2) все совершенные конъюнкты от переменных ;
3) нет конъюнктов отличающихся порядком переменных.
Дизъюнкт ( ) – это дизъюнкция переменных, либо их отрицаний. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конъюнктов. Совершенная ДНФ (СДНФ) – ДНФ, в которой каждый конъюнкт зависит от всех переменных.
3) Лемма о несамодвойственной ф-ии
. Тогда (содержат «0» и «1»)
Лемма о немонотонной ф-ии
. Тогда ф-я отрицания
2вар., F M=> [{f,0,1}]
4) Понятие прямой теоремы и произвольных от неё высказываний
Прямая теорема – высказывание вида A . Производное высказывание от прямой теоремы
Опр. А наз антецедей , В называется консеквент, а само утверждение наз.прямой теоремой; условие В необходимо для А , условие А достаточнодля В.
Расм.также B .
Опр. B -обратное , -против высказывание, теорема обратная противоположной
5)
6) Т. о графике:
Опр.пусть f : , определим множество функции f,
Теорема о графике. Пусть тогда верны утверждения: