M3_przyklady.pdf

Przykłady

Przykład 1

Udowodnimy dla przykładu następującą własność mieszaną sumy i różnicy zbiorów

( A – B ) ∪ B = A ∪ B .

Aby udowodnić tę własność zgodnie z deﬁnicją równości zbiorów, należy pokazać, że:

∀ x ( x ∈ ( A – B ) ∪ B ⇔ x ∈ A ∪ B ),

czyli dla dowolnego elementu x należy wykazać równoważność x ∈ ( A – B ) ∪ B ⇔ x ∈ A ∪ B .

Weźmy zatem dowolny element x .

Rozpisując lewą stronę równoważności, otrzymujemy:

L : x ∈ ( A – B ) ∪ B ⇔  x ∈ ( A – B ) ∨ x ∈ B  ⇔  ( x ∈ A ∧ ¬ x ∈ B ) ∨ x ∈ B  ⇔

⇔  ( x ∈ A ∨ x ∈ B ) ∧ ( ¬ x ∈ B ∨ x ∈ B ) ⇔ 1 x ∈ A ∨ x ∈ B ⇔ x ∈ A ∪ B : P

Następnie, wykorzystując prawo przechodniości równoważności [( α ⇔ β ) ∧ ( β ⇔ γ )] ⇒ ( α ⇔ γ ),

otrzymujemy ﬁnalnie:

x ∈ ( A – B ) ∪ B ⇔ x ∈ A ∪ B .

Przykład 2

Udowodnimy własność A ∪ X = X . Należy pokazać, że ∀ x [ x ∈ A ∪ X ⇔ x ∈ X ].

Weźmy dowolny element x . Mamy:

L : x ∈ A ∪ X ⇔  x ∈ A ∨ x ∈ X .

Zauważmy, że jeżeli jeden składnik alternatywy jest prawdziwy, to cała alternatywa jest prawdziwa, zatem

możemy dopisać zdanie prawdziwe x ∈ X (dwie formuły prawdziwe są sobie oczywiście równoważne).

Uzasadniona jest zatem następująca równoważność:

x ∈ A ∨ x ∈ X ⇔   x ∈ X : P.

I ﬁnalnie:

x ∈ A ∪ X ⇔  x ∈ X .

1 Prawy czynnik koniunkcji jest prawdziwy (wyrażenie typu ¬α ∨ α ), zatem całe wyrażenie jest równoważne

lewemu czynnikowi koniunkcji.

Przykład 3

Pokażemy, że A ⊆ B ⇔  A ∩ B = A . Aby to uczynić, musimy udowodnić dwie implikacje:

(*) A ⊆ B ⇒  A ∩ B = A oraz (**) A ∩ B = A ⇒  A ⊆ B .

(*) Załóżmy, że A ⊆ B , czyli ∀ x [ x ∈ A ⇒ x ∈ B ].

Aby udowodnić równość zbiorów A ∩ B = A , wykażemy dwie inkluzje: A ∩ B ⊆ A oraz A ⊆ A ∩ B .

Pierwsza z nich jest oczywista na podstawie jednej z własności z Twierdzenia 1 2 .

Aby udowodnić drugą inkluzję, załóżmy, że x ∈ A . Z założenia (*) wiemy, że również x ∈ B . Mamy

zatem:

x ∈ A ∧ x ∈ B ,

czyli:

x ∈ A ∩ B .

Co kończy dowód drugiej z inkluzji potrzebnych do udowodnienia implikacji (*).

(**) Załóżmy, że A ∩ B = A , czyli ∀ x [ x ∈ A ∩ B ⇔ x ∈ A ]. Aby udowodnić inkluzję A ⊆ B , załóżmy, że

x ∈ A .

Z założenia (**) wiemy, że ponieważ A ∩ B = A , mamy wtedy x ∈ A ∩ B , czyli x ∈ A ∧ x ∈ B.

Oczywiście z prawa opuszczania koniunkcji mamy x ∈ B .

Co kończy dowód implikacji (**).

Oczywiście, zważywszy na odpowiednie prawo rachunku zdań 3 , równoważność A ⊆ B ⇔  A ∩ B = A

została udowodniona.

Przykład 4

Rozważmy zbiór X = { ∅ , a }. Wtedy jego zbiór potęgowy P ( X ) = { ∅ , { ∅ }, { a }, { ∅ , a }}.

Przykład 5

Niech X = { a , { b , c }}. Zauważmy, że zbiór ma tylko dwa elementy. Są to a oraz { b , c }. Zbiór potęgowy

wygląda zatem następująco: P ( X 2 ) = { ∅ , { a }, { { b , c } }, { a , { b , c }}}.

Przykład 6

Niech X = {{{ a }, { b }}, c }. Zauważmy, że zbiór ma tylko dwa elementy. Są to {{ a }, { b }} oraz c . Zbiór

potęgowy wygląda zatem następująco: P ( X ) = { ∅ , {{{ a }, { b }}}, { c }, {{{ a }, { b }}, c }}.

Przykład 7

Rozważmy następujący zbiór X = { a , b , c , d } oraz rodzinę ℑ 1 = {{ a , b }, { b }}.

Zauważmy, że X – { a , b } = { c , d } ∉ ℑ 1 , a także X – { b } = { a , c , d } ∉ ℑ 1 . Każde z tych spostrzeżeń

2 A ∩ B ⊆ A .

3 Prawo [( α ⇒ β ) ∧ ( β ⇒ α )] ⇔ ( α ⇔ β ).

wystarcza, aby orzec, że ℑ 1 nie jest ciałem zbiorów. Wzbogaćmy zatem rozważaną wyżej rodzinę ℑ 1

o wskazane zbiory. Niech ℑ 2 = {{ a , b }, { b }, { c , d }, { a , c , d }}.

Zauważmy teraz następujące fakty: { a , b } ∪ { c , d } = { a , b , c , d } = X ∉ ℑ 2 , { b } ∪ { c , d } = { b , c , d } ∉ ℑ 2 .

Wzbogaćmy więc rozważaną rodzinę o zbiór X, zbiór { b , c , d } oraz ich dopełnienia (rozpatrywane

w uniwersum X ), czyli zbiór pusty ∅ oraz zbiór { a }. Otrzymujemy ℑ 3 = { ∅ , { a , b }, { b }, { c , d }, { a , c , d }, { b ,

c , d }, { a }, X }. Okazuje się, że dopiero rodzina ℑ 3 jest ciałem zbiorów. Zauważmy również, że

z powyższych rozważań wynika, że jest najmniejszym ciałem zbiorów ( w uniwersum X) zawierającym

rodzinę ℑ 1 .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: