Jeśli A mapuje się redukowalnie do B, to dopełniacz A jest mapowalny redukowalny do dopełniacza B

11

Studiuję do finałowej teorii obliczeń i walczę z właściwym sposobem odpowiedzi na pytanie, czy to stwierdzenie jest prawdziwe w odniesieniu do fałszu.

Przez definicję z możemy skonstruować następujące oświadczenie,≤m

w∈A⟺f(w)∈B→w∉A⟺f(w)∉B

W tym miejscu utknąłem, chcę powiedzieć, że skoro mamy taką funkcję obliczalną to da nam mapowanie od A do B, jeśli istnieje, inaczej nie.f

Nie wiem, jak to poprawnie sformułować, czy nawet jestem na dobrej drodze.

complexity-theory computability reductions trigoman
źródło
To opiera się wyłącznie na logice, a mianowicie, że jest logicznie równoważne ¬ BA⟹B .¬B⟹¬A
Dave Clarke
1
Powinieneś podać kontekst i zdefiniować swój zapis ( , → , ≤ m ). Ale jeśli używasz wspólnych notacji ( ⇔ jest logiczną równoważnością, →⇔→≤m⇔→ to implikacja, a ustawienie to klasyczna logika), to komentarz Dave'a i odpowiedź Kaveha są poprawne.
Gilles „SO- przestań być zły”

Odpowiedzi:

18

Jak powiedział Dave, wynika to z prostej logicznej równoważności: jest takie samo jak ¬ p ↔ ¬ q . Teraz wstaw p = w ∈ A i q = fp↔q¬p↔¬qp=w∈A .q=f(w)∈B

oznacza, że ​​istnieje możliwość całkowitego obliczeniaA≤mB st dla wszystkich w ,fw

.w∈A↔f(w)∈B

W powyższym argumencie jest to to samo co

.w∉A↔f(w)∉B

Lub równoważnie

.w∈A¯↔f(w)∈B¯

A zatem to samo pokazuje, że ˉ A ≤ m ˉ BfA¯≤mB¯ .

Kaveh
źródło
-1

A≤mBw∈A↔f(w)∈Bw∈A↔f(w)∈BA≤mB

Garfield
źródło
A≤MBfw∈A⟺f(w)∈B