Ответы на вопросы из коллекции "Дискретная математика" на СтудИзбе

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

• отношение транзитивно
• отношение симметрично
• отношение антирефлексивно
• отношение рефлексивно

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

• 15
• 25
• 12
• 5

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

• 907
• 812
• 625
• 519

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

• {2,3,4}
• {1,2,3,4}
• {1,2,3}

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

• 212
• 512
• 144
• 24

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

• односторонне связным
• сильно связным
• несвязным
• слабо связным

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

• 81
• 512
• 72
• 1024

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

• 16 ребер
• 6 ребер
• одно ребро
• 4 ребер

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

• (1,2,3,4,5,6)
• (1,3,3,3,3,5)
• (1,2,3,4,5,5)
• (1,2,3,4,4,5)

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

• Это равенство неверно при любых Р.
• Это равенство верно при любых Р.
• Это равенство при некоторых Р верно, а при некоторых других Р неверно.

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

• такого элемента не существует
• 1
• 0

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

• множество чисел, кратных 5
• множество [0,1]
• множество натуральных чисел

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

• 10
• 25
• 35
• 125

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

• 3
• 9
• 27
• 81

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

• рефлексивным
• симметричным
• антисимметричным

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

• ACA*B
• A2*B
• A2CA*B
• CA*A

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

• множество натуральных чисел;
• множество рациональных чисел;
• множество действительных чисел;
• множество [0,1]

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

• G всюду определено;
• G сюръективно?
• G функционально;

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

• 1
• 2
• n-1
• n

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

• 0 элементов
• 2 элемента
• 5 элементов
• 8 элементов

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

• эквивалентность
• константа
• стрелка Пирса

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

• 125
• 60
• 5
• 20

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

• 5
• 1
• 2
• 4

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

• 6
• 3
• 4
• 5

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

• 3
• 2
• 1
• 5

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

• стрелка Пирса
• конъюнкция
• эквивалентность

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

• (x∨z)&(y∨z)
• (¬x∨z)&(y∨z)
• (x∨¬z)&(y∨z)

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

• такого элемента не существует
• 1
• 2

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

• (d,a)
• (a,d), (b,d)
• никакие, так как R транзитивно;
• (a,d)

Соответствие 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 при этом соответствии?

• {1,2,3,4}
• {1,4}
• {2,3}

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

• С = AB
• С = A∩B
• С = A∪B
• С = BA

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

• xz⊕x⊕y⊕1
• xyz⊕xy⊕x⊕y⊕1
• xy⊕x⊕y⊕z
• xyz⊕x⊕y⊕1

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

• множество натуральных чисел;
• множество действительных чисел;
• множество [0,1]
• множество рациональных чисел;

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

• разность
• пересечение
• объединение

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

• f1
• f3
• f2

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

• 4
• 2
• 1
• 3

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

• f1
• f3
• f2

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

• (¬x∨z)&(y∨z)
• (x∨z)&(y∨z)
• (x∨¬z)&(y∨z)

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

• 2
• 1
• n-1
• n

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

• множество отрицательных чисел
• множество положительных чисел
• множество натуральных чисел
• множество нечетных чисел

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

• в 3 цвета
• в 4 цвета
• в 2 цвета

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

• (1,2,3,4,5)
• (2,2,3,3,4)
• (1,2,3,3,4)
• (1,2,3,3,5)

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

• ∀x∃y((x∈M)&(y∈M)&(x
• ∀x∃y((x∈M)∨((y∈M)&(x
• ∀x∃y(x∈M→​((y∈M)&(x

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

• f1
• f2
• f3

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

• 1
• -1
• его не существует

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

• 64
• 10
• 24
• 46

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

• 10
• 15
• 21
• 25

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

• 3
• 60
• 15
• 35

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

• 1
• 2
• 3
• 6

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

• 24
• 9
• 18
• 6

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

• (a,c), (a,d)
• (c,d), (d,c)
• никакие, так как R транзитивно;
• (b,a)

Соответствие 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 при этом соответствии?

• {1,2,3,4}
• {1,2,3}
• {1,4}

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

• множество чисел, кратных 3
• множество отрицательных чисел
• множество [0,1]

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

• одно ребро
• 5 ребер
• 10 ребер
• 25 ребер

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

• сильно связным
• односторонне связным
• слабо связным

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

• Это равенство неверно при любых Р.
• Это равенство при некоторых Р верно, а при некоторых других Р неверно.
• Это равенство верно при любых Р.

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

• 8
• 9
• 28

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

• отношение рефлексивно
• отношение антирефлексивно
• отношение симметрично
• отношение транзитивно

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

• имеет цикл с четным числом вершин
• имеет цикл с нечетным числом вершин
• ациклический граф

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

• ∃x∀y(((x∈M)&(y∈M)&(x
• ∀x∃y(((x∈M)&(y∈M)&(x
• ∃x∃y(((x∈M)&(y∈M)&(x

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

• f1
• f2
• f3

Между множествами 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)}. Какое соответствие функционально?

• G и H
• только G
• только H
• ни G, ни H

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

• 6 элементов
• 5 элементов
• 3 элемента
• 8 элементов

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

• 3
• 4
• 1
• 14

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

• 720
• 30
• 10
• 1000

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

• 732
• 214
• 618
• 395

Между множествами 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)}. Какое соответствие функционально?

• только H
• ни G, ни H
• G и H
• только G

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

• 20
• 5
• 55
• 120

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

• 15
• 9
• 36
• 6

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

• граф G - сильно связный
• все вершины G имеют петли
• граф G содержит циклы
• некоторые вершины G имеют петли

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

• G — полный граф
• G — неориентированный цикл
• G — неориентированное дерево

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

• n-1
• 1
• 2

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

• n+1
• n2
• n-2
• n

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

• несвязным?
• сильно связным;
• слабо связным;
• односторонне связным;

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

• несвязным
• односторонне связным
• сильно связным
• слабо связным

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

• 6
• 2
• 4
• 5

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

• 1
• 2
• 3
• 5

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

• (1,2,3,3)
• (1,1,2,3)
• (1,2,2,3)
• (1,2,3,4)

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

• ∀x∀yP(x,y) = ∀y∀xP(x,y)
• ∀x(P(x)∨Q(x)) = ∀xP(x)∨∀xQ(x)
• ∃x(P(x)∨Q(x)) = ∃xP(x)∨∃xQ(x).

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

• ∀x∃y((x∈M)&(y∈M)&(y
• ∀x∃y(x∈M→​((y∈M)&(y
• ∀x∃y((x∈M)∨((y∈M)&(y

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

• Это равенство верно при любых Р.
• Это равенство неверно при любых Р.
• Это равенство при некоторых Р верно, а при некоторых других Р неверно.

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

• f3
• f1
• f2

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

• импликация
• отрицание
• константа

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

• отрицание
• сложение по модулю 2
• дизъюнкция

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

• xyz⊕xz⊕x⊕y⊕z
• xyz⊕yz⊕x⊕z
• xz⊕x⊕y⊕z
• xy⊕xz⊕y⊕z

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

• импликация
• конъюнкция
• штрих Шеффера?

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

• f3
• f2
• f1

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

• 232
• 32
• 25

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

• его не существует
• 1
• 0

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

• рациональные числа с операцией умножения
• неотрицательные целые числа с операцией сложения
• множество {-1,1} с операцией умножения
• четные числа с операцией сложения

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

• целые числа, кратные 3
• множество {-1,1}
• неотрицательные целые числа
• целые числа

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

• множество натуральных чисел
• множество целых степеней двойки
• множество {0,1,2}

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

• объединение относительно пересечения
• пересечение относительно разности
• разность относительно объединения

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

• 120
• 801
• 729
• 216

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

• 99
• 212
• 84
• 125

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

• 12
• 15
• 4
• 9

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

• 60
• C106
• A106
• 610

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

• 9
• 3
• 6
• 27

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

• 40
• 20
• 380
• 400

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

• 4
• 24
• 12
• 3