Ответы к контрольной работе: Дискретная математика

На множестве натуральных чисел задано отношение «x+y делится на 2». Отметьте верное утверждение:

Сколько нечетных двузначных чисел можно составить из цифр 1,2,5,7,8 (цифры можно использовать только 1 раз)?

Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово caabd?

Чему равна проекция множества A = {(1,2),(1,3),(2,3),(3,4)} на первую координату?

Даны три множества: A = {1,2,3}, B = {a,b}, C = {0,1}. Каково число различных функций типа AB2→​C?

Каким может быть граф конденсации?

Чему равно число таблиц размером 33 с элементами из множества мощности 2?

Сколько ребер могут иметь простые графы без петель с 4 вершинами?

Существуют ли простые графы без петель с 6 вершинами со следующим набором степеней:

Дано равенство ∀x∃yP(x,y) = ∃y∀xP(x,y). Какие из утверждений верны?

Какой элемент является образующей в группе целых чисел со сложением?

Отметьте подмножества, которые в алгебре целых чисел со сложением образуют подалгебру:

В палитре художника 5 различных красок. Художник берет кистью наугад любую из красок и ставит цветное пятно на ватмане. Затем берет следующую кисть, окунает ее в любую из красок и делает второе пятно по соседству. Сколько различных комбинаций существует для трех пятен? Порядок пятен на ватмане не важен?

Трое студентов сдают экзамен. Сколькими способами могут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?

Каким может быть дополнение к отношению строгого порядка?

Функция f(x1,x2) имеет тип A2*B, функция g(y1,y2) имеет тип CA*A. Какой тип имеет функция f(x1,g(y1,y2))?

Какие из множеств имеют мощность континуума:

Соответствие G между множествами A = {a,b,c,d} и B = {1,2,3,4} задано множеством пар G = {(a,2),(c,1),(c,3),(d,3),(d,4)}. Отметьте верное утверждение:

Какую длину может иметь максимальный путь в ациклическом графе с n вершинами?

Множество A содержит 5 элементов, множество B содержит 8 элементов. Сколько элементов может содержать разность AB?

Какая из функций являются монотонной?

Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал пяти различных цветов?

Отметьте возможные длины максимального пути в ациклическом графе с 6 вершинами и 5 ребрами:

Какое расстояние между двумя вершинами возможно графе с 5 вершинами?

Какой радиус может быть у графа с 5 вершинами?

Какая из функций является линейной?

Какая из формул эквивалентна формуле (x&y)∨(y&z)∨(¬y&z)?

Какой элемент является образующей в группе целых степеней двойки с умножением?

На множестве A = {a,b,c,d} задано бинарное отношение R = {(a,b),(a,c),(b,c),(c,d)}. Какие пары нужно добавить к R, чтобы получить его транзитивное замыкание?

Соответствие G между множествами A = {a,b,c,d,e} и B = {1,2,3,4} задано множеством пар G = {(a,1),(b,2),(b,3),(c,1),(c,4),(e,3)}. Какое из множеств является образом элемента b при этом соответствии?

Даны множества A = {a,b,d,e}, B = {b,c,e,f,g}, С = {c,f,g}. Отметьте верное равенство:

Функция f задана таблицей: xyzf00010011010001101000101011001111 Какой из полиномов Жегалкина ей соответствует?

Какие из множеств являются счетными?

Какие из операций над множествами коммутативны?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000001001110010100011011100111101100110110111001 Какие из этих функций содержат несущественные переменные?

Какой радиус может быть у графа с 4 вершинами?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000010001000010000011110100011101100110001111111 Какие из этих функций функционально полны в слабом смысле?

Какая из формул эквивалентна формуле (¬x&y)∨(x&z)∨(¬x&z)?

Сколько центров может быть у дерева с n вершинами?

Какие из множеств замкнуты относительно умножения?

Во сколько цветов можно раскрасить цикл, содержащий 9 вершин?

Существуют ли простые графы без петель с 5 вершинами со следующим набором степеней:

Какая из формул исчисления предикатов выражает тот факт, что в множестве М, в котором определен частичный порядок, не существует максимального элемента?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000000001010010010011101100011101001110100111111 Какие из этих функций функционально полны в слабом смысле?

Чему равен единичный элемент в группе {-1,1} с умножением?

Даны три множества: A = {a,b,c}, B = {-1,1}, C = {0,1}. Каково число различных функций типа AB*C2?

В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 5 открыток?

Сколькими способами можно выбрать три различные краски из имеющихся пяти (порядок красоок важен)?

В группе из 17 человек английский язык изучают 10 человек, французский язык изучают 6 человек и оба языка изучают 2 человека. Сколько человек в группе не изучает ни английский, ни французский языки?

Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?

На множестве A = {a,b,c,d} задано бинарное отношение R = {(a,b),(b,c),(b,d)}. Какие пары нужно добавить к R, чтобы получить его транзитивное замыкание?

Соответствие G между множествами A = {a,b,c,d,e} и B = {1,2,3,4} задано множеством пар G = {(a,2),(b,1),(c,3),(d,1),(d,4),(e,3)}. Какое из множеств является образом элемента d при этом соответствии?

Отметьте подмножества, которые в алгебре целых чисел с умножением образуют подалгебру:

Сколько ребер могут иметь простые графы без петель с 5 вершинами?

Каким может быть ориентированное дерево?

Дано равенство ∀x∀yP(x,y) = ∃x∃yP(x,y). Какие из утверждений верны?

Каково число логических функций от 3 переменных?

Между точками горизонтальной прямой задано отношение «левее» (x левее y). Отметьте верное утверждение:

Граф является двудольным, если он ...

Какая из формул исчисления предикатов выражает тот факт, что в множестве М, в котором определен частичный порядок, существует максимальный элемент?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000111001001010011011101100010101000110011111101 Какие из этих функций содержат несущественные переменные?

Между множествами A = {a,b,c,d} и B = {1,2,3,4} множеством пар заданы соответствия G = {(b,1),(c,2),(d,2),(d,3)} и H = {(a,2),(b,2),(c,4),(d,1)}. Какое соответствие функционально?

Множество A содержит 5 элементов, множество B содержит 8 элементов. Сколько элементов может содержать их пересечение?

В группе из 15 человек 6 человек увлекаются театром, 8 человек увлекаются спортом и 3 человека увлекаются и театром, и спортом. Сколько человек в группе не увлекаются ни театром, ни спортом?

В некоторых видов спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. В соревновании участвует 10 человек. Сколько возможно различных исходов?

Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово bcacd?

Между множествами A = {a,b,c,d} и B = {1,2,3,4} множеством пар заданы соответствия G = {(a,1),(b,1),(c,3),(d,4)} и H = {(a,1),(c,1),(c,3),(d,4)}. Какое соответствие функционально?

Сколько различных слов можно получить перестановками букв в слове abcde?

Сколькими способами можно выбрать гласную и согласную буквы из слова «пехота»?

Степень Cn матрицы смежности C ориентированного графа G содержит ненулевые элементы во всех клетках главной диагонали если:

Для любого k число путей длины k, начинающихся с любой вершины графа G, всегда одинаково, если

Сколько висячих вершин может быть у дерева с n вершинами?

Дан ациклический граф с n вершинами. Сколько в нем может быть вершин, которые не являются ни источниками, ни стоками?

Какие графы могут совпадать со своим графом конденсации?

Граф задан матрицей смежности: 0110100011000010000100000 Отметьте каким он является:

Какое расстояние между двумя вершинами возможно графе с 6 вершинами?

Какой радиус может быть у графа с 6 вершинами?

Существуют ли простые графы без петель с 4 вершинами со следующим набором степеней:

Отметьте неверную формулу:

Какая из формул исчисления предикатов выражает тот факт, что в множестве М, в котором определен частичный порядок, не существует минимального элемента?

Дано равенство ∀x∃yP(x,y) = ∃x∀yP(x,y). Какие из утверждений верны?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000010001010010000011000100001101101110110111111 Какие из этих функций функционально полны в слабом смысле?

Какие из функций являются линейными?

Какие из функций являются монотонными?

Функция f задана таблицей: xyzf00000011010101101001101111001111 Какой из полиномов Жегалкина ей соответствует?

Какие из функций ассоциативны?

В таблице приведены три функции f1, f2, f3 от переменных x, y, z: xyzf1f2f3000010001111010101011010100110101011110001111110 Какие из этих функций содержат несущественные переменные?

Каково число логических функций от 5 переменных?

Чему равен единичный элемент в группе целых чисел со сложением?

Какие из множеств с указанной операцией над элементами образуют группу?

Какие из множеств с операцией сложения образуют группу?

Отметьте подмножества, которые в алгебре действительных чисел с умножением образуют подалгебру:

Отметьте дистрибутивны слева множества:

Чему равно число таблиц размером 23 с элементами из множества мощности 3?

Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово abcad?

В кондитерском магазине продавались три сорта пироженных: эклеры, наполеоны и слоеные. Сколькими способами можно купить 4 пироженных?

Сколькими способами из 10 спортсменов можно отобрать команду из 6 человек?

Сколько различных слов можно получить перестановками букв в слове abc?

В группе из 20 человек нужно выбрать старосту и профорга. Сколькими способами это можно сделать?

Надо послать 4 срочных письма. Сколькими способами можно это сделать, если для передачи писем можно послать трех курьеров и каждое письмо можно дать любому из курьеров?