Introduction to logic starting with predicate logic 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?
 A: The best really introductory textbook on FOL (first-order logic) that I have ever seen is "Language, Proof and Logic". It is really designed for beginners; it teaches not only the syntax and semantics of FOL (not as mathematical objects but truly at a beginner's level), but also teaches a complete Fitch-style deductive system for FOL. Beware of using any 'introductory texts' without checking thoroughly, as many of them that I have come across have fundamental conceptual flaws! I did not check 100% of LPL, but I didn't notice any significant issue so far.
After your target audience has learnt everything in LPL, they can easily move on to the other texts mentioned in this thread. Hannes' text, for example, starts by giving some simple structures from ordinary mathematics and explaining how we use FOL to axiomatize them.
A: In my not-at-all-humble opinion beginning logic has to do with what follows from what.  phi (a formula) follows from Sigma (a set of formulae) iff Sigma u {~phi} is inconsistent.  If you can convince your students of that, then Smullyan truth trees (applied to Sigma u {~phi}) are obviously the way to go.
The truth tables follow from the trees, but that needs the extra assumption that there are only two truth values.  Because, if phi is true in the two-valued Boolean algebra then it will be true in all Boolean algebras (with 1 read as true).  That there are only two truth values is a silly prejudice that even the ancient Greek originators of logic did not believe.
