Лекции по "Математической логике"

Слово – конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.

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.com)