Примитивный рекурсивный алгоритм

[PATIfon]

Здравствуйте.. Подтолкните на мысль.. Задача: являются ли две данных формулы исчисления высказываний равносильными? Является ли данная задача алгоритмически разрешимой и существует ли примитивный рекурсивный алгоритм ее решения?

[Xaositect]

Формула - это строка. Как Вы определяете примитивно рекурсивные алгоритмы на строках?

Ну а вообще можно сначала свести задачу об эквивалентности к задаче о тавтологии ($F\equiv G$ тогда и только тогда, когда $FG\vee \bar{F}\bar{G}$ - тавтология) и решать уже ее.