Теория алгоритмов. Зюзысов В.М. - 30 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

MUIUUIU Правило 2
MUIIU Правило 4
Любые утверждения о свойствах этой теории являются метатеоремами.
Предлагается читателю задача: «Найдите вывод MU или докажите, что он невозможен».
Формальная система PR
Алфавит: {P, R, –}.
Выражения – элементы {P, R, –}*.
Формулы – строки (последовательности) вида xPyRz, где x, y и z – строчки, состоящие
только из тире.
Схема аксиом:
xP–Rx– является аксиомой, когда x состоит только из тире (каждое из двух вхождений x
замещает одинаковое число тире).
Правило вывода (схема):
Пусть x, y и z – строчки, состоящие только из тире
. Пусть xPyRz является теоремой. Тогда
xPy–Rz– также будет теоремой.
В системе PR используются только удлиняющие правила, т. е. количество
символов в формуле в результате применения правила вывода увеличивается.
Задачи. 1. Докажите: Формальная система, имеющая только удлиняющие правила
(и не имеющая укорачивающих правил), имеет разрешающий алгоритм.
2. Найдите разрешающий алгоритм для теорем
PR.
Прежде, чем читать дальше, попробуйте решить данные задачи.
Разрешающий алгоритм для формальных систем, имеющих только удлиняющие
правила, можно сформулировать в следующем виде.
Пусть F – проверяемая формула и M – множество всех аксиом теории.
While ∀x∈M((длина(x)≤ длина(F)) & F∉M do
Begin
Для каждой формулы x∈M выполняем следующее
:
Begin
Пусть R
x
обозначает множество всех формул, получаемых из x однократным
применением правил вывода.
Полагаем M равным (M∪R
x
)\{x}.
End
End
If F∈M then F – теорема else F – не теорема.
Выберем следующую интерпретацию системы PR (одна из возможных).
Универсум – множество целых положительных чисел. •
•
•
•
Последовательность, состоящая из n тире, интерпретируется как число n.
P интерпретируется как символ +.
R интерпретируется как символ =.
Нетрудно убедиться, что указанная
интерпретация теореме xPyRz ставит в
соответствие истинное утверждение о целых положительных числах «x+y=z» и поэтому
данная интерпретация является моделью системы PR.
Теперь мы можем использовать более простой разрешающий алгоритм для теории
PR: формула xPyRz является теоремой тогда и только тогда, когда x+y=z – истина.
В модели теоремы и
истины совпадают – то есть, между теоремами и фрагментами
реального мира существует изоморфизм.
Грубо говоря: «изоморфизм» есть преобразование, сохраняющее информацию.
Слово «изоморфизм» приложимо к тем случаям, когда две сложные структуры могут быть
отображены одна в другую таким образом, что каждой части одной структуры
соответствует какая-то часть другой структуры («соответствие» здесь
означает, что эти
части выполняют в своих структурах сходные функции).

Страницы