Математическая Логика
Лемма:
Док:

3.1.4 Теорема Дедукции.
Если из

и 2а)
,
где
по правилу
m.p.
,
ч.т.д.
2б)
- уже выводили
,
ч.т.д.
Базис индукции:
N=1
- формальный
вывод из длинного
списка

(только что
доказано), осуществим
переход по
индукции:

по индукции
и по лемме
2

Пример:

по теореме
дедукции

3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
- тавтология
при любой интерпретации алфавита (символов переменных)

3.2.2 Понятие интерпретации.

символ переменной
переменную
поставим в
соответствие.
,
где
- проекция на
.


;
- только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:
Где:

3.2.3 Доказательство теоремы.


ф
ормальный
вывод

3.3 Непротиворечивость ИВ.
3.3.1 Определение.
ИВ противоречиво, если формула А выводима в нем.
.
формула
выводима в
ИВ)
ИВ
противоречиво.
ИВ
противоречиво.
ИВ непротиворечиво, если оно не является противоречивым.
Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.
Док-во:
(1) Если
,
то соответствующая
ей булева функция
будет тождественно
равна 1.

(2) Если любая формула выводима, то выводима и А, что соответствует пункту 1.
(3) Пусть
и
- булева функция
- противоречие.
3.4 Формальные исчисления.
Алфавит – конечное или счетное множество символов, возможно, разбитых на группы. Алфавит должен быть упорядоченным множеством.
Слово – конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.
V – множество всех слов.
Вычислимая
функция от
нескольких
натуральных
переменных

( f – может быть не всюду определенной )
f – называется
вычислимой,
если
такая машина
Тьюринга, которая
её вычисляет.
- разрешимое
множество, если
характеристическая
функция
- является
вычислимой.
Множество
называется
перечислимым,
если
такая вычислимая
функция

М - разрешимо
М и N
M
перечислимы.
М – перечислимо
М –
область определения
некоторой
вычислимой
функции.
Множество всех формул F – некоторое разрешимое подмножество V.
Т – счетное
множество, если
его биективное
отображение
на V.
- обозначение
счетного множества.
(
- алеф-нуль)
Если
и зафиксировано
биективное
и вычислимое
отображение
(вычис.),
то L – ансамбль.
V – ансамбль (слова лексикографически упорядочены и занумерованы)
Определение:
В произвольном
формальном
исчислении:
- множество
всех аксиом
– разрешимое
подмножество
множества всех
формул.

Правило вывода:
,при
разрешимо.
Для ИВ N=2.
Пример:
(пустое слово)
,


1 и
2 – формальные
выводы.
3 – не является формальным выводом.
4 Предикаты и кванторы.
4.1 Определение предиката.

- высказывание,
содержащее
переменную.
- предметная
область предиката.

Пусть А – множество объектов произвольной природы (предметная область предиката).
-местный
предикат
– произвольное
отображение

М
ножество
истинности
данного предиката

-
- характеристическая
функция от x на множестве
А - совпадает
с предикатами



4.2 Понятие квантора.
k
– связанная
переменная
n – свободная переменная
t – свободная,
x –
связанная.
, a,b,y –
свободные
переменные,
x –
связанная.





4.3 Геометрическая интерпретация навешивания кванторов.
-




- ортогональная
проекция на
ось x

Пронесение отрицания через кванторы

Геометрическое 'доказательство':
не обладает
свойством, что
прямая
целиком лежит
в



ч.т.д.


Курс лекций по математической логике, читаемый Андреевым Кириллом Кирилловичем
Создал Томашевич Максим Сергеевич (info@tommax.bizland)