Математическая логика, рекурсивное определение функции f...

[vadim55]

дано рекурсивное определение функции f (высказывание прнадлежит N)
f[P]=1 (простое высказывание P)
f[~(a)]=f[(a)]+3 (для любого высказывания a)
f[(a)->(b)]=f[a]+f[b]+5 (для любых высказываний a и b )


1.что здесь определено(какую информацию несет функция f?)
обьяснить?
2.доказать с помощью индукции что для любого высказывания a
f[a] дает число которое при делении на 3 дает остаток 1

[Профессор Снэйп]

Для всех высказываний, построенных из "простых высказываний" (надо думать, этим термином автор задачи обозначает пропозициональные переменные) при помощи импликаций и отрицаний, определено значение функции $f$. То, что $f$ от любого высказывание даёт остаток $1$ при делении на $3$, доказывается элементарно, индукцией по длине высказывания.

Какую информацию несёт функция $f$? Ну, наверное можно сказать, что она как-то измеряет сложность высказывания Более точно --- она выдаёт количество символов (вместе со скобками), участвующих в записи высказывания. Длину высказывания, короче, она выдаёт.

[vadim55]

Профессор Снэйп писал(а):

Для всех высказываний, построенных из "простых высказываний" (надо думать, этим термином автор задачи обозначает пропозициональные переменные) при помощи импликаций и отрицаний, определено значение функции $f$. То, что $f$ от любого высказывание даёт остаток $1$ при делении на $3$, доказывается элементарно, индукцией по длине высказывания.

Какую информацию несёт функция $f$? Ну, наверное можно сказать, что она как-то измеряет сложность высказывания Более точно --- она выдаёт количество символов (вместе со скобками), участвующих в записи высказывания. Длину высказывания, короче, она выдаёт.

1.как доказать с помощью индукции мне совершенно не ясно.
2.Вы имеете ввиду количество символов включая скобки,символы и сами высказывания?
можно ли это как то записать(вывод к которому Вы пришли?)
буду признателен за помощь.

[Профессор Снэйп]

Индукция по длине высказывания. Высказывание --- это последовательность символов, записанная по определённым правилам. Для высказываний, состоящих из одного символа, утверждение выполняется. Пусть теперь $\Phi$ --- высказывание, состоящее из $k > 1$ символов и для всех высказываний длины $<k$ интересующие нас утверждения справедливы. Тогда либо $\Phi = \neg (\Psi)$ для некоторого высказывания $\Psi$, либо $\Phi = (\Psi) \rightarrow (\Lambda)$ для некоторых высказываний $\Psi$ и $\Lambda$. В первом случае для $\Psi$, а во втором --- для $\Psi$ и $\Lambda$ интересующие нас утверждения справедливы по индукционному предположению. Но тогда для $\Phi$ они тоже будут справедливы.

[vadim55]

Профессор Снэйп писал(а):

Для всех высказываний, построенных из "простых высказываний" (надо думать, этим термином автор задачи обозначает пропозициональные переменные) при помощи импликаций и отрицаний, определено значение функции $f$. То, что $f$ от любого высказывание даёт остаток $1$ при делении на $3$, доказывается элементарно, индукцией по длине высказывания.

Какую информацию несёт функция $f$? Ну, наверное можно сказать, что она как-то измеряет сложность высказывания Более точно --- она выдаёт количество символов (вместе со скобками), участвующих в записи высказывания. Длину высказывания, короче, она выдаёт.

я хотел бы понять как Вы по определению функции пришли к заключению о том
какую информацию она несёт ?