# Lecture 2: Boolean Algebra and Formal Logic

Taught by ArsDigita
• Currently 4.0/5 Stars.
12798 views | 2 ratings
Part of video series
Lesson Summary:

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.

Lesson Description:

Learn about boolean Algebra, what it is, and how it relates to logic. Also, learn about formal logic rules.

• 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

• Currently 4.0/5 Stars.
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.
• #### JMP92

• Currently 4.0/5 Stars.