Равенство на множества.

[Гост]

Нека A, B, C и D са множества. При какви условия е изпълнено, че
$$ (A \cap B) \times (C \cup D) = ( A \times C) \cap (B \times D).$$

[Davids]

Ами, при такива задачи общо взето имаш два еквивалентни варианта за доказателство, в зависимост от предпочитанието ти и сложността на проблема.
Първи подход: разказвателно, базирана на чиста речева логика.
Най-често работи при по-очевидни примери, за какъвто можем да счетем евентуално и този. Би изглеждало нещо такова:
Да допуснем, че даденото е изпълнено, т.е. $(A\cap B)\times (C\cup D) = (A\times C)\cap(B\times D)$.
Отляво имаме декартово произведение, чиито елементи са наредени двойки от вида $(x, y)$, където $x\in (A\cap B)$ и $y\in (C\cup D)$.
Отдясно на свой ред имаме сечение на декартови произведения, т.е. всяка една двойка $(x, y)$ от лявата страна (за които двойки казахме вече какво е в сила) също е в сила, че $(x, y)\in A\times C$ и $(x,y)\in B\times D$, т.е. $x\in A$ и $y\in C$ и $x\in B$ и $y\in D$. Което обаче е равносилно на $x \in A\cap B$ и $y\in C\cap D$, т.е. $(x, y) \in (A\cap B)\times(C\cap D)$
Поради равенството важи и обратната посока (т.е. за всяка двойка от дясната страна е в сила и лявата страна).
Значи получихме, че $(A\cap B)\times (C\cup D) = (A\cap B)\times(C\cap D)$.

Дотук преформулирахме даденото равенство в условието. Сега си задаваме въпроса: какво ни е нужно, за да е изпълнено то?

Първи случай (и много важно да не се изпусне!):
- Ако $A\cap B = \emptyset$, то равенството е очевидно изпълнено.

В противен случай вече тривиално (по дефиниция за декартов продукт) достатъчно условие е $C\cup D = C\cap D$.
Продължаваме с натуралните разсъждения. Какво ни казва така полученото равенство?
Ами казва ни, с прости думички, че: всеки елемент от обединението на C и D е също елемент на сечението им... и обратното. Тоест, ако вземем елемент от С, то той трябва да е в D; аналогично - ако вземем елемент от D, то той трябва да е в C. С което чисто логически описахме дефиницията на "равенство на две множества". Значи търсеното условие в този случай е $C = D$.

И така окончателен отговор е: достатъчно условие е $A \cap B = \emptyset$ или $C = D$.

Лично на мен обаче често не ми се губи време в изписване на думички... пък и ме помързява... пък и наистина, лирическите описания невинаги ми помагат много да структурирам мисълта си и да проследя закономерностите оптимално. За щастие затова си имаме формални нотации, към които аз повечко залитам (и понякога злоупотребявам с тях )

Стигаме до втори подход: абсолютно формално в чисто алгебрична форма.
Работи винаги.
Та, просто за сравнение, същата писаница отгоре може да бъде формулирана формално така:
$(A\cap B)\times (C\cup D) = (A\times C)\cap(B\times D)$
$\equiv \forall x, y\bigg(x\in A \land x\in B \land (y\in C\lor y\in D) \Longleftrightarrow x\in A\land y\in C\land x\in B \land y\in D\bigg)$

За улеснение, в тази ситуация можем да положим булеви променливи със стойности: $a = x\in A, b = x\in B, c = y\in C, d = y\in D$. Но генерално, такъв тип твърдения (наречени предикати) е добре да се дефинират като функция на дадения елемент (например $a(x) = x\in A$). В случая обаче дадените елементи $x, y$ винаги си вървят в комплектче с принадлежност към даденото множество, което ни позволява директно да полагаме целите твърдения с булеви променливи.
Също за улеснение и поради защото ме мързи да преписвам, ще си спестя квантора с мотива, че преформулирам еквивалентно израза в скобите. Кванторът не променя тази еквивалентност, но за коректност принципно е добре да си го лепнем отново накрая, когато формулираме следствието... Както и да е, де, можем да формализираме още много, но става леко излишно и пренатруфено, а искам да се фокусирам върху интуицията.

Така, и сега вече нещата са изнесени изцяло в контекста на булевата алгебра (в което аз намирам невероятна изящност ):

$$\begin{aligned}&\equiv& a\land b\land (c\lor d) &\Longleftrightarrow a\land c\land b\land d\\
&\equiv& (a\land b) &\Longrightarrow (c\lor d \Leftrightarrow c\land d)\\
&\equiv& (a\land b) &\Longrightarrow (\lnot(c\lor d\lor (c\land d))~~\lor~~ ((c\lor d)\land c\land d))\\
&\equiv& (a\land b) &\Longrightarrow (\lnot(c\lor d)~~ \lor~~ (c\land d))\\
&\equiv& (a\land b) &\Longrightarrow (c \Longleftrightarrow d)\\
&\equiv& \lnot a \lor \lnot b \lor (c \Leftrightarrow d)\end{aligned}$$

За да не се чудиш откъде на къде твърденията са равносилни, ще изброя последователно законите, които използвахме във всяка стъпка:
1) $a\land b \Leftrightarrow a\land c \equiv a \Longrightarrow (b\Leftrightarrow c)$
2) $a\Leftrightarrow b \equiv \lnot(a\lor b)\lor(a\land b) \equiv (\lnot a\land \lnot b)\lor(a\land b)$
3) $a \lor (a\land b) \equiv a\land(a\lor b) \equiv a$
4) отново 2), но наобратно
5) дефиницията на импликация: $a \Rightarrow b \equiv \lnot a \lor b$

Показаното горе беше праволинейното следване на законите, докато тъпо и упорито не стигнем до каквото искаме. Ако вкараме малко алгебрична хитрост обаче, можем да си съкратим работата:
Нека вземем този израз, който получихме вдясно от импликацията на втория ред:
$c\lor d \Longleftrightarrow c\land d$
Можем да докажем, че е еквивалентен на $c \Leftrightarrow d$ чрез същото наблюдение от по-горния параграф:
Нека $c = 0 \equiv (0 \lor d \Leftrightarrow 0\land d) \equiv (d \Leftrightarrow 0) \equiv d = 0$
Нека $c = 1 \equiv (1 \lor d \Leftrightarrow 1\land d) \equiv (1 \Leftrightarrow d) \equiv d = 1$
И с това получихме еднозначно съответствие между $d$ и $c$, следователно можем да заключим, чe $c\lor d \Longleftrightarrow c\land d \equiv d \Leftrightarrow c$.

И така, като си лепнем удобно игнорираните квантори отново, получаваме абсолютно идентично изказване от горния подход:
$\forall x, y\bigg(\lnot a \lor \lnot b\lor (c \Leftrightarrow d)\bigg)$
$\Longleftrightarrow \forall x(\lnot a \lor \lnot b) ~\lor~ \forall y(c \Leftrightarrow d )$
$\Longleftrightarrow \nexists x(a \land b) ~\lor~ \forall y(c \Leftrightarrow d)$
$\Longleftrightarrow \nexists x(x\in A \land x\in B) ~\lor~ \forall y(y\in C \Leftrightarrow y\in D)$
$\Longleftrightarrow A\cap B = \emptyset ~\lor~ C = D$

Също, често ще ти е полезно да кривваш от следването на логическите преобразувания и с малко по-креативно използване на тавтологии (много полезен трик, учудващо често...) лесно и правдободобно ще можеш да изведеш търсената еквивалентност (без да разбиваш оператора "$\Leftrightarrow$" на елементарните му части, например). Разбира се, този тип "натъкмяване" е полезен най-често, когато доказваш нещо, т.е. предварително знаеш какво искаш да получиш. Другият вариант е да си в търсене на някакво опростяване на даден по-сложен булев израз и да имаш интуитивна идея, но там вече е фрийстайл и интуицията идва с опита.

Няма да споменавам за практическата сила на "таблиците на истинността", които просто правят доказването на еквивалентности детска игра... Нещо подобно, но в опростен вид, използвахме по-горе когато давахме конкретни стойности на променливите. Но повечето образователни институции забраняват доказването на тъждества с този метод, понеже не носи много логическа изследователска стойност.

Та, обобщено:
Основен плюс на този подход, е че извършваш (макар и в някои случаи излишно тегави, но!) еквивалентни преобразувания. Което убива нуждата от разглеждане на случаи, допускания, противоречия и (най-сладкото) разглеждане "на двете посоки".

Разбира се, минусите също ги има и вероятно са очевидни - за много хора е по-трудно за четене и схващане отколкото описанията на естествен език. Лично за мен обаче (и съм се конфронтирал с доста хора по този въпрос), четенето на логически символи вместо думички като "и", "или", "е елемент на", "следва", "е равносилно", "ако...., то....", в много от по-комплексните контексти всъщност е по-праволинейно и четливо, понеже можеш да развиеш чисто алгебричната интуиция, базирана на формалните закони на булевата алгебра. Което превръща огромни тегави зависимости, в които можеш да се оплетеш десет пъти докато ги описваш с изречения, в наистина просто една алгебрична зависимост, която за по-тренираното око често е дори очевидна!

В крайна сметка, изводът от моя опит е: балансът е някъде в златната среда. И двата подхода са правилни, оставено е на теб да си прецениш с кой да работиш, стига да успяваш да поддържаш коректност и сам да не се оплиташ. Моят избор е по-формалният, много хора залагат на разказвателния подход; най-често обаче комбинация от двете се оказва оптимална.

Булевата алгебра е може би един от най-често приложимите дялове от математиката; цялата ни реч и начинът ни на мислене са базирани на закономерностите, които тя формализира. Така че познаването на (по мое мнение) не толкова трудоемките й закони със сигурност само ще ти помогне.

Добро обобщение на основните закони, както и мотивацията за тях (по доста достъпен логически път, според мен), има в много източници из интернет. Аз лично се накефих на този пичага. Добра последователност, малко практически приложения и малко упражнения. Общо взето добър старт в цялата нестрашна философия на булевата алгебра.

Това е от мен, надявам се да ти бях полезен.

[Гост]

Нищо не разбрах ама е много яко!

[Davids]

И така окончателен отговор е: достатъчно условие е $A \cap B = \emptyset$ или $C = D$.

Всъщност, това твърдение е вярно, но не е най-коректното възможно. При така поставеният въпрос на задачата, е добре да се замислим за понятията "необходимо" и "достатъчно" условия. А конкретният пример е много добро онаглеждение.
Нека $A$ е някакво съждение.
"Необходимо" условие за $A$ е всяко такова условие $B$, без което $A$ не може да е вярно. С други думи, няма как $B$ да не е вярно, а $A$ да е вярно. Ако се замислим малко, това е точно смисловата дефиниция на импликацията $A \Rightarrow B$.
Тоест, "необходимо"-то условие е отдясно на импликацията: $A \Rightarrow B$.

Аналогично, "достатъчно" условие за $A$ е всяко такова условие $B$, от което следва $A$. С други думи, $B$ ни гарантира, че $A$ ще е изпълнено; или $B \Rightarrow A$.
Тоест, "достатъчно"-то условие е отляво на импликацията: $B \Rightarrow A$.

Сега вече лесно можем да видим, че ако едно условие $B$ е "необходимо и достатъчно" за $A$, то $(B\Rightarrow A) \land (A\Rightarrow B)$, което е абсолютно равносилно по дефиниция на $A \Leftrightarrow B$.
Тоест, "необходимо и достатъчно" условие за $A$ е всяко такова условие $B$, което е еквивалентно на $A$.

Взимайки това предвид, задачата ни пита: "при какви условия е изпълнено, че....".
Значи:
$A\cap B = \emptyset$ е достатъчно условие.
$C = D$ също е достатъчно условие.
НО нито едно от тях не е само по себе си необходимо! Защо? Защото винаги можем да не изпълним едното, а да изпълним другото; тогава търсеното равенство пак ще е изпълнено.

С това да стигнем до същинската поправка на цитата:

И така окончателен отговор е: необходимо и достатъчно условие е $A \cap B = \emptyset$ или $C = D$.