Пусть формулы задаются такими правилами: переменная есть формула: если f и g - формулы, то f|g|| - тоже формула. Верна ли в таком случае теорема об однозначности разбора?

Достаточно доказать, что формулы обладают свойством беспрефиксности. Делать это можно с помощью с индукции по построению. Как её проводить - вопрос для меня.

задан 6 Дек '15 23:49

10|600 символов нужно символов осталось
2

Достаточно доказать, что если слова (строки, последовательности символов) $%f_1|g_1||$% и $%f_2|g_2||$% совпали для некоторых формул $%f_i$%, $%g_i$%, то $%f_1$% совпадает с $%f_2$%, и $%g_1$% совпадает с $%g_2$%. Тогда дальнейший разбор происходит однозначно (индукция).

Понятно, что две "палочки" на конце можно убрать, и тогда получится побуквенное равенство слов $%f_1|g_1=f_2|g_2$%. Если одна из формул $%g_i$% является переменной, то и другая должна быть такой же точно переменной, то есть $%g_1=g_2$%, и далее $%f_1=f_2$%. Поэтому предположим, что обе формулы $%g_i$% строятся по второму правилу. Тогда можно положить $%g_1=h_1|k_1||$% и $%g_2=h_2|k_2||$% для некоторых формул $%h_i$%, $%k_i$%, приходя к равенству $%f_1|h_1|k_1=f_2|h_2|k_2$%.

Индукцией по длине слова, то есть по общему количеству символов, докажем для произвольного $%m$%, что из равенства вида $%\phi_1|\phi_2|...|\phi_m=\psi_1|\psi_2|...|\psi_m$% следует $%\phi_i=\psi_i$% для всех $%i$%, где $%\phi_i$% и $%\psi_i$% -- произвольные формулы.

Случай, когда $%\phi_m$% или $%\psi_m$% является переменной, разбирается аналогично тому, как это делалось выше. Если же обе формулы составлены по второму правилу, то можно положить $%\phi_m=\phi_m'|\phi_m''||$% и $%\psi_m=\psi_m'|\psi_m''||$% для некоторых формул, откуда $%\phi_1|\phi_2|...|\phi_m'|\phi_m''=\psi_1|\psi_2|...|\psi_m'|\psi_m''$%. Количество "слогов" у нас увеличилось, но суммарное количество символов уменьшилось, поэтому можно применить индукционное предположение. Легко видеть, что из него всё следует.

ссылка

отвечен 7 Дек '15 2:10

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×505
×281

задан
6 Дек '15 23:49

показан
1708 раз

обновлен
7 Дек '15 2:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru