Discrete Mathematics Sets - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Discrete Mathematics Sets. Доклад-сообщение содержит 71 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Discrete Mathematics Sets Adil M. Khan Professor of Computer Science Innopolis University “Drama is imagination limited by logic. Mathematics is logic limited by imagination!” - Nathan Campbell -

Слайд 2

Описание слайда:

Set Theory A set is collection of things: Set of Numbers Set of Clothes Set of Nodes in a network Set of other sets This simple definition is enough to prove “Cantor’s Theorem”– Limit of what problems a computer can solve.

Слайд 3

Описание слайда:

Set Theory George Cantor: First to realize the potential usefulness of investigating properties of sets. Many scientists of his time resisted accepting the validity of his work. Now, abstract set theory is regarded as the foundation of mathematical thought.

Слайд 4

Описание слайда:

Set Theory: Definitions What is a Set ? “A set is an unordered collection of distinct elements”. What does it mean?

Слайд 5

Описание слайда:

Set Theory: Definitions An element is something contained within a set {1, 2, 3}--1, 2, and 3 are the elements of the above set. Notice the curly brackets {1, 2, 3} and {3, 2, 1} are they two different sets? What about {1}, and {1, 1, 1, 1}? Notes: let S denote a set and a an element of S. Then, a ∈ S means that a is an element of S, a S means that a is not an element of S

Слайд 6

Описание слайда:

Set Theory: Definitions There is no requirement that all the elements of a set of be the same type. S = {{1, 2}, {2, 3}, 4} Does 1 ∈ S? Does {1, 2} ∈ S?

Слайд 7

Описание слайда:

A Special Set The Empty set: An empty set is a set that does not contain any elements One way to represent the empty set is as { } However, in practice Ø is used. Remember, for any object x the statement x ∈ Ø is always false. Notes: It's possible to build sets that contain the empty set – {Ø}

Слайд 8

Описание слайда:

Operations on Sets Questions that are normally asked about collection of things: What do the collections have in common? What do they have collectively? What does one collection have that the other does not? Try to think about examples from your own real-life where you might have asked one or more of these questions?

Слайд 9

Описание слайда:

Set Intersection The intersection of two sets A and B, denoted A ∩ B, is the set of elements contained in both A and B.

Слайд 10

Описание слайда:

Set Union The union of two sets A and B, denoted A ∪ B, is the set of all elements contained in either of the two sets. Union can be applied to only sets: {1, 2, 3} ∪ 4 vs. {1, 2, 3} ∪ {4} Same is true of intersection. Notes: Given two sets, we can find what they have in common by finding their intersection and can find what they have collectively by using the union. But both of these operations are symmetric; it doesn't really matter what order the sets are in, since A∪B = B∪A and A ∩ B = B ∩ A.

Слайд 11

$Set Difference The set difference of B and A, denoted B – A or B \ A, is the set of elements contained in B but not contained in A. Set difference is...$

Описание слайда:

Set Difference The set difference of B and A, denoted B – A or B \ A, is the set of elements contained in B but not contained in A. Set difference is not symmetric {3, 4, 5} – {1, 2, 3} vs. {1, 2, 3} – {3, 4, 5}

Слайд 12

Описание слайда:

Set Symmetric Difference The set symmetric difference of two sets A and B, denoted A Δ B, is the set of elements that are contained in exactly one of A or B, but not both. For example, {1, 2, 3} Δ {3, 4, 5} = {1, 2, 4, 5}

Слайд 13

Описание слайда:

Special Sets Collection of things too big to be expressed by listing all of their elements. Set of all integers Set of all possible English sentences Can we get gather them together into a set? If so, how do we describe such as set?

Слайд 14

Описание слайда:

Set of All Integers Let’s begin by: {..., -2, -1, 0, 1, 2, ... } Is this description for the set of all integers mathematically rigorous? When dealing with mathematics, it is important to be precise with notations: no ambiguity! That’s why, mathematicians have invented special symbols to denote special sets. For example: The set of all integers is denoted Z. Intuitively, it is the set {..., -2, -1, 0, 1, 2, ...}

Слайд 15

Описание слайда:

Other Special Sets The set of all natural numbers, denoted N, is the set N = {0, 1, 2, 3, ...} The set of positive natural numbers N+ is the set N+ = {1, 2, 3, ...} The set of all real numbers is denoted R. A finite set is a set containing only finitely many elements. An infinite set is a set containing infinitely many elements. Notes: Some mathematicians treat 0 as a natural number, while others do not.

Слайд 16

Описание слайда:

Set Builder Notation So far, we have seen just the primitive set operations. Intersection, Union, Difference Used to create new sets by combining existing sets. However, mostly we create sets by putting together elements that share some property Set of all even numbers Set of all golden watches This is where set builder notation comes in action.

Слайд 17

Описание слайда:

Set Builder Notation {variable | condition on that variable} {n | n ∈ N and n is even} – the set of even natural numbers {x | x ∈ R and x > 0} – the set of positive real numbers {w | w is a golden watch} – the set of golden watches

Слайд 18

Описание слайда:

Predicate To formalize the definition of “set builder notation”, we will use the “predicate” A predicate is a statement about some object x that is either true or false. Given this definition, the set builder notation can be formally defined as: “The set { x | P(x) } is the set of all x such that P(x) is true.” Notes: It turns out that allowing us to define sets this way can, in some cases, leads to paradoxical sets, sets that cannot possibly exist. We'll discuss this later on when we talk about Russell's Paradox.

Слайд 19

Описание слайда:

Transforming Sets Vs.

Слайд 20

Описание слайда:

Relations on Sets Set Equality: If A and B are sets, then A = B precisely when they have the same elements as one another. This definition is sometimes called the axiom of extensionality. {1, 2, 3} = {2, 3, 1} = {3, 1, 2} N = { x | x ∈ Z and x ≥ 0 } Notes: It is important to note that the manner in which two sets are described has absolutely no bearing on whether or not they are equal; all that matters is what the two sets contain. In other words, it's not what's on the outside (the description of the sets) that counts; it's what's on the inside (what those sets actually contain)

Слайд 21

Описание слайда:

Relations on Sets Subset: A set A is a subset of another set B if every element of A is also contained in B. In other words, A is a subset of B precisely if every time x ∈ A, then x ∈ B is true. If A is a subset of B, we write A⊆B. Superset: If A⊆B, then we say that B is a superset of A. We denote this by writing B ⊇ A.

Слайд 22

Описание слайда:

Relations on Sets Strict Subset and Superset: A set A is a strict subset of B if A⊆B and AB. we denote this by writing A ⊂ B. Consequently, B is the strict superset of A -- .

Слайд 23

Описание слайда:

Set Equality Revisited So you now know what does it mean for a set A to be a subset of set B, You can use this to formally define set equality as Given sets A and B, A equals B, written A=B, iff, every element of A is in B and every element of B is in A.

Слайд 24

Описание слайда:

Set Equality Revisited Example: Define sets A and B as follows, Is A=B?

Слайд 25

Описание слайда:

Set Equality Revisited Example: Define sets A and B as follows, Is A=B? Solution: To prove this, both subset relations must be proved.

Слайд 26

Описание слайда:

Set Equality Revisited Example: Define sets A and B as follows, Is A=B? Solution: To prove this, both subset relations must be proved. Part 1: Proof that

Слайд 27

Описание слайда:

Слайд 28

Описание слайда:

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

Set Equality Revisited Example: Define sets A and B as follows, Is A=B? Solution: To prove this, both subset relations must be proved. Part 1: Proof that Suppose x is a particular but arbitrarily chosen element of A. We must show that by definition of B, this means we must show that x = 2 (some integer)-2. By definition of A, x = 2a. Let b be an integer such that b = a+1 Of course, b is an integer because it is a sum of integers.

Слайд 31

Описание слайда:

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Subset Relations Inclusion of Intersection: Inclusion in Union: For all sets A and B: Transitive Property of Subsets: For all sets A, B and C, if

Слайд 35

Описание слайда:

Subset Relations Proof of a Subset Relation: For all sets A and B, Proof: Suppose that A and B are any sets. To prove , we must show that,

Слайд 36

Описание слайда:

Subset Relations Proof of a Subset Relation: For all sets A and B, Proof: Suppose that A and B are any sets. To prove , we must show that, This is a universal statement. So to prove it, suppose any

Слайд 37

Описание слайда:

Subset Relations Proof of a Subset Relation: For all sets A and B, Proof: Suppose that A and B are any sets. To prove , we must show that, This is a universal statement. So to prove it, suppose any is in A and is in B,

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

Relations on Sets Given any set S, is Ø a subset of S? To answer this question, ask yourself what does it mean for set A to be a subset of B. Is Ø a subset of S? So for a set A to be a subset of B, “Every element of A is also contained in B” So for Ø to be a subset of S, “Every element of Ø must also be contained in S” Now tell me, is Ø ⊆S?

Слайд 40

Описание слайда:

Two Possibilities Since Ø contains no elements, the claim “every element of Ø is an element of S” is false, because we can't find a single example of an element of Ø that is contained in S. Since Ø contains no elements, the claim “every element of Ø is an element of S” is true, because we can't find a single example of an element of Ø that isn't contained in S. What do you think, which is correct?

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

The Vacuous Truth A statement is vacuously true, if it is true simply because it does not assert anything. “A statement which is true but completely void of meaning” For example: Whenever there are cows on the moon, I can fly What do you think, can I fly?  -- even though I wish I could So, the statement “I can fly” is certainly false!

Слайд 43

Описание слайда:

The Vacuous Truth However, our reference statement – “Whenever there are cows on the moon, I can fly” Says that, it happens to be true that I can fly provided that there are cows on the moon. Of course there are no cows on the moon, and of course I cannot fly. But the presence of cows on the moon has coincided perfectly with the instances of me being able to fly. Thus the statement is True!

Слайд 44

Описание слайда:

Examples Vacuous Truth If I am a dinosaur, then the moon is on fire. If 1 = 0, then 3 = 5. Notes: They are called vacuously true because although they're considered true statements, they're meaningless true statements that don't actually provide any new information or insights. More formally, The statement “if P, then Q” is vacuously true if P is always false.

Слайд 45

Описание слайда:

An Old Case “Are all unicorns pink?” Would you say “yes” or “no”? Notes: There is no unicorn, so how can we say whether they are pink or not. To answer this, let’s rewrite the statement in “if, then” form “If x is a unicorn, then x is pink” Not what do you think? “True” or “False”?

Слайд 46

Описание слайда:

An Old Case Thus, since “x is a unicorn” is never true, the statement “if x is a unicorn, then x is pink” is true! More generally, The statement “Every X has property Y” is (vacuously) true if there are no X's

Слайд 47

Описание слайда:

Back to Is Ø a subset of S? Now, tell me if this statement is true or false? “every element of Ø is an element of S”

Слайд 48

Описание слайда:

Back to Is Ø a subset of S? Now, tell me if this statement is true or false? “every element of Ø is an element of S” Thus, For any set S, Ø ⊆ S.

Слайд 49

Описание слайда:

Uniqueness of Empty Set Corollary: Uniqueness of the Empty set. There is only one set with no elements. Proof: Suppose E1 and E2 are both sets with no elements. Then we know that if E is a set with no elements and A is any set then E ⊆ A. Therefore, E1 ⊆ E2. Since E1 has no elements. Also E2 ⊆ E1. Since E2 has no elements. Thus E1 = E2 by definition of set equality.

Слайд 50

Описание слайда:

Proving that a Set is Empty Example: Prove that for any set A, Ø.

Слайд 51

Описание слайда:

Proving that a Set is Empty Example: Prove that for any set A, Ø. Solution: Let A be a particular but arbitrarily chosen set. To show that Ø, it suffices to show that has no elements.

Слайд 52

Описание слайда:

Proving that a Set is Empty Example: Prove that for any set A, Ø. Solution: Let A be a particular but arbitrarily chosen set. To show that Ø, it suffices to show that has no elements. Suppose there is an element x such that . Then by definition of intersection, and .

Слайд 53

Описание слайда:

Слайд 54

Описание слайда:

Слайд 55

Описание слайда:

The Power Set Given any set S, there are sets that are subsets of S. There is one that we already know, which set is that? The power set of a set S, denoted ℘(S), is the set of all subsets of S Example 1: Subsets of set {1, 2, 3} are Eight subsets in total

Слайд 56

Описание слайда:

The Power Set: Example 2 Example: Subsets of set {1, 2, 3,4} are Sixteen subsets in total. In some cases, there are infinitely many subsets. For example, think about the power set of the set N

Слайд 57

Описание слайда:

Set Cardinality A way to compare the relative sizes of different sets. The cardinality of a set is a measure of size of the set. We denote the cardinality of set A as |A| For Example: Note: the cardinality of a finite set is always an integer value or a natural number. What about the cardinality of infinite set?

Слайд 58

Описание слайда:

Cardinality of a Power Set of a Set Theorem: For all integers , if a set X has n elements, then has 2n elements. Proof by Mathematical Induction: “wait until we learn what is mathematical induction and how to use it”

Слайд 59

Описание слайда:

Algebraic Proofs using Set Identities Example 1: Deriving a set difference property: Construct an algebraic proof that for all sets A , B and C,

Слайд 60

Описание слайда:

Слайд 61

Описание слайда:

Algebraic Proofs using Set Identities Example 1: Deriving a set difference property: Construct an algebraic proof that for all sets A , B and C, Solution: Let A,B and C by any sets, then By the set difference law By the commutative law for

Слайд 62

Описание слайда:

Слайд 63

Описание слайда:

Слайд 64

Описание слайда:

Слайд 65

Описание слайда:

Algebraic Proofs using Set Identities Example 2: Deriving a set identity using properties of : Construct an algebraic proof that for all sets A and B, Solution: Suppose A and B are any two sets. Then By the set difference law By De Morgan’s law By the distributive law By the complement law By the set Identity/Difference law

Слайд 66

Описание слайда:

Disproving by Counter Example When, the optimistic approach of proving a universal statement about sets isn’t helping you You can take the pessimistic approach of disproving the statement by finding a counter example

Слайд 67

Описание слайда:

Disproving by Counter Example Is (A - B) (B - C) A- C ? Solution: Let A={1, 2, 4, 5}, B={2, 3, 5, 6} and C={4, 5, 6, 7}. Then A – B = {1, 4}, B – C = {2, 3}, and A – C = {1, 2}. Hence (A - B) (B - C)= {1, 4} {2, 3} = {1, 2, 3, 4}, Whereas A – C ={1, 2}. Since {1,2,3,4} {1,2}, we have that (A - B) (B - C) A- C.

Слайд 68

Описание слайда:

Computer Representation of Sets Many ways: For example: Storing the elements of a set in an unordered fashion; However, set operations would be time consuming An alternative method that makes computing combinations of set easy

Слайд 69

Описание слайда:

Representing Sets Using Bit Strings Let U be a finite universal set not larger than the available memory in a computer First, specify an arbitrary ordering of the elements of U, for instance a1, a2, . . . , an. Represent a subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A and is 0 if ai does not belong to A.

Слайд 70

Описание слайда:

Representing Sets Using Bit Strings Let U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is, ai = i. (a):What bit strings represent the subset of all odd integers in U, (b): The subset of all even integers in U, and (c): The subset of integers not exceeding 5 in U? (a): 10 1010 1010 (b): 01 0101 0101 (c): 11 1110 0000

Слайд 71

Описание слайда:

Advantages: Representing Sets Using Bit Strings Using bit strings to represent sets, it is easy to find complements of sets and unions, inter- sections, and differences of sets. For Example: To find the bit string for the complement of a set from the bit string for that set: We simply change each 1 to a 0 and each 0 to 1, Notes: For more, please see Examples 19 and 20, Ch: 2, Rosen, P: 135.