Логика - доступно для всех

Онлайн школа английского языка нового поколения. Более 7 лет предоставляет обучение английскому языку по Skype (Скайп) и является лидером данного направления! Основные преимущества:

• Вводный урок бесплатно;
• Большое число опытных преподавателей (нейтивов и русскоязычных);
• Курсы НЕ на определенный срок (месяц, полгода, год), а на конкретное количество занятий (5, 10, 20, 50);
• Более 10 000 довольных клиентов.
• Стоимость одного занятия с русскоязычным преподавателем - от 600 рублей, с носителем языка - от 1500 рублей

Узнать детали

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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