如果a映射可还原为b,则a的补体映射可简化为b的补充
-
16-10-2019 - |
题
我正在研究我的计算理论最终,并且正在为回答这种陈述是否正确的正确方法而苦苦挣扎。
由 定义 $ leq_m $,我们可以构建以下语句,
$ w 在a iff f(w) in B rightarrow w notin a iff f(w)
这就是我卡住的地方,我想说的是,由于我们具有这样的可计算函数$ f $,因此只有一个如果有的话,它只会给我们从a到b的映射,否则它不会。
我不知道该如何正确地说,或者我什至在正确的轨道上。
解决方案
正如戴夫(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} $。
其他提示
$ 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 $,但不是互惠
不隶属于 cs.stackexchange