Discrete Maths, Lecture#2

These are my notes from 2nd lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture starts with Shai describing how mathematicians "reach" the proof. They start with trying to convince the other person about the new idea they've come up with and asking questions like.. do you get what I mean?... do you believe that its true? And that is how proofs begin... does it seem reasonable?.. does it seem plausible?.. do you believe in it? So basically you think and think and think, you get the idea, you check the idea, if found a hole you plug the the hole.. then check again..iterate this process and once all the holes are filled.. then you write the idea in english or in rigorous mathematical notation.

However when you need to prove something, first you should try to convince yourself that the idea you're trying to prove is indeed true by way of taking particular examples and see its true. Once you've convinced yourself and have a better understanding of the idea then you can think about the proof better.


On a high level this lecture answers following questions..
How to build electric circuits using truth table?
How to do arithmatic(addition in particular) using circuits and logic?
High level notion of NP and NP-complete problems?
Using reduction to prove if a problem is NP-complete or not?

Here are my notes...