Matematička logika i teorija skupova - teški zadaci sa rešenjima

Rešenje:
Neka su [tex]T[/tex], [tex]H[/tex], [tex]F[/tex] skupovi učenika koji trče, igraju rukomet i igraju fudbal. Svaki učenik se bavi bar jednim sportom, pa je [tex]|T\cup H\cup F|=40[/tex]. Prema principu uključenja i isključenja
[tex]|T\cup H\cup F|=|T|+|H|+|F|-|T\cap H|-|H\cap F|-|T\cap F|+|T\cap H\cap F|[/tex]
[tex]40=18+20+27-7-12-|T\cap F|+4=50-|T\cap F|\ \Rightarrow\ |T\cap F|=10[/tex]
Traženi učenici čine skup [tex](T\cap F)\setminus H[/tex]:
[tex]|(T\cap F)\setminus H|=|T\cap F|-|T\cap H\cap F|=10-4=6[/tex]
Provera: sedam oblasti Venovog dijagrama sadrže [tex]5[/tex] (samo trčanje), [tex]5[/tex] (samo rukomet), [tex]9[/tex] (samo fudbal), [tex]3[/tex] (samo trčanje i rukomet), [tex]8[/tex] (samo rukomet i fudbal), [tex]6[/tex] (samo trčanje i fudbal) i [tex]4[/tex] (sva tri sporta) učenika; svi brojevi su nenegativni i njihov zbir je [tex]40[/tex].

Rešenje:
Svi elementi skupa [tex]D_y[/tex] su neparni. Ako je [tex]x[/tex] neparan i [tex]x\ge 3[/tex], zbir [tex]x+y[/tex] je paran i [tex]x+y\ge 4[/tex], pa nije prost broj. Posebno, [tex]P(3,y)[/tex] je netačno za svako [tex]y\in D_y[/tex].
Zato je [tex]\forall x\,\exists y\,P(x,y)[/tex] netačno (ne važi za [tex]x=3[/tex]), a netačno je i [tex]\exists y\,\forall x\,P(x,y)[/tex] (ni za jedno [tex]y[/tex] ne važi pri [tex]x=3[/tex]).
Za [tex]x=6[/tex] svi zbirovi su prosti brojevi:
[tex]6+1=7 ; \quad 6+5=11 ; \quad 6+7=13[/tex]
[tex]6+11=17 ; \quad 6+13=19 ; \quad 6+17=23[/tex]
pa je [tex]\exists x\,\forall y\,P(x,y)[/tex] tačno. Tada je tačno i [tex]\forall y\,\exists x\,P(x,y)[/tex] (za svako [tex]y[/tex] uzimamo [tex]x=6[/tex]), pa je njegova negacija [tex]\exists y\,\forall x\,\neg P(x,y)[/tex] netačna.
Jedini tačan iskaz među ponuđenima je [tex]\exists x\,\forall y\,P(x,y)[/tex].

Rešenje:
Svaki par [tex](a,b)\in R_1[/tex] kombinuje se sa svakim parom [tex](b,c)\in R_2[/tex] koji počinje istim [tex]b[/tex] i daje [tex](a,c)\in R_1\mathbin{\char59}R_2[/tex]. U [tex]R_2[/tex] nema para koji počinje sa [tex]2[/tex], pa [tex](1,2)[/tex] i [tex](2,2)[/tex] ne daju ništa. Ostali parovi iz [tex]R_1[/tex] daju:
[tex](1,3)\in R_1\land(3,1)\in R_2\ \Rightarrow\ (1,1)[/tex]
[tex](2,4)\in R_1\land(4,3),(4,4)\in R_2\ \Rightarrow\ (2,3),(2,4)[/tex]
[tex](3,4)\in R_1\land(4,3),(4,4)\in R_2\ \Rightarrow\ (3,3),(3,4)[/tex]
[tex](4,3)\in R_1\land(3,1)\in R_2\ \Rightarrow\ (4,1)[/tex]
Dakle,
[tex]R_1\mathbin{\char59}R_2=\{(1,1),(2,3),(2,4),(3,3),(3,4),(4,1)\}[/tex]
Redosled je bitan: [tex]R_2\mathbin{\char59}R_1=\{(1,2),(1,3),(1,4),(3,2),(3,3),(4,3),(4,4)\}[/tex] je druga relacija.

Rešenje:
Refleksivnost važi: za svako [tex]X[/tex] je [tex]X\subseteq X[/tex] i [tex]|X\setminus X|=|\varnothing|=0\le 1[/tex], pa je [tex]X\,R\,X[/tex].
Simetričnost ne važi: [tex]\varnothing\,R\,\{1\}[/tex], jer je [tex]\varnothing\subseteq\{1\}[/tex] i [tex]|\{1\}\setminus\varnothing|=1[/tex], ali [tex]\{1\}\,R\,\varnothing[/tex] ne važi, jer [tex]\{1\}\not\subseteq\varnothing[/tex].
Antisimetričnost važi: ako je [tex]X\,R\,Y[/tex] i [tex]Y\,R\,X[/tex], onda je [tex]X\subseteq Y[/tex] i [tex]Y\subseteq X[/tex], pa je [tex]X=Y[/tex].
Tranzitivnost ne važi: [tex]\varnothing\,R\,\{1\}[/tex] i [tex]\{1\}\,R\,\{1,2\}[/tex], ali [tex]|\{1,2\}\setminus\varnothing|=2\gt 1[/tex], pa [tex]\varnothing\,R\,\{1,2\}[/tex] ne važi.
Dakle, [tex]R[/tex] je refleksivna i antisimetrična, ali nije ni simetrična ni tranzitivna (posebno, nije ni relacija parcijalnog poretka ni relacija ekvivalencije).

Rešenje:
Žegalkinov polinom funkcije [tex]f[/tex] je jedinstven i ima oblik (sve operacije su po modulu [tex]2[/tex])
[tex]f=a_0\oplus a_1x_1\oplus a_2x_2\oplus a_3x_3\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus a_{23}x_2x_3\oplus a_{123}x_1x_2x_3[/tex]
Iz vektora vrednosti je
[tex]f(0,0,0)=1 ; \ f(0,0,1)=1 ; \ f(0,1,0)=0 ; \ f(0,1,1)=1[/tex]
[tex]f(1,0,0)=0 ; \ f(1,0,1)=0 ; \ f(1,1,0)=1 ; \ f(1,1,1)=1[/tex]
Zamenjujemo tačke redom, po rastućem broju jedinica:
[tex]f(0,0,0)=a_0=1[/tex]
[tex]f(1,0,0)=a_0\oplus a_1=0\Rightarrow a_1=1[/tex]
[tex]f(0,1,0)=a_0\oplus a_2=0\Rightarrow a_2=1[/tex]
[tex]f(0,0,1)=a_0\oplus a_3=1\Rightarrow a_3=0[/tex]
[tex]f(1,1,0)=a_0\oplus a_1\oplus a_2\oplus a_{12}=1\oplus a_{12}=1\Rightarrow a_{12}=0[/tex]
[tex]f(1,0,1)=a_0\oplus a_1\oplus a_3\oplus a_{13}=a_{13}=0[/tex]
[tex]f(0,1,1)=a_0\oplus a_2\oplus a_3\oplus a_{23}=a_{23}=1[/tex]
[tex]f(1,1,1)=1\oplus 1\oplus 1\oplus 0\oplus 0\oplus 0\oplus 1\oplus a_{123}=a_{123}=1[/tex]
Dakle,
[tex]f=1\oplus x_1\oplus x_2\oplus x_2x_3\oplus x_1x_2x_3[/tex]

Rešenje:
Neka je [tex]F[/tex] broj netačnih iskaza u [tex]A[/tex], [tex]0\le F\le 12[/tex]. Po svom sadržaju, [tex]p_i[/tex] je tačan ako i samo ako je [tex]F\ge i[/tex].
Dakle, tačni su upravo iskazi [tex]p_1,\ldots,p_F[/tex], a netačni su [tex]p_{F+1},\ldots,p_{12}[/tex]. Brojeći netačne iskaze na dva načina, dobijamo:
[tex]12-F=F\Rightarrow F=6[/tex]
Provera: ako su [tex]p_1,\ldots,p_6[/tex] tačni, a [tex]p_7,\ldots,p_{12}[/tex] netačni, onda je netačno upravo [tex]6[/tex] iskaza, pa „bar [tex]i[/tex] je netačno” važi upravo za [tex]i\le 6[/tex], što se slaže sa pretpostavkom. Pošto je [tex]F=6[/tex] jedina mogućnost, tačno je upravo [tex]6[/tex] iskaza.

Rešenje:
Najpre uprostimo desnu stranu:
[tex](x,y)\in(A×C)\cap(B×D)\Leftrightarrow x\in A\cap B\ \land\ y\in C\cap D[/tex]
[tex](A×C)\cap(B×D)=(A\cap B)×(C\cap D)[/tex]
Pošto je [tex]C\cap D\subseteq C\cup D[/tex], desna strana je uvek sadržana u levoj. Ako je [tex]A\cap B=\varnothing[/tex], obe strane su prazne i jednakost važi.
Neka je [tex]A\cap B\ne\varnothing[/tex]; fiksirajmo [tex]x_0\in A\cap B[/tex] i pretpostavimo da jednakost važi. Za svako [tex]y\in C\cup D[/tex] par [tex](x_0,y)[/tex] pripada levoj strani, pa i skupu [tex](A\cap B)×(C\cap D)[/tex], tj. [tex]y\in C\cap D[/tex]. Dakle, [tex]C\cup D\subseteq C\cap D[/tex], pa je
[tex]C\subseteq C\cup D\subseteq C\cap D\subseteq D[/tex]
i analogno [tex]D\subseteq C[/tex], tj. [tex]C=D[/tex]. Obrnuto, ako je [tex]C=D[/tex], onda je [tex]C\cup D=C\cap D[/tex] i obe strane se poklapaju. Prema tome, jednakost važi ako i samo ako je [tex]A\cap B=\varnothing[/tex] ili [tex]C=D[/tex].

Rešenje:
Radimo u univerzalnom skupu [tex]U[/tex] koji sadrži [tex]A[/tex], [tex]B[/tex] i [tex]C[/tex]. Za [tex]X\subseteq U[/tex] neka je [tex]\chi_X[/tex] njegova karakteristična funkcija:
[tex]\chi_X(x)=\begin{cases}1, & x\in X\\ 0, & x\notin X\end{cases}[/tex]
Dva podskupa skupa [tex]U[/tex] su jednaka ako i samo ako su im karakteristične funkcije jednake. Po definiciji, [tex]x\in X\triangle Y[/tex] ako i samo ako [tex]x[/tex] pripada tačno jednom od skupova [tex]X[/tex] i [tex]Y[/tex], tj. tačno jedna od vrednosti [tex]\chi_X(x)[/tex] i [tex]\chi_Y(x)[/tex] jednaka je [tex]1[/tex]. Zato je
[tex]\chi_{X\triangle Y}=\chi_X\oplus\chi_Y[/tex]
gde je [tex]\oplus[/tex] sabiranje po modulu [tex]2[/tex]: [tex]0\oplus 0=1\oplus 1=0[/tex], [tex]0\oplus 1=1\oplus 0=1[/tex]. Primenom ovoga dva puta dobijamo
[tex]\chi_{A\triangle(B\triangle C)}=\chi_A\oplus(\chi_B\oplus\chi_C)[/tex]
[tex]\chi_{(A\triangle B)\triangle C}=(\chi_A\oplus\chi_B)\oplus\chi_C[/tex]
Sabiranje po modulu [tex]2[/tex] je asocijativno (to je obično sabiranje celih brojeva posle kojeg se uzima ostatak pri deljenju sa [tex]2[/tex]), pa se dve karakteristične funkcije poklapaju u svakoj tački [tex]x\in U[/tex]. Prema tome, [tex]A\triangle(B\triangle C)=(A\triangle B)\triangle C[/tex]. Rečima: obe strane se sastoje upravo od elemenata koji pripadaju neparnom broju (jednom ili trima) od skupova [tex]A[/tex], [tex]B[/tex], [tex]C[/tex].

Rešenje:
Zbog asocijativnosti kompozicije važi [tex]f^a \circ f^b = f^{a+b}[/tex] za sve prirodne [tex]a, b[/tex], a svaki stepen [tex]f^m[/tex] je bijekcija skupa [tex]S[/tex] na sebe, jer je kompozicija bijekcija takođe bijekcija.
Ako [tex]S[/tex] ima [tex]k[/tex] elemenata, postoji samo [tex]k![/tex] bijekcija [tex]S \to S[/tex], pa se u beskonačnom nizu [tex]f^1, f^2, f^3, \ldots[/tex] neki član ponavlja: [tex]f^i = f^j[/tex] za neke [tex]1 \le i \lt j[/tex]. Neka je [tex]m = j - i \ge 1[/tex]. Tada je
[tex]f^m \circ f^i = f^{m+i} = f^j = f^i[/tex]
Komponovanjem obe strane zdesna sa inverznom funkcijom bijekcije [tex]f^i[/tex] dobijamo [tex]f^m = \mathrm{id}_S[/tex]. Neka je sada [tex]n = 2m - 1 \ge 1[/tex]. Tada je
[tex]f^n \circ f = f \circ f^n = f^{2m} = f^m \circ f^m = \mathrm{id}_S[/tex]
pa je [tex]f^n[/tex] obostrani inverz funkcije [tex]f[/tex]. Inverz bijekcije je jedinstven, zato je [tex]f^{-1} = f^n[/tex].
(Biramo [tex]n = 2m - 1[/tex], a ne [tex]m - 1[/tex], da bi bilo [tex]n \ge 1[/tex] i kada je [tex]m = 1[/tex], tj. kada je [tex]f = \mathrm{id}_S[/tex].)