If natural language is not fully logical, how could it be possible to explain something purely logical through it?
Well, simply put, "purely logical" is a suspect term. However, let's say what you mean is a formal, that is syntactically abstract, artificial language of logic as used in formal systems. In this case, explanations of the "purely logical" things, like FOL, for instance are ONLY meaningful because they abstract something more concrete; that is, pure logic is "distilled" natural logic, which is called informal logic. It is from the natural language that the ideas of the formalisms are originally drawn, and therefore it is in the natural language and the experiences that they represent they have any meaning at all, at least according to intuitionism.
As someone who programs computers, I don't have the luxury of assuming mathematical and logical expressions are some sort of Platonic entities floating around in a "Heaven of Numbers". Logic operations and computer languages that create and use them, particularly in higher-order languages out of type theories, don't spontaneous exist. They simply have to be built. In the case of high-level languages, they come from the machine codes. In the case of machine codes, they come from the work of computer engineers and the hardware they design. Put simply, they are constructed. The AND is constructed (usually out of NAND gates on a chip). The OR. The XOR. What we know as predication in philosophy is simply a computer procedure.
So how do we describe these operations and primitives of pure logic, like variables, domains of discourse, and identity? With natural language, intuition, and metaphors. But you may protest, how can something impure characterize something pure? And here then is the crux of your dilemma. You are engaged in the fallacy of division in the very question you ask! From WP:
A fallacy of division1 is an informal fallacy that occurs when one reasons that something that is true for a whole must also be true of all or some of its parts.
So, implicit in your question is "how can something that is purely logical be explained by something that is not purely logical"? Simple, the purely logical systems to which you refer have logical parts, but those logical parts don't have to themselves be purely logical! And it's just as simple as that. Thus, we explain AND in terms of choices, and apples, and use our intuitions. The parts of anything which you might consider (like a formal system of logic) to be purely logical can have many properties that are not purely logical. To put it in a different perspective, how can one explain the flight of a plane when none of the parts by themselves are capable of flying?!? Simple. It's the combination, the structure if you will, that creates emerging properties. A formal system might be characterized as purely logical, but that pure logic (a term that is ill-defined) is nothing more than that which comes from a systems whose sum is more than its parts.