Wenn A auf B reduzierbar abgebildet wird, ist das Komplement von A auf das Komplement von B reduzierbar

Ich studiere für mein Finale in Theorie der Berechnung und ich kämpfe mit der richtigen Art zu antworten, ob diese Aussage wahr oder falsch ist.

Durch die Definition von wir die folgende Aussage konstruieren:$\leq_m$

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

Hier stecke ich fest, ich möchte sagen, dass wir, da wir eine so berechenbare Funktion dann die Zuordnung von A nach B erhalten, wenn es eine gibt, sonst nicht.$f$

Ich weiß nicht, wie ich das richtig ausdrücken soll oder ob ich überhaupt auf dem richtigen Weg bin.

Wie Dave sagte, folgt aus einer einfachen logischen Äquivalenz: ist dasselbe wie ¬ p ↔ ¬ q . Nun stellen p = w ∈ A und q = f ( w ) ∈ B .$p \leftrightarrow q$$\lnot p \leftrightarrow \lnot q$$p= w\in A$$q = f(w) \in B$

bedeutet, dass esfür alle w eine insgesamt berechenbare f stgibt.$A \leq_m B$$f$$w$

.$w \in A \leftrightarrow f(w) \in B$

Nach dem obigen Argument ist dies dasselbe wie

.$w \notin A \leftrightarrow f(w) \notin B$

Oder gleichwertig

.$w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$

Und daher sind die gleichen zeigt , dass ˉ A ≤ m ˉ B .$f$$\bar{A} \leq_m \bar{B}$

$A \leq_m B$$w \in A \leftrightarrow f(w) \in B$$w \in A \leftrightarrow f(w) \in B$$A \leq_m B$