Оглавление

1.Высказывания. Примеры высказываний. Пропозициональные переменные. Определения основных логических операций. 4

2.Алфавит, язык, правильно построенные формулы алгебры высказываний. Примеры ппф. 4

3.Теорема о замене подформулы ппф АВ. Пример 4

4.Теорема о подстановке формулы вместо пропозициональной переменной в ппф. Пример. 5

5.Значение ппф АВ. Таблица истинности. Пример построения таблицы истинности. Выполнимые, опровержимые, тождественно истинные, тождественно ложные формулы АВ. Примеры. 5

6.Теорема о подстановке ппф вместо пропозициональной переменной в тождественно истинной формуле. 7

7.Теорема о правиле modus ponens 7

8.Эквивалентные формулы алгебры высказываний. 7

9.Теорема о подстановке ппф вместо пропозициональной переменной в эквивалентные формулы АВ. 7

10.Теорема о замене подформулы на эквивалентную формулу в ппф АВ. 8

11.Понятие формулы с тесными отрицаниями. Пример. 8

12.Теорема об эквивалентной формуле с тесными отрицаниями 8

13.Понятие днф и кнф. Примеры. 8

14.Теорема о существовании эквивалентной днф 8

15.Теорема о существовании эквивалентной кнф 8

16.Теоремы о виде тождественно ложной днф, тождественно истинной кнф 9

17.Понятия сднф, скнф. Построение сднф, скнф по таблице истинности данной формулы. 10

18.Построение сднф по данной днф. 10

19.Построение скнф по данной кнф 10

20.Условия существования скнф, сднф 10

21.Понятие логического следствия в АВ. Содержательный пример. 11

22.Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок. Примеры. 13

23.Установление факта логического следствия из данного множества посылок по таблице истинности. 14

24.Установление факта логического следствия из данного множества посылок путем определения совместности соответствующей системы логических уравнений. 14

25.Основные теоремы о логическом следствии (сведение установления факта логического следствия из данного множества посылок к установлению факта логического следствия из другого множества посылок) 15

26.Основные теоремы о логическом следствии (сведение установления факта логического следствия из данного множества посылок к проверке тождественной истинности или тождественной ложности формул АВ) 15

27.Схемы аксиом ИВ. Получение аксиом из схем аксиом ИВ. Пример. 16

28.Правило вывода modus ponens. Пример применения 16

29.Понятие доказательства в ИВ. Понятие исчисления. 18

30.Понятие доказательства из гипотез в ИВ 18

31.Основные теоремы о доказуемости из гипотез в ИВ. 18

32.Теорема о дедукции в ИВ 18

33.Понятие производного допустимого правила вывода в ИВ. Пример. 19

34.Технология доказательства с использованием произвольных допустимых правил вывода: сведение к подзадачам. Пример. 20

35.Теорема о совпадении множества тождественно истинных формул АВ и доказуемых формул ИВ: план доказательства 20

36.Связь между наличием факта логического следствия в АВ и тождественной истинностью вложенной импликации посылок и логического следствия этих посылок 20

37.Связь между наличием факта логического следствия в АВ и доказуемостью из гипотез в ИВ. 20

38.Непротиворечивость ИВ 20

39.Понятие алгебраической системы 21

40.Алфавит и язык АП. Сигнатура. Понятие терма данной сигнатуры. Пример. Ппф АП. Пример. Предложение. Пример. 22

41.Понятие алгебраической системы данной сигнатуры 24

42.Свободные и связанные переменные. Термы, свободные для данной переменной в данной формуле. 24

43.Значение терма данной сигнатуры в алгебраической системе той же сигнатуры. Пример. 24

44.Значение ппф АП данной сигнатуры в алгебраической системе той же сигнатуры 26

45.Кванторы и как обобщения логических связок & и . 26

46.Выполнимые формулы АП. Пример. 27

47.Тождественно истинные формулы АП. Пример доказательства тождественной истинности. 28

48.Эквивалентные формулы АП. Пример. 28

49.Теорема о замене подформулы на эквивалентную подформулу в ппф алгебры предикатов. 28

50.Теорема о подстановке ппф вместо атомной формулы в эквивалентные ппф алгебры предикатов 29

51.Пренексные нормальные формы. Теорема о существовании эквивалентной пнф: алгоритм получения эквивалентной пнф. 30

52.Сколемовская стандартная форма (ссф): основная теорема, функции Сколема. 30

53.Сколемовская стандартная форма (ссф): следствие основной теоремы. 31

54.Сколемовская стандартная форма(ссф): процедура построения, алгоритм Сколема. 31

55.Понятие логического следствия в АП. Пример. 31

56.Выполнимые и невыполнимые множества посылок в АП 32

57.Понятие резольвенты в АВ. Пример. 33

58.Теорема о свойстве резольвенты. 33

59.Основная теорема 33

60.Формулировка принципа резолюции в АВ 33

61.Схема применения принципа резолюции для доказательства факта логического следствия в АВ. Пример применения принципа резолюции для доказательства факта логического следствия. 33

62.Схема построения модели алгоритма 35

63.Характерные черты алгоритма 35

64.Элементы модели алгоритма 35

65.Основные предположения об элементах модели алгоритма 35

66.Устройство машины Тьюринга 36

67.Комбинации машин Тьюринга: композиция 36

68.Комбинации машин Тьюринга: разветвление 38

69.Комбинации машин Тьюринга: разветвление с циклом. 38

70.Вычислимые по Тьюрингу функции. 39

71.Разрешимые (рекурсивные) множества. Пример. Рекурсивно перечислимые множества. Пример. 39

72.Алгоритмически неразрешимые проблемы. Пример. Тезис Тьюринга. 40