Генераторы псевдослучайных чисел

G является PRG и принимает семя s. Является ли G'(s) = [G(s)]' (т. е. дополнение G(s)) также ПРГ?

Мое доказательство от противного: Предположим, что G' не является PRG, тогда G''(s) = [[G(s)]']' = G(s) также не является PRG, что является противоречием, поскольку наше исходное предположение состоит в том, что G является ПРОГ.

Имеет ли это доказательство смысл? Может ли кто-нибудь указать на какие-либо ошибки?

Это доказательство неверно.

Предложение «дополнение любой функции, являющейся ПРГ, является ПРГ» пытались доказать от противного. Противоположное этому утверждению не то, что «дополнение любой функции, являющейся ПРГ, не является ПРГ», которое используется в попытке доказательства для обоснования уравнения после «тогда».

Правильное обратное: «существует функция, которая является PRG, дополнение которой не является PRG», и доказательство от противного должно начинаться с этого (как это делает предлагаемое доказательство) и заключать противоречие, не делая необоснованных гипотез. Подсказка: правильное доказательство будет использовать определение «является PRG».

Метааргумент о том, что доказательство вопроса неверно (но не говорит где): используемый аргумент работает так же хорошо, если мы заменим «ГРП» на «тождество» в формулировке доказывающего предложения и придем к ложному заключению, что « дополнение любой функции, являющейся тождеством, есть тождество».

Общий совет: обычно бывает полезно написать и использовать определения, входящие в формулировку предложения, для доказательства или опровержения.