Si A est mappé réductible à B alors le complément de A est mappé réductible au complément de B

J'étudie pour ma finale en théorie du calcul, et je me bats avec la bonne façon de répondre si cette affirmation est vraie ou fausse.

Par la définition de nous pouvons construire l'instruction suivante,$\leq_m$

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

C'est là que je suis coincé, je veux dire que puisque nous avons une telle fonction calculable cela ne nous donnera le mappage de A à B que s'il y en a une, sinon ce ne sera pas le cas.$f$

Je ne sais pas comment formuler cela correctement, ou si je suis même sur la bonne voie.

Comme l'a dit Dave, il résulte d'une simple équivalence logique: est le même que . Maintenant mettre et .¬ p ↔ ¬ q p = w ∈ A q = f ( w ) ∈ $p \leftrightarrow q$$\lnot p \leftrightarrow \lnot q$$p= w\in A$$q = f(w) \in B$

f $A \leq_m B$ signifie qu'il existe un total calculable pour tout ,$f$$w$

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

Par l'argument ci-dessus, c'est la même chose que

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

Ou équivalent

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

Et donc, le même montre que .ˉ A ≤ m ˉ $f$$\bar{A} \leq_m \bar{B}$

w ∈ A ↔ f ( w ) ∈ B w ∈ A ↔ f ( w ) ∈ B A ≤ m$A \leq_m B$ n'implique pas seulement l'inverse est vrai si alors mais pas réciproquement$w \in A \leftrightarrow f(w) \in B$$w \in A \leftrightarrow f(w) \in B$$A \leq_m B$