CS6030 - Logic and Combinatorics for Computer Science

Meetings  

• Theme 1 : Describing Sets: Logic and Proofs. - 34 meetings

  • Meeting 01 : Mon, Jul 31, 10:00 am-10:50 am -

  Acad : Why this course? Choice between LCCS and LARP courses. The story and the thread the course will follow. Reference textbooks. Admin : Evaluation plans, TA and Instructor contact hours, course homepage, mailing list

  References
  Exercises
  Reading

  Acad : Why this course? Choice between LCCS and LARP courses. The story and the thread the course will follow. Reference textbooks. Admin : Evaluation plans, TA and Instructor contact hours, course homepage, mailing list
  

  References:

  None

  • Meeting 02 : Tue, Aug 01, 09:00 am-09:50 am -

  Introduction to propositional logic. Proposition, logical connectives. Logical equivalence.

  References	Chapter 1 of [RosenTextBook]
  Exercises
  Reading

  Introduction to propositional logic. Proposition, logical connectives. Logical equivalence.
  

  References:

  Chapter 1 of [RosenTextBook]

  • Meeting 03 : Wed, Aug 02, 08:00 am-08:50 am -

  Well formed formuale (contd from previous lecture). Satisfiability. Evaluation vs Satisfiability testing. Deduction; Arguments. Inference rules. Validity of inference rules.

  References	Chapter 1 from [RosenTerxtBook]
  Exercises
  Reading

  Well formed formuale (contd from previous lecture). Satisfiability. Evaluation vs Satisfiability testing. Deduction; Arguments. Inference rules. Validity of inference rules.
  

  References:

  Chapter 1 from [RosenTerxtBook]

  • Meeting 04 : Fri, Aug 04, 12:00 pm-12:50 pm -

  More on inference rules. Limitations of propositional logic. Notion of a predicate.

  References	[Rosen]
  Exercises
  Reading

  More on inference rules. Limitations of propositional logic. Notion of a predicate.
  

  References:

  [Rosen]

  • Meeting 05 : Mon, Aug 07, 10:00 am-10:50 am -

  Lecture cancelled due to unavailability of the instructor.

  References
  Exercises
  Reading

  Lecture cancelled due to unavailability of the instructor.
  

  References:

  None

  • Meeting 06 : Wed, Aug 09, 08:00 am-08:50 am -

  Introduction to predicate logic. Syntax of a well formed formula. Towards a semantics.

  References
  Exercises
  Reading

  Introduction to predicate logic. Syntax of a well formed formula. Towards a semantics.
  

  References:

  None

  • Meeting 07 : Fri, Aug 11, 12:00 pm-12:50 pm -

  Notion of a model. Relations vs predicated. Model for a w.f.f. Satisfiability.

  References	[HR] Chapter 2.
  Exercises
  Reading

  Notion of a model. Relations vs predicated. Model for a w.f.f. Satisfiability.
  

  References:

  [HR] Chapter 2.

  • Meeting 08 : Mon, Aug 14, 10:00 am-10:50 am -

  More on satisfiability. Aspects of first order predicate logic: Model Checking, Satisfiability, Validity, Expressive Power, Provability. Notion of a proof.

  References	[HR] Chapter 2 + Your class notes.
  Exercises
  Reading

  More on satisfiability. Aspects of first order predicate logic: Model Checking, Satisfiability, Validity, Expressive Power, Provability. Notion of a proof.
  

  References:

  [HR] Chapter 2 + Your class notes.

  • Meeting 09 : Tue, Aug 15, 09:00 am-09:50 am -

  No lecture. [Independence Day]

  References
  Exercises
  Reading

  No lecture. [Independence Day]
  

  References:

  None

  • Meeting 10 : Wed, Aug 16, 08:00 am-08:50 am -

  Expressive Power, Provability. Notion of a proof. Proof techniques: Direct proof.

  References	[Rosen]
  Exercises
  Reading

  Expressive Power, Provability. Notion of a proof. Proof techniques: Direct proof.
  

  References:

  [Rosen]

  • Meeting 11 : Mon, Aug 21, 10:00 am-10:50 am -

  Proof of contrapositive. Proof by contradiction. Examples.

  References	[Rosen]
  Exercises
  Reading

  Proof of contrapositive. Proof by contradiction. Examples.
  

  References:

  [Rosen]

  • Meeting 12 : Tue, Aug 22, 09:00 am-09:50 am -

  Principle of mathematical induction. Notion of countable sets. Examples of countable sets. Uncountable sets.

  References	[Rosen] and Notes by M. B. Williams (sent to the course group)
  Exercises
  Reading

  Principle of mathematical induction. Notion of countable sets. Examples of countable sets. Uncountable sets.
  

  References:

  [Rosen] and Notes by M. B. Williams (sent to the course group)

  • Meeting 13 : Wed, Aug 23, 08:00 am-08:50 am -

  The set of real numbers is uncountable.

  References	and Notes by M. B. Williams (sent to the course group)
  Exercises
  Reading

  The set of real numbers is uncountable.
  

  References:

  and Notes by M. B. Williams (sent to the course group)

  • Meeting 14 : Fri, Aug 25, 12:00 pm-12:50 pm -

  No Lecture (Ganesh Chathurthi)

  References	[Rosen]
  Exercises
  Reading

  No Lecture (Ganesh Chathurthi)
  

  References:

  [Rosen]

  • Meeting 15 : Tue, Aug 29, 09:00 am-09:50 am -

  Principle of mathematical induction. Examples.

  References	[Rosen]
  Exercises
  Reading

  Principle of mathematical induction. Examples.
  

  References:

  [Rosen]

  • Meeting 16 : Wed, Aug 30, 08:00 am-08:50 am -

  Strong induction. Examples.

  References	[Rosen]
  Exercises
  Reading

  Strong induction. Examples.
  

  References:

  [Rosen]

  • Meeting 17 : Fri, Sep 01, 12:00 pm-12:50 pm -

  Well ordering principle. Equivalence to Strong induction

  References	[Enderton]
  Exercises
  Reading

  Well ordering principle. Equivalence to Strong induction
  

  References:

  [Enderton]

  • Meeting 18 : Mon, Sep 04, 10:00 am-10:50 am -

  Logic revisited. Syntax and semantics of propositional and predicate logic. Axiomatization of propositional logic.

  References
  Exercises
  Reading

  Logic revisited. Syntax and semantics of propositional and predicate logic. Axiomatization of propositional logic.
  

  References:

  None

  • Meeting 19 : Fri, Sep 08, 12:00 pm-12:50 pm -

  Axiomatization of propositional logic. Soundness. Proof of soundness.

  References
  Exercises
  Reading

  Axiomatization of propositional logic. Soundness. Proof of soundness.
  

  References:

  None

  • Meeting 20 : Mon, Sep 11, 10:00 am-10:50 am - Jayalal Sarma

  Axiomatization of propositional logic: Properties of derivability.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Axiomatization of propositional logic: Properties of derivability.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 21 : Tue, Sep 12, 09:00 am-09:50 am -

  Proof of completeness theorem for propositional logic.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Proof of completeness theorem for propositional logic.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 22 : Wed, Sep 13, 08:00 am-08:50 am -

  Completeness them (contd). Soundness and completeness of predicate first order logic (without proof)

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Completeness them (contd). Soundness and completeness of predicate first order logic (without proof)
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 23 : Fri, Sep 15, 12:00 pm-12:50 pm -

  Peano's arithmetic and Goedel's ioncompleteness theorem (without proof). Expressibility.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Peano's arithmetic and Goedel's ioncompleteness theorem (without proof). Expressibility.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 24 : Mon, Sep 18, 10:00 am-10:50 am -

  Review: Soundness, completeness. Expressibility, some examples.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Review: Soundness, completeness. Expressibility, some examples.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 25 : Tue, Sep 19, 09:00 am-09:50 am -

  Expressive power of first order logic: more example. Bipartiteness is not expressible in FOL. Proof.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Expressive power of first order logic: more example. Bipartiteness is not expressible in FOL. Proof.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 26 : Wed, Sep 20, 08:00 am-08:50 am -

  Bipartiteness is not expressible. Compactness theorem.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Bipartiteness is not expressible. Compactness theorem.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 27 : Fri, Sep 22, 12:00 pm-12:50 pm -

  Compactness theorem using Consistency vs Satisfiability theorem. Proof sketch for Consistency vs Satisfiability.

  References	Notes written by Jayalal. Us the link shared through the google group.
  Exercises
  Reading

  Compactness theorem using Consistency vs Satisfiability theorem. Proof sketch for Consistency vs Satisfiability.
  

  References:

  Notes written by Jayalal. Us the link shared through the google group.

  • Meeting 28 : Mon, Sep 25, 10:00 am-10:50 am -

  Second order logic. An example formula. Program verification.

  References	For more details on logic of graphs check out the wikipedia page and references therein: https://en.wikipedia.org/wiki/Logic_of_graphs https://en.wikipedia.org/wiki/Hoare_logic
  Exercises
  Reading

  Second order logic. An example formula. Program verification.
  

  References:

  For more details on logic of graphs check out the wikipedia page and references therein: https://en.wikipedia.org/wiki/Logic_of_graphs https://en.wikipedia.org/wiki/Hoare_logic

  • Meeting 29 : Tue, Sep 26, 09:00 am-09:50 am -

  Linear Temporal Logic: Syntax.

  References	[HR] , i.e.,Book by Huth and Ryan, see the references section for more details.
  Exercises
  Reading

  Linear Temporal Logic: Syntax.
  

  References:

  [HR] , i.e.,Book by Huth and Ryan, see the references section for more details.

  • Meeting 30 : Wed, Sep 27, 08:00 am-08:50 am -

  Linear time temporal logic: semantics

  References	[HR]
  Exercises
  Reading

  Linear time temporal logic: semantics
  

  References:

  [HR]

  • Meeting 31 : Thu, Sep 28, 12:00 pm-12:50 pm -

  Example formulas using LTL. Expressing properties of concurrent processes, traffic signal system etc.

  References	[HR]
  Exercises
  Reading

  Example formulas using LTL. Expressing properties of concurrent processes, traffic signal system etc.
  

  References:

  [HR]

  • Meeting 32 : Wed, Oct 04, 08:00 am-08:50 am -

  Logical equivalences. Computation Tree Logic (CTL) syntax and semantics.

  References	[HR]
  Exercises
  Reading

  Logical equivalences. Computation Tree Logic (CTL) syntax and semantics.
  

  References:

  [HR]

  • Meeting 33 : Mon, Oct 09, 10:00 am-10:50 am -

  Introduction to Modal logic: syntax and semantics. Kripke structures.

  References	[HR]
  Exercises
  Reading

  Introduction to Modal logic: syntax and semantics. Kripke structures.
  

  References:

  [HR]

  • Meeting 34 : Tue, Oct 10, 09:00 am-09:50 am -

  Example formulas in modal logic.

  References	[HR]
  Exercises
  Reading

  Example formulas in modal logic.
  

  References:

  [HR]

• Theme 2 : Size of Sets: Counting and Combinatoric - 10 meetings

  • Meeting 35 : Wed, Oct 11, 08:00 am-08:50 am -

  Basic principles of counting. Review of basic counting techniques. Permutations, Combinations. Double Counting as a combinatorial proof technique.

  References	[RosenTextBook], Chapter 5.
  Exercises
  Reading

  Basic principles of counting. Review of basic counting techniques. Permutations, Combinations. Double Counting as a combinatorial proof technique.
  

  References:

  [RosenTextBook], Chapter 5.

  • Meeting 36 : Fri, Oct 13, 12:00 pm-12:50 pm -

  More double counting. Inclusion exclusion: Derangements. Counting via bijections.

  References	<a href= "http://www-bcf.usc.edu/~pengshi/math149/counting.pdf"> Slides </a> on counting by Peng Shi. For bijection <a href="http://yufeizhao.com/olympiad/bijections.pdf"> See </a> note written by Zhao. Also read [RosenTextBook] Chapter 5.
  Exercises
  Reading

  More double counting. Inclusion exclusion: Derangements. Counting via bijections.
  

  References:

  Slides on counting by Peng Shi. For bijection See note written by Zhao. Also read [RosenTextBook] Chapter 5.

  • Meeting 37 : Mon, Oct 16, 10:00 am-10:50 am -

  Counting via bijections: counting paths in a grid. Number of paths that do not cross the diagonal and stay below the diagonal. The Pigeonhole Principle. Statement.

  References	[RosenTextBook]. For bijection <a href="http://yufeizhao.com/olympiad/bijections.pdf"> See </a> note written by Zhao.
  Exercises
  Reading

  Counting via bijections: counting paths in a grid. Number of paths that do not cross the diagonal and stay below the diagonal. The Pigeonhole Principle. Statement.
  

  References:

  [RosenTextBook]. For bijection See note written by Zhao.

  • Meeting 38 : Tue, Oct 17, 09:00 am-09:50 am -

  Applications of PHP. Simple applications. Erdős–Szekeres theorem on sequences.

  References	[RosenTextBook]. For Erdős–Szekeres theorem, Proofs from THE BOOK, Martin Aigner and Gunter Ziegler, Springer.
  Exercises
  Reading

  Applications of PHP. Simple applications. Erdős–Szekeres theorem on sequences.
  

  References:

  [RosenTextBook]. For Erdős–Szekeres theorem, Proofs from THE BOOK, Martin Aigner and Gunter Ziegler, Springer.

  • Meeting 39 : Wed, Oct 18, 08:00 am-08:50 am -

  No Lecture

  References
  Exercises
  Reading

  No Lecture
  

  References:

  None

  • Meeting 40 : Fri, Oct 20, 12:00 pm-12:50 pm -

  Erdős–Szekeres theorem on sequences (contd) Further applications of PHP. Ramsey type theorems.

  References	For Erdős–Szekeres theorem, Proofs from THE BOOK, Martin Aigner and Gunter Ziegler, Springer. For Ramsey type theorem [RosenTextBook]
  Exercises
  Reading

  Erdős–Szekeres theorem on sequences (contd) Further applications of PHP. Ramsey type theorems.
  

  References:

  For Erdős–Szekeres theorem, Proofs from THE BOOK, Martin Aigner and Gunter Ziegler, Springer. For Ramsey type theorem [RosenTextBook]

  • Meeting 41 : Mon, Oct 23, 10:00 am-10:50 am -

  An application of Ramsey theorem. Recurrence relations. Solving recurrence relations. Linear homogeneous recurrences.

  References	[RosenText]
  Exercises
  Reading

  An application of Ramsey theorem. Recurrence relations. Solving recurrence relations. Linear homogeneous recurrences.
  

  References:

  [RosenText]

  • Meeting 42 : Fri, Oct 27, 12:00 pm-12:50 pm -

  Linear homogeneous recurrences distinct roots case. With repeated roots. Examples.

  References	[RosenText]
  Exercises
  Reading

  Linear homogeneous recurrences distinct roots case. With repeated roots. Examples.
  

  References:

  [RosenText]

  • Meeting 43 : Mon, Oct 30, 10:00 am-10:50 am -

  Linear non-homogeneous recurrences.

  References	[RosenText]
  Exercises
  Reading

  Linear non-homogeneous recurrences.
  

  References:

  [RosenText]

  • Meeting 44 : Tue, Oct 31, 09:00 am-09:50 am -

  Examples of recurrence relations.

  References	[RosenText]
  Exercises
  Reading

  Examples of recurrence relations.
  

  References:

  [RosenText]

• Theme 3 : Structured Sets: Algebraic and Combinatorial Structures - 6 meetings

  • Meeting 45 : Wed, Nov 01, 08:00 am-08:50 am -

  Recurrence relation (contd). Linear non-homogeneous recurrences. Examples.

  References	[RosenText]
  Exercises
  Reading

  Recurrence relation (contd). Linear non-homogeneous recurrences. Examples.
  

  References:

  [RosenText]

  • Meeting 46 : Fri, Nov 03, 12:00 pm-12:50 pm -

  Structured sets: Partially ordered sets. Definitions and properties. Dilworth's theorem (statement).

  References	[Cameron]
  Exercises
  Reading

  Structured sets: Partially ordered sets. Definitions and properties. Dilworth's theorem (statement).
  

  References:

  [Cameron]

  • Meeting 47 : Mon, Nov 06, 10:00 am-10:50 am -

  Dilworth's theorem (Proof). Applications of Dilworth's theorem.

  References	Chapter 12, Theorem 12.5.3 in [Cameron].
  Exercises
  Reading

  Dilworth's theorem (Proof). Applications of Dilworth's theorem.
  

  References:

  Chapter 12, Theorem 12.5.3 in [Cameron].

  • Meeting 48 : Tue, Nov 07, 09:00 am-09:50 am -

  Dilworth's theorem (contd) Structured sets: Groups. Definitions and examples.

  References	[RosenText]
  Exercises
  Reading

  Dilworth's theorem (contd) Structured sets: Groups. Definitions and examples.
  

  References:

  [RosenText]

  • Meeting 49 : Wed, Nov 08, 08:00 am-08:50 am -

  More on groups. Subgroups. Examples: Subgroups on Z. Groups of symmetry (automorphisms). Lagrange's theorem.

  References	[RosenText]
  Exercises
  Reading

  More on groups. Subgroups. Examples: Subgroups on Z. Groups of symmetry (automorphisms). Lagrange's theorem.
  

  References:

  [RosenText]

  • Meeting 50 : Fri, Nov 10, 12:00 pm-12:50 pm -

  More on group of symmetries. Concluding remarks.

  References
  Exercises
  Reading

  More on group of symmetries. Concluding remarks.
  

  References:

  None

• Theme 4 : Tutorials - 6 meetings

  • Meeting 51 : Tue, Aug 08, 09:00 am-09:50 am -

  Tutorial -1 .

  References
  Exercises
  Reading

  Tutorial -1 .
  

  References:

  None

  • Meeting 52 : Fri, Aug 18, 12:00 pm-12:50 pm -

  Tutorial - 2

  References
  Exercises
  Reading

  Tutorial - 2
  

  References:

  None

  • Meeting 53 : Mon, Aug 28, 10:00 am-10:50 am -

  Tutorial - 3

  References
  Exercises
  Reading

  Tutorial - 3
  

  References:

  None

  • Meeting 54 : Tue, Sep 05, 09:00 am-09:50 am -

  Tutorial 4

  References
  Exercises
  Reading

  Tutorial 4
  

  References:

  None

  • Meeting 55 : Fri, Oct 06, 12:00 pm-12:50 pm -

  Tutorial 5

  References
  Exercises
  Reading

  Tutorial 5
  

  References:

  None

  • Meeting 56 : Tue, Oct 24, 09:00 am-09:50 am -

  Tutorial 6

  References
  Exercises
  Reading

  Tutorial 6
  

  References:

  None

• Theme 5 : Evaluation Meetings - 5 meetings

  • Meeting 57 : Wed, Sep 06, 08:00 am-08:50 am -

  QUIZ - 1. Syllabus: Lectures 1 -17

  References
  Exercises
  Reading

  QUIZ - 1. Syllabus: Lectures 1 -17
  

  References:

  None

  • Meeting 58 : Sat, Oct 07, 02:00 pm-03:30 pm -

  LWE - 1

  References
  Exercises
  Reading

  LWE - 1
  

  References:

  None

  • Meeting 59 : Wed, Oct 25, 08:00 am-08:50 am -

  QUIZ - 2. Syllabus Lectures 18-41

  References
  Exercises
  Reading

  QUIZ - 2. Syllabus Lectures 18-41
  

  References:

  None

  • Meeting 60 : Thu, Nov 09, 02:00 pm-03:30 pm -

  LWE - 2. Syllabus: Lectures 33-48

  References
  Exercises
  Reading

  LWE - 2. Syllabus: Lectures 33-48
  

  References:

  None

  • Meeting 61 : Thu, Nov 16, 01:00 pm-04:00 pm -

  End Semester exam. Syllabus: Everything!!

  References
  Exercises
  Reading

  End Semester exam. Syllabus: Everything!!
  

  References:

  None