The typical introduction to logic starts with propositional logic and later goes over to predicate logic, in the order syntax -- semantics -- possibly some calculus. My experience is that this is perceived as a huge skew in the learning curve; beginners tend to think that logic is just boring play with truth tables until suddenly there's predicate logic and everything stops to make sense entirely.
This got me curious as to how one might go about introducing logic by starting directly, but softly with predicate logic, then later treating propositional logic as a specialization. I imagine that, presupposing some elementary set theory (just the basics of what is a set, tuple etc.), one could come from some first idea of a structure and stepwise introduce formulas as a way to express what is going on in that structure, instead of starting with the inductive definition of a formal language and then building a semantics "on top" of it, in the hope that this may get the reader a better first intuition of what the semantics of predicate logic is about.
What I'm looking for is a textbook not too heavily aimed at proofs or mathematical logic/model theory, but a more generally/practically oriented introduction to the syntax and semantics of FOL that will simply put the reader in a position to make sense of and come up with simple predicate logic formulas, and get the idea of validity of an inference, but supported by rigorous definitions and not only informal descriptions.
(I figured there would be more folks here having an overview of the literature than over at Philosophy SE; feel free to migrate if you think it is a better fit there.)
So: Do you know of any good textbooks providing a general introduction to logic starting with predicate logic, perhaps (but not necessarily) introducing the concept of a structure very early on?