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

Пример: [pic]

[pic] по теореме дедукции [pic]

3.2 Критерий выводимости в ИВ.

3.2.1 Формулировка теоремы.

[pic] - тавтология при любой интерпретации алфавита (символов переменных)

[pic]

3.2.2 Понятие интерпретации.

[pic] символ переменной [pic] [pic] переменную поставим в соответствие.

[pic], где [pic] - проекция на [pic].

[pic]

; [pic] - только символ переменных, т.к. это заглавное слово формативной последо- вательности вида:

Где: [pic]

3.2.3 Доказательство теоремы.

формальный вывод [pic]

1)

3.3 Непротиворечивость ИВ.
3.3.1 Определение.

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

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

3) [pic]ИВ противоречиво.
ИВ непротиворечиво, если оно не является противоречивым.

Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.
Док-во: (1) Если [pic], то соответствующая ей булева функция будет тождественно равна 1. [pic]

(2) Если любая формула выводима, то выводима и А, что соответствует пункту 1.
(3) Пусть [pic] и [pic] [pic] - булева функция

[pic] - противоречие.

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

Вычислимая функция от нескольких натуральных переменных [pic]
( f – может быть не всюду определенной ) f – называется вычислимой, если [pic] такая машина Тьюринга, которая её вычисляет.

[pic] - разрешимое множество, если характеристическая функция
[pic] - является вычислимой.
Множество [pic] называется перечислимым, если [pic] такая вычислимая функция
[pic]
М - разрешимо [pic] М и N M перечислимы.
М – перечислимо [pic] М – область определения некоторой вычислимой функции.
Множество всех формул F – некоторое разрешимое подмножество V.
Т – счетное множество, если [pic] его биективное отображение на V.
[pic] - обозначение счетного множества. ([pic] - алеф-нуль)

Рекомендуем скачать другие рефераты по теме: вопросы и ответы, дипломная работа по юриспруденции.



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

Поделитесь этой записью или добавьте в закладки