Математическая Логика (стр. 4 из 4)

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

3.3.1 Определение.

1) ИВ противоречиво, если формула А выводима в нем.

.

2)

формула выводима в ИВ) ИВ противоречиво.

3)

ИВ противоречиво.

ИВ непротиворечиво, если оно не является противоречивым.

Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.

Док-во: (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

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

Геометрическое 'доказательство':

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

ч.т.д.