Задача 1
В классе [tex]40[/tex] учеников, и каждый из них занимается хотя бы одним из видов спорта: бегом, гандболом или футболом. Бегом занимаются [tex]18[/tex] учеников, в гандбол играют [tex]20[/tex], в футбол — [tex]27[/tex], бегом и гандболом занимаются [tex]7[/tex], гандболом и футболом — [tex]12[/tex], а всеми тремя видами спорта — [tex]4[/tex] ученика. Сколько учеников занимаются бегом и играют в футбол, но не играют в гандбол?
Решение:
Пусть [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].
Задача 2
Дан предикат [tex]P(x,y)[/tex]: «[tex]x+y[/tex] — простое число», где [tex]x\in D_x=\{1,2,3,4,5,6,7\}[/tex] и [tex]y\in D_y=\{1,5,7,11,13,17\}[/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].
Задача 3
Пусть [tex]A=\{1,2,3,4\}[/tex], а [tex]R_1=\{(1,2),(1,3),(2,4),(2,2),(3,4),(4,3)\}[/tex] и [tex]R_2=\{(1,1),(1,2),(3,1),(4,3),(4,4)\}[/tex] — отношения на множестве [tex]A[/tex]. Их композиция определяется как [tex]R_1\mathbin{\char59}R_2=\{(a,c) : \exists b\in A\ ((a,b)\in R_1\land(b,c)\in R_2)\}[/tex]. Найдите [tex]R_1\mathbin{\char59}R_2[/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] — другое отношение.
Задача 4
Пусть [tex]\mathcal{P}(\mathbb{Z})[/tex] — множество всех подмножеств [tex]\mathbb{Z}[/tex], а [tex]R[/tex] — отношение на [tex]\mathcal{P}(\mathbb{Z})[/tex], заданное условием [tex]X\,R\,Y\Leftrightarrow X\subseteq Y[/tex] и [tex]|Y\setminus X|\le 1[/tex]. Какими из свойств рефлексивности, симметричности, антисимметричности и транзитивности обладает [tex]R[/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] рефлексивно и антисимметрично, но не симметрично и не транзитивно (в частности, это не частичный порядок и не отношение эквивалентности).
Задача 5
Булева функция [tex]f(x_1,x_2,x_3)[/tex] задана вектором своих значений [tex](1\,1\,0\,1\,0\,0\,1\,1)[/tex], т.е. это значения [tex]f(0,0,0) ; f(0,0,1) ; f(0,1,0) ; \ldots ; f(1,1,1)[/tex] в лексикографическом порядке. Найдите полином Жегалкина функции [tex]f[/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]
Задача 6
Дано множество высказываний [tex]A=\{p_1,p_2,\ldots,p_{12}\}[/tex], причём для каждого [tex]i\in\{1,2,\ldots,12\}[/tex] высказывание [tex]p_i[/tex] гласит: «По крайней мере [tex]i[/tex] высказываний из [tex]A[/tex] ложны». Сколько высказываний из [tex]A[/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].
Задача 7
Пусть [tex]A[/tex], [tex]B[/tex], [tex]C[/tex] и [tex]D[/tex] — множества. При каком необходимом и достаточном условии выполняется равенство [tex](A\cap B)×(C\cup D)=(A×C)\cap(B×D)[/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].
Задача 8
Симметрическая разность двух множеств определяется как [tex]X\triangle Y=(X\setminus Y)\cup(Y\setminus X)[/tex]. Докажите, что для любых множеств [tex]A[/tex], [tex]B[/tex] и [tex]C[/tex] выполняется [tex]A\triangle(B\triangle C)=(A\triangle B)\triangle C[/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].
Задача 9
Пусть [tex]S[/tex] — конечное множество и [tex]f\colon S \to S[/tex] — биекция. Положим [tex]f^1 = f[/tex] и [tex]f^n = f \circ f^{n-1}[/tex] при [tex]n \gt 1[/tex]. Докажите, что существует натуральное число [tex]n[/tex], для которого [tex]f^{-1} = f^n[/tex], где [tex]f^{-1}[/tex] — функция, обратная к [tex]f[/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].)
Меню
Лёгкий
Высшая математика