Czy zachodzi równość dla zbiorów

[Krrystian]

Mam problem w udowodnieniu tego równania:

\(\displaystyle{ (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A) }\)

Przedstawię tok mojego rozumowania:
1. Obieramy dowolny \(\displaystyle{ x \in R }\)
\(\displaystyle{ x \in ((A \cup B) \setminus (A \cap B)) = x \in ((A \setminus B) \cup (B \setminus A))}\)
2. Lewa strona:
\(\displaystyle{ (x \in A \cup x \in B) \wedge \neg (x \in A \cap x \in B))}\) ---> Z definicji różnicy zbiorów
\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) ---> Z definicji sumy zbiorów

3. Prawa strona:
\(\displaystyle{ (x \in A \wedge \neg (x \in B)) \cup (x \in B \wedge \neg (x \in A)) }\) ---> Z def. różnicy zbiorów
\(\displaystyle{ (x \in A \wedge \neg (x \in B)) \vee (x \in B \wedge \neg (x \in A)) }\) ---> Z def. sumy zbiorów

Tutaj zaczyna się problem, według tego co zrobiłem \(\displaystyle{ P \neq L }\) Prosiłbym o pomoc lub też korektę moich błędów. Gdzieś w zeszycie miałem zapisane o czymś takim jak ''Różnica symetryczna zbiorów'', aczkolwiek nie wiem jak mógłbym ją, i czy w ogóle, wykorzystać. Z góry dziękuję.

[Jan Kraszewski]

1. Obieramy dowolny \(\displaystyle{ x \in R }\)

A cóż to jest \(\displaystyle{ R}\) i skąd pomysł, by wziąć dowolny \(\displaystyle{ x}\) właśnie stamtąd?

\(\displaystyle{ x \in ((A \cup B) \setminus (A \cap B)) = x \in ((A \setminus B) \cup (B \setminus A))}\)

Źle. Zbiory są równe, a formuły równoważne. Powinni być

\(\displaystyle{ x \in ((A \cup B) \setminus (A \cap B)) \Leftrightarrow x \in ((A \setminus B) \cup (B \setminus A)).}\)

2. Lewa strona:
\(\displaystyle{ (x \in A \,\red{\cup}\, x \in B) \wedge \neg (x \in A\,\red{\cap}\, x \in B))}\) ---> Z definicji różnicy zbiorów
\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) ---> Z definicji sumy zbiorów

3. Prawa strona:
\(\displaystyle{ (x \in A \wedge \neg (x \in B)) \, \red{\cup}\, (x \in B \wedge \neg (x \in A)) }\) ---> Z def. różnicy zbiorów
\(\displaystyle{ (x \in A \wedge \neg (x \in B)) \vee (x \in B \wedge \neg (x \in A)) }\) ---> Z def. sumy zbiorów

Znów mylisz byty - nie wolno stosować operacji mnogościowych do formuł. Powinno być:

2. Lewa strona (rownoważnie):
\(\displaystyle{ (x \in A\cup B) \wedge \neg (x \in A\cap B))}\) ---> Z definicji różnicy zbiorów
\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) ---> Z definicji sumy i przekroju zbiorów

3. Prawa strona (równoważnie):
\(\displaystyle{ (x \in A \setminus B)) \lor (x \in B\setminus A) }\) ---> Z def. sumy zbiorów
\(\displaystyle{ (x \in A \wedge \neg (x \in B)) \vee (x \in B \wedge \neg (x \in A)) }\) ---> Z def. różnicy zbiorów

Tutaj zaczyna się problem, według tego co zrobiłem \(\displaystyle{ P \neq L }\)

No i co z tego? Ciebie nie interesuje \(\displaystyle{ P=L}\), tylko \(\displaystyle{ P \Leftrightarrow L}\), a żeby to uzyskać, trzeba się trochę napracować. Weź lewą stronę, poprzekształcaj ją równoważnie stosując prawo rozdzielności koniunkcji względem alternatywy.

Gdzieś w zeszycie miałem zapisane o czymś takim jak ''Różnica symetryczna zbiorów'', aczkolwiek nie wiem jak mógłbym ją, i czy w ogóle, wykorzystać.

Ta równość to po prostu pewna własność różnicy symetrycznej zbiorów:

\(\displaystyle{ A\Delta B= (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A). }\)

JK

[Krrystian]

A cóż to jest \(\displaystyle{ R}\) i skąd pomysł, by wziąć dowolny \(\displaystyle{ x}\) właśnie stamtąd?

Przyznaje się, nie wiem skąd. Czy mógłby on należeć do jakiegokolwiek zbioru zamiast \(\displaystyle{ R}\)?

No i co z tego? Ciebie nie interesuje \(\displaystyle{ P=L}\), tylko \(\displaystyle{ P⇔L}\), a żeby to uzyskać, trzeba się trochę napracować. Weź lewą stronę, poprzekształcaj ją równoważnie stosując prawo rozdzielności koniunkcji względem alternatywy.

Dziękuje za poprawę zapisu.

Więc kontynuując:

2. Lewa strona (rownoważnie):
\(\displaystyle{ (x \in A\cup B) \wedge \neg (x \in A\cap B))}\) ---> Z definicji różnicy zbiorów
\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) ---> Z definicji sumy i przekroju zbiorów
\(\displaystyle{ \neg [(x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))]}\) ---> Z prawa De Morgana
\(\displaystyle{ ( \neg (x \in A) \wedge \neg (x \in B)) \vee ( x \in A \wedge x \in B)}\)

Mówiąc szczerze, nie wiem jak mógłbym wykorzystać prawo rozdzielności koniunkcji względem alternatywy. Brakuje mi pomysłu. Ogólnie jedyne co mi przychodzi do głowy, to czy jeżeli mamy właśnie to prawo to możemy je użyć właśnie w taki sposób (jeszcze nie spotkałem się z takim "stylem" użycia prawa rozdzielności, gdzie z dwóch stron mamy zapis zbiorów, z czego nie mają jednego elementu wspólnego):
\(\displaystyle{ (\neg (x \in A) \wedge x \in B) \vee (\neg (x \in B) \wedge x \in A) }\)
I wtedy \(\displaystyle{ L \Leftrightarrow P }\)

[Jan Kraszewski]

2. Lewa strona (rownoważnie):
\(\displaystyle{ (x \in A\cup B) \wedge \neg (x \in A\cap B))}\) ---> Z definicji różnicy zbiorów
\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) ---> Z definicji sumy i przekroju zbiorów
\(\displaystyle{ \neg [(x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))]}\) ---> Z prawa De Morgana

A to niby skąd? Zanegowanie formuły nie jest przejściem równoważnym...

Mówiąc szczerze, nie wiem jak mógłbym wykorzystać prawo rozdzielności koniunkcji względem alternatywy. Brakuje mi pomysłu. Ogólnie jedyne co mi przychodzi do głowy, to czy jeżeli mamy właśnie to prawo to możemy je użyć właśnie w taki sposób (jeszcze nie spotkałem się z takim "stylem" użycia prawa rozdzielności, gdzie z dwóch stron mamy zapis zbiorów, z czego nie mają jednego elementu wspólnego)

Prawo rozdzielności mnożenia względem dodawania mówi tylko, że \(\displaystyle{ a(b+c)=ab+ac}\), a jakoś nie masz problemów z przekształceniem (na mocy tego prawa) \(\displaystyle{ (a+b)(c+d)=...}\)

Masz \(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) i (formalnie rzecz biorąc) musisz zastosować prawo rozdzielności trzykrotnie (tak samo, jak przy powyższym wyrażeniu algebraicznym):

\(\displaystyle{ \red{(x \in A \vee x \in B)} \wedge ( \neg (x \in A) \vee \neg (x \in B)) \Leftrightarrow \\
(\red{(x \in A \vee x \in B)} \wedge \neg (x \in A) ) \vee (\red{(x \in A \vee x \in B)} \wedge \neg (x \in B)) \Leftrightarrow... }\)

itd.

JK

[Krrystian]

A to niby skąd? Zanegowanie formuły nie jest przejściem równoważnym...

Wziąłem sobie do serca rozdzielność koniunkcji względem alternatywy, jak to wyżej Pan uwzględnił w wypowiedzi.

Masz \(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B))}\) i (formalnie rzecz biorąc) musisz zastosować prawo rozdzielności trzykrotnie (tak samo, jak przy powyższym wyrażeniu algebraicznym):

\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B)) \Leftrightarrow \\
(x \in A \vee x \in B) \wedge \neg (x \in A) ) \vee (x \in A \vee x \in B) \wedge \neg (x \in B)) \Leftrightarrow \\
[(x \in A \wedge \neg (x \in A)) \vee (x \in B \wedge \neg (x \in A) )] \vee [(x \in A \wedge \neg (x \in B)) \vee (x \in B \vee \neg (x \in B))]\Leftrightarrow \\}\)

Gdzie: \(\displaystyle{ (x \in A \wedge \neg (x \in A)) }\) oraz \(\displaystyle{ (x \in B \vee \neg (x \in B))}\) dla których wartość logiczna jest równa 0, więc mogę je zredukować w tym przypadku, dlatego:
\(\displaystyle{ (x \in B \wedge \neg (x \in A) )\vee (x \in A \wedge \neg (x \in B)) }\)

Dzięki czemu: \(\displaystyle{ L\Leftrightarrow P }\)

[Jan Kraszewski]

\(\displaystyle{ (x \in A \vee x \in B) \wedge ( \neg (x \in A) \vee \neg (x \in B)) \Leftrightarrow \\
(x \in A \vee x \in B) \wedge \neg (x \in A) ) \vee (x \in A \vee x \in B) \wedge \neg (x \in B)) \Leftrightarrow \\
[(x \in A \wedge \neg (x \in A)) \vee (x \in B \wedge \neg (x \in A) )] \vee [(x \in A \wedge \neg (x \in B)) \vee (\red{x \in B \vee \neg (x \in B)})]\Leftrightarrow \\}\)

Gdzie: \(\displaystyle{ (x \in A \wedge \neg (x \in A)) }\) oraz \(\displaystyle{ (x \in B \vee \neg (x \in B))}\) dla których wartość logiczna jest równa 0, więc mogę je zredukować w tym przypadku, dlatego:
\(\displaystyle{ (x \in B \wedge \neg (x \in A) )\vee (x \in A \wedge \neg (x \in B)) }\)

Dzięki czemu: \(\displaystyle{ L\Leftrightarrow P }\)

No widzisz, dałeś radę. Przy czym nie tyle "redukujesz", co korzystasz z prawa \(\displaystyle{ p\lor 0 \Leftrightarrow p.}\)

Poza tym masz jedną pomyłkę: zamiast \(\displaystyle{ x \in B \vee \neg (x \in B)}\) powinno być \(\displaystyle{ x \in B \land \neg (x \in B)}\).

JK

PS No i nie wyjaśniłeś, skąd wziąłeś \(\displaystyle{ R}\)...

@edit: poprawa pomyłki.