Дискретная математика

Ориентированный граф G содержит циклы. Какое из утверждений всегда верно?

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

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

• импликация
• штрих Шеффера?
• (Правильный ответ) конъюнкция

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

• 6
• (Правильный ответ) 3
• 2
• 1

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

• (Правильный ответ) 35
• 25
• 10
• 125

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

• вычитание чисел
• (Правильный ответ) сложение чисел
• разность множеств

Чему равна наибольшая нижняя грань для {b,d}?

• e
• (Правильный ответ) f
• g

В потоковой сети, приведенной на рисунке, все пропускные способности равны 4: Нарушены ли в ней правила распределения потоков?

• (Правильный ответ) Да, нарушен закон Кирхгофа.
• Да, нарушено ограничение на пропускную способность.
• Нет, все верно.

В таблице приведены три функции f1, f2, f3 от переменных x, y, z:

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

• f1
• f2
• (Правильный ответ) f3

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

• (Правильный ответ) ACB??C
• AB??C
• ABAC??C
• AC??A

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

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

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

• (Правильный ответ) только G
• только H
• ни G, ни H
• G и H

Граф задан матрицей смежности:

0110100011000010000100000 Отметьте каким он является:

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

Даны множества , , . Отметьте верное равенство:

• (Правильный ответ)

Чему равна наибольшая нижняя грань для {c,f}?

• g
• (Правильный ответ) h
• e

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

• 8
• 9
• (Правильный ответ) 28

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

• (Правильный ответ) A2C??B
• AC??B
• AC??C
• ACAC??C

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

• (Правильный ответ) объединение множеств
• (Правильный ответ) пересечение множеств
• возведение в степень

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

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

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

• эквивалентность
• стрелка Пирса
• (Правильный ответ) константа

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

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

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

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

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

• 125
• 84
• 212
• (Правильный ответ) 99

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

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

В таблице приведены три функции f1, f2, f3 от переменных x, y, z:

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

• f1
• (Правильный ответ) f3
• f2

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

• ?x?y(((x?M)&(y?M)&(x<y))??(x=y))
• ?x?y(((x?M)&(y?M)&(x<y))??(x=y))
• (Правильный ответ) ?x?y(((x?M)&(y?M)&(x<y))??(x=y))

Множества A, B, C выражены через три других множества D, E, F следующими равенствами (знак пересечения опущен): A = D?EF, B = ((D\E)?E)F, С = DF?EF. Отметьте верное равенство:

• A=B
• (Правильный ответ) B=C
• A=C

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

• второй граф
• (Правильный ответ) первый граф
• третий граф

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

• 9
• 27
• (Правильный ответ) 6
• 3

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

• действительные числа отрезка [0,1]
• множество всех натуральных чисел;
• множество всех рациональных чисел;
• (Правильный ответ) множество {1,2,3}

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

• (Правильный ответ) (¬x?z)&(y?z)
• (x?z)&(y?z)
• (x?¬z)&(y?z)

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

• рефлексивным
• антисимметричным
• (Правильный ответ) симметричным

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

• (Правильный ответ) антисимметричным
• симметричным
• (Правильный ответ) рефлексивным

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

• (Правильный ответ) 2
• 5
• (Правильный ответ) 1
• 3

В таблице приведены три функции f1, f2, f3 от переменных x, y, z:

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

• f2
• (Правильный ответ) f3
• f1

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

• 625
• 812
• 907
• (Правильный ответ) 519

Множества A, B, C выражены через три других множества D, E, F следующими равенствами (знак пересечения опущен): A = D\(E?F), B = DE?DF, C = (D\E)?(D\F). Отметьте верное равенство:

• B=C
• (Правильный ответ) A=C
• A=B

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

• (Правильный ответ) пересечение относительно разности
• разность относительно объединения
• (Правильный ответ) объединение относительно пересечения

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

• 3
• 81
• (Правильный ответ) 27
• 9

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

• (Правильный ответ) пересечение
• разность
• (Правильный ответ) объединение

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

• (1,2,3,3,5)
• (1,2,3,4,5)
• (1,2,3,3,4)
• (Правильный ответ) (2,2,3,3,4)

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

• (Правильный ответ) пересечение множеств
• (Правильный ответ) умножение чисел
• вычитание чисел

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

• (1,2,3,4,4,5)
• (1,2,3,4,5,6)
• (Правильный ответ) (1,3,3,3,3,5)
• (1,2,3,4,5,5)

Соответствие 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}
• {1,2,3,4}
• (Правильный ответ) {1,4}

На множестве действительных чисел задано отношение |x-y|<5. Отметьте верное утверждение:

• отношение транзитивно
• отношение антирефлексивно
• (Правильный ответ) отношение симметрично
• (Правильный ответ) отношение рефлексивно

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

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