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



Ориентированный граф 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)
Узнать сколько стоит решение этого задания
(ответ в течение 5 мин.)
X