Redutibilidade de 2 versões do problema de satisfação

Question

Preciso de ajuda com este problema.

.

Existem 2 versões do problema de satisfabilidade:

[1] Versão de decisão: Determine se uma fórmula arbitrária f é Satisfatório ou não

[2] Versão de pesquisa: Se uma fórmula arbitrária f é satisfável, uma atribuição de valores de verdade para variáveis na fórmula que faz f Satisfatório.Se f é insatisfatório, retorne nil.

Mostrar que [2] é reduzível para [1].

Eu tenho que provar que o algoritmo do Oracle de [1] implica o de [2] para dizer "[2] é reduzível para [1]".

Eu vejo que [2] é apenas o algoritmo do Oracle de [1], uma vez que discrimina a satisfação de uma fórmula arbitrária f.

Isso pode significar que o algoritmo do Oracle de [1] implica isso de [2]?Se pode, qual seria o motivo?

Answer 1

Qualquer algoritmo que decide que a satisfomoção de uma fórmula também pode ser usada para encontrar uma tarefa para uma fórmula satisfatória:

Embora nem todas as variáveis sejam atribuídas:

• Escolha uma variável e escolha o valor 0.

• Se a fórmula não for mais satisfável, substitua o valor com 1.