Если А сопоставлено с уменьшенным до B, то комплемент A имеет картирование, уменьшаемое до комплемента B

Question

Я учусь на свой финал в теории вычислений, и я борюсь с правильным способом ответа, является ли это утверждение истинным для ложного.

Посредством определение $ leq_m $ мы можем построить следующее утверждение,

$ w in a iff f (w) in b rightarrow w notin a iff f (w) notin b $

Здесь я застрял, я хочу сказать, что, поскольку у нас есть такая вычислительная функция $ f $, это даст нам отображение от A до B, если она есть, иначе она не будет.

Я не знаю, как правильно выразить это, или если я даже на правильном пути.

Answer 1

Как сказал Дейв, это следует из простой логической эквивалентности: $ P LeftrightArrow Q $ - это то же самое, что $ lnot P LeftrightArrow lnot q $. Теперь положите $ p = W в $ и $ q = f (w) in b $.

$ A leq_m b $ означает

$ w in leftrightarrow f (w) in b $.

По аргументу выше, это то же самое, что и

$ 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 $ не использует $ w in leftrightarrow f (w) in b $ только наоборот, правда, если $ w in leftrightarrow f (w) in b $ then $ a leq_m b $, но не взаимная