### 2 videos in "Logic"

## Lecture 2: Boolean Algebra and Formal Logic

Lecture 2: Boolean Algebra and Formal Logic

10400 views, 2 ratings - 01:33:36

Part of video series ArsDigita Discrete Math Course

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/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

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

- 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?

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.

Helpful video. More info than the class I am taking right now.