Propositional logic and first order logic textbook - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:58:25Z http://mathoverflow.net/feeds/question/39214 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook Propositional logic and first order logic textbook Ralf 2010-09-18T12:06:36Z 2013-03-07T19:15:07Z <p>What are in your opinion some good propositional and first order logic textbooks (undergraduate level) ? I need one that focuses mainly on the aspects of logic related to computer science. thanks in advance. </p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39223#39223 Answer by Rob Simmons for Propositional logic and first order logic textbook Rob Simmons 2010-09-18T15:59:28Z 2010-09-18T15:59:28Z <p>The question as currently stated is a little vague, but I took a course on logic and theorem proving as it relates to computer science as an undergraduate, and the textbook, Huth and Ryan's "Logic in Computer Science" (which I see now has a <a href="http://www.cs.bham.ac.uk/research/projects/lics/" rel="nofollow">second edition</a>) was a reasonable textbook.</p> <p>For a somewhat different value of "aspects of logic related to computer science," Pfenning's notes on from his <a href="http://www.cs.cmu.edu/~fp/courses/15317-f09/schedule.html" rel="nofollow">undergraduate course on Constructive Logic</a> are relatively complete and might be useful.</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39228#39228 Answer by Elmer Fud for Propositional logic and first order logic textbook Elmer Fud 2010-09-18T17:10:51Z 2010-09-18T17:10:51Z <p>Not quite a textbook, but a collection of historical projects about elementary logic and related issues in discrete mathematics and computer science can be found at www.cs.nmsu.edu/historical-projects Click on the project "Deduction Through the Ages ..."</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39238#39238 Answer by Carl Mummert for Propositional logic and first order logic textbook Carl Mummert 2010-09-18T19:14:43Z 2010-09-19T14:07:57Z <p>It depends on what you mean by "related to computer science". Undergraduate computer science "logic" books tend to focus more on computability, like</p> <ul> <li><p>Hopcroft and Ullman, <em>Introduction to Automata Theory, Languages, and Computation</em></p></li> <li><p>Papadimitriou, <em>Computational Complexity</em></p></li> </ul> <p>Undergraduate mathematical "logic" books tend to focus on propositional logic and first-order logic but not things like computational complexity. One well-regarded book of that sort is</p> <ul> <li>Enderton, <em>A Mathematical Introduction to Logic</em></li> </ul> <p>That book does prove the unique readability (parsing) algorithm for propositional and first-order formulas. </p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39244#39244 Answer by François G. Dorais for Propositional logic and first order logic textbook François G. Dorais 2010-09-18T20:43:51Z 2010-09-18T20:55:40Z <p>Though a little advanced, <em>Logic for Applications</em> by Nerode and Shore fits the bill. (<a href="http://books.google.com/books?id=OKHZnyJkb4kC&amp;printsec=frontcover&amp;dq=shore+nerode&amp;source=bl&amp;ots=HKmWA8Sa1F&amp;sig=lQppbdpbE5HmLvPwZWYCoPggROQ&amp;hl=en&amp;ei=6SKVTOWEJ8SinQf83uzjBw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CBIQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">Google books</a>) The book has an extensive treatment of propositional and first-order logic, with an emphasis on resolution as a proof method. Hilbert style systems are also discussed to some length, but natural deduction is lacking. I found that the Prolog related parts can be successfully skipped if necessary.</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39251#39251 Answer by Andrew L for Propositional logic and first order logic textbook Andrew L 2010-09-18T21:40:35Z 2010-09-18T21:40:35Z <p>My favorite introductory book on mathematical logic is Robert S.Wolfe's A TOUR THROUGH MATHEMATICAL LOGIC.Amazingly well written,it covers an extraordinary amount of material in both logic and set theory,complete with biographical vignettes and historical insights.There a deep discussion of first order logic and it's place in metamathematical systems.It also has a wonderful introductory chapter on the theory of computation and it's origins.This is the book I would recommend to any of my students if they asked me about logic. </p> <p>After that,there are several more advanced texts that I like,particularly the ones by Shoenfield and the classic by my old teacher,Elliot Mendelson.</p> <p>You can't go wrong with any of those. </p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/39443#39443 Answer by Sergei Tropanets for Propositional logic and first order logic textbook Sergei Tropanets 2010-09-20T22:34:44Z 2010-09-20T22:34:44Z <p>I don't understand what people usually mean when they say "aspects of some mathematical field related to computer science" (how they know what is really related to CS?), but if you really want to study or teach first order logic, then, in my opinion, there is old but still the best book for that -- Joseph Shoenfield's Mathematical logic.</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/66535#66535 Answer by Pablo for Propositional logic and first order logic textbook Pablo 2011-05-31T10:16:02Z 2011-05-31T10:16:02Z <p><em>A first course in logic</em> by S. Hedman (OUP) is excellent.</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/67674#67674 Answer by PA for Propositional logic and first order logic textbook PA 2011-06-13T15:55:04Z 2011-06-13T15:55:04Z <p>I'm suprised that no one has yet mentioned Boolos 'Computability and Logic'. The first 100 pages are pretty solid computability theoyr, and then follows Meta-logic, with an especially good précis on first-order logic that emphasizes the difference between a Language, an theory, and logical/non-logical symbols. Worth a gander, espeically if you're interested in CS related logic.</p> <p>Robert Sores '<em>Recursively Enumerable Sets and Degrees</em>' is another good place to start for recursion theory, as well as general logic. His approach is very clear (if a little assuming that you're following <em>everything</em> at once) and the first 120pp are very informative on recursively enumerable sets (now usually called computably enumerable). But for undergraduates, I'd go with the Boolos...</p> <p>Note of warning - Mendelson's book <em>Introduction to Mathematical Logic</em> I found confusing when starting out - this was confirmed by supervisors/colleagues.</p> <p>I hope this helps!</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/67687#67687 Answer by Brendan Cordy for Propositional logic and first order logic textbook Brendan Cordy 2011-06-13T17:49:03Z 2011-06-13T17:49:03Z <p>As a clear introduction to propositional and first order logic for the mathematically minded, I think Logic and Structure by Van Dalen is in a class of its own. The majority of the book is not particularly CS focused, but the beginnings of recursion theory are covered in the last chapter.</p> http://mathoverflow.net/questions/39214/propositional-logic-and-first-order-logic-textbook/123897#123897 Answer by Suman for Propositional logic and first order logic textbook Suman 2013-03-07T19:05:25Z 2013-03-07T19:15:07Z <p>A very clear (and free) introductory textbook is <em>A Problem Course in Mathematical Logic</em> - "a freeware mathematics text by Stefan Bilaniuk" available as pdf, ps and Latex source on <a href="http://euclid.trentu.ca/math/sb/pcml/pcml.html" rel="nofollow">http://euclid.trentu.ca/math/sb/pcml/pcml.html</a>:</p> <blockquote> <p>A Problem Course in Mathematical Logic is intended to serve as the text for an introduction to mathematical logic for undergraduates with some mathematical sophistication. It supplies definitions, statements of results, and problems, along with some explanations, examples, and hints. The idea is for the students, individually or in groups, to learn the material by solving the problems and proving the results for themselves. The book should do as the text for a course taught using the modified Moore-method.</p> <p>The material and its presentation are pretty stripped-down and it will probably be desirable for the instructor to supply further hints from time to time or to let the students consult other sources. Various concepts and and topics that are often covered in introductory mathematical logic or computability courses are given very short shrift or omitted entirely, among them normal forms, definability, and model theory.</p> <p>Parts I and II, Propositional Logic and First-Order Logic respectively, cover the basics of these topics through the Soundness, Completeness, and Compactness Theorems, plus a little on applications of the Compactness Theorem. They could be used for a one-term course on these subjects. Part III, Computability, covers the basics of computability using Turing machines and recursive functions; it could be used as the basis of a one-term course. Part IV, Incompleteness, is concerned with proving the Gödel Incompleteness Theorems.</p> </blockquote>