Learning Objective
Learning Objectives: Rigorous mathematical reasoning based on Logic and Set Theory is the basic method of Computer Science. Moreover, Logic is a very important tool in many areas of Computer Science like Computer Architecture (Logic Gates), Software Engineering (Specification and Verification), Programming Languages (Semantics, Logic Programming), Databases (Relational Algebra and SQL), Artificial Intelligence (Automatic Theorem Proving), Algorithms (Complexity and Expressiveness), and Theory of Computation (General Notions of Computability). The first objective of this course is to introduce the students to Set Theory and Logic and train them for rigorous mathematical reasoning. The second objective is to equip them with the background needed to learn the specific topics in Logic needed for other areas of Computer Science.
Learning Outcomes
After successful completion of this course, a student will be able to
- Follow a rigorous mathematical proof and identify gaps in reasoning if any.
- Convert sentences in natural language to logical expressions and vice versa.
- Apply standard proof techniques to prove statements about simple mathematical structures like Natural Numbers and Groups.
- Prove properties of recursively defined structures using structural induction.
Syllabus:
Introduction to Logic and Proofs (12 lectures): History of logic, Role of logic in Computer Science. Logic puzzles - Wason selection task, Knights and Knaves. Propositional logic - introduction and applications. Propositional equivalences. Predicate logic - predicates, variables, quantifiers, nested quantifiers. Rules of inference - valid arguments. Proof Techniques - Direct proof, Proof by contraposition, Proof by contradiction, Proof by cases, Exhaustive proofs, Existential proofs. Examples of each.
Naive Set Theory (6 lectures): Review of elementary set theory. Computer representation of sets. Russell’s paradox. Review of functions - injections, surjections and bijections. Schröder–Bernstein theorem. Cardinality of sets, Countable and uncountable sets, Cantor’s diagonalisation argument. Infinitely many infinities.
Induction and Recursion (6 lectures): Mathematical induction, Strong induction and Well ordering principle. Proofs using them. Recursively defined objects and Structural induction.
Relations (6 lectures): Relations- properties, applications, representations. Closure of relations. Equivalence relations and Partial orders.
A Glimpse of Number theory: Modular arithmetic, Primes, GCD, the Euclidean Algorithm, Bézout’s identity. Solving congruences, the Chinese Remainder Theorem, Fermat’s little theorem. Primitive roots and Discrete logarithms. Applications to cryptography - the RSA cryptosystem.
A Formal Revisit to Logic: Relational structures and signatures. Syntax - terms, formulas and sentences. Scope of quantifiers, free and bounded occurrences of variables. Valuation and interpretation. First-order theories, models and axiomatisation.
Textbooks
- Kenneth Rosen, Discrete Mathematics and Applications, McGraw-Hill Education (7th Edition). ISBN-13: 978-0073383095
- Dexter Kozen, Theory of Computation (Chapter E.), Springer India (1 December 2007). ISBN-13: 978-8181286963
Reference
- Michael Huth and Mark Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press (2nd edition). ISBN-13: 978-0521543101
Casual Reading
- Raymond M. Smullyan, What is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles, Dover Publications. ISBN-13: 978-0486481982
- Irving M . Copi, Introduction to Logic Pearson Education (14th edition) ISBN-13: 978-9332539617\
Past Offerings
- Offered in Aug-Dec, 2022 by Deepak Rajendraprasad
- Offered in Jul-Dec, 2021 by Krithika
- Offered in Jul-Dec, 2020 by Krithika
- Offered in July-Dec, 2019 by Jasine
- Offered in July-Dec, 2018 by Deepak
Course Metadata
| Item | Details |
|---|---|
| Course Title | Logic for Computing |
| Course Code | CS2010 |
| Course Credits | 3-0-0-3 |
| Course Category | PMT |
| Proposing Faculty | Deepak Rajendraprasad |
| Approved on | Senate 6 of IIT Palakkad |
| Course prerequisites | NOT GIVEN |
| Course status | NEW |