Let's define Naturalism as the view that only nature, e.g. physical space, time, matter and energy exists. Not only does God not exist, but nothing like God exists, either. I propose that a commitment to the positive ontological status of the laws of logic refutes Naturalism.
1. The laws of logic are immutable. (Premise)
2. Nature is dynamic. (Premise)
3. Therefore, the laws of logic cannot be part of nature. (Implied by 1 and 2)
The laws of logic, if they exist at all, include the laws of non-contradiction, identity, excluded middle, modus ponens, and so forth. These are not to be confused with the laws of nature (gravity, electromagnetism, and the strong and weak atomic forces). The laws of logic are immutable. Square-circles cannot suddenly become possibilities. It can never be the case that A is ~A.
Nature, on the other hand, is dynamic (mutable). It is in a constant state of flux. Acorns have their potentialities actualized into oak trees, for example.
What this implies, according to (3), is that the laws of logic cannot be part of nature. After all, if the laws of logic were part of nature, then that would imply the laws of logic could change. Since this is impossible, it follows that the laws of logic exist independently of nature. Since Naturalism is the view that only nature exists, the existence of the laws of logic refutes Naturalism. One is either left with Platonism or theism (as a result of conceptualism).