Скупови – пример 2

Доказивање сложеније скуповне једнакости

Задаци

Текст задатака објашњених у видео лекцији.

Реши скуповну једнакост:

Пр.2 $A\backslash \left( {B \cup C} \right) = \left( {A\backslash B} \right) \cap \left( {A\backslash C} \right)$

Скуповне једнакостi решавамо тако што их преводимо у исказне формуле а затим показуjемо да су те формуле таутологије. Према дефеницији једнакости скупова, два скупа су једнакa ако и само ако за свако x ако x припада jедном скупу то је еквивалентно да x припада и другом скупу

$\left( {\forall х } \right)\left( {х \in \left( {А\backslash \left( {B \cup C} \right)} \right)} \right) \Leftrightarrow \left( {x \in \left( {\left( {А\backslash B} \right) \cap \left( {A\backslash C} \right)} \right)} \right)$

$\left( {\forall x} \right)\left( {x \in A \wedge x \notin \left( {B \cup C} \right)} \right) \Leftrightarrow \left( {x \in \left( {А\backslash B} \right) \wedge x \in \left( {A\backslash C} \right)} \right)$

$\left( {\forall х} \right)\left( {х \in A \wedge \neg \left( {x \in \left( {B \cup C} \right)} \right)} \right) \Leftrightarrow \left( {\left( {x \in A \wedge x \notin B} \right) \wedge \left( {x \in A \wedge \left( {x \notin C} \right)} \right)} \right)$

$\begin{aligned}&\left( {\forall х} \right)\left( {х \in A \wedge \neg \left( {x \in B \vee x \in C} \right)} \right) \Leftrightarrow \\ &\Leftrightarrow \left( {\left( {x \in A \wedge \neg \left( {x \in B} \right)} \right) \wedge \left( {x \in A \wedge \neg \left( {x \in C} \right)} \right)} \right)\end{aligned}$

Ако са p означимо $x \in A$ ,са q - $x \in B$ и са r - $x \in C$ , на оваj начин нашу скуповну једнакост преводимо у исказну форму, имамо $\left( {p \wedge \neg \left( {q \vee r} \right)} \right) \Leftrightarrow \left( {\left( {p \wedge \neg q} \right) \wedge \left( {p \wedge \neg r} \right)} \right)$

Показуjемо да добиjена формула таутологиjа табличнoм методом.

Са A означимо $p \wedge \neg q$ , са B означимо $p \wedge \neg r$ , са С означимо $p \wedge \neg \left( {q \vee r} \right)$ и са D означимо $\left( {p \wedge \neg q} \right) \wedge \left( {p \wedge \neg r} \right)$

$p$	$q$	$r$	$¬q$	$¬r$	$q\vee r$	$\neg\left( {q \vee r} \right)$	$C$	$A$	$B$	$D$	$C \Leftrightarrow D$
$\top$	$\top$	$\top$	$\bot$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$
$\top$	$\top$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\bot$	$\top$
$\top$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\bot$	$\bot$	$\top$	$\bot$	$\bot$	$\top$
$\top$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$
$\bot$	$\top$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$
$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$
$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$

Наша формула jе тачна за све вредности исказних слова, односно она jе таутологиjа. Ми смо показали да jе исказна формула таутологиja, односно наша скуповна jеднакост jе тачна.

Сложенија скуповна једнакост доказује се на исти начин као једноставна: обе стране се преведу у исказне формуле, па се таблицом провери да је њихова еквиваленција таутологија. Разлика се преводи као $x \in A \setminus B \Leftrightarrow p \wedge \neg q$ , а $x \notin B \cup C$ као $\neg(q \vee r)$ . Тако једнакост $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ постаје $(p \wedge \neg(q \vee r)) \Leftrightarrow ((p \wedge \neg q) \wedge (p \wedge \neg r))$ .

Кључ је Де Морганов закон $\neg(q \vee r) \Leftrightarrow (\neg q \wedge \neg r)$ : обе стране су тачне само за $p = \top$ , $q = r = \bot$ , а у осталих седам врста нетачне. На исти начин доказује се $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ . Честа грешка је да се унија и пресек не замене: $A \setminus (B \cup C)$ у општем случају није једнако $(A \setminus B) \cup (A \setminus C)$ .

Елемената у осенченом делу: 3

Кликните на

A \setminus (B \cup C)

, па на

(A \setminus B) \cap (A \setminus C)

: осенчен је исти део. Кад изаберете унију

(A \setminus B) \cup (A \setminus C)

, осенчи се више, па једнакост са унијом не важи.

Кад у претрази огласа искључите две агенције одједном, добијате исто као кад искључите сваку посебно, па узмете пресек; по истом закону раде црне листе у програмима за електронску пошту.

Обавештење о попусту

Књижара у Новом Саду шаље обавештење о попусту свим купцима са картицом ( $A$ ), осим онима који су се одјавили са обавештења ( $B$ ) и онима који су књигу већ купили ( $C$ ). Јелена одједном избацује $B \cup C$ , а Милош прави спискове $A \setminus B$ и $A \setminus C$ и узима њихов пресек. Докажите да увек добијају исти списак и проверите то за $A$ = {Ана, Бранко, Весна, Горан, Дејан, Ема}, $B$ = {Бранко, Горан} и $C$ = {Горан, Ема}.

Решење

Треба доказати $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ , тј. да је $(p \wedge \neg(q \vee r)) \Leftrightarrow ((p \wedge \neg q) \wedge (p \wedge \neg r))$ таутологија.
По Де Моргановом закону $\neg(q \vee r)$ има исту вредност као $\neg q \wedge \neg r$ , па је лева страна $p \wedge \neg q \wedge \neg r$ . Десна страна је исто то, јер се $p$ само понавља.
Обе стране су тачне само у врсти $p = \top$ , $q = r = \bot$ , а у осталих седам врста нетачне, па је формула таутологија.
Провера: $B \cup C$ = {Бранко, Горан, Ема}, па $A \setminus (B \cup C)$ = {Ана, Весна, Дејан}. Милош има $A \setminus B$ = {Ана, Весна, Дејан, Ема} и $A \setminus C$ = {Ана, Бранко, Весна, Дејан}, а њихов пресек је опет {Ана, Весна, Дејан}.

Одговор: Оба начина увек дају исти списак, а у примеру обавештење добијају Ана, Весна и Дејан.

Задатак за вежбу

Да ли за све скупове важи $A \setminus (B \cup C) = (A \setminus B) \cup (A \setminus C)$ ? Ако не важи, нађите контрапример.

Прикажи решење

Не важи. За $A = \{1, 2\}$ , $B = \{1\}$ и $C = \{2\}$ лева страна је $\emptyset$ , а десна $\{2\} \cup \{1\} = \{1, 2\}$ . У таблици се то види у врсти $p = \top$ , $q = \top$ , $r = \bot$ .