<<
>>

3.4 Формальные исчисления.

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

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

пустое слово.

V – множество всех слов.

Вычислимая функция от нескольких натуральных переменных

( f – может быть не всюду определенной )

f – называется вычислимой, если такая машина Тьюринга, которая её вычисляет.

- разрешимое множество, если характеристическая функция

- является вычислимой.

Множество называется перечислимым, если такая вычислимая функция

М - разрешимо М и N \M перечислимы.

М – перечислимо М – область определения некоторой вычислимой функции.

Множество всех формул F – некоторое разрешимое подмножество V.

Т – счетное множество, если его биективное отображение на V.

- обозначение счетного множества. ( - алеф-нуль)

Если и зафиксировано биективное и вычислимое отображение (вычис.),

то L – ансамбль.

V – ансамбль (слова лексикографически упорядочены и занумерованы)

Определение: В произвольном формальном исчислении: - множество всех аксиом – разрешимое подмножество множества всех формул.

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

,при разрешимо. Для ИВ N=2.

Пример:

(пустое слово) ,

1 и 2 – формальные выводы.

3 – не является формальным выводом.

<< | >>
Источник: Конспекты лекций по математической логике. 2017

Еще по теме 3.4 Формальные исчисления.:

  1. 4. Проблема способа изложения положительной теоретическойметафизики как науки
  2. ПРОБЛЕМА СООТНОШЕНИЯ МЫШЛЕНИЯ И ЯЗЫКА В ТРУДАХ Г. В. ЛЕЙБНИЦА, И. КАНТА, Ф. В. ШЕЛЛИНГА И Г. ФРЕГЕ 
  3. Математическое моделирование
  4. ИСЧИСЛЕНИЕ ЛОГИЧЕСКОЕ
  5. ЛОГИКА ФОРМАЛЬНАЯ
  6. 1.1. Исчисление высказываний и гибель формул
  7. ДЕДУКЦИЯ
  8. ИСЧИСЛЕНИЕ
  9. МЕТАТЕОРИЯ
  10. Примечание 2 Цель дифференциального исчисления, вытекающая из его применения
  11. § 4. СТРУКТУРА И ФУНКЦИИ НАУЧНОЙ ТЕОРИИ. ЗАКОН КАК КЛЮЧЕВОЙ ЕЕ ЭЛЕМЕНТ
  12. 2.3. Исчисление высказываний
  13. 3.1 Исчисления высказывания (ИВ).
  14. 3.4 Формальные исчисления.
  15. Тема 2. Логические исчисления
  16. 2.6. Исчисление высказываний.
  17. 3.2. Исчисление предикатов
  18. Эйнар Хауген НАПРАВЛЕНИЯ В СОВРЕМЕННОМ ЯЗЫКОЗНАНИИ
  19. ЯЗЫК ПРОГРАММИРОВАНИЯ PLANNER