3180. Skupovi i skupovne operacije

TEKST ZADATKA

Dokazati da važi: $(A \setminus B) \times C = (A \times C) \setminus (B \times C)$ ;

REŠENJE ZADATKA

Dokaz ćemo sprovesti pokazujući da proizvoljan uređeni par $(x, y)$ pripada levoj strani jednakosti ako i samo ako pripada desnoj strani.

Polazimo od definicije Dekartovog proizvoda za levu stranu jednakosti:

(x, y) \in (A \setminus B) \times C \iff x \in (A \setminus B) \land y \in C

Primenjujemo definiciju razlike skupova na prvi deo izraza:

\iff (x \in A \land x \notin B) \land y \in C

Koristimo asocijativnost i komutativnost logičkog I ( $\land$ ) da grupišemo iskaze drugačije:

\iff (x \in A \land y \in C) \land x \notin B

S obzirom na to da važi $y \in C ,$ iskaz $x \notin B$ je ekvivalentan iskazu $x \notin B \lor y \notin C .$ Ovo važi jer je $y \notin C$ netačno, pa tačnost disjunkcije zavisi isključivo od $x \notin B :$

\iff (x \in A \land y \in C) \land (x \notin B \lor y \notin C)

Primenjujemo De Morganov zakon na drugi deo izraza kako bismo izvukli negaciju:

\iff (x \in A \land y \in C) \land \neg(x \in B \land y \in C)

Prepoznajemo definiciju Dekartovog proizvoda u oba dela izraza:

\iff (x, y) \in A \times C \land \neg((x, y) \in B \times C)

Zapisujemo negaciju pripadnosti skupu na standardan način:

\iff (x, y) \in A \times C \land (x, y) \notin B \times C

Na kraju, primenjujemo definiciju razlike skupova, čime dobijamo desnu stranu jednakosti:

\iff (x, y) \in (A \times C) \setminus (B \times C)

Pošto smo pokazali ekvivalenciju za proizvoljan element, zaključujemo da su skupovi jednaki, čime je dokaz završen.

(A \setminus B) \times C = (A \times C) \setminus (B \times C)

66.v