Trình tạo ngẫu nhiên giả

G là một PRG và nhận một hạt giống s. G'(s) = [G(s)]' (tức là phần bù của G(s)) có phải là PRG không?

Bằng chứng của tôi bằng mâu thuẫn: Giả sử G' không phải là PRG, thì G''(s) = [[G(s)]']' = G(s) cũng không phải là PRG, điều này mâu thuẫn vì giả định ban đầu của chúng ta là G là một PRG.

Liệu bằng chứng này có ý nghĩa? Bất cứ ai có thể chỉ ra bất kỳ sai lầm (s) được thực hiện?

Bằng chứng này là sai.

Nó đã cố gắng chứng minh mệnh đề "phần bù của bất kỳ chức năng nào là PRG là PRG" bằng mâu thuẫn. Điều trái ngược với mệnh đề đó không phải là "phần bù của bất kỳ hàm nào là PRG không phải là PRG", được sử dụng trong bằng chứng đã cố gắng biện minh cho phương trình sau "thì".

Điều ngược lại đúng là "tồn tại một hàm là PRG mà phần bổ sung không phải là PRG", và chứng minh bằng mâu thuẫn phải bắt đầu từ đó (như cách chứng minh được đề xuất), và kết luận mâu thuẫn, không đưa ra giả thuyết không có cơ sở. Gợi ý: một bằng chứng đúng sẽ sử dụng định nghĩa "là PRG".

Lập luận meta rằng bằng chứng của câu hỏi là sai (nhưng không cho biết ở đâu): đối số được sử dụng cũng hoạt động tốt nếu chúng ta thay đổi "PRG" thành "identity" trong tuyên bố của mệnh đề cần chứng minh và đi đến kết luận sai rằng " phần bổ sung của bất kỳ chức năng nào là bản sắc là bản sắc".

Gợi ý chung: thường hữu ích khi viết và sử dụng (các) định nghĩa liên quan đến phát biểu của một mệnh đề để chứng minh hoặc bác bỏ.