Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Discrete structures: Chapter 14 - Amer Rasheed

Chapter 14 - Introductions to Set Theory II. In this chapter, the following content will be discussed: Procedural versions, properties of sets, empty set properties, difference properties, set identities, boolean algebra and set theory, puzzles. | (CSC 102) Lecture 14 Discrete Structures Previous Lectures Summary Why study set Theory Sets Operations on sets Memberships Notations Venn diagrams Introductions to Set Theory II Today's Lecture Procedural Versions Properties of Sets Empty Set Properties Difference Properties Set Identities Boolean Algebra and Set theory Puzzles Procedural Versions of Set Definitions Let X and Y be subsets of a universal set U and suppose x and y are elements of U. 1. x ∈ X ∪ Y ⇔ x ∈ X or x ∈ Y 2. x ∈ X ∩ Y ⇔ x ∈ X and x ∈ Y 3. x ∈ X − Y ⇔ x ∈ X and x ∉ Y 4. x ∈ X ⇔ x ∉ X’ 5. (x, y) ∈ X × Y ⇔ x ∈ X and y ∈ Y Properties of Sets Theorem: 1. Inclusion of Intersection: For all sets A and B, A ∩ B ⊆ A and (b) A ∩ B ⊆ B. 2. Inclusion in Union: For all sets A and B, A ⊆ A ∪ B and (b) B ⊆ A ∪ B. 3. Transitive Property of Subsets: For all sets A, B, and C, if A ⊆ B and B ⊆ C, then A ⊆ C. Proof (For all sets A and B), A ∩ B ⊆ A. Suppose x is an element in A ∩ B and then you show that x is in A. To say that x is in A ∩ B means that x is in A and x is in B. This allows you to complete the proof by deducing that, in particular, x is in A, as was to be shown. Note that this deduction is just a special case of the valid argument form p ∧ q ∴ p. Similarly we will done with others Set Identities Let all sets referred to below be subsets of a universal set U. 1. Commutative Laws: For all sets A and B, (a) A ∪ B = B ∪ A and (b) A ∩ B = B ∩ A. 2. Associative Laws: For all sets A, B, and C, (a) (A ∪ B) ∪ C = A ∪ (B ∪ C) and (b) (A ∩ B) ∩ C = A ∩ (B ∩ C). 3. Distributive Laws: For all sets, A, B, and C, (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and Cont . (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 4. Identity Laws: For all sets A, A ∪ ∅ = A, (b) A ∩ U = A. 5. Complement Laws: (a) A ∪ A′ = U, (b) A ∩ A′ = ∅. 6. Double Complement Law: For all sets A, (A′)′ = A. 7. Idempotent Laws: For all sets A, (a) A ∪ A = A, (b) A ∩ A = A. 8. Universal Bound Laws: For all sets A, A ∪ U = U, (b) A ∩ ∅ = ∅. 9. De Morgan’s Laws: . | (CSC 102) Lecture 14 Discrete Structures Previous Lectures Summary Why study set Theory Sets Operations on sets Memberships Notations Venn diagrams Introductions to Set Theory II Today's Lecture Procedural Versions Properties of Sets Empty Set Properties Difference Properties Set Identities Boolean Algebra and Set theory Puzzles Procedural Versions of Set Definitions Let X and Y be subsets of a universal set U and suppose x and y are elements of U. 1. x ∈ X ∪ Y ⇔ x ∈ X or x ∈ Y 2. x ∈ X ∩ Y ⇔ x ∈ X and x ∈ Y 3. x ∈ X − Y ⇔ x ∈ X and x ∉ Y 4. x ∈ X ⇔ x ∉ X’ 5. (x, y) ∈ X × Y ⇔ x ∈ X and y ∈ Y Properties of Sets Theorem: 1. Inclusion of Intersection: For all sets A and B, A ∩ B ⊆ A and (b) A ∩ B ⊆ B. 2. Inclusion in Union: For all sets A and B, A ⊆ A ∪ B and (b) B ⊆ A ∪ B. 3. Transitive Property of Subsets: For all sets A, B, and C, if A ⊆ B and B ⊆ C, then A ⊆ C. Proof (For all sets A and B), A ∩ B ⊆ A. Suppose x is an element in A ∩ B and then you show that x is in A. To say that x is