Прошу совета по реализации на C/C++ следующего алгоритма! Какие есть идеи хранения и преобразования выражения? Алгоритм следующий:
# Транслятор формул ИППП в множество предложений
Разработать способ "машинного" представления (т.е. представления линейной последовательностью символов кодировки ASCII) языка "чистого" исчисления предикатов первого порядка (ИППП) (см. [1, с. 228]). "Чистым" называется ИППП, в конструировании формул которого не участвуют функциональные буквы и термы. При этом правила построения атомарных формул заимствовать из языка Пролог [3, 4].
Разработать программу, осуществляющую преобразование вводимых пользователем (на предложенном языке) формул ИППП в множество предложений.
Примечание. Такое преобразование имеет много общего с преобразованием произвольных логических формул в конъюктивную нормальную форму.
Алгоритм преобразования состоит из следующих шагов [7].
1. Исключение из исходной формулы символов импликации, для чего используется ~F|G вместо А->G (где F и G — любые формулы ИППП, ~ — знак отрицания, | — симол операции ИЛИ, ? — символ операции И).
2. Ограничение области действия отрицания только атомарными формулами, для чего используются правила деМоргана:
~F|~G вместо ~(F?G)
~F?~G вместо ~(F|G)
3. Разделение переменных — переименование их с тем, чтобы каждый квантор имел свою переменную.
4. Исключение кванторов существования введением сколемовских констант и функций. Здесь формула вида
Ey(...P(y)...) заменяется формулой ...P(a)...
А формула вида
Ax(Ey(...P(x,y)...)) заменяется формулой Ax(...P(x,f(x))...)
5. где A обозначает квантор всеобщности, E — квантор существования, a — сколемовская константа, f(x) — сколемовская функция. Вынесение кванторов всеобщности в начало формулы и их исключение из формулы.
6. Приведение формулы ("очищенной" от кванторов) в конъюктивную нормальную форму. Используется (F|G)?(F|H) вместо F|(G?H).
7. Исключение символа ? (И), в результате образуется множество дизъюнктов, называемых также предложениями.
