Zbadać jakie relacje inkluzji zachodzą między zbiorami

[Dario1]

Zbadać jakie relacje inkluzji zachodzą między zbiorami \(\displaystyle{ A,B,C}\), jeśli prawdziwa jest równość

\(\displaystyle{ \left( A \cup B\right)-C=\left( A-C\right) \cup B}\)


Nie wychodzą mi tego typu zadania.

[szw1710]

Spróbuj to sobie narysować na diagramach Venna.

[Dario1]

Na diagramach Venna mi wychodzi jak trzeba, ale jak to uzasadnić? Przesz nie napiszę, że to wynika z diagramów Venna...

[Jan Kraszewski]

Jak z diagramów Venna wiesz, co powinno wyjść, to dorobienie uzasadnienia nie powinno być dużym problemem. Co Ci tutaj z diagramów wyszło?

JK

[Dario1]

Wyszło mi, że \(\displaystyle{ B \cap C=\emptyset}\)

[Jan Kraszewski]

To teraz możesz to udowodnić, zakładając nie wprost, że tak nie jest.

Inna sprawa, czy to odpowiada na polecenie w zadaniu - byłeś pytany o inkluzje.

JK

[Dario1]

W odpowiedzi, jest tak jak napisałem. Też się trochę dziwię. A jak to udowodnić może tak:

Załóżmy nie wprost, że \(\displaystyle{ \neg B \cap C=\emptyset}\). To oznacza, że istnieje \(\displaystyle{ x \in
B \cap C \Leftrightarrow x \in B \wedge x \in C \Rightarrow x \in B \cup \left( A-C\right)}\), ale \(\displaystyle{ x\notin\left( A \cup B\right)-C}\) bo \(\displaystyle{ x \in C}\). Sprzecznosc.

Dobrze?

[Jan Kraszewski]

Dobrze.

JK

[SzostekKarol]

Inkluzji można wyznaczyć zazwyczaj kilka, są równoważne oraz takie co wynikają z tego zdania.
Tutaj akurat można napisać dwie równoważne inkluzje.

Formalne rozwiązanie wygląda jak poniżej.

Oznaczamy:
\(\displaystyle{
[(A \cup B) \setminus C=(A \setminus C) \cup B] \Leftrightarrow *
}\)

Równoważność zbiorów jest to zdanie w sensie logicznym, które ma wartość logiczną 0 albo 1, i można je zapisać za pomocą kwantyfikatora o ogólnego w przestrzeni \(\displaystyle{ U}\):
\(\displaystyle{
* \Leftrightarrow \forall _{x\in U}\left \{ [(x\in A\vee x\in B)\wedge x \notin C] \Leftrightarrow [(x\in A \wedge x \notin C) \vee x \in B] \right \}
}\)

Pod kwantyfikatorem mamy funkcje logiczną, która po podstawieniu za x elementu ze zbioru (tj: przestrzeni ma wartość logiczna) np \(\displaystyle{ x_{i}}\), jest zdaniem.
Wprowadzimy oznaczenia:
\(\displaystyle{
x_{i} \in A \rightarrow a \\
x_{i}\in B \rightarrow b\\
x_{i}\in C \rightarrow c \\
x_{i}\notin C \Leftrightarrow x_{i}\in \sim C \rightarrow \sim c
}\)

Po wprowadzeniu oznaczeń możemy dla funkcji zdaniowej pod kwantyfikatorem napisać zdanie w postaci:
\(\displaystyle{
[(a \vee b)\wedge \sim c] \Leftrightarrow [ a \wedge \sim c) \vee b]
}\)

Narysujmy tabelkę prawdy dla zdania oraz równoważnych inkluzji:

[Jan Kraszewski]

Inkluzji można wyznaczyć zazwyczaj kilka, są równoważne oraz takie co wynikają z tego zdania.

Akurat w tym zadaniu nie ma żadnych inkluzji pomiędzy zbiorami \(\displaystyle{ A,B,C}\), które wynikałyby z podanej równości. Jest tylko jedna zależność: \(\displaystyle{ B\cap C=\emptyset}\).

Formalne rozwiązanie wygląda jak poniżej.

Fuj. To jest typ rozwiązania, który zwalczam u swoich studentów.

Równoważność zbiorów jest to zdanie w sensie logicznym,

Nie ma czegoś takiego jak "równoważność zbiorów".

można je zapisać za pomocą kwantyfikatora o ogólnego w przestrzeni \(\displaystyle{ U}\):

I tu dodatkowo pojawia się nieznana przestrzeń \(\displaystyle{ U}\).

Narysujmy tabelkę prawdy dla zdania oraz równoważnych inkluzji:

Jak to mawiał mój wykładowca: "To rozwiązanie nie dotyka istoty rzeczy". Dość paskudne manipulacje na znaczkach. A przecież to, co zrobił powyżej Dario1 jest dużo krótsze i efektywniejsze (a ponadto dotyka istoty rzeczy, czyli zrozumienia relacji pomiędzy zbiorami).

JK

[SzostekKarol]

Inkluzji można wyznaczyć zazwyczaj kilka, są równoważne oraz takie co wynikają z tego zdania.
Tutaj akurat można napisać dwie równoważne inkluzje.

Formalne rozwiązanie wygląda jak poniżej.

Oznaczamy:
\(\displaystyle{
[(A \cup B) \setminus C=(A \setminus C) \cup B] \Leftrightarrow *
}\)

Równość zbiorów jest to zdanie w sensie logicznym, które ma wartość logiczną 0 albo 1, i można je zapisać za pomocą kwantyfikatora ogólnego w przestrzeni \(\displaystyle{ U}\):
\(\displaystyle{
* \Leftrightarrow \forall _{x\in U}\left \{ [(x\in A\vee x\in B)\wedge x \notin C] \Leftrightarrow [(x\in A \wedge x \notin C) \vee x \in B] \right \}
}\)

Pod kwantyfikatorem mamy funkcje logiczną, która po podstawieniu za x elementu ze zbioru (tj: przestrzeni ma wartość logiczna) np \(\displaystyle{ x_{i}}\), jest zdaniem.
Wprowadzimy oznaczenia:
\(\displaystyle{
x_{i} \in A \rightarrow a \\
x_{i}\in B \rightarrow b\\
x_{i}\in C \rightarrow c \\
x_{i}\notin C \Leftrightarrow x_{i}\in \sim C \rightarrow \sim c
}\)

Po wprowadzeniu oznaczeń możemy dla funkcji zdaniowej pod kwantyfikatorem napisać zdanie w postaci:
\(\displaystyle{
[(a \vee b)\wedge \sim c] \Leftrightarrow [ a \wedge \sim c) \vee b]
}\)

Narysujmy tabelkę prawdy dla zdania oraz równoważnych implikacji odpowiadających inkluzjom:
\(\displaystyle{
\begin{tabular}{ |c|c|c||c|c|c|c|c|c||c|c|c|c|c| }
\hline
& & & & d & e & f & g & & & & & h & \\
a & b & c & \sim c & a \vee b & d \wedge \sim c & a \wedge \sim c & f \vee b & f \Leftrightarrow g & b \Rightarrow \sim c & \sim b & c \Rightarrow \sim b & b \wedge c & h \Leftrightarrow 0 \\
\hline
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
\hline
\end{tabular}
}\)

Z tabeli widzimy, że
\(\displaystyle{
{[(a \vee b)\wedge \sim c] \Leftrightarrow [ a \wedge \sim c) \vee b]} \Leftrightarrow [ b \Rightarrow \sim c ] \Leftrightarrow [c \Rightarrow \sim b ] \Leftrightarrow [(b \wedge c ) = 0 ]
}\)

Stąd można wskazać równoważne inkluzje i inne równości:
\(\displaystyle{
* \Leftrightarrow [ B \subset C' ] \Leftrightarrow [ C \subset B' ] \Leftrightarrow [ (B \cap C)=\varnothing ]
}\)

Dla niedowiarków proponuje zrobić zadania w których jest wiele równoważnych inkluzji oraz po kilka zbiorów pustych:
\(\displaystyle{
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup A]
\\
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup (A \cap C )]
}\)
Trzy zadania na diagramach Venna:

Ale zapewne Pan Jan Kraszewski mimo mojego wywodu i tak ich nie odnajdzie inkluzji bo nie wie co to postać normalna
Administratora proszę o usunięcie wcześniejszego niepełnego wpisu, którego nie dokończyłem a edycja została zablokowana, nie mogę go też usunąć.

[krl]

No tak, Jan Kraszewski oczywiście nie wie, co to jest postać normalna. Całe szczęście, że z pomocą śpieszy Karol Szostek.
Chciałbym odpowiedzieć na pierwsze pytanie w tym wątku. Literalnie rzecz biorąc, z podanej równości zbiorów nie wynikają żadne inkluzje
między zbiorami \(\displaystyle{ A,B,C}\). Takich inkluzji może być łącznie co najwyżej sześć, no bo możliwe są tylko inkluzje
\(\displaystyle{ A\subseteq B, B\subseteq A, B\subseteq C, C\subseteq B, A\subseteq C, C\subseteq A}\), w każdym z tych sześciu przypadków można wskazać przykład zbiorów \(\displaystyle{ A,B,C}\) takich, że podana równość zbiorów zachodzi, natomiast dana inkluzja nie zachodzi. W tym celu pomocniczo warto posłużyć się diagramem Venna i faktem, że podana równość zbiorów równoważna jest temu, że \(\displaystyle{ B\cap C=\emptyset}\). (Można nawet podać jeden przykład zbiorów \(\displaystyle{ A,B,C}\), dla których zachodzi podana równość, a żadna z inkluzji miedzy nimi nie.)

Zadanie można rozumieć szerzej, tak jak robi to Karol Szostek. Mianowicie można zapytać się, ile jest inkluzji między zbiorami utworzonymi z podzbiorów \(\displaystyle{ A,B,C}\) przestrzeni \(\displaystyle{ X}\) przy pomocy działań mnogościowych, przy założeniu, że zachodzi podana równość zbiorów. Oczywiście, niektóre inkluzje powinniśmy utożsamiać, np. \(\displaystyle{ A\subseteq A\cup B}\) to w istocie to samo co \(\displaystyle{ A\cap A\subseteq A\cup B}\), gdyż \(\displaystyle{ A\cap A =A}\).
Przy tym naturalnym zastrzeżeniu łatwo policzyć, że podana równość zbiorów implikuje \(\displaystyle{ 729}\) inkluzji.
(wskazówka: \(\displaystyle{ 729=3^6}\)). Miłym ćwiczeniem dla fanów postaci normalnej będzie zapewne wypisanie wszystkich tych inkluzji.

Ciekawe jest też zadanie Karola Szostka, w którym jest "kilka zbiorów pustych". Myślę, że Jan Kraszewski by go nie rozwiązał.

[SzostekKarol]

Zaraz zaraz, przecież w tym innym sensie jest nieskończenie wiele inkluzji a nie 729 ??? i jest też nieskończenie wiele równań pomiędzy zbiorami równoważnych podanemu równaniu.
Według mnie dobre podejście to takie w którym podajemy inkluzje w których:

lewa strona (poprzednik) implikacji funkcji zdaniowej pod kwantyfikatorem jest w postaci alternatywnej minimalnej
prawa strona (następnik) implikacji funkcji zdaniowej pod kwantyfikatorem jest w postaci koniunkcyjnej minimalnej

\(\displaystyle{
A \subseteq B \Leftrightarrow \forall _{x\in U} [x \in A \Rightarrow x \in B]
}\)

Implikacja ma wartość zero w polach tabeli prawdy, w których wartości zerowe przyjmuje rozpatrywana równoważność funkcji zdaniowej.

Takich inkluzji jest tylko dwie w tym przypadku, ponieważ w tabelce jest dwa zera są one niezależne od a=0,1 dla których b=c=1. !!!!
Dlatego mamy tylko dwie równoważne implikacje w których poprzednik i następnik jest w postaci minimalnej.

\(\displaystyle{
b \Rightarrow \sim c \\
c \Rightarrow \sim b
}\)

Są to dwie minimalne inkluzje, oczywiście nie zachodzące bezpośrednio miedzy zbiorami A, B, C.

Dodam jeszcze, że inkluzje mogą być równoważne \(\displaystyle{ \Leftrightarrow}\) albo wynikać \(\displaystyle{ \Rightarrow}\) z podanej równości.
Pytanie co oznacza zdanie "Jakie inkluzje zachodzą?"
Może być też tak, że z jakiejś inkluzji wynika \(\displaystyle{ \Rightarrow}\) podana równość.

Dodano po 2 godzinach 48 minutach 35 sekundach:
Rozwiązanie Zadania
\(\displaystyle{
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup A]
}\)

Funkcja z pod kwantyfikatora.
\(\displaystyle{
[(a \wedge \sim b) \vee ( b \wedge c)] \Leftrightarrow [ c \wedge \sim b) \vee a] \Leftrightarrow *
}\)

Tabela prawdy:
\(\displaystyle{
\begin{tabular}{ |c|c|c||c|c|c|c|c|c|c||c|c|c|c|c|c|}
\hline
& & & & d & e & f & g & h & * & x & i & y & & & \\
a & b & c & \sim b & a \wedge \sim b & b \wedge c & c \wedge \sim b & d \vee e & f \vee a & g \Leftrightarrow h & c \Rightarrow a & a \wedge b & i \Rightarrow c & * \Rightarrow x & * \Rightarrow y & x \wedge y \\
\hline
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
\end{tabular}
}\)

Tabela minimalizacji dla \(\displaystyle{ * \Leftrightarrow (x \wedge y)}\)
\(\displaystyle{
\begin{tabular}{ |c||c|c|c|c|}
\hline
a,b& 00 & 01 & 11 & 10 \\
c & & & & \\
\hline
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 \\
\hline
\end{tabular}
}\)

W tabeli minimalizacji można zaznaczyć dwa obszary dla zer i napisać odpowiednią podstać koniunkcyjną normalną:
\(\displaystyle{
[(a \vee \sim c)\wedge (\sim a \vee \sim b \vee c)] \Leftrightarrow [( c \Rightarrow a) \wedge [(a \wedge b) \Rightarrow c]]
\\
[(a \vee \sim c)\wedge (\sim a \vee \sim b \vee c)] \Rightarrow ( c \Rightarrow a)
\\
[(a \vee \sim c)\wedge (\sim a \vee \sim b \vee c)] \Rightarrow[(a \wedge b) \Rightarrow c]
}\)

Stąd mamy
\(\displaystyle{
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup A] \Leftrightarrow [(C\subseteq A)\wedge [(A \cap B) \subseteq C]]
\\
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup A] \Rightarrow (C\subseteq A)
\\
[(A \setminus B) \cup (B \cap C)=(C \setminus B) \cup A] \Rightarrow [(A \cap B) \subseteq C]
}\)

Identycznie można rozwiązać każde takie zadanie z dowolną ilością zbiorów. Dowolną jak dowolną ale dla 6 czy 7 da się narysować tabelki

[Jan Kraszewski]

Administratora proszę o usunięcie wcześniejszego niepełnego wpisu, którego nie dokończyłem a edycja została zablokowana, nie mogę go też usunąć.

Nie usunę, bo to zaburza ciągłość dyskusji. Pełny wpis jest i to wystarczy.

Ale zapewne Pan Jan Kraszewski mimo mojego wywodu i tak ich nie odnajdzie inkluzji bo nie wie co to postać normalna

Nie odnajdzie, bo stosuję naturalną, ścisłą interpretację treści zadania, jak Ci to wyjaśnił krl. Ale cieszę się, że umiesz rysować duże tabelki, choć ciężko zrozumieć, po co - do tego, że warunek w zadaniu jest równoważny z \(\displaystyle{ B\cap C=\emptyset}\) można dojść dużo szybciej bez mnóstwa zbędnych znaczków. Na tym właśnie polega wspomniana przeze mnie "istota rzeczy".

Zaraz zaraz, przecież w tym innym sensie jest nieskończenie wiele inkluzji a nie 729 ???

Bo?

Według mnie dobre podejście to takie w którym podajemy inkluzje w których:

lewa strona (poprzednik) implikacji funkcji zdaniowej pod kwantyfikatorem jest w postaci alternatywnej minimalnej
prawa strona (następnik) implikacji funkcji zdaniowej pod kwantyfikatorem jest w postaci koniunkcyjnej minimalnej

Każdy ma prawo do swoich przekonań, ale jako osoba będąca bliżej elementarnej teorii mnogości (zwanej czasem Wstępem do matematyki) od Ciebie stwierdzam, że nie uważam tego podejścia za dobre (uważam je za sztuczne).

Inna sprawa, że samo zadanie nie jest wg mnie dobrze sformułowane, bo treść sugeruje, że jakieś inkluzje jednak są, podczas gdy ich nie ma.

Ciekawe jest też zadanie Karola Szostka, w którym jest "kilka zbiorów pustych". Myślę, że Jan Kraszewski by go nie rozwiązał.

Tak, myślę, że poddałbym przy drugim zbiorze pustym...

JK

[SzostekKarol]

Jestem pewien, że nawet po moim wpisie nie czaisz o co w tym chodzi Panie Jan Kraszewski.