МЛ

1. Формулы логики высказываний. Логические связки. Высказывание – это повествовательное предложение естественного или искусственного языка, по которому можно сказать, истинно оно или нет (ложно). Пр: 1. Париж – столица Франции (ист.). 2. 2>5 (ложно). 3. Я лгу (парадокс лжеца) – не высказывание. 1 – истина (U, t), 0 – ложь (^, f). В логике высказываний используется формальный алфавит. Алфавит А логики высказываний состоит из 3-х групп символов: 1. проп. переменные A, B, C. 2. проп. связки (логические связки):

¬(-) - логическое отрицание («не»); ^ (&) - конъюнкция («и») – умножение; v (+) - дизъюнкция («или») – сложение; → - импликация (следование); ↔ - эквивалентность

3. вспомогательные символы: (,) – скобки.

Формула: 1. все переменные – формулы. 2. если А и В – формулы, то (¬А), (А^В), (АvВ), (А→В), (А↔В) – формулы. 3. других формул нет.

2. Таблицы истинности. Построение таблицы по формуле и формулы по таблице.

A	¬A	A	B	A^B	AvВ	А→В	А↔B
0	1	0	0	0	0	1	1
1	0	0	1	0	1	1	0
		1	0	0	1	0	0
		1	1	1	1	1	1

Приоритет логических связей (по уменьшению области действия): ↔, →, v, ^, ¬

Скобки в формулах опускаются, если формулу можно …. по следующему правилу: (правило расстановки скобок) 1. Находим логическое отрицание и помещаем в скобки наименьшую следующую за ним формулу. 2. Находим вхождение конъюнкции и заключаем в скобки наименьшие формулы, находящиеся по обеим сторонам данного вхождения. 3. Находим вхождение дизъюнкции и заключаем в скобки наименьшие формулы, находящиеся по обеим сторонам данного вхождения. 4. Находим вхождение импликации и заключаем в скобки наименьшие формулы, находящиеся по обеим сторонам данного вхождения. 5. Находим вхождение эквивалентности и заключаем в скобки наименьшие формулы, находящиеся по обеим сторонам данного вхождения.

3. Тождественно истинные (ложные) и выполнимые формулы логики высказываний. Формула А тождественно истинная (общезначимая тавтология), если она принимает значение «истинна» независимо от значений входящих в нее элементов. Таблица истинности тождественно истинной формулы состоит из одних единиц.

Т1 Пусть формула А содержит переменные А₁, А₂,…, А_n и формула В получается из А заменой А₁, А₂,…, А_n формулами А₁, А₂,…, А_n соответственно, тогда если ╒А, то ╒В. Обратное утверждение неверно

Т2 Если ╒А и ╒А→В, то ╒В. тождественно ложное (противоречие, невыполнимая формула), если ее таблица истинности состоит из нулей.

Т3 А – тождественно истинная тогда, когда ¬А – тождественно ложная.

Формула называется выполнимой, если она принимает значение «истинна» хотя бы на одном наборе истинностных значений входящих в нее переменных.

А₁, А₂,…, А_n – множество совместное, если существует хотя бы один набор значений входящих в эти формулы переменных, на котором все формулы принимают значение истинности.

4.Равносильные ф-лы.Опр. А и В равносил. (А 3 черты В), (А˜В, А=В) если они приним. одинак. знач-я на всех наборах входящ. в них перемен. , др. словами ф-лы равносил. если у них совп. табл. истиности. Теор.5: А(3 черты)В тогда, когда ф-ла ≠А↔В.

5.Основн. равносильности ЛВ. Опр. А и В равносил. (А 3 черты В), (А˜В, А=В) если они приним. одинак. знач-я на всех наборах входящ. в них перемен. , др. словами ф-лы равносил. если у них совп. табл. истиности. Теор.5: А(3 черты)В тогда, когда ф-ла ≠А↔В.Теор.6: для любых ф-л А,В,С выполн. 1)(АˆВ)ˆС= Аˆ(ВˆС) 2)(АˇВ)ˇС=Аˇ(ВˇС) 3)АˆВ=ВˆА 4)АˇВ=ВˇА(3,4-комутативность) 5)Аˆ(ВˇС)=(АˆВ)ˇ(АˇС) 6)АˇВˆС=(АˇВ)ˆ(АˇС) (5,6-дистрибутивность) 7)АˇА=А 8)АˆА=А (7,8-идемпотентность) 9)АˇАˆВ=А 10)Аˆ(АˇВ)=А (9,10-элиминация) 11)неАˆА=0 12)АˇнеА=1(12-закон искл. 3-го) 13)не не А=А(зак. 2-ого отрицан.) и т.д.

6.Определения ДНФ и КНФ. Алгоритмы приведения

ДНФ формулы – формула, равносильная исходной и и записанная в виде дизъюнкции элементарных конъюнкций, построенных на пропозициональных переменных, т.е. F = K₁ K₂ K₃ . . ., где K_i = ( ABC . . .) КНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных, т.е.

F = D₁ D₂ D₃ . . . , где D_i = ( ABC . . . ).

Алгоритм приведения к нормальной форме

Шаг 1. Устранить логические связки “” и “” всюду по правилам:

F₁  F₂ =(F₁F₂)(F₂F₁)=( F₁ F₂)( F₂ F₁)=( F₁ F₂)( F₁ F₂);

F₁  F₂ = F₁F₂ = (F₁ ( F₂)).

Шаг 2. Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:

( F) = F ;

(F₁ F₂ ) = ( F₁) ( F₂);

(F₁F₂) = ( F₁)( F₂).

Шаг 3. Применить закон дистрибутивности:

a) для КНФ: F₁(F₂ F₃) = (F₁ F₂)(F₁F₃);

b) для ДНФ: F₁(F₂ F₃) = (F₁F₂)(F₁F₃).

7. Определения СДНФ и СКНФ. Теоремы существования и единственности.

Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной

Алгоритм преобразования ДНФ к виду СДНФ.

Шаг 1: если в элементарную конъюнкцию F не входит подформула F_i или F_i, то дополнить элементарную конъюнкцию высказыванием (F_iF_i) и выполнить преобразование формулы по закону дистрибутивности: F(F_iF_i)= FF_iFF_i;

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или F_j, то повторить шаг 1, иначе – конец.

Алгоритм преобразования КНФ к виду СКНФ.

Шаг 1: если в элементарную дизьюнкцию F не входит подформула F_i или F_i, то дополнить элементарную дизьюнкцию высказыванием (F_iF_i) и выполнить преобразование формулы по закону дистрибутивности: F(F_i F_i) = (F F_i)(FFi);

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или F_j, то повторить шаг 1, иначе – конец.

8.Логич. следов. в ЛВ, его св-в. Опр.ф-ла В след. из ф-лы А если В приним. знач-е истина на всех наборах перемен. на котор. истина ф-ла А . Опр.А1,А2,…Аm≠В ф-ла В логич. след. из ф-л А1,А2,…если В приним. знач-е истина на всех наборах перемен. ,на котор. ф-лы А1,А2,…Аn одновремен. приним. знач-е истина.Чтоб установ., что из ф-лы А=>В мы должны выпис. табл. истиности и сравн. Теор.7: а)А≠В≠А→В. ф-ла В след. из А, когда импликац. из А в В явл. общезначимой. б) А1,…Аm≠В<=>А1,…А(m-1)≠Аm→В. ф-ла В логич. => из ф-л А1…Аm когда из ф-л А1,…А(m-1)=>импликация. Следствие ф-лы В логич. след. из ф-л А1,А2,…когда ф-ла явл. тождеств. истиной А1…Аm≠ВА1→(А2→…(Ак→В)). Теор.8: А1…Аm≠ВА1ˆ…ˆАm ≠В т. и только тогда, когда В=> из коньюнкций.Следств. А1…Аm≠В≠А1ˆ… ˆАm→В. В=> из А1…Аm когда след. ф-ла явл. тождеств. истин. Теор.9: 1)А1,А2,…Аm≠Аi, i=1..m; 2) Пусть А1,…Аm ≠Вi, i=1…p; и из В1,В2…Вp≠С, тогда А1…Аm≠С.

9.Совместные и несовмест. мн-ва ф-л.Критерий совместности. Опр. мн-во ф-л А1,А2,..Аn наз. совместным если сущ. хотя бы 1 набор значений вход. в эти ф-лы перемен, на котор. все ф-лы приним. знач-е истина. Теор.4: (критерий совместности) мн-во ф-л А1,А2,..Аn совместно, тогда и только тогда, когда ф-ла А1ˆ,А2ˆ… Аn –выполнима.

10. Применение формул ЛВ к анализу рассуждений естественного языка.

А (не А; А не имеет места; А неверно);

АВ (А и В; как А так и В; А вместе с В; не только А, но и В; А, хотя и В; А, несмотря на В);

АВ (А или В; А и (или) В; А или В, или оба; А, если не В);

АВ (если А, то В; В, если А; А только если В; А влечёт В; для В достаточно А; для А необходимо В);

АВ ( А если и только если В; А тогда и только тогда, когда В; из а следует В и наоборот; для а необходимо и достаточно В; А равносильно В; А эквивалентно В)

Упрощение или сокращение текста

Рассм. Клуб с правилами:

1) члены фин. комитета (А) должны избир. Среди членов общ. дирекции (В),

2) нельзя быть одновременно членом общей дирекции и библиотечного совета (С) не будучи членом финансового комитета;

3) ни один член библиотечного совета не может быть членом финансового комитета

(АВ)(ВСА)(СА)(АВ)(ВСА)(СА)( АВ)  (ВСССАСВАСААА) (АВ) 

( ВССАСВАСА) (АВ)( С(В1АА) 

ВА) (АВ)( СВАВВ) (АВ)( СВ(АВ)) 

(АВ)( СВ)( САВ) (АВ) ( СВ) (АВ) (СВ)

Правило

Ни один член библиотечного совета не может быть членом общей дирекции.

Анализ рассуждений

Она сказала, что придёт, если не будет дождя. Но идёт дождь, значит она не придёт.

ДП, Д╒П

Д	П	Д	ДП	П
0	0	1	0	1
0	1	1	1	0
1	0	0	1	1
1	1	0	1	0

Если в предложении есть причинно-следственная связь или следование во времени, то нецелесообразно применять конъюнкции.

Энтимема – это довод, основанный на гипотезах, которые неявно подразумеваются.

Иван выше Маши, Пётр выше Ивана, значит Пётр выше Маши.

А, В ╒ С

Если Иван выше Маши, Пётр выше Ивана, то Пётр выше Маши

АВС А, В ╒ С

11. Предикаты и операции на множестве.

Предикат – это высказывательная ф-ция, определённая на некотором множестве Д, то есть каждому набору (d1…dn) diД сопоставляется некоторое высказывание P(d1…dn), 2, xy=P(x,y).

Предикат – это любая n-местная функция, принимающая значения из множества {0,1}.

Так как предикат принимает значение либо истина, либо ложь, то все логические связки применимы в предикатах.

xP(x) для всякого х выполнено свойство Р

xP(x) существует х, обладающий свойством Р

Группа символов

1) предикатные переменные 1={x1, x2, …, xn}

2) предикатные константы 2={а1, а2, …, аn}

3) предикатные символы 3={Pi ni}, iI, Pi -номер символа, ni – местность

4) функциональные символы 4={fj^y} jО

5) символы логических операций 5={, , , , , x, x}

6) вспомогательные символы 6={, ( )}

Множество =234 называется сигнатурой

12. Термы, атомарные формулы и формулы ЛП.

Терм t – сигнатура  определяется по индукции.

1. Все предметные константы и и предметные переменные являются термами.

2. Если fⁿ – n-местный функциональный символ, а f1, …, fn – термы, то f⁰(t1, …, tn) – термы.

3. Других термов, кроме построенных по пунктам 1, 2 нет

а1, х1, f₁¹(x1), f₂²(a1, f₁¹(x1))

Если Pⁿ – местный предикатный символ, t1, …, tn – термы, то слово формализованного языка вида Pⁿ(f1,…, fn) – элементарная (атомарная) формула.

Формула логики предикатов определяется по индукции.

1. Любая элементарная формула – формула.

2. Если А и В формулы, то (А), (АВ), (АВ), (АВ) – формулы.

3. Если х – предметная переменная, а А – формула, то (xА), (xА)-формулы.

xА – область действия квантора существования,

xА – область действия квантора всеобщности.

4. Других формул, кроме построенных по пунктам 1-3 нет.

13. Своб. и связ. вхождения переем. в ф-лу. Своб. и связ. перем. Замкнутые ф-лы. Опр. Вхожд. перем. Xi в ф-лу А наз. связ., если Xi попад. в обл. действ. Xi или Xi, в случае – вхожд. наз. своб-ым. Зам! В одну и ту же ф-лу переем. Xi может входить как связ., так и своб-но. Опр. Переем. Xi в ф-ле А связ., если сущ. ее связ. вхожд. Перем. Xi своб. в ф-ле А, если сущ. е своб. вхожд. в данную ф-лу. опр. Терм t своб. д/перем. Xi в ф-ле А, если перем. Xi не попад. в обл. действ. никакого квант. Xj или Xj, где Xj – перем, вход. в терм t. Опр. Ф-ла А наз. замкнутой, если перем, вход. в ф-лу, не имеют своб. вхождений.

14. Алгебр. сис-мы Опр. Алг. сис-ма M=<D,> сигнатуры  -- это не просто мн-во D, д/кот. кажд. пред. симв. сигн.  пост. в соотв. некот. отнош. на выходе, кажд. функц. симв. пост. операция, а кажд. перем. типа const – в соотв. став. мн-во D. Опр.Алг. сис-ма наз. моделью, если ее сигн. не содерж. функц. симв-в. Мн-во D наз носит. сис-мы. В матем. логике алг. сис-ма обычно наз. интерпр-ией, а носитель – предм. обл.

15. Тождеств. истинные/ложные и выполнимые( в сис-ме0 ф-лы. Опр. Ф-ла А наз. истинной в данной интерпретации, если она выполнена на всех послед-ях данной интерпр. Опр. Ф-ла А наз. ложной в данной интерпр., если она не вып-на ни на одной из посл-ей данной интерпр. Ф-ла выполнима, если она в данной интерпр. выполнима.

Опр. Ф-ла наз. тожд. истинной, если она истинна в люб. интерпр. Опр. Ф-ла наз. парадосом, если она ложна в любой интерпретации. Опр. Ф-ла наз. выполнимой, если сущ. интерпрет., в кот. хотя бы на 1 посл-ти данная ф-ла выполнена.

16. Равносильные (в системе) формулы.

Определение: Формулы А и В логич. эквивал.(А≡В) если каждая из них логически влечет другую.

Теорема№11

Пусть х_i – предметная переем. А(х_i)-произвольная ф-ла, С – ф-ла не содержащая свободных вхождений х_i.

а) Если ╞ С -> А(х_i), то ╞ С -> f (х_i , А(х_i))

б) Если ╞ А(х_i) -> С, то ╞ х_i А(х_i)-> С

Теорема№12

Пусть х₁…х_n – предметные перемен. А(х₁…х_n) – произвольн. ф-ла, r₁…r_n – предметные перемен. (не обязательно отличные друг от друга и от х₁…х_n), А(r₁…r_n) – результат подстановкив ф-лу А(х₁…х_n) переменных r₁…r_n , на места свободных вхождений переменных х₁…х_n – соответственно.

Тогда если данная подстановка свободна, то если ╞ А(х₁…х_n), то ╞ А(r₁…r_n)

Теорема№13

1. А╞ В  ╞ A -> B

2. A ≡ B  ╞ A <-> B (теорема 5)

Если А╞ В и А истинна в некоторой импликации, тогда В истинна в той же импликации

17. Основные равносильности ЛП.

Для формул ЛП справедливы все формулы логики высказывании (Теорема 6)

Теорема№14

Пусть А(x_i), B(x_i) – произвольные формулы, С – формула не содержащая свободных вхождений x_i , тогда справедливы следующие формулы:

1. x_i C ≡ C

2. x_i C ≡ C

3. x_i A(x_i)^ x_i B(x_i) ≡ x_i(A(x_i)^B(x_i))

4. x_i A(x_i)\/C ≡ x_i (A(x_i)\/C)

5. x_i A(x_i)\/ x_i B(x_i) ≡ x_i (A(x_i)\/B(x_i))

6. x_i A(x_i)^C ≡ x_i (A(x_i)^C)

7. ⌐(x_i A(x_i)) ≡ x_i ⌐(A(x_i))

8. ⌐(x_i A(x_i)) ≡ x_i ⌐(A(x_i))

9. x_i (C -> A(x_i)) ≡ C -> x_i A(x_i)

10. x_i (C -> A(x_i)) ≡ C -> x_i A(x_i)

11. x_i (A(x_i) -> C) ≡ x_i A(x_i) -> C

12. x_i (A(x_i) -> C) ≡ x_i A(x_i) -> C

13. x_i (A(x_i) -> B(x_i)) ≡ x_i A(x_i) -> x_i B(x_i)

14. x_i A(x_i) ≡ x_j A(x_j) – рез-т подстановки x_j на места своб. вхождений x_i

15. x_i A(x_i) ≡ x_j A(x_j)

Замечание: x_i A(x_i)^ x_i B(x_i) ≠ x_i(A(x_i)^B(x_i))

x_i A(x_i)\/ x_i B(x_i) ≠ x_i (A(x_i)\/B(x_i))

Теорема№15

Для любых формул А и В следующие формулы являются логически общезначимыми(╞):

1. ╞ x_ix_j A -> x_jx_j A

2. x_i A(x_i)\/ x_i B(x_i) -> x_i (A(x_i)\/B(x_i))

3. x_i (A(x_i)^B(x_i)) ->x_i A(x_i)^ x_i B(x_i)

4. ╞x_i (A(x_i) -> B(x_i)) -> (x_i A(x_i) -> x_i B(x_i))

5. ╞ (x_i A(x_i) -> x_i B(x_i)) -> x_i (A(x_i) -> B(x_i))

18. Предваренная нормальная форма(ПНФ) формул ЛП. Алгоритм приведения.

Определение: Нормальной формой(НФ) – формул ЛП называется формула которая содержит только операции ^ \/ и кванторы, а инверсии отнесены к предикатным символам.

Определение: ПНФ – формул ЛП называется равносильная ей формула логики предикатов вида: Q₁x₁Q₂x₂…Q_nx_nA(x₁…x_m), где Q_i{}, n≤m, а вормула А приведена к НФ и не содержит кванторов.

Для любой формулы логики предикатов существует эквивалентная ей ПНФ.

Алгоритм приведения к ПНФ:

1. Исключить “->” , “”

2. Отрицание перенести к предикатным символам

Вынести кванторы используя Теорему№14

19.Формал. теории.Вывод в формал. теории.Опр.ф-ла А наз. теоремой в теории Т если сущ. вывод теории Т, в котор. послед. ф-ла совп. с А. Опр.если сущ. эффективн. процедура, котор. позвол. опред. по любой ф-ле теории, явл. ли она теоремой, или нет, то теор. наз. разрешим.,в противн. сл. неразрешимой.Правило вывода: сущ. единств. прав. наз. правилом отделен. modus poneus (mp). Формал. теория наз.непротивореч. если в ней не сущ. такой ф-лы А, что и А и ее отрицание доказуемы; в противн. случ. теория наз. противоречивой. Формал. теория наз полной, если любая общезнач. ф-ла в ней доказуема, если нет то неполная.

19. Формальные теории

Определение: формальная теория – способ изложения логики без приписывания какого либо значения пропозициональным переменным, предикатам и формулам.

Состоит из следующих компонент :

1. множество знаков, обр алфавит

2. множ-во слов, сост из алфавита - формулы

3. помн-ва формул всего мн-ва формул – аксиомы

4. мо-во правил вывода, с пом кот из форм получ форм

В язык теории входит форм и алфавит.

Формальное доказательство – конечн. Послед. Формул A1,A2…, An,

Где Ai –аксиома либо получ из прошл аксиом с пом прав вывода, An – формула А(теорема) Обозн ├A

Форм теория – полная, если для кажд высказ имеем ├ A или ├ ¬ A

Форм теория –непротиворечивая, если в ней недоказуема формула

A&¬ A

20. Исчисление высказываний

Это следующая форм теор :

Алфавит :

• знаки пропорц переменных - X1…xn

• Логич связки - ^, &, ¬, =>

• Вспомогательные знаки – (,)

Формулы :

• Пропозициональная переменная – атомарная формула

• Если A и B – форм то и A&B, A^B, A=>B –форм

• Если A – форм, то ¬ A – форм

Аксиомы (схемы Клини)

• A=>(B=>A)

• (A=>(B=>C))=>((A=>B)=>(A=>C))

• (A&B)=>A

• (A&B)=>B

• A=>(B=>(A&B))

• A=>(A^B)

• B=>(A^B)

• (A=>C)=>((B=>C)=>((A^B)=>C)

• (A=>B)=>((A=>¬B)=> ¬ A)

Правила вывода

• A, A=>B | B - modus ponens

21. Теорема дедукции

Определение док-ва :

Пусть Г- мно-во формул. Форм А выводима из мн-ва гипотез Г, если сущ конеч послед формул A1…An, где Ai –аксиома либо гипотеза либо получ из предид пом прав вывода и An – форм A. Последовательность A1…An – вывод форм А из мн-ва гипотез Г. Использ обозн для вывода : Г├ А. Если Г = 0 то вывод – док-во форм А, а сама форм А - теорема. Использ симв запись для теорем ├ А.

Теор. Дедукции:

Г, A=>B, то Г├ (А=>B)

22. теорема о полноте ИВ. Следствие о непротиворечивости ИВ.

Для исчисления высказываний справедливо утверждение :

╞A тогда и только тогда, когда ├ А (1)

ИВ – полная теория . Следует утвержд. (1)

ИВ – непротиворечивая теория . Следует из (1) : Если бы была доказуема формула A=B&¬B , то была бы общезначимой формула B&¬B. Но она – ложна.

23.Исчисление предикатов.Опр. теория 1-ого пор-ка, не содерж. собств. аксиом аз. исчисл. предикат. Аксиомы (А1) А→(А→В) (А2)(А→(В→С))→(А→В)→(А→С) (А3) (¬В→¬А)→((¬В→А)→В) (А4) для люб. XА(х)→А(t) , где t терм свободн. для перем. х в ф-ле А(х) (А5) для люб. х(А→В)→(А→для люб. хВ) .Теор.25: любая теор. ислисл. предик. явл. общезначим. ф-лой .

24. Теорема о полноте ИП.

Т. Гёделя – для исчисления предикатов справедливо утверждение :

╞A тогда и только тогда, когда ├ А (1)

ИП – полная теория . Следует утвержд. (1)

ИП – непротиворечивая теория . Следует из (1) : Если бы была доказуема формула A=B&¬B , то была бы общезначимой формула B&¬B. Но она – ложна.

25.Теории. Непротиворечивые теории. Полные теории. Форм. теория наз. непротив., если в ней не сущ. такой ф-лы А, что А и ¬А доказуемы. В прот. случае теор. наз. против-ой.// Форм. теория наз. полной, если люб. общезн. ф-ла в ней доказ-ма. Если это не вып., то теория наз неполной.

26. Форм. арифм. Теор. Геделя о неполн. Собств. аксиомы ФА: (S1) x1=x2→(x1=x3→x2=x3) (S2)x1=x2→x1'=x2' (S3)0±x' (S4)x1'=x2'→x1=x2 (S5) x1+0=x1 (S6) x1+x2'=(x1+x2)' (S7)x1*0=0 (S8)x1x2'=x1x2+x1 (S9) A(0)=(Yx(A(x) →A(x'))→YxA(x)), где А – произв. ф-ла. Теоремы: 1)t=t 2)t=r→r=t 3)t=r→(r=s→t=s) 4)r=t→(s=t→r=s) 50t=r→t+s=r+s 6)t=0+t 7)t'+r=(t+r)' 8)t+r=r+t 9)t=r→s+t=s+r 10)(t+r)+s=t+(r+s) 11)t=r→ts=rs 12)0*t=0 13)t'r=tr+r 14)tr=rt 15)t=r→st=sr //Т.Геделя. Всяк. непротив. формализ-ия арифм. или люб. мат. теории, содерж. арифм., неполна и непополнима в том смысле, что: а)в этой теории сущ. ист. ф-лы, кот. неразрешимы, т.е. в данной теории не выв-ся на А, ни ¬А; б)каким бы кон. мн-вом не расширить сист. аксиом, в этой теории найд-ся неразреш. ф-лы.

27. Прав. резолюций для ИВ. Схема метода рез-ий для ИВ. A1,..An+B<=>+A1^A2^..An→B. Мет. рез. док-ет: ¬(A1^A2^..An→B)≡0, где ¬(A1^A2^..An→B)≡1^A2^..An^¬B.//Прав. рез. x۷y,¬y۷z+x۷z MP—ч.сл. при x=0 =>y,y→z+z. Осн. идея мет. рез. – провер, содерж. ли мн-во диз-ов □, и если нет, --вывод. ли □ из мн-ва диз-ов. Схема мет. рез.: 1) прив-ти гипотезы и отриц. закл-ия к КНФ. 2)Получ. мн-во диз-ов из кажд. КНФ. 3) Прим. прав. рез-ий до тех пор, пока не пол-ся □. Вывод мет. рез. удобно предст. в виде дерева.

28. Правило рез-ий для ИП. Схема метода рез-ий для ИП. A1,..An+B<=>А1^A2^..An^¬B≡0 x۷y,¬y۷z+x۷z – прав. рез.Д/ИП не сущ. алгор., кот. устан. бы, явл. ли ф-ла тожд. ложной или нет. Но сущ. алгор., кот. док-ют, что ф-ла тожд. ложна, если она на самом деле тожд. ложна. На ост. ф-ах эти алг. вообще не остан. Схема мет. рез.: 1) прив. гипотезы и отр. закл-ия к ПНФ, а затем к СНФ (если перед квант. сущ. нет квант-ов, то пер. замен. на конст.,если есть, то – на ф-ию от переем, попад. в обл. действ. квант-ов) 2)Выпис. диз-ты 3)производим унификацию.(строим мн-во рассоглас, если в нем сущ. переем. x_k и терм t_k такие, что x_k не вход. в t_k, тогда t_k│x_k. Если такие t_k и x_k не сущ, то мн-во не униф. и алг-м заканч. работу )

29. Машина Тьюринга. – это формализ-ия интуит. понятия алго-ма. Состоит из: 1)бескон. лента 2)конечн. мн-во симв. S₀,S₁,..S_n, наз. алфав. МТ 3)q₀,q₁,.. q_m – внутр. сост-ия МТ 4)счит. головка.// МТ раб. не непрер-но, а в дискретный момент врем.//Опер-ии: q_iS_kS_jq_r – замен. S_k на S_j; qiS_kLq_r – сдвиг. на 1 кв. влево; q_iS_kRq_r – сдвиг. на 1 кв. вправо; остан-ся.// Наборы четверок (привед. выше) наз. МТ, если д/люб. 2 четв. первые 2 симв. не совпад. Конфиг. МТ – посл-ть симв. типа Pq_sQ, где P и Q – слова алф-та МТ, причем слово Q – не пустое. МТ выч-ет ф-ию f(x1,x2,..xn), если сущ. такие конфиг. α1,α2..αm такие, что α1=q₀x1*x2*..xn, αm=Pq_rQ, где PQ=R1f(x1,x2..xn)R2. В общ. случ. МТ может не остан.,=>ф-ия не опред. Ф-ия, д/кот. сущ. МТ, выч-ая эту ф-ию, наз. выч-мой по Тьюрингу.

30. Вычислимые ф-ии. Пусть Q~ счетн. беск. класс ??-ов, кажд. из кот. треб-ет представл. некот. объекта (тип ??-ов "чему равно?"). Если сущ. процед., дающ. ответ на кажд. ?-ос класса Q~, то она наз. выч-ой пр-ой или выч. алгор-ом. Пр. Чему = корни ур-ия ax²+bx+c=0.//ф-ия наз вычисл., если сущ. выч-ая процед. для соотв. ей класса вопросов.

31.Универсал. МТ. Кодировка R 101 –вправ. , L 1001 –влево, q0 100001, q1 1000001, q_m 2(m+2)-нулей. Унив. ф-ция Клини R(x,y) выч. по след. алг-му 1)если Х не явл. номером МТ то ф-ция R(x) не определ. 2)если Х некот. номер нек. МТ то выпис. команды дан. МТ x=I(T₁) 3)запуск. машин. в конфиг. q0y(y-цифра) 4)если маш. когда ниб. остан. то кол-во единиц на ленте явл. значением ф-ции Клини. В ост. сл. ф-ция не опред. Теор. 38: ф-ция Клини выч. по Тьюрингу. Теор. (теор. о неподв. (.) ) для люб. вычисл. по Тьюр. ф-ции f(x) сущ. X₀ €N, такое, что след. равен. выпол. для любого у K(X₀, y)=K(f(x), y).

32. Теор. о неразреш. проблемы остановки. Опр. Массовая пробл. это бесконеч. класс однотип. задач. Пробл. остановки закл. в след. : остан. ли произвол. МТ, начин. работу с пуст. ленты. Теор.43: проблема остановк. алгоритмич. неразрешима Д-во K(x,x) сущ. Т_К Рассм. Т₀ : q₀S₀→q₀X(с чер.) Рассм. МТ Т=Т₀ *Т_К, тогда получ. Т_ост.  K(x,x) опред. Если сущ. алг-м , котор. опред. останавл. ли маш. с пуст. клетки, когда алг-м опред. Теор.44: не сущ. алг-мов котор. портит все МТ. МТ наз. оптимал. если не сущ. никакой МТ реализ. те же ф-цию и содерж. меньшее число команд. Теор.45 не сущ. алг-ма котор. бы по любой маш.Тьюр. опред. оптимал. ли она или нет Д-во пред. что сущ. алг-м. Тогда для люб. маш. Т постр. эквивал. ей маш. Т₁ след. образом перибир. все нат. числа, пока не найд. маш. Т обл. след. св-ами 1)X₀=I(T₁)-номер МТ 2)Т₁ оптимал. 3)Т₁ содерж. больше команд чем Т. Т.о. мы постр. маш. Т, не эквивал. исходной, по опред. это невозможно. Т.о алг-ма для опред. оптимал. ли МТ-нет.

33.Теор.о неразреш. проблемы эквивалентности.Предпол. Т₁ и Т₂ –МТ. Сущ. ли алг-м, котор. опред. эквивал. машина или нет? Теор.46: Не сущ. алг-ма, котор. по 2-м произвол. МТ опред. эквивал. они или нет.Д-во: пред. что сущ. алг-м. Рассм. произвол. МТ Т с числом команд n. И рассмотр. все МТ с числом команд <n. Это число конечно.Для всех таких пар {T, T_i}. Если не нашли ни какой эквивал. МТ, то Т-явл. оптимальной, Если нашли эквивалент. то Т-не оптимальна. Т.о. если есть алг-м, опред. оптимал. ли машина или нет. А по теореме это невозможно. Значит и алг-ма, опред. оптимал. ли эта маш. не существует.

34.Теор.о неразрешим. распознования выводимости. Вывод в формал. теории.Опр.ф-ла А наз. теоремой в теории Т если сущ. вывод теории Т, в котор. послед. ф-ла совп. с А. Опр.если сущ. эффективн. процедура, котор. позвол. опред. по любой ф-ле теории, явл. ли она теоремой, или нет, то теор. наз. разрешим.,в противн. сл. неразрешимой.Правило вывода: сущ. единств. прав. наз. правилом отделен. modus poneus (mp). Формал. теория наз.непротивореч. если в ней не сущ. такой ф-лы А, что и А и ее отрицание доказуемы; в противн. случ. теория наз. противоречивой. Формал. теория наз полной, если любая общезнач. ф-ла в ней доказуема, если нет то неполная. Верно ли для произвол. ф-л А и В данной теории, что А вывод. из В (А(зачеркн. палочка)В).Теор.47: проблема распознав. выводимости для формал. теории S алгоритмически не разрешима.

35.Ассоциативные исчисления.А- алфавит, ∑_Т-мн-во формал. равенств, А={a,b,c}, ∑_А={аа=вв, авв=вс, ас=св}. < А₁∑_А >-ассоциативное исчисление. Есть посл-ть p₁…p_n , если для любого i=i…n-1, слово p_i+1 получ. из слова p_i

непосредств. примен. рав-ва из сигма, то слова p₁…p_n наз. эквивалентными. Проблема рав-ва слов: сущ. ли алг-м, опред. для 2-х слов вывод. одно из друг. или нет А={a,b,c} ∑_T={ax=xax, bx=xbx} Алгоритм 1)вычеркив. слова p₁ и p₂ если получили ≠ слова, значит p₁ не вывод. из p₂ и алг-м заканчив. работу 2)для кажд. из 2-х слов p₁ и p₂ выпис. правый блок до буквы ­Х , если получ. блоки ≠, то слово p₁ не вывод. из p₂, алг-м заканч. работу. 3)в слов. p₁ и p₂ счит. буквы Х справа идущие подряд. Если их кол-во ≠, то p₁ не вывод. из p₂, в противн. сл. слово p₁ вывод. из p₂. Интерпр. МТ в ассоц. исчислен. Q_T={q₀,q₁…q_n} S_T={S₀…S_n} S_T-это мн-во, в кач-ве алфавита А возьмем объед. мн-в А_Т=Q_TˇS_T; ∑_Т (мн-во формал. равенств.)={q_iS_jS_kq_r→q_iS_j=q_rS_k}. Слово р-наз. словом машин. вида Аq_iS_jB если слова А, В сост. из слов мн-ва S_T Теор.48: пусть 2 слова маш. вида p₁=A₁q’S’B₁ (1) p₂=A₂q’’S’’B₂ (2) – в алфавите А_Т и соотв. МТ содержащей сост. q’’ только в одной команде. Тогда МТ начин. с конфигурац. (1) заканч. раб. в (2), когда в слов. p₁ и p₂ эквивал. исчислению <A_T, ∑_T> . Теор. 49 сущ. ассоц. исчисления в котор. проблема равенства слов алгоритмич. неразрешима.