如果a映射可还原为b，则a的补体映射可简化为b的补充

Question

我正在研究我的计算理论最终，并且正在为回答这种陈述是否正确的正确方法而苦苦挣扎。

由 定义 $ leq_m $，我们可以构建以下语句，

$ w 在a iff f（w） in B rightarrow w notin a iff f（w）

这就是我卡住的地方，我想说的是，由于我们具有这样的可计算函数$ f $，因此只有一个如果有的话，它只会给我们从a到b的映射，否则它不会。

我不知道该如何正确地说，或者我什至在正确的轨道上。

Answer 1

正如戴夫（Dave）所说，它遵循一个简单的逻辑等价：$ p leftrightarrow q $与$ lnot p leftrightArrow lnot q $相同。现在，将$ p = w 在$和$ q = f（w） in B $中。

$ a leq_m b $表示所有$ w $都有一个可计算的$ f $ st，

$ w 在b $中 leftrightArrow f（w）中。

通过上面的论点，这与

$ w notin a leftrightArrow f（w） notin b $。

或等效

$ w in bar {a} leftrightArrow f（w） in bar {b} $。

因此，相同的$ f $表明$ bar {a} leq_m bar {b} $。

Answer 2

$ a leq_m b $在 leftrightArrow f（w） in b $中不隐含$ w ，只有另一种方式是true如果$ w in a leftrightArrow f（w） in b $ in b $，则$ a a a a a a leq_m b $，但不是互惠