Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

(3) Пусть и - булева функция

- противоречие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

Рекомендуем скачать другие рефераты по теме: изложение 3, пушкин реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата