Just because nature has (as far as we can tell) always operated by fixed laws does not mean logic to understand them has always existed.
log·ic [ lójjik ]
1.theory of reasoning: the branch of philosophy that deals with the theory of deductive and inductive arguments and aims to distinguish good from bad reasoning
2.system or instance of reasoning: any system of, or an instance of, reasoning and inference
3.sensible argument and thought: sensible rational thought and argument rather than ideas that are influenced by emotion or whim
Logic is a process and idea, and doesn't exist outside of a mind, even if everything were still operating by fixed laws of nature.