- Meeting 01 : Wed, Jul 30, 12:00 pm-12:55 pm - Raghavendra Rao
References | |
Exercises | |
Reading | |
Administrative Announcements. Organization of the course and evaluation scheme. Review of Some basic concepts in discrete mathematics: Sets, Functions, and relations.
- Meeting 02 : Fri, Aug 01, 11:00 am-11:50 am - Raghavendra Rao
References | |
Exercises | |
Reading | |
TA Introduction, Grouping. Review of some discrete mathematical concepts:
Sets, relations, Functions etc.
- Meeting 03 : Mon, Aug 04, 09:00 am-09:50 am - Jayalal Sarma
References | |
Exercises | |
Reading | |
Intel FDIV Bug, M$ Blue screens - the need for a formal set up for arguing about systems we design. The problems ultimately boils down to describing and reasoning about some sets. Quick history on propositional logic. Laws of thought. Truth Table. Tautologies, Contradictions and Contingents. Real world examples.
References: | Section 1.1 in Rosen's Textbook.
|
Exercises: | Think of a logic which might be able represent statements like "Alice knows that Bob ate the pie".
|
Reading: | |
- Meeting 04 : Tue, Aug 05, 08:00 am-08:50 am - Jayalal Sarma
References | |
Exercises | |
Reading | |
Logical Implications and Equivalences. Practical Applications. Arguments, Argument forms. Validity of an argument. Fallacious Arguments. Propositional Proofs.
References: | Section 1.5 in Rosen's Textbook.
|
- Meeting 05 : Wed, Aug 06, 12:00 pm-12:50 pm - Jayalal Sarma
References | |
Exercises | |
Reading | |
Rules of inferences. Composing valid arguments to build proofs. Resolution as a single universal rule of inference. Principle of resolution. Prolog. The limitations of propositional logic.
- Meeting 06 : Fri, Aug 08, 11:00 am-11:50 am - Jayalal Sarma
References | |
Exercises | |
Reading | |
Need of predicate logic. Quantifiers and Domains of discourse. Interaction between quantifiers between themselves propositional operators. Rules of inference in predicate logic. Example application. First and Second order Logics. Axioms + Rules of inferences. The structure of a proof.
- Meeting 07 : Mon, Aug 11, 09:00 am-09:50 am - Raghavendra Rao
References | |
Exercises | |
Reading | |
Various proof techniques: direct proof with two examples. Proof by examples:pitfalls.
References: | [KR] Section 1.6
|
- Meeting 08 : Tue, Aug 12, 08:00 am-08:50 am -
References | |
Exercises | |
Reading | |
Indirect proof with examples. Proof by contradiction. How to identify the contradiction? Examples.
References: | [KR] Section 1.6 and 1.8.
|
Reading: | Invalid proof techniques Gives a list of reasons why a proof could be invalid. |
- Meeting 09 : Wed, Aug 13, 06:00 am-06:00 am -
References | |
Exercises | |
Reading | |
More examples for proof by contradiction, Mathematical Fallacies: examples, Existence proofs: Constructive vs non-constructive proofs.
References: | [KR] Sections 1.6 and 1.8.
|
- Meeting 10 : Mon, Aug 18, 09:00 am-09:50 am -
References | |
Exercises | |
Reading | |
Introduction to set theory. Axioms of set theory, Russel's paradox. Notion of cardinality. Countable, countably infinite sets.
- Meeting 11 : Mon, Aug 18, 04:45 pm-05:35 pm -
References | |
Exercises | |
Reading | |
Set of rational numbers is a countably infinite set.
Union of countably infinite sets. Enumerability is equivalent to countability.
Compensation for Aug 15
- Meeting 12 : Tue, Aug 19, 08:00 am-08:50 am -
References | |
Exercises | |
Reading | |
Uncountability of the set of real numbers: Cantor's diagonalization argument.
- Meeting 13 : Wed, Aug 20, 12:00 pm-01:00 pm -
References | |
Exercises | |
Reading | |
Can the cardinality Natural number be equal to that of its power set? Introduction to Mathematical induction.
- Meeting 14 : Fri, Aug 22, 11:00 am-11:50 am -
References | |
Exercises | |
Reading | |
The principle of mathematical induction. Proof by induction. Strong induction. Example.
References: | Section 4.1 of [KR]
|
- Meeting 15 : Mon, Aug 25, 04:45 pm-05:35 pm -
References | |
Exercises | |
Reading | |
The well ordering axiom. An example application.
Equivalence to the principle of mathematical Induction.
- Meeting 16 : Tue, Aug 26, 08:00 am-08:50 am -
References | |
Exercises | |
Reading | |
Well ordering principle: an example of a proof using WOP. More proofs by induction: Survivor in a knife fight game.
References: | Example 12 in page 286 of [KR].
|
- Meeting 17 : Wed, Aug 27, 09:00 am-09:50 am -
References | |
Exercises | |
Reading | |
Fallacies in mathematical induction-- pitfalls in inductions proofs. Further application of diagonalization: Computability. Halting problem is not computable.