Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I am working on a project that requires me to learn about logic (specially first order and second order).
Looking for a good book or online reference that can help me with questions such as:
A. What is the difference between Logic, Language and Calculus?
B. How to define operators and their semantics?
etc.
As a beginner, it would be great to read a step by step like instructions with easy examples that helps me understand and build on.
Thanks in advance Karl
Answer to A. Barwise & Etchemendy's Language, Proof, and Logic is a decent introduction to logic. From the perspective of someone coming from a CS background I found it especially accessible and fun. It's very clearly written, has lots of examples, and comes with 3 programs:
- Tarski's World: is a block world where you can verify the truths of sentences or find counterexamples in an intuitive, visual environment
- Fitch: is a Fitch-style proof system that will check your proofs
- Boole: is a truth-table tool
Once you're done with the main course (I-II), in part III they have more fun topics to explore:
- ZFC
- program correctness
- resolution
- Skolemization
- metalogic (e.g. Lowenheim-Skolem, Compactness, Incompleteness)
As I said, B & E is an introductory course, so next you can move to what's called mathematical logic, which is more technical but more precise and will turn out to be more rewarding in the long run. A canonical text here is Enderton's A Mathematical Introduction to Logic, which even has a special chapter dedicated to Second-Order Logic (something you said you're interested in). It's not as interactive as B & E, but it's a classic and it will prepare you for more advanced logic.
Answer to B. How to give the semantics of operators should become clear after studying these texts. But if you're looking for special kinds of semantics, such as Kripke, topological, neighborhood, measure-theoretic, domain-theoretic, probabilistic, etc., you'll have to do a little digging to find papers that explain how these things are done.
Hope that addresses at least some of your questions.
