Lecture 3: More logic and quantifiers in sets
5404 views
|
2
ratings
Lesson Summary:
In this lesson, the focus shifts from logic to sets, which build upon the concepts of logic. Sets are used in computer science for various things, such as checking if a certain input is part of a set or creating data structures. The lesson covers the basics of sets, including the empty set and the universal set, as well as operations on sets such as union and intersection. A proof for the distributive law of sets is also provided.
Lesson Description:
Learn more about logic as it pertains to sets in this lesson.
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/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 2 - A problem set with some problems from this lecture
- Problem Set 2 Solutions - Solutions to the Problem Set
- Exam 1 - An exam for the current material
Questions answered by this video:
- What are sets and what do sets have to do with logic?
- What do sets have to do with Computer Science?
- What is the empty set?
- What are subsets and Venn Diagrams?
- How do you prove that two sets are equal?
- How can you prove that AuB = BuA?
- How can you tell that sets are equal using pictures and Venn Diagrams?
- Why is AuB complement equal to A complement intersect B complement?
- How do you prove that A u (B1 ^ B2 ^ B3 ... Bn) = (A u B1) ^ (A u B2) ^ ... (A u Bn) using induction?
- How can you prove that 1^2 + 2^2 + 3^2 + ... + n^2 = n(n+1)(2n+1)/6?
- What is the Set Inclusion-Exclusion Theorem?
- How do you find the cardinality of the set A u B?
- What is |A u B u C|?
- What are some tricks to counting sets?
- How can you use the 3-set inclusion-exclusion theorem to find how many numbers between 1 and 1,000 are divisible by 3 or 5 or 7?
-
Staff Review
This lesson is all about sets and how sets relate to logic that was covered in the previous two lessons. A bunch of examples are done and many sets are shown to be equal or equivalent using logic rules as well as Venn Diagram pictures. Some great proofs are done in sets. Counting and cardinality of sets is also covered in this lecture, and some really great and interesting examples are discussed, solved, and proved. This is a fun, useful lesson.
