Jak udowodnić różnicę symetryczną zbiorów? kajka: Jak udowodnić różnicę symetryczną zbiorów? A + B = (A ∪ B) − (A ∩ B)

Jack: najpierw zawieranie się w lewą stronę, potem w prawą .... nie udaje się tak?

kajka: Nic się nie udaje. Nie wiem od czego zacząć. I w jaki sposób udowadniać to

ICSP: Uzyj funkcji charakterystycznej zbiorów.

kajka: Można jaśniej?

Jack: czekaj... przecież to jest definicja różnicy sym. Co chcesz dowodzić − definicję?

Godzio: Definicja różnicy symetrycznej to chyba taka jest: x ∊ (A + B) ⇔ [ ( x∊(A\B) ) ∨ ( x∊(B\A) ) ] Przynajmniej ja taką miałem, pewnie zaczynając od tego ma się dojść do tamtego, co jest raczej banalne ...

Jack: No właśnie − zależy co się przyjmie za def. Jeśli jest tak, jak pisze Godzio, trzeba wykazać równoważność prawych stron, co nie powinno być trudne.

kajka: Właśnie nie wiem co tutaj trzeba dowodzić. Mógłbyś powiedzieć, które z tych numerów trzeba udowodnić? Mam: 1. Suma zbiorów: x ε A ∪ B ⇔ [(x ε A) ∨ (x ε B)] 2. Iloczyn zbiorów: (x ε A ∩ B) ⇔ [(x ε A) ∧ (x ε B)] 3. Różnica zbiorów: (x ε A − B) ⇔ [(x ε A) ∧ (x ∉ B)] 4. Różnica symetryczna zbioru: a) A + B = (A ∪ B) − (A ∩ B) b) A + B = (A − B) ∨ (B − A) 5. Twierdzenie. Własności zawierania się zbiorów. a) ∅ ⊆ A b) A ⊆ A c) [(A ⊆ B) ∧ (B ⊆ C)] ⇔ (A ⊆ C) 6. Twierdzenie. Własności sumy zbiorów. a) A ∪ B = B ∪ A b) A (B ∪ C) = (A ∪ B) ∪ C c) ∅ ∪ A = A d) A ∪ A = A 7. Twierdzenie. Zależności. a) A ⊆ A ∪ B b) B ⊆ A ∪ B c) [(A ⊆ B) ∧ (C ⊆ D) ⇒ (A ∪ C) ⊆ (B ∪ D) d) [(A ⊆ C) ∧ (B ⊆ C) ⇒ (A ∪ B) ⊆ C 8.Twierdzenie. Własności iloczynu zbioru. a) A ∩ B = B ∩ A b) A ∩ (B ∩ C) = (A ∩ B) ∩ C c) ∅ ∩ A = ∅ d) A ∩ A = A 9. Twierdzenie a) A ∩ B ⊆ A b) A ∩ B ⊆ B c) (A ⊆ B) ∧ (C ⊆ D) ⇒ (A ∩ C) ⊆ (B ∩ D) d) [(A ⊆ B) ∧ (A ⊆ C)] ⇒ (A ⊆ B ∩ C) 10. Twierdzenie a) A ∩ (B ∪ C) = (A ∩ B) ∨ (A ∩ C) b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) c) (def.) (x ε A − B) ⇔ (x ε A) ∧ (x ∉ B) 11. Prawa de Morgana dla różnicy zbiorów a) A − (B ∪ C) = (A − B) ∩ (A − C) b) A − (B ∩ C) = (A − B) ∪ (A − C) 12. Dopełnienie zbiorów: A' = X −A 13. Różnica symetryczna zbiorów a) A + B = (A ∪ B) − (A ∩ B) b) A + B = (A − B) ∨ (B −A) 14. Twierdzenie a) A + B = B + A b) A + (B + C) = (A + B) + C c) A ∩ (B + C) = (A ∩ B) + (A ∩ C) d) A + ∅ = A e) A + A = ∅

Jack: udowodnić można wszystko bez 1,2,3 i 4=13 − bo to definicje. Ewentualnie można dowieźć równoważności definicji 4 i 13.

Jack: dowieść

Gustlik: Wygląda to tak, jak na rysunku, dwa zbiory z "pustą" częscią wspólną.

kajka: Może być tak? Co z 5c? 5a) (A ⊆ B) ⇔ ∀ [(x ε A) ⇒ (A ε B)] (∅ ε A) ⇔ ∀ [(x ε ∅) ⇒ (x ε A)] 5b) (A ε A) ⇔ ∀ [(x ε A) ⇒ (x ε A)]

Jack: 5b) A⊂A. Niech x − dowolny element uniwersum. Zał., że x∊A, stąd oczywiście mamy, że x∊A, a więc dostajemy implikację: x∊A ⇒ x∊A, czyli z def. A⊂A (tej definicji tu nie masz, ale ⊂ tak się definiuje, że A⊂B ⇔_def ∀x (x∊A ⇒ x∊B),) 5a) ∅ ⊂A. czyli ∀x (x∊∅ ⇒ x∊A) − jest to prawda, ponieważ poprzednik implikacji jest fałszywy z def. zbioru pustego .

kajka: czyli to co zapisałam na zajęciach jest dobrze? I jak udowodnić 5c?

Jack: Teraz zauważyłem ze chcesz dowieść 5c) ... c) [(A ⊆ B) ∧ (B ⊆ C)] ⇔ (A ⊆ C) (→) i Zał. że (A ⊆ B) ∧ (B ⊆ C), czyli ∀x (x∊A → x∊B) ∧ ∀x (x∊B → x∊C) Z przechodniości implikacji: (p→q) ⋀ (q→r) ⇔ (p→r), otrzymujemy tezę (opuszczając duży kwantyfikator, zostajemy przy zmiennej x). (←) Zał, że (A ⊆ C) ⇔ ∀x (x∊A → x∊C). Tutaj można wykorzystać to samo prawo, ponieważ występuje w nim równoważność: (p→r) ⇔ (p→q) ⋀ (q→r), co dowodzi tezy.

Jack: bez komentarza, troszkę sucho...nie wiem, jak to oceniać.

kajka: Na udowodnienie 6a w internecie znalazłam takie coś: 6a) x ε (A ∪ B) ⇔ x ε (B ∪ A) ⇒ x ε (A ∪ B) ⇔ x ε A ∨ x ε B ⇔ x ε B ∨ x ε A ⇔ x ε (B ∪ A) 6b) A ∪ (B ∪ C) = (A ∪ B) ∪ C ⇔ x ε (A ∪ B) ∪ C ⇔ x ε A ∪ (B ∪ C) ⇒ x ε (A ∪ B) ∪ C ⇔ x ε (A ∪ B) ∨ x ε C ⇔ (x ε A ∨ x ε B) ∨ x ε C ⇔ x ε A ∨ (x ε B ∨ x ε C) ⇔ x ε A ∨ x ε (B ∪ C) ⇔ x ε A ∪ (B ∪ C) 6c) ∅ ∪ A = A (nie wiem jak to udowodnić) 6d) A ∪ A = A (A = A) ⇔ ∀ x (x ε A) ⇔ (x ε B) ⇒ ∀ x (x ε A ∪ A) ⇔ (x ε A) ⇔ ∀ x [(x ε A ∨ x ε A) ⇔ (x ε A)]

kajka: sprawdzi to ktoś?