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

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

Задаци

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

Докажи скуповну једнакост:

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

Jеднакост jе $A \cup \left( {B \cup C} \right) = \left( {A \cup B} \right) \cup C$ еквивалентна сваком од наредних услова:

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

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

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

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

$p$	$q$	$r$	${q \vee r}$	$А$	${p \vee q}$	$В$	$A \Leftrightarrow B$
$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\top$	$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$
$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\bot$	$\top$	$\top$	$\top$	$\bot$	$\top$	$\top$
$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$

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

Скуповна једнакост се доказује тако што се преведе у исказну формулу. Два скупа $X$ и $Y$ су једнака ако за свако $x$ важи $x \in X \Leftrightarrow x \in Y$ . Означите $p: x \in A$ , $q: x \in B$ и $r: x \in C$ . Тада $x \in A \cup B$ постаје $p \vee q$ , $x \in A \cap B$ постаје $p \wedge q$ , а $x \notin A$ постаје $\neg p$ .

Једнакост $A \cup (B \cup C) = (A \cup B) \cup C$ тако прелази у $(p \vee (q \vee r)) \Leftrightarrow ((p \vee q) \vee r)$ . Ако је та формула таутологија, што се провери таблицом од осам врста, једнакост важи за све скупове. Због асоцијативности у $A \cup B \cup C$ заграде нису потребне. Пазите: провера на једном примеру или цртежу није доказ, али један контрапример јесте доказ да једнакост не важи.

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

Кликните редом на

(A \cup B) \cup C

и

A \cup (B \cup C)

: осенчен је исти део, јер је унија асоцијативна. Бојан и Вера су у по два скупа, али се у унији броје само једном.

Програми за базе података преуређују упите по законима као што су асоцијативност и дистрибутивност уније и пресека: резултат остаје исти, а рачуна се брже.

Спискови за такмичење

Школа у Шапцу саставља јединствен списак ученика за такмичење од три списка: $A$ = {Ана, Бојан, Вера}, $B$ = {Бојан, Дуња} и $C$ = {Вера, Ђорђе, Ема}. Секретарица спаја прво $A$ и $B$ , па додаје $C$ , а педагог прво спаја $B$ и $C$ , па додаје $A$ . Докажите да ће увек добити исти списак, ма какви били спискови, и проверите то на овим списковима.

Решење

Секретарица прави $(A \cup B) \cup C$ , а педагог $A \cup (B \cup C)$ . Са $p: x \in A$ , $q: x \in B$ и $r: x \in C$ једнакост постаје $((p \vee q) \vee r) \Leftrightarrow (p \vee (q \vee r))$ .
Обе стране су нетачне само у врсти $p = q = r = \bot$ , кад ученик није ни на једном списку, а у осталих седам врста обе су тачне.
Стране се поклапају у свих осам врста, па је формула таутологија и $(A \cup B) \cup C = A \cup (B \cup C)$ за све скупове.
Провера: $A \cup B$ = {Ана, Бојан, Вера, Дуња}, па $(A \cup B) \cup C$ = {Ана, Бојан, Вера, Дуња, Ђорђе, Ема}. Са друге стране $B \cup C$ = {Бојан, Дуња, Вера, Ђорђе, Ема}, па и $A \cup (B \cup C)$ има истих 6 ученика.

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

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

Истим поступком докажите дистрибутивни закон $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

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

Једнакост прелази у $(p \wedge (q \vee r)) \Leftrightarrow ((p \wedge q) \vee (p \wedge r))$ . Ако је $p = \bot$ , обе стране су $\bot$ ; ако је $p = \top$ , обе стране имају вредност $q \vee r$ . Стране се поклапају у свих осам врста, па је формула таутологија и једнакост важи.