- Meeting 01 : Mon, Jan 11, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Introduction, Course Outline, Administrative Announcements, Grading Policy.
References: | http://www.cse.iitm.ac.in/~meghana/DM16/DM16-intro.pdf
|
- Meeting 02 : Thu, Jan 14, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Introduction to Logic, propositions, compound propositions, truth table, deriving an expression using truth table, logical connectives, implication.
References: | Section 1.1 Rosen.
Lecture slides: http://www.cse.iitm.ac.in/~meghana/DM16/Intro-Logic.pdf
|
- Meeting 03 : Thu, Jan 14, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Examples and problem solving in class.
- Meeting 04 : Fri, Jan 15, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Pongal Holiday.
- Meeting 05 : Mon, Jan 18, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Conditional statements revisited, converse, inverse, contrapositive, logical equivalences, logic puzzles.
- Meeting 06 : Thu, Jan 21, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Predicates, Quantifiers, expressing statements using quantifiers, restricted domains, negation of quantifiers, equivalences between statements having quantifiers, nested quantifiers, order of quantifiers.
- Meeting 07 : Thu, Jan 21, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Examples and problem solving in class.
- Meeting 08 : Fri, Jan 22, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Argument and argument forms, rules of inference, modus ponens, modus tollens, universal versions of both, addition, simplification, hypothetical syllogism, disjunctive syllogism.
References: | Section 1.6 Rosen.
|
- Meeting 09 : Mon, Jan 25, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Non-instructional day (Shastra)
- Meeting 10 : Thu, Jan 28, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Methods of proofs, direct proofs, proof by contrapositive, contradiction, proof by cases, existence proofs. examples of each of the cases.
References: | Section 1.8 Rosen.
|
- Meeting 11 : Thu, Jan 28, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Games and forward-backward reasoning. Chess board tilings with dominoes.
Examples and problem solving in class.
References: | Section 1.8 Rosen.
|
- Meeting 12 : Fri, Jan 29, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Game of Chomp, why does the game have to have a winning strategy. Proof of existence of a winning strategy for player-1. Example of non-constructive existence proof.
References: | Section 1.8 Rosen.
|
- Meeting 13 : Mon, Feb 01, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Another example of non-constructive existential proof. Common mistakes in proofs. Contradiction and contrapositive revisited.
Can we prove every true statement? First example of a paradox.
- Meeting 14 : Thu, Feb 04, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Introduction to sets, subsets, empty set, power set, set identities, set operations.
References: | Section 2.1 Rosen.
|
- Meeting 15 : Thu, Feb 04, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Proofs by induction, examples, well-ordering property, tiling a 2^n * 2^n chess board with one cell removed using triaminoes, strong induction.
- Meeting 16 : Mon, Feb 08, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
More examples on Proof by induction. Proving inequalities, the cardinality of the power set of a finite set, tournament example.
Examples of pitfalls in proof by induction.
References: | Section 5.1 and Section 5.2 from Rosen.
|
- Meeting 17 : Thu, Feb 11, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Discussion of solutions to SE-1.
Barber's puzzle, Russell's paradox. Possible solution to include sets from a known Universe.
References: | Section 2.2 from C. L. Liu.
|
- Meeting 18 : Thu, Feb 11, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Back to sets, cartesian products, relations, functions,
one-one, onto functions. Examples.
References: | Section 2.3 from Rosen.
|
- Meeting 19 : Fri, Feb 12, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Cardinality of infinite sets, definition of countably infinite. Examples of sets which are countably infinite.
- Meeting 20 : Thu, Feb 18, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Proving that a set is countably infinite. Equivalent ways of proving countably infinite:
- Setting up a one-one onto function from Z+ to set S.
- Setting an onto function from Z+ to S.
- Setting a one-one function from S to Z+.
- Meeting 21 : Thu, Feb 18, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Cartesian Product of Z+ X Z+ is countably infinite.
Set of rationals is countably infinite.
Set of reals is uncountable -- Cantor's diagonalization.
Power set of Z+ is uncountable.
- Meeting 22 : Fri, Feb 19, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Sequences as functions. Examples of sequences, Recursively defined sequences, examples. Solving recurrences by repeated subsitution, examples.
References: | Section 2.4 Rosen.
|