Lecture 2: Boolean Algebra and Formal Logic
In this lesson, the concept of proofs in mathematics is explored, and the process of refining a mathematical idea and turning it into a proof is discussed. The importance of having a solid, rigorous proof is emphasized, and the idea of a proof being sociological is introduced. The role of intuition in creating a proof is also discussed, as well as the importance of finding a balance between rigor and intuition. Overall, the lesson provides a valuable insight into the process of creating and refining mathematical proofs.
Learn about boolean Algebra, what it is, and how it relates to logic. Also, learn about formal logic rules.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
- Lecture Notes - Lecture Notes from the course
- Problem Set 1 - A problem set with some problems from this lecture
- Problem Set 1 Solutions - Solutions to the Problem Set
- Problem Set 2 - A problem set with some problems from this lecture
- Problem Set 2 Solutions - Solutions to the Problem Set
- How do you prove that you can get a total of 61 or higher with some combination of 7s and 11s?
- What is an example of an incorrect proof by induction where the base case is not covered?
- What is Boolean Algebra?
- What are some rules, identities, equivalences, and proofs using truth tables in logic?
- What is Disjunctive Normal Form?
- What is Conjunctive Normal Form?
- How do you change between Disjunctive and Conjunctive Normal Form?
- What is the NOR or NAND function in logic?
- How can you rewrite a logical statement by replacing all not, and, and or operators with nor or nand?
- What are binary numbers and how do you convert decimal numbers into binary?
- How do you add numbers in binary?
- What is a half adder circuit and how does it work?
- How do computer circuits work on the inside?
- What is a reduction in logic and problem solving?
- What is an NP-complete problem and what does it mean for a problem to be NP-complete?
- What is a non-deterministic polynomial algorithm?
- What is an example of a P or polynomial-time algorithm?
- What is the traveling salesman problem and why is it an NP problem?
- Why is it important to be able to show that a problem is NP-complete?
- Why is satisfiability hard and how can you show that it is hard using reduction?
- How do you show that a problem is easy using reduction?
- How does 2SAT reduce to finding strongly connected components in a graph?
-
Staff Review
This video starts with an incorrect proof to a problem by induction. The idea and philosophy behind proofs is dealt with. This leads into a very rigorous discussion on Boolean Algebra carrying through what was started in the last lecture. Circuits are explained using their binary components. Finally, hard problems, P, NP, and NP-complete problems are analyzed along with reductions of these problems. -
