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

Объясните, пожалуйста, как можно проверить эту теорему?

задан 15 Окт 21:14

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

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

Лемма. Пусть $%\Phi_1$%, ... , $%\Phi_m$%, $%\Phi_1'$%, ... , $%\Phi_m'$% -- формулы; $%k_1,...,k_{m-1}$% -- целые неотрицательные числа. Выражение $%|^k$% означает $%k$% повторённых палочек. Если два выражения $%\Phi_1|^{k_1}\cdots|^{k_{m-1}}\Phi_m$% и $%\Phi_1'|^{k_1}\cdots|^{k_{m-1}}\Phi_m'$% графически равны, то $%\Phi_i=\Phi_i'$% для всех $%1\le i\le m$%.

Доказательство. Проводим индукцию по длине выражения, то есть по количеству используемых символов. Если $%\Phi_m$% равно переменной, то она с этой переменной совпадает. Тогда $%\Phi_m'$% этой переменной оканчивается, и тоже с ней совпадает. Сокращаем на переменную справа, а также на $%|$% в степени $%k_{m-1}$%. После чего применяем индукционное предположение. Аналогично поступаем, если $%\Phi_m'$% является переменной.

В противном случае $%\Phi_m=|\phi\psi|$% и $%\Phi_m'=|\phi'\psi'|$% для некоторых формул. Подставляем, сокращаем на палочку справа, в результате чего уменьшается длина выражения. Значение $%k_{m-1}$% увеличиваем на единицу, $%k_m$% полагаем равным нулю. Из совпадения двух более коротких выражений с новыми значениями формул и параметров, имеем $%\Phi_1=\Phi_1'$%, ... , $%\Phi_{m-1}=\Phi_{m-1}'$%, $%\phi=\phi'$%, $%\psi=\psi'$%. Отсюда следует, что $%\Phi_m=\Phi_m'$%.

Лемма доказана.

Однозначность теперь следует из того, что если две формулы не являются переменными, и $%|\phi\psi|=|\phi'\psi'|$%, то выражения $%\phi\psi$% и $%\phi'\psi'$% равны графически, что является частным случаем леммы при $%m=2$%, $%k_1=0$%, откуда члены формулы $%\phi$% и $%\psi$% однозначно восстанавливаются, что и означает однозначность разбора.

ссылка

отвечен 16 Окт 2:42

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

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

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

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

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

отмечен:

×911

задан
15 Окт 21:14

показан
43 раза

обновлен
16 Окт 2:42

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

по почте:

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

по RSS:

Ответы

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

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