Forget about the "natural" thing for a second. Let's look at your sentences again:
All matter attracts all other matter;
¬(φ ∧ ¬φ).
The first is a physical principle and it does seem to be true of our universe, so we may go ahead and call it "natural". The second is a logical principle, which, having nothing to do with our universe is trivially going to be true of it. (2) may be applied to states of affairs in our universe, but that simply means that (2) has an application in the real world, not that it is about the natural world (not uncontroversial; cf. Pincock's The Applicability of Mathematics).
Their difference, following Carnap, I would characterize as follows.
Definition 1. A sentence φ is a physical law iff the interpretation of the physical constants occurring in φ makes φ true.
Definition 2. A sentence φ is a logical law iff the interpretation of the logical constants occurring in φ makes φ true.
An interpretation of the physical constants is a model that satisfies the laws of physics. An interpretation of the logical constants is a model that satisfies the axioms of logic. The assumption is that there is a standard interpretation for these constants (you may disagree; cf. MacFarlane's Logical Constants). That's the motivation behind the definitions. Let's apply Definition (2) to your sentence (2):
Claim. ¬(φ ∧ ¬φ) is a logical law, i.e., when '¬' and '∧' are interpreted, ¬(φ ∧ ¬φ) becomes true.
Proof. Consider the standard truth-tables f¬ (unary) and f∧ (binary) for '¬' and '∧' respectively. Truth-table f¬ maps its single argument to True if it's False and to False if it's True. Truth-table f∧ maps its two arguments to True if they're both True; otherwise it returns False. We can evaluate the claim by evaluating the truth-value of f¬(φ ∧ ¬φ) ≡ f¬(f∧(φ, ¬φ)) ≡ f¬(f∧(φ, f¬(φ))). Now, whatever φ is, φ and f¬(φ) are going to have different truth-values, so f∧(φ, f¬(φ)) ≡ ⊥. All that remains to check is the truth-value of f¬(⊥), which is obviously ⊤.
This shows that (2) is true solely by virtue of the interpretation of the logical constants and is thus, by Definition (2) a logical law. I'm confident that the physical truth of (1), if indeed it is a physical law, can be proved solely on the basis of the interpretation of the physical constants that occur in its definition.
This, of course, is only one way of looking at things. For a general background, I recommend following Mauro's suggestions in the comments above. It's important to become aware that there are disagreements among respected philosophical logicians about what exactly logical constants and logical principles are. There are also different ways of looking at the physical/logical distinction, and any good metaphysics or philosophy of science compilation will contain relevant standard texts on that.