Создание приведенности 2 версий проблемы удовлетворенности

Question

Мне нужна помощь с этой проблемой.

Есть 2 версии проблемы удовлетворенности:

[1] Версия решения: определить, является ли произвольная формула F Удовлетворный или нет

[2] Версия поиска: если произвольная формула F является удовлетворенной, вернуть назначение значений истинности для переменных в формуле, которая делает F Удовлетворный.Если f неудовлетворен, верните нуль.

Покажите, что [2] - это резьба применимо до [1].

Я должен доказать, что алгоритм Oracle из [1] влечет за собой [2], чтобы сказать «[2] - это сокращается в [1]».

Я вижу, что [2] - это просто алгоритм Oracle [1], поскольку оно дискриминирует удовлетворение произвольной формулы F.

Может ли это означать алгоритм Oracle [1], влечет за собой [2]?Если может, то, что было бы причиной?

Answer 1

Любой алгоритм, который решает удовлетворительность формулы, также может использоваться для поиска задания для удовлетворяющей формулы:

Пока не все переменные назначены:

.

• Выберите переменную и выберите значение 0.

• Если формула больше не удовлетворяемая, замените значение с 1.