Математическа логика и теория на множествата - трудни задачи с решения

Решение:
Нека [tex]T[/tex], [tex]H[/tex], [tex]F[/tex] са множествата на учениците, които бягат, играят хандбал и играят футбол. Всеки ученик практикува поне един спорт, затова [tex]|T\cup H\cup F|=40[/tex]. По формулата за включване и изключване
[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]
Търсените ученици образуват множеството [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]
Проверка: седемте области на диаграмата на Вен съдържат [tex]5[/tex] (само бягане), [tex]5[/tex] (само хандбал), [tex]9[/tex] (само футбол), [tex]3[/tex] (само бягане и хандбал), [tex]8[/tex] (само хандбал и футбол), [tex]6[/tex] (само бягане и футбол) и [tex]4[/tex] (и трите спорта) ученици; всички числа са неотрицателни и сборът им е [tex]40[/tex].

Решение:
Всички елементи на [tex]D_y[/tex] са нечетни. Ако [tex]x[/tex] е нечетно и [tex]x\ge 3[/tex], сборът [tex]x+y[/tex] е четен и [tex]x+y\ge 4[/tex], следователно не е просто число. В частност [tex]P(3,y)[/tex] е невярно за всяко [tex]y\in D_y[/tex].
Следователно [tex]\forall x\,\exists y\,P(x,y)[/tex] е невярно (не е изпълнено за [tex]x=3[/tex]), а също [tex]\exists y\,\forall x\,P(x,y)[/tex] е невярно (за всяко [tex]y[/tex] условието не е изпълнено при [tex]x=3[/tex]).
При [tex]x=6[/tex] всички сборове са прости числа:
[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]
следователно [tex]\exists x\,\forall y\,P(x,y)[/tex] е вярно. Тогава е вярно и [tex]\forall y\,\exists x\,P(x,y)[/tex] (за всяко [tex]y[/tex] вземаме [tex]x=6[/tex]), затова отрицанието му [tex]\exists y\,\forall x\,\neg P(x,y)[/tex] е невярно.
Единственото вярно съждение сред предложените е [tex]\exists x\,\forall y\,P(x,y)[/tex].

Решение:
Всяка двойка [tex](a,b)\in R_1[/tex] се комбинира с всяка двойка [tex](b,c)\in R_2[/tex], започваща със същото [tex]b[/tex], и дава [tex](a,c)\in R_1\mathbin{\char59}R_2[/tex]. В [tex]R_2[/tex] няма двойка, започваща с [tex]2[/tex], затова [tex](1,2)[/tex] и [tex](2,2)[/tex] не дават нищо. Останалите двойки от [tex]R_1[/tex] дават:
[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]
Следователно
[tex]R_1\mathbin{\char59}R_2=\{(1,1),(2,3),(2,4),(3,3),(3,4),(4,1)\}[/tex]
Редът е от значение: [tex]R_2\mathbin{\char59}R_1=\{(1,2),(1,3),(1,4),(3,2),(3,3),(4,3),(4,4)\}[/tex] е друга релация.

Решение:
Рефлексивност: за всяко [tex]X[/tex] имаме [tex]X\subseteq X[/tex] и [tex]|X\setminus X|=|\varnothing|=0\le 1[/tex], затова [tex]X\,R\,X[/tex].
Симетричност няма: [tex]\varnothing\,R\,\{1\}[/tex], защото [tex]\varnothing\subseteq\{1\}[/tex] и [tex]|\{1\}\setminus\varnothing|=1[/tex], но [tex]\{1\}\,R\,\varnothing[/tex] не е изпълнено, защото [tex]\{1\}\not\subseteq\varnothing[/tex].
Антисиметричност: ако [tex]X\,R\,Y[/tex] и [tex]Y\,R\,X[/tex], то [tex]X\subseteq Y[/tex] и [tex]Y\subseteq X[/tex], следователно [tex]X=Y[/tex].
Транзитивност няма: [tex]\varnothing\,R\,\{1\}[/tex] и [tex]\{1\}\,R\,\{1,2\}[/tex], но [tex]|\{1,2\}\setminus\varnothing|=2\gt 1[/tex], затова [tex]\varnothing\,R\,\{1,2\}[/tex] не е изпълнено.
Следователно [tex]R[/tex] е рефлексивна и антисиметрична, но не е симетрична и не е транзитивна (в частност не е нито частична наредба, нито релация на еквивалентност).

Решение:
Полиномът на Жегалкин на [tex]f[/tex] е единствен и има вида (всички операции са по модул [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]
От вектора на стойностите имаме
[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]
Заместваме точките по реда на нарастване на броя на единиците:
[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]
Следователно
[tex]f=1\oplus x_1\oplus x_2\oplus x_2x_3\oplus x_1x_2x_3[/tex]

Решение:
Нека [tex]F[/tex] е броят на неверните съждения в [tex]A[/tex], [tex]0\le F\le 12[/tex]. По съдържанието си [tex]p_i[/tex] е вярно точно когато [tex]F\ge i[/tex].
Значи верните съждения са точно [tex]p_1,\ldots,p_F[/tex], а неверните са [tex]p_{F+1},\ldots,p_{12}[/tex]. Преброяваме неверните съждения по два начина:
[tex]12-F=F\Rightarrow F=6[/tex]
Проверка: ако [tex]p_1,\ldots,p_6[/tex] са верни, а [tex]p_7,\ldots,p_{12}[/tex] са неверни, то неверните съждения са точно [tex]6[/tex] и „поне [tex]i[/tex] са неверни“ е вярно точно за [tex]i\le 6[/tex], което съвпада с приетото. Тъй като [tex]F=6[/tex] е единствената възможност, верните съждения са точно [tex]6[/tex].

Решение:
Първо опростяваме дясната страна:
[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]
Тъй като [tex]C\cap D\subseteq C\cup D[/tex], дясната страна винаги се съдържа в лявата. Ако [tex]A\cap B=\varnothing[/tex], двете страни са празни и равенството е изпълнено.
Нека [tex]A\cap B\ne\varnothing[/tex]; фиксираме [tex]x_0\in A\cap B[/tex] и допускаме, че равенството е изпълнено. За всяко [tex]y\in C\cup D[/tex] двойката [tex](x_0,y)[/tex] е в лявата страна, следователно и в [tex](A\cap B)×(C\cap D)[/tex], т.е. [tex]y\in C\cap D[/tex]. Така [tex]C\cup D\subseteq C\cap D[/tex] и значи
[tex]C\subseteq C\cup D\subseteq C\cap D\subseteq D[/tex]
и аналогично [tex]D\subseteq C[/tex], т.е. [tex]C=D[/tex]. Обратно, ако [tex]C=D[/tex], то [tex]C\cup D=C\cap D[/tex] и двете страни съвпадат. Следователно равенството е изпълнено тогава и само тогава, когато [tex]A\cap B=\varnothing[/tex] или [tex]C=D[/tex].

Решение:
Работим в универсално множество [tex]U[/tex], съдържащо [tex]A[/tex], [tex]B[/tex] и [tex]C[/tex]. За [tex]X\subseteq U[/tex] нека [tex]\chi_X[/tex] е характеристичната му функция:
[tex]\chi_X(x)=\begin{cases}1, & x\in X\\ 0, & x\notin X\end{cases}[/tex]
Две подмножества на [tex]U[/tex] са равни точно когато характеристичните им функции са равни. По дефиниция [tex]x\in X\triangle Y[/tex] точно когато [tex]x[/tex] принадлежи на точно едно от множествата [tex]X[/tex] и [tex]Y[/tex], т.е. точно една от стойностите [tex]\chi_X(x)[/tex] и [tex]\chi_Y(x)[/tex] е равна на [tex]1[/tex]. Следователно
[tex]\chi_{X\triangle Y}=\chi_X\oplus\chi_Y[/tex]
където [tex]\oplus[/tex] е събиране по модул [tex]2[/tex]: [tex]0\oplus 0=1\oplus 1=0[/tex], [tex]0\oplus 1=1\oplus 0=1[/tex]. Прилагайки това два пъти, получаваме
[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]
Събирането по модул [tex]2[/tex] е асоциативно (това е обикновено събиране на цели числа, последвано от вземане на остатъка при деление на [tex]2[/tex]), затова двете характеристични функции съвпадат във всяка точка [tex]x\in U[/tex]. Следователно [tex]A\triangle(B\triangle C)=(A\triangle B)\triangle C[/tex]. С думи: и двете страни се състоят точно от елементите, които принадлежат на нечетен брой (едно или три) от множествата [tex]A[/tex], [tex]B[/tex], [tex]C[/tex].

Решение:
Поради асоциативността на композицията [tex]f^a \circ f^b = f^{a+b}[/tex] за всички естествени [tex]a, b[/tex], а всяка степен [tex]f^m[/tex] е биекция на [tex]S[/tex] върху себе си, тъй като композиция на биекции е биекция.
Ако [tex]S[/tex] има [tex]k[/tex] елемента, биекциите [tex]S \to S[/tex] са само [tex]k![/tex], затова в безкрайната редица [tex]f^1, f^2, f^3, \ldots[/tex] има повторение: [tex]f^i = f^j[/tex] за някои [tex]1 \le i \lt j[/tex]. Нека [tex]m = j - i \ge 1[/tex]. Тогава
[tex]f^m \circ f^i = f^{m+i} = f^j = f^i[/tex]
Като композираме двете страни отдясно с обратната функция на биекцията [tex]f^i[/tex], получаваме [tex]f^m = \mathrm{id}_S[/tex]. Нека сега [tex]n = 2m - 1 \ge 1[/tex]. Тогава
[tex]f^n \circ f = f \circ f^n = f^{2m} = f^m \circ f^m = \mathrm{id}_S[/tex]
следователно [tex]f^n[/tex] е двустранна обратна на [tex]f[/tex]. Обратната функция на биекция е единствена, затова [tex]f^{-1} = f^n[/tex].
(Избираме [tex]n = 2m - 1[/tex], а не [tex]m - 1[/tex], за да е [tex]n \ge 1[/tex] и когато [tex]m = 1[/tex], т.е. когато [tex]f = \mathrm{id}_S[/tex].)