Докажите, что составное высказывание (A → B) ∨ (B → C) является тавтологией.
Ассоциативна ли импликация? Другими словами, равносильны ли высказывания A → (B → C) и(A → B) → C?
Выполняется ли дистрибутивность для конъюнкции относительно импликации? Другими словами, равносильны ли высказывания A ∧ (B → C) и (A ∧ B) → (A ∧ C)?
Выполняется ли дистрибутивность для импликации относительно импликации? Другими словами,равносильны ли высказывания A → (B → C) и (A → B) → (A → C)?
Запишите с помощью связок ¬, →, ∧, ∨ составное высказывание «истинны более половины высказываний A, B, C»
Докажите, что для любых неотрицательных действительных чисел a, b, n из a · b = n следует (a ⩽ √n) ∨ (b ⩽√n).
Докажите, что $ n^{25} + n^{64} $ чётно для всех положительных целых n.
Рассмотрим такие целые числа x, y, z, w, что$x^2 + y^2 + z^2 = w^2$.Обозначим через A высказывание «w чётное», через B — «все числа x, y, z чётные».Докажите, что A ≡ B.
Верно ли, что для любых множеств A, B и C а) выполняется равенство (A \ B) ∩ (A ∪ B) \ (A ∩ B) = A \ B? б) выполняется равенство (A ∩ B) \ C = (A \ C) ∩ (B \ C)? в) выполняется включение (A ∪ B) \ (A \ B) ⊆ B ? г) выполняется равенство (A \ B) ∪ (A \ C) ∩ A \ (B ∩ C) = A \ (B ∪ C)?
Пусть $ A_{1} ⊇ A_{2} ⊇ A_{3} ⊇ · · · ⊇ A_{n} ⊇ . . . $ — невозрастающая последовательность множеств, а $ B_{1} ⊆ B_{2} ⊆B_{3} ⊆ · · · ⊆ B_{n} ⊆ . . . $ — неубывающая последовательность множеств. Известно, что $ A_1 \backslash B_1 = A_9 \backslash B_9 $.Докажите, что $ A_2 \backslash B_8 = A_5 \backslash B_5 $
Для любого целого положительного n докажите равенство $ \mathbf{1}^\mathbf{3}{+\ \mathbf{2}}^{\mathbf{3}\ }+...+\mathbf{n}^\mathbf{3}=\left(\mathbf{1}+\mathbf{2}\ +\ ...\ +\ \mathbf{n}\right)^\mathbf{2} $
Числа Фибоначчи задаются правилами $ F_{0} = 1; F_{1} = 1; F_{n+2} = F_{n+1} + F_{n} $ для всех n ⩾ 2.Докажите, что для любого k ⩾ 1 выполняется равенство $ F_{2k} - F_{2k - 1} + ... + F_{2} - F_{1} = F_{2k - 1}$
В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда $ a_1, a_2, . . . , a_k $ и переставить его числа в обратном порядке: $ a_k, a_{k−1}, . . . , a_1 $ . Докажите, что возможно расставить числа в порядке возрастания после применения нескольких таких операций
Найдите наименьшее количество вершин в графе, сумма степеней вершин в котором равна 24.
Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?
В стране Радуга есть 7 городов с официальными названиями Красный, Оранжевый, Жёлтый, Зелёный, Голубой, Синий, Фиолетовый. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если количество общих букв в названиях городов не меньше 3. (Количество вхождений букв несущественно, прописные и строчные не различаются, используются только официальные названия.) Можно ли добраться из города Красный в город Фиолетовый, используя эти авиалинии (возможно, с пересадками)?
Вершинами графа $L_n$ являются отрезки координатной плоскости [(0, i); (n + 1, i)] и [(i, 0); (i, n + 1)](для целых i от 1 до n, всего 2n вершин), в квадратных скобках указаны координаты концов отрезка.Две вершины графа (то есть отрезки) соединены ребром тогда и только тогда, когда эти отрезкипересекаются. Найдите максимальный размер независимого множества в графе $ L_n $.
Докажите, что при n ⩾ 1 связен любой граф на 2n + 1 вершине, степень каждой из которых не меньше n.
В графе 2n + 1 вершина, степень каждой равна n. Докажите, что после удаления любого подмножества из менее чем n рёбер получается связный граф.
Вершинами графа $ Q_{n,r} $ являются двоичные слова длины n, а соседями являются пары слов, отличающихся ровно в r позициях.Связен ли граф $ Q_{2021,47} $?
Докажите, что в любом графе на 2n вершинах с $ n^2 + 1 $ ребром, n ⩾ 2, найдётся треугольник: три попарно смежные вершины.
Найдите наибольшее количество вершин в связном графе, сумма степеней вершин в котором равна 20.
В связном графе на n вершинах нет мостов. Какое наименьшее количество рёбер может быть в таком графе?
В дереве на 13 вершинах есть ровно две вершины степени 6. Следует ли из этого, что в этом дереве есть вершина степени 2?
В связном графе степени всех вершин чётные. Докажите, что граф останется связным и после удаления любого из рёбер.
Дополнением G¯ графа G называется такой граф на том же множестве вершин, что и у графа G,в котором пара вершин связана ребром тогда и только тогда, когда в G эта пара вершин ребром н связана. Докажите, что если в графе больше 5 вершин, либо сам граф, либо его дополнение содержат цикл длины 3.
В дереве нет вершин степени 2. Докажите, что количество висячих вершин (т.е. вершин степени 1) больше половины общего количества вершин.
В дереве на 2021 вершине нет простого пути длины 6. Докажите, что в этом дереве есть вершина степени не меньше 33.
Вершины ориентированного графа — целые числа от 0 до 9. Ребро идет из вершины x в вершину y если y − x = 2 или x − y = 3. Найдите количество компонент сильной связности в этом графе.
Известно, что в ориентированном графе на ⩾ 2 вершинах из любой вершины в любую другую идёт ровно один простой путь. Верно ли, что исходящие степени вершин в этом графе равны 1?
Турниром называется такой ориентированный граф, в котором нет петель и для любых двух различных вершин x, y есть ровно одно ребро с концами x, y. Докажите, что в любом турнире есть вершина, из которой достижима любая вершина турнира.
Пусть в ориентированном графе G исходящая степень каждой вершины равна входящей. Если стереть ориентацию на рёбрах, то получится связный неориентированный граф H. Докажите, что ориентированный граф G сильно связен.
Таблица из 100 строк и 2 столбцов заполнена числами от 0 до 9 так, чтобы выполнялись условия: (а) все строки таблицы различны; (б) ни одну строку в таблице нельзя получить из какой-нибудь вышестоящей строки заменами большего числа на меньшее. Докажите, что какая-то из строк таблицы равна (5, 5). Какой по счёту может быть эта строка (начиная с верха)? Укажите все возможные значения и докажите корректность приведенного ответа.
Граф $ K_6 $ состоит из 6 вершин, каждая пара которых соединена ребром. Найдите наименьшую длину пути, проходящего по всем рёбрам этого графа. (напомним, что длина пути на 1 меньше количества вершин.)
Граф G можно по крайней мере тремя различными способами правильно раскрасить в 2 цвета. Докажите, что G несвязный.
Докажите, что в дереве на 2n вершинах можно выбрать независимое множество из n вершин.
В графе 17 вершин. Они расставлены по кругу так, что каждое из 34 рёбер графа соединяет пару соседних в расстановке вершин или пару вершин, между которыми есть ровно одна другая вершина. Можно ли вершины этого графа правильно раскрасить в 3 цвета?
На столе лежит 200 фишек: 100 красных, на которых написаны числа от 1 до 100, и 100 синих,на которых также написаны числа от 1 до 100. Враг забрал 99 фишек со стола (по своему усмотрению). Докажите, что на столе осталась пара из красной и синей фишек, сумма чисел на которых не меньше 101.
В графе на 30 вершинах (необязательно двудольном) между любыми тремя вершинами есть хотябы два ребра. Докажите, что в графе есть совершенное паросочетание (из 15 рёбер).
Вася составил список из всех 12-элементных подмножеств 26-элементного множества, каждое записал по одному разу. Петя добавляет по одному элементу в каждое множество списка. Докажите, что Петя может так выполнить добавления, чтобы среди полученных 13-элементных множеств не было одинаковых.
Докажите, что R(3, 4) = 9. (R(3, 4) — наименьшее из тех чисел n, что в любом графе на n вершинах есть либо клика размера 3, либо независимое множество размера 4.)
Про функцию f из множества X в множество Y и множество B ⊆ Y известно, что $ f^{-1}(B) = X $. Верно ли, что B = Y ?
Функция f определена на множестве X и принимает значения в множестве Y , при этом A ∪ B ⊆ Xи f(A) = f(B). Верно ли, что при этих условиях $ f^{−1}(f(A)) = f^{−1}(f(B))$?Приведите доказательство или контрпример в каждом случае.
Функция f определена на множестве A ∪ B и принимает значения в множестве Y . Если заменить в утверждении f(A Δ B) ? f(A) Δ f(B) знак ? на один из знаков включения ⊆ или ⊇, получится утверждение. Какие из получившихся двухутверждений верны для любой f? Приведите доказательство или контрпример в каждом случае.
О функциях f из множества A в множество B и g из множества B в множество C известно, что g ◦ f биекция. Верно ли, что g всюду определена? (Множества A, B, C не обязательно конечные.)
О всюду определённых функциях f, g из множества A в себя известно, что f ◦ g ◦ f = $ id_A $. Верно ли, что f — биекция? (Множество A не обязательно конечное.)
О функциях f, g из множества A в себя (не обязательно всюду определённых) известно, что g◦f всюду определённая. Множество A состоит из 2021 элемента. Найдите минимально возможное количество элементов в образе f ◦ g(A).
В графе на n вершинах для любой пары вершин u и v есть ровно две вершины, с которыми соединены и u, и v. Докажите, что степени всех вершин в этом графе одинаковы.
Правильный n-угольник разбит диагоналями на треугольники (диагонали пересекаются разве что в вершинах многоугольника). Вершинами графа T∗ являются треугольники разбиения. Два треугольника связаны ребром в графе T∗, если у них есть общая сторона. Докажите, что T∗ — дерево.
Докажите, что множество конечных подмножеств рациональных чисел счётно.
Верно ли, что если $ A $ бесконечно, а $ B $ счётно, то $ A△B $ равномощно $ A $
Установите взаимно однозначное соответствие между множеством бесконечных последовательностей из 0 и 1 и множеством бесконечных последовательностей из 0, 1, 2, 3.
Крестом называется фигура, состоящая из двух диагоналей квадрата. Докажите, что любое множество непересекающихся крестов на плоскости конечно или счётно.
Верно ли, что множество прямых на плоскости имеет мощность континуум?
Докажите, что множество неубывающих бесконечных последовательностей натуральных чисел имеет мощность континуум.
Верно ли, что множество невозрастающих бесконечных последовательностей натуральных чисел имеет мощность континуум?
Счётно ли множество бесконечных двоичных последовательностей $ b_0, b_1, . . . , b_n, $ . . . , в которых каждый отрезок нечётной длины $ b_i, b_{i+1}, . . . , b_{i+2k} $ содержит почти поровну нулей и единиц (модуль разности равен 1)?
Углом на плоскости называется фигура, состоящая из точки и двух исходящих из неё лучей. Можно ли расположить на плоскости континуум непересекающихся углов, таких чтобы никакие два из них не имели одинаковую градусную меру?
Докажите, что если A ∪ B имеет мощность континуум, то A или B имеет мощность континуум. (Замечание. Никому неизвестно, существуют ли множества промежуточной мощности между счетными и континуальными.)
Рассмотрим на множестве R бинарное отношение R(x, y), означающее, что x/y > 0. Чему равно R ◦R?
Бинарное отношению R ⊂ {a, b, c, d, e, f, g, h} × {1, 2, 3, 4, 5, 6, 7, 8} состоит из пар {(a, 1),(b, 2),(c, 4),(d, 8),(e, 8),(f, 8),(g, 8),(h, 8)}. Найдите количество элементов в отношениях $ R^T ◦ R $ и $ R ◦ R^T $ .
Пусть $ R_1, R_2 $ — такие отношения на множествах A и B, что $ R_1 ∪ R_2 $ является функцией. Докажите, что тогда и $ R_1 $ , и $ R_2 $ также являются функциями.
Всегда ли композиция отношений эквивалентности является отношением эквивалентности?
Найдите нестрогий порядок на четырёх элементах, в котором есть ровно три пары несравнимых элементов.
В связном графе степени восьми вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности. Верно ли аналогичное утверждение для графов с 10 вершинами степени 3 (и произвольным количеством вершин степени 4)?
Про порядки A и B известно, что A + B ∼= B + A. Верно ли, что тогда A ∼= B? (∼= обозначает изоморфизм порядков.)
или напишите нам прямо сейчас:
My<cod/>.net