Reduzierbarkeit von 2 booleschen Befriedigungsproblemen

Question

Ich bitte um Hilfe bei diesem Problem.

Es gibt 2 boolesche Befriedigungsprobleme.

problem $ A $ : Bestimmen, ob eine beliebige Formel der Größe $ n $ $ erfüllt $ .
Problem $ B $ : Bestimmen, ob eine beliebige Formel der Größe $ n-1 $ $ erfüllt $ in welcher $ n $ ist eine positive Integer $ \ ge 2 $

Beweisen Sie, dass $ A $ lösbar sein kann, wenn $ B $ lösbar ist.

Ich denke, die Lösung würde zeigen, dass $ A $ Turning-reduzierbar auf $ B $ . Es bedeutet, dass ich den Oracle-Algorithmus von $ B $ anzeigen muss, der den Oracle-Algorithmus von $ A $ ableitet.

Wie Sie sehen, ist die beliebige Formel von $ B $ $ n-1 $ , aber Das von $ A $ ist $ n $ . Wie kann ich angenommen werden, dass der Oracle-Algorithmus über $ A $ aus dem Oracle von $ B $ B $ , was Bestimmt die Formel von 1-geringerer Größe als der von $ B $ ?

Answer 1

Problem A ist bei Problem B auf die folgende Weise reduzierbar:

.
• Wählen Sie eine Variable in problemat ein und setzen Sie sie auf 0
• Jetzt haben wir eine Formel der Größe N-1, wenn sie mit B zufriedenstellend ist, dann erfüllen Sie die Zufriedenheit
Wählen Sie ansonsten erneut ein Problem ein und setzen Sie die Variable auf 1
• Jetzt haben wir wieder eine Formel der Größe N-1, wenn sie mit B zufriedenstellend ist, dann ermessen Sie die Zufriedenheit, die sonst zurückgegeben werden sollen, um unzufrieden zu werden

Mit anderen Worten: Teilen Sie das Problem A in zwei Probleme B mit einer beliebigen Variablen.Wenn B für 0 und 1 unbefriedigbar sagt, ist es nicht zufriedenstellbar.Wenn es für mindestens einen der beiden befriedigend ist, ist es befriedigt.