5.4. Prawa rachunku zbiorów typu bezzałożeniowego.

5.4.1. Łyk teorii.

B adając teorię zbiorów odnaleźć możemy wyrażenia będące zawsze prawdziwymi, niezależnie od tego, do jakich zbiorów się one odnoszą. Przykładem takich wyrażeń mogą być wzory: (A  B) = (B  A), (A  B)  A czy też (A  B  B  C)  A  C. Takie zawsze prawdziwe wyrażenia nazywamy prawami rachunku zbiorów. Pierwsze dwa z powyższych wzorów mają postać równości oraz inkluzji pewnych zbiorów; stwierdzają one bezwarunkowe zachodzenie pewnego związku. Trzeci z przestawionych wzorów ma postać implikacji; mówi on, że pewna zależność zachodzi, jeśli zachodzi inna. Tego typu, założeniowymi prawami, zajmiemy się w kolejnym paragrafie. Obecnie natomiast omówimy wyrażenia mające postać równości bądź inkluzji zbiorów.

Do wykrywania omawianych, bezzałożeniowych, praw rachunku zbiorów posłużyć się możemy metodą wykorzystującą klasyczny rachunek zdań i pojęcie tautologii. W miarę dobra znajomość KRZ jest więc konieczna do dalszych rozważań.

Ponieważ wyrażenia, które będziemy badali, mają postać równości bądź zawierania się zbiorów, rozpoczniemy od uświadomienia sobie, co dokładnie oznaczają te dwie zależności. Fakt, że jeden zbiór zawiera się w drugim, przedstawić możemy przy pomocy stwierdzenia, że jeśli jakiś obiekt jest elementem zbioru A, to również jest on elementem B (dla dowolnego obiektu x, jeśli x należy do A, to x należy do B). Można zapisać to wzorem:

1) A  B  x (x  A  x  B)

To, że dwa zbiory są równe, oznacza, że jeśli dowolny obiekt jest elementem A, to jest on również elementem B, a jeśli jest elementem B, to jest też elementem B. Innymi słowy, to, że dowolny x należy do A, jest równoważne temu, że należy on do B. Formalnie:

2) A = B  x (x  A  x  B)

W naszych prawach, które będziemy badali, występują również pojęcia iloczynu, sumy, różnicy i dopełnienia zbiorów. Dlatego też powinniśmy zdań sobie sprawę, co oznacza fakt, że jakiś obiekt należy do iloczynu, sumy lub różnicy dwóch zbiorów, czy też dopełnienia jakiegoś zbioru.

To, że pewien obiekt x jest elementem iloczynu (czyli części wspólnej) zbiorów A i B oznacza, że należy on zarówno do A jak i do B. Symbolicznie:

3) x  (A  B)  (x  A  x  B)

Fakt, że jakiś obiekt x należy do sumy zbiorów A i B, oznacza, że należy on do A lub też należy do B. Formalnie:

4) x  (A  B)  (x  A  x  B)

To, że pewien x należy do różnicy zbiorów A i B oznacza, że należy on do zbioru A i jednocześnie nie jest prawdą, że należy do B. Symbolicznie:

5) x  (A – B)  (x  A  ~ (x  B))

Należenie jakiegokolwiek obiektu x do dopełnienia pewnego zbioru A oznacza po prostu, że nie jest prawdą, iż ów x należy do A:

6) x  A’  ~ (x  A)

Znajomość powyższych wzorów 1) – 6) będzie konieczna, aby móc sprawdzić, czy jakieś wyrażenie jest prawem rachunku zbiorów.

5.4.2. Praktyka: wykrywanie praw rachunku zbiorów przy pomocy rachunku zdań.

Wykrycie, czy dane wyrażenie, mające postać równości bądź inkluzji zbiorów, jest ogólnie obowiązującym prawem, będzie polegało na przekształceniu formuły rachunku zbiorów na formułę rachunku zdań, a następnie sprawdzeniu, czy otrzymany schemat jest tautologią. Jeśli otrzymana formuła okaże się tautologią, będzie to oznaczało, że wyjściowy wzór jest prawem rachunku zbiorów; jeśli formuła nie będzie tautologią, to znak, że badane wyrażenie nie jest takim prawem.

Przekształcanie formuły rachunku zbiorów na rachunek zdań polegać będzie na systematycznym stosowaniu poznanych wyżej wzorów, aż otrzymamy wyrażenie, w którym nie będzie symboli oznaczających inkluzję, równość, sumę, iloczyn, różnicę i dopełnienie zbiorów, zamiast których pojawią się symbole rachunku zdań (implikacja, równoważność, alternatywa, koniunkcja, negacja). Przekształcenia takie będziemy wykonywali krok po kroku. W pierwszym ruchu będziemy zawsze stosowali wzór 1) lub 2), aby zamienić inkluzję bądź równość zbiorów na implikację lub równoważność. Następnie, w zależności od potrzeb, będziemy korzystali ze wzorów 3) – 6).

Przykład:

Sprawdzimy, czy prawem rachunku zbiorów jest wyrażenie:

(A – B)  (A  B)

Ponieważ całe wyrażenie ma postać inkluzji, rozpoczniemy od zastosowania wzoru 1), dzięki któremu otrzymamy:

x [x  (A – B)  x  (A  B)]

Kwantyfikator na początku formuły, informujący nas, że implikacja powinna zachodzić dla każdego obiektu x, możemy w następnych krokach pomijać. Skoro bowiem implikacja ma być prawdziwa dla każdego (dowolnego) x, to w tym również dla naszego konkretnego obiektu x, który sobie wybraliśmy. A zatem możemy zapisać:

x  (A – B)  x  (A  B)

Teraz możemy przystąpić do kolejnych przekształceń. Poprzednik implikacji stwierdza, że nasz obiekt x należy do różnicy zbiorów A i B; musimy tam zatem zastosować wzór 5). W odniesieniu do następnika powinniśmy natomiast skorzystać ze wzoru 4). Otrzymamy wtedy:

(x  A  ~ (x  B))  (x  A  x  B)

Uwaga na błędy!

Dokonując przekształceń należy bardzo uważać, aby nie zmienić struktury nawiasów. Jeżeli wzór mówi, że nasz x należy do pewnej całości umieszczonej w nawiasie, to po wykonaniu przekształcenia nawias ten musi pozostać. Można obrazowo powiedzieć, że x „wchodzi w głąb” nawiasu, nie naruszając go jednak.

Po przekształceniu symboli związanych ze zbiorami (poza ) na symbole rachunku zdań możemy naszą formułę zmienić całkowicie na schemat KRZ, podstawiając na przykład za wyrażenie x  A zmienną p, natomiast za x  B zmienną q. Otrzymamy wtedy:

(p  ~ q)  (p  q)

Teraz pozostaje nam sprawdzenie, czy otrzymana formuła jest tautologią. Uczynienie tego skróconą metodą zero-jedynkową nie powinno sprawić nikomu najmniejszych trudności.

(p  ~ q)  (p  q)

1 1 1 0 0 1 0 0

Otrzymana sprzeczność (która mogła komuś również wyjść w poprzedniku implikacji) wskazuje, że formuła KRZ nie może być fałszywa, a zatem jest ona tautologią. Na tej podstawie możemy stwierdzić, że badane przez nas wyrażenie jest prawem rachunku zbiorów.

▲

Przykład:

Sprawdzimy, czy prawem rachunku zbiorów jest wyrażenie:

(A’  B’) = (A  B)’

W pierwszym kroku musimy zastosować wzór 2) i pozbyć się znaku równości:

x [x  (A’  B’)  x  (A  B)’]

Po opuszczeniu kwantyfikatora otrzymujemy:

x  (A’  B’)  x  (A  B)’

Teraz możemy przystąpić do dalszych przekształceń. W każdym nawiasie mamy jednak dwa różne działania: iloczyn i dopełnienie w pierwszym oraz sumę i dopełnienie w drugim. Dokonując przekształceń, zajmujemy się zawsze najpierw działaniem w danym momencie głównym, „najszerszym” w danej formule. W pierwszym członie równoważności działaniem takim jest iloczyn; nasz x należy tam do iloczynu A’ oraz B’. W związku z tym najpierw zastosujemy tam wzór 3). Natomiast w drugim członie równoważności głównym działaniem jest dopełnienie; x należy do dopełnienia sumy A oraz B. Dlatego też w pierwszej kolejności zastosujemy tam wzór 6); skoro x należy do dopełnienia sumy A i B, to znaczy, iż nie jest prawdą, że należy on do tej sumy. Dokonując przekształceń pamiętamy o zachowaniu struktury nawiasów. Otrzymujemy:

(x  A’  x  B’)  ( ~ (x  (A  B))

Uwaga na błędy!

W omawianym przykładzie szczególnie istotne jest właściwe umieszczenie nawiasów z prawej strony równoważności. Musimy tam dodać jeden (wynikający ze wzoru 6)) nawias, który wskazuje że całe wyrażenie: x  (A  B) jest nieprawdziwe. Błędne byłoby dodanie samej negacji, bez nawiasu, czyli: ~ x  (A  B)

Teraz możemy dokonać dalszych przekształceń. Z lewej strony musimy zastosować (dwukrotnie) wzór 6), natomiast z prawej wzór 4). Otrzymamy wtedy:

(~ (x  A)  ~ (x  B))  ( ~ (x  A  x  B))

Uwaga na błędy!

Jeśli w pewnym miejscu mamy znak negacji przed nawiasem (tak jak w prawej części naszej równoważności) to negację taką zostawiamy w tym miejscu. Nie wolno jej pod żadnym pozorem „wciskać” do środka nawiasu lub robić z niej dwóch negacji. Błędne byłyby następujące przekształcenia prawej strony naszej formuły: (~ x  A  x  B) lub ( ~ x  A  ~ x  B).

Doświadczenie wskazuje, że takie błędy są bardzo często popełniane przez studentów, dlatego warto dobrze sobie zapamiętać powyższą uwagę.

W tym momencie możemy ostatecznie przekształcić naszą formułę na wyrażenie rachunku zdań podstawiając p za x  A oraz q za x  B. Otrzymamy wzór:

(~ p  ~ q)  ~ (p  q)

Łatwo sprawdzić, że powyższa formuła jest tautologią (pamiętamy, że w przypadku równoważności musimy rozpatrzyć dwie możliwości):

1 0 1 1 0 0 0 0 1 0

(~ p  ~ q)  ~ (p  q)

1 0 0 1 0 0 1 0 0 0

Ponieważ otrzymana formuła jest tautologią, badane wyrażenie jest prawem rachunku zbiorów.

▲

Przykład:

Sprawdzimy, czy prawem rachunku zbiorów jest wyrażenie:

[(A  B) – C]  [(A – B )  (B – C)]

Po zastosowaniu wzoru 1) i opuszczeniu kwantyfikatora otrzymujemy:

x  [(A  B) – C]  x  [(A – B )  (B – C)]

W poprzedniku implikacji głównym działaniem jest odejmowanie, dlatego najpierw musimy zastosować tam wzór 5). W następniku główne działanie, to iloczyn, więc wykorzystujemy wzór 3). Otrzymujemy:

[x  (A  B)  ~ (x  C)]  [x  (A – B )  x  (B – C)]

Teraz w poprzedniku implikacji musimy jeszcze skorzystać ze wzoru 3), a w następniku, dwukrotnie, ze wzoru 5):

[(x  A  x  B)  ~ (x  C)]  [(x  A  ~ (x  B ))  (x  B  ~ (x  C))]

Po podstawieniu zmiennej p za x  A, q za x  B oraz r za x  C otrzymamy:

[(p  q)  ~ r]  [(p  ~ q)  (q  ~ r)]

Po sprawdzeniu formuły skróconą metodą zero-jedynkową okazuje się, że może ona stać się schematem zdania fałszywego, a więc nie jest ona tautologią:

[(p  q)  ~ r]  [(p  ~ q)  (q  ~ r)]

1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0

Skoro otrzymana formuła nie jest tautologią, to badane wyrażenie nie jest prawem rachunku zbiorów.

▲