Material
Mathematics for Computer Science (MIT) by Lehman, Leighton, Meyer
Preliminary logic primer, P. Madhusudan (for CS173)
Notes on induction on natural numbers, P. Madhusudan (for CS173)
More notes on induction, Chandra Chekuri (for CS173)
Syntax and semantics of propositional logic; syntax and semantics of first order logic over multiple sorts; some equivalences
Inference in formal logic being purely syntactic; logic giving the structure of proofs; structure of direct proofs; structure of proofs using the contrapositive; structure of proofs by case analysis; structure of proofs by contradiction;
Logic in computer science; Propositional logic: evaluation under a valuation (circuit value problem; PTime complete), satisfiability (NP-complete), validity, relationship between satisfiability and validity; the advent of efficient SAT solvers; First-order logic: the validity problem, Church-Turing theorem that this problem is undecidable; undecidability of logic of numbers with addition and multiplication.