Yes, you can build a logic-based (declarative) language out of an imperative (procedural) language - and vice versa. All the basic models of computation are essentially equivalent as regards what can and cannot be computed (Church-Turing thesis). However, different programming paradigms can be better suited to different kinds of things. Imperative languages are popular because they most closely model the way the computer actually works at the hardware level, which is basically to execute a sequence of instructions that tell it to do things like store and load data to/from memory, and perform basic math operations on data.
Another programming paradigm besides imperative and logic-based is functional programming, where you define functions (like in math) that take one or more parameters and return an output value. The tricky thing is that functional programming doesn't allow you to create loops like in imperative programming, so you have to use recursion a lot to get stuff done. This sounds like it would be really cumbersome, but functional programming can actually be a really elegant way to express some algorithms.
I don't know much about the internal construction of logic-based languages, but I suspect that they are based on some kind of path-finding algorithm. Basically, you can imagine it using an analogy of a road map: all the possible statements (true and false) the system can generate are like intersections, and there are rules that enable you to deduce one statement from another, like roads connecting the intersections. Then, determining whether a statement is true or false is equivalent to determining whether there is a path from some given starting point (the database of true statements) to the statement you are interested in. If there is, the "path" you followed is a proof of the statement. This sort of path-finding problem has been studied a lot by computer scientists and there are a whole load of algorithms to deal with it.
If you are interested in knowing more about formal logical systems and how computers can be programmed to "reason" in them, a couple of good books (oriented for non-programmers) are: The Advent of the Algorithm by David Berlinski and Godel, Escher, Bach by Douglas R. Hofstadter.