Laws of logic are necessary truths. The least debated law is the law of non-contradiction: statements that are contradictory cannot both be true in the same way at the same time. To say that it is a necessary truth is to say that there is no possibility that it could be false. Or, in possible world parlance, there is no possible world in which the law of non-contradiction is false.
Physicalism is the view that there is no entity that is non-physical or that is not reducible to a physical entity. All physical states of affairs are contingent upon other physical states of affairs. It is possible, therefore, that everything true about what is physical could have been otherwise including the laws of physics. Consequently, on physicalism, all truths are contingent truths.
Therefore, Either the law of non-contradiction is not a necessary truth or physicalism is false.
Physicalists often accept that the laws of logic are contingent truths. They could have been otherwise. Further, they often regard laws of logic as unreal. Instead they are useful tools by which we represent experience to ourselves. Often physicalists argue that the laws of logic are language dependent constructs, they are a property of linguistic utterances or they are actually physical entities, inscriptions on the brain.
Let's take the latter claim--that the laws of logic are properties of physical entities such as brains or sentences. Here is one reason to reject this claim. A law of logic is something that is believed. Let's begin with brains. I cannot believe a set of neurons or cells any more than I can believe any other physical entity. I can believe things about physical entities. I can believe that my fridge contains tasty food, but I cannot believe my fridge. My fridge is neither true or false. The same is true for any part of my brain - it cannot be believed since none of it can be true or false. What I am believing is some proposition about some physical entity, but not the physical entity itself.
Perhaps sentences have the properties we need. It certainly sounds better to say sentence, s, is true. But this is equally problematic. When I believe that 2+2=4 I am not standing in relation to the digital inscription before me. For a start, I can believe 2+2=4 whether or not there is any sum inscription to stand in relation to. Furthermore, even if no one ever wrote 2+2=4 or uttered it, it would still be true. In fact, there are many such propositions. Te law of non-contradiction isn't identical to a sentence any more than it is a property of a brain. One might say that once one has heard the sentence one has some physical inscription written into the brain but that is to return to the brain problem in the previous paragraph.
I'm not sure how one can live with the law of non-contradiction being only contingently true, but such is the fate of the physicalist. There is nothing, on physicalism, to prevent one saying, "it is possible that P be true and false in the same way at the same time." This should, I think, be cause to reject physicalism.
See Plantinga, Warrant and Proper Function for more about propositions esp p. 117-120.