Si A est réductibles de cartographie à B, alors le complément de A est la cartographie réductibles au complément de B

Question

Je suis étudiant pour ma dernière en théorie du calcul, et je me bats avec la bonne façon de répondre si cette affirmation est vraie de la fausse.

Par la de $ \ leq_m $, nous pouvons construire la déclaration suivante,

w $ \ in A \ ssi f (w) \ in B de la rightarrow w \ notin A \ ssi f (w) \ notin B $

est où je suis coincé, je veux dire que, puisque nous avons une telle fonction calculable $ f $, alors cela ne fera que nous donner la cartographie de A à B, s'il y en a un, sinon il ne sera pas.

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

Answer 1

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

$ A B de leq_m les moyens de $ il y a un total de calculable $ f $ S.T. pour tous $ w $,

  

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

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

  

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

Ou équivalente

  

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

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

Answer 2

$ A \ leq_m B $ $ fait pas implie w \ in A \ leftrightarrow f (w) \ in B $ seulement dans l'autre sens est vrai si $ p \ in A \ leftrightarrow f (w) \ in B $, alors $ A \ B $ leq_m mais pas reciprocaly