[Росдистант] Основы дискретной математики и логики (тесты, вопросы, ответы)
Тольяттинский государственный университет (Росдистант), ТГУ. Основы дискретной математики и логики (8138, 8472). Итоговый тест. Ответы на вопросы.
Для Росдистант имеются и другие готовые работы. Пишем уникальные работы под заказ. Помогаем с прохождением онлайн-тестов. Пишите, пожалуйста, в личку (Евгений).
ИТОГОВЫЙ ТЕСТ (в базе более 80 вопросов)
В деревне Вишкиль 9 домов. Из каждого дома тянутся четыре шланга к четырем другим домам. Сколько шлангов в деревне?
Выберите один ответ:
16
18
20
22
На книжную полку надо поставить 7 книг, из которых 3 – одного автора. Сколькими способами это можно сделать, если книги одного автора должны стоять вместе?
Выберите один ответ:
6
720
24
144
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
Ответ:
На множестве R заданы предикаты
. Какое утверждение является верным?
Выберите один ответ:
Первый предикат является следствием второго, а второй – следствием первого
Первый предикат является следствием второго, но второй предикат не является следствием первого
Второй предикат является следствием первого, но первый предикат не является следствием второго
Ни один из предикатов не является следствием другого
Аня решила сварить компот из фруктов 2-ух видов. Сколько различных вариантов (по сочетанию фруктов) компота может сварить Аня, если у нее имеется 7 видов фруктов?
Ответ:
Если связи между вершинами графа характеризуются определенной ориентацией, то граф называется
Выберите один ответ:
циклическим
взвешенным
конечным
орграфом
Укажите условия, каждое из которых является необходимым для того, чтобы связный граф с n вершинами был планарным (m – число ребер).
Выберите один ответ:
m = 8 при n = 6
m < 19 при n = 8
Даны универсальное множество U = {1, 2, 3, 4, 5, 6, 7} и в нем подмножества A = {x | x < 4}, C = {1, 2, 5, 6}. Найти
.
Выберите один ответ:
{1, 2, 3, 4, 5, 6}
{4, 5, 6}
{x | x < 7}
{3, 2, 6, 1, 5}
{1, 2}
СДНФ – это
Выберите один ответ:
дизъюнкция простых конъюнкций
конъюнкция простых дизъюнкций
дизъюнкция простых конъюнкций, причем в каждую конъюнкцию входят все переменные данного списка
конъюнкция простых дизъюнкций, причем в каждую дизъюнкцию входят все переменные данного списка
Любой подграф связного графа G, содержащий все вершины графа G и являющийся деревом, называется … .
Ответ:
Установите соответствие между элементами столбцов.
Ориентированный граф
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Связный граф
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Эйлеров граф
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Нулевой граф-схема
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Дерево
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Плоский граф
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
Полный граф
Выберите...
Можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах
Связный граф, не содержащий циклов
Каждая пара вершин соединена ребром
Схема, состоящая из изолированных вершин
Каждая пара вершин соединена хотя бы одним путем
Связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
Ребра графа имеют направление, изображаемое стрелками
При опросе 13 человек, каждый из которых знает по крайней мере один иностранный язык, выяснилось, что 10 человек знают английский язык, 7 – немецкий, 6 – испанский, 5 – английский и немецкий, 4 – английский и испанский, 3 – немецкий и испанский. Сколько человек знают все три языка?
Ответ:
Циклический маршрут, который является цепью, – это
Выберите один ответ:
эйлеров граф
цикл
эйлерова цепь
эйлеров цикл
Какие операции обладают свойством ассоциативности?
Выберите один или несколько ответов:
Разность множеств
Объединение множеств
Пересечение множеств
Симметрическая разность множеств
Булева функция f = (0010) называется
Выберите один ответ:
эквивалентностью
дизъюнкцией
импликацией
стрелкой Пирса
штрихом Шеффера
суммой по модулю два
Логическое значение последнего высказывания
… .
Ответ:
В графе из n вершин остов содержит
Выберите один ответ:
n + 1 ребро
n – 1 ребро
n ребер
2n ребер
Укажите неверное утверждение.
Выберите один ответ:
Об истинности высказывания можно говорить только в настоящем времени
Высказывание и его отрицание не могут быть истинными или ложными одновременно
Не всякое предложение является высказыванием
Земля – это планета Солнечной системы
ДНФ – это
Выберите один ответ:
дизъюнкция простых конъюнкций
конъюнкция простых дизъюнкций
дизъюнкция простых конъюнкций, причем в каждую конъюнкцию входят все переменные данного списка
конъюнкция простых дизъюнкций, причем в каждую дизъюнкцию входят все переменные данного списка
Из трех отличников 9 «A» класса и четырех отличников 9 «Б» класса надо выбрать двух человек (из каждого класса по одному) для поездки за рубеж. Сколькими способами это можно сделать?
Ответ:
Булева функция f = (1110) называется
Выберите один ответ:
эквивалентностью
дизъюнкцией
импликацией
стрелкой Пирса
штрихом Шеффера
суммой по модулю два
Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных уроков?
Выберите один ответ:
10 000
60 480
56
39 450
Невыполнимой является формула
Выберите один ответ:
Множество
является универсальным для множеств
,
и
. Из каких элементов состоит множество
?
Выберите один ответ:
Какое наименьшее число ребер нужно удалить из графа K
6
, чтобы получился планарный граф?
Ответ:
Пусть
. Размещением элементов из
по
называется
Выберите один ответ:
упорядоченное множество из
элементов, принадлежащих
неупорядоченное множество из
элементов, принадлежащих
упорядоченное множество из произвольных
элементов
неупорядоченное множество из произвольных
элементов
Функция
принимает значения
Выберите один ответ:
01110110
00011100
01110111
00000001
01000011
На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 по 100 на первом, втором, третьем и четвертом этапах?
Выберите один ответ:
1200
88 000
11 880
3000
Сколько ребер в полном графе с 10 вершинами?
Ответ:
Полным является граф
Выберите один ответ:
1
2
3
4
Оля решила послать пять разных поздравительных открыток пяти подругам. Сколькими способами она может это сделать?
Ответ:
Разложите на простые множители число 30. Сколькими способами можно записать в виде произведения простых множителей число 30?
Ответ:
Множество
является универсальным для множеств
,
,
,
. Из каких элементов состоит множество
?
Выберите один ответ:
Несвязный неориентированный граф, не содержащий циклов, петель и кратных ребер, – это
Выберите один ответ:
плоский граф
дерево
лес
полный граф
Закон, утверждающий, что если из одного высказывания вытекает второе, то из отрицания второго вытекает отрицание первого, называется законом
Выберите один ответ:
контрапозиции
транзитивности
Де Моргана
поглощения
Из колоды в 36 карт наудачу без возвращения вынимают по одной карте три раза. Сколько существует различных способов получения трех карт, среди которых на первых двух местах – бубны, а на третьем – пики?
Выберите один ответ:
648
712
834
612
Какое соответствие называется функциональным?
Выберите один ответ:
Каждому элементу из первой проекции множества G соответствует единственный элемент из В
Различным элементам из первой проекции множества G соответствуют различные элементы множества В
Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят ... .
Ответ:
Сколько различных флагов из трех вертикальных полос можно составить, используя полосы пяти цветов?
Ответ:
Любой граф, изоморфный плоскому, называется
Выберите один ответ:
кратным
симметрическим
хроматическим
планарным
Множество
является универсальным для множеств
,
и
. Из каких элементов состоит множество
?
Выберите один ответ:
Множество истинности предиката
где
состоит из ... элементов.
Ответ:
Расстояние до вершины дерева называют
Выберите один ответ:
ярусом вершины
высотой вершины
удаленностью вершины
этажом
Логическое значение высказывания
равно … .
Ответ:
Фиктивными переменными для функции f (x, y, z) = (0011 0000) являются
Выберите один ответ:
x
y
z
x, y
x, z
y, z
Связный неориентированный граф, не содержащий циклов, петель и кратных ребер, – это
Выберите один ответ:
плоский граф
дерево
лес
полный граф
Формула
преобразовывается в эквивалентную ей, но не содержащую фиктивных переменных
Выберите один ответ:
y
Логическое значение последнего высказывания
… .
Ответ:
Логическое значение последнего высказывания
… .
Ответ:
Каким свойством обладает отношение F = (A, G), где A = N, G: x r y Ы xy кратно трем?
Выберите один ответ:
Рефлексивность
Антирефлексивность
Симметричность
Антисимметричность
Транзитивность
Укажите элементарные конъюнкции, входящие в СДНФ функции f (x, y, z) = (1000 0111).
Выберите один или несколько ответов:
xyz
А = {1; 2}, В = {2; 3}. Найти А х В.
Выберите один ответ:
{(2; 1); (2; 2); (3; 1); (3; 2)}
{(1; 2); (1; 1); (2; 1); (2; 2)}
{(1; 2); (1; 3); (2; 2); (2; 3)}
{(2; 3); (2; 2); (3; 2); (3; 3)}
Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно ... .
Ответ:
Если граф содержит хотя бы один цикл, то граф называется
Выберите один ответ:
циклическим
взвешенным
конечным
орграфом
Логическое значение последнего высказывания
… .
Ответ:
Фиктивными переменными для функции f (x, y, z) = (0111 0111) являются
Выберите один ответ:
x
y
z
x, y
x, z
y, z
Сумма биномиальных коэффициентов разложения (a + b)5 равна ... .
Ответ:
Эйлеровыми являются графы
Выберите один ответ:
1, 2
1, 3
1, 4
2, 3
2, 4
Предикаты «х кратно 8» и «х – четное число» равносильны на множестве
Выберите один ответ:
{16}
{14}
{14; 16}
{14; 15; 16}
Операция «симметрическая разность множеств» определяется как
Выберите один ответ:
{:x
A или x
{:x
A и x
{:x
A и x
U{:x
A и x
{:x
A
Функция f (x, y, z) = (0010 0110) является
Выберите один ответ:
линейной
монотонной
самодвойственной
функцией из класса
функцией из класса
Выберите один ответ:
a
b
c
d
e
Найти количество натуральных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел: 6, 15 и 10.
Выберите один ответ:
457
734
583
423
Сочетанием с повторениями элементов из
по
называется
Выберите один ответ:
неупорядоченная система из
элементов, принадлежащих
, в которой допускается повторение элементов
упорядоченная система из
элементов, принадлежащих
, в которой допускается повторение элементов
неупорядоченная система из
элементов, принадлежащих
неупорядоченная система из
элементов, в которой допускается повторение элементов
Сколькими способами можно переставить буквы в слове «тик-так», чтобы одинаковые буквы не шли друг за другом?
Выберите один ответ:
84
72
48
86
Число
всех функций из
, зависящих от n переменных
, равно
Выберите один ответ:
Закон, утверждающий, что если из одного высказывания вытекает второе, а из него – третье, то и из первого высказывания вытекает третье, называется законом
Выберите один ответ:
контрапозиции
транзитивности
Де Моргана
поглощения
Дизъюнктивная нормальная форма называется тупиковой, если
Выберите один ответ:
она состоит из простых импликант, что удаление из нее любой конъюнкции нарушает равносильность ДНФ данной функции
она состоит из всех простых импликант данной булевой функции
она имеет наименьшее число символов переменных из всех ДНФ, задающих функцию
она имеет наибольшее число символов переменных из всех ДНФ, задающих функцию
Множество
является универсальным для множеств
,
и
. Из каких элементов состоит множество
?
Выберите один ответ:
Логическое значение высказывания
… .
Ответ:
Множество
является универсальным для множеств
,
,
,
. Из каких элементов состоит множество
?
Выберите один ответ:
Сколько чисел, меньших чем миллион, можно написать с помощью цифр 3 и 7?
Выберите один ответ:
126
252
216
226
Сколькими способами из 25 учеников класса можно выбрать четырех для участия в праздничном концерте?
Выберите один ответ:
12 650
100
75
10 000
Цикл, содержащий все ребра графа, – это
Выберите один ответ:
гамильтонов цикл
цикл
эйлеров граф
эйлеров цикл
гамильтонов граф
Сколько словарей надо издать, чтобы можно было выполнять переводы с любого из пяти языков на любой другой из этих пяти языков?
Ответ:
Какое минимальное количество ребер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
Выберите один ответ:
14
15
16
13
17
Сколькими способами можно составить бригаду из четырех плотников, если имеются предложения от 10 человек?
Ответ:
Укажите формулу алгебры предикатов, которая не является общезначимой.
Выберите один ответ:
Какими свойствами обладает отношение F = (A, G), где A = R2, G: (x, y) r (z, t) Ы x = z и y = t?
Выберите один или несколько ответов:
Рефлексивность
Антирефлексивность
Симметричность
Антисимметричность
Транзитивность
Формула бином Ньютона используется
Выберите один ответ:
для возведения в степень n суммы двух слагаемых
для возведения в степень n суммы k слагаемых
для определения мощности декартова произведения n множеств
для определения мощности объединения n множеств
Абитуриенту необходимо сдать 4 экзамена за 10 дней. Сколькими способами можно составить ему расписание, если в один день можно сдавать только один экзамен?
Ответ:
Фиктивными переменными для функции f (x, y, z) = (1101 1101) являются
Выберите один ответ:
x
y
z
x, y
x, z
y, z
Сколькими способами можно расставить в шеренгу 5 львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом?
Выберите один ответ:
43 200
13 400
32 700
54 200
На множестве R заданы предикаты
. Какое утверждение является верным?
Выберите один ответ:
Первый предикат является следствием второго, а второй – следствием первого
Первый предикат является следствием второго, но второй предикат не является следствием первого
Второй предикат является следствием первого, но первый предикат не является следствием второго
Ни один из предикатов не является следствием другого
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
Ответ:
Сколькими способами можно с помощью букв К, А, В, С обозначить вершины четырехугольника?
Ответ:
В какой последовательности выполняются операции, если в булевой формуле отсутствуют скобки?
Дизъюнкция
Ответ 1
Выберите...
3
1
2
4
Отрицание
Ответ 2
Выберите...
3
1
2
4
Импликация и эквивалентность
Ответ 3
Выберите...
3
1
2
4
Конъюнкция
Ответ 4
Выберите...
3
1
2
4
Комбинаторный анализ занимается изучением
Выберите один ответ:
объектов из конечного множества
и их свойств
элементов из конечного множества
и их свойств
объектов из бесконечного множества
и их свойств
элементов из бесконечного множества
и их свойств
Пусть
и
. Сочетаниями с повторениями из
по 2 будут
Выберите один ответ:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
Формула
является
Выберите один или несколько ответов:
выполнимой
опровержимой
тавтологией
противоречием
Сколько существует различных полиномов Жегалкина от трех переменных?
Ответ:
Пусть
и
. Выпишем все размещения из этого множества по 2.
Выберите один ответ:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
Логическое значение последнего высказывания
… .
Ответ:
Гамильтоновым циклом графа с множеством вершин {a, b, c, d, e, f} является
Выберите один ответ:
abeca
fbecdf
abecdfa
abcdfca
Какое соответствие называется всюду определенным?
Выберите один ответ:
Каждому элементу из первой проекции множества G соответствует единственный элемент из В
Различным элементам из первой проекции множества G соответствуют различные элементы множества В
Сколько ребер в полном графе с 15 вершинами?
Ответ:
В дереве имеется ровно три листа a, b, c, причем d(a, b) = 8, d(a, c) = 9, d(b, c) = 5. Сколько всего вершин в этом дереве?
Ответ:
Сколькими способами можно группу из 17 учащихся разделить на 2 группы так, чтобы в одной группе было 5 человек, а в другой – 12 человек?
Выберите один ответ:
60
85
6188
6000
Формула
является
Выберите один ответ:
тавтологией
противоречием
выполнимой и опровержимой
выполнимой
опровержимой
Логическое значение высказывания
равно … .
Ответ:
Сколькими способами можно переставить буквы в слове «космос»?
Ответ:
Какими свойствами обладает отношение F = (A, G), где A = {Прямые в пространстве}, G: x r y Ы x и y имеют хотя бы одну общую точку?
Выберите один или несколько ответов:
Рефлексивность
Антирефлексивность
Симметричность
Антисимметричность
Транзитивность
Закон, утверждающий, что отрицание конъюнкции равнозначно дизъюнкции отрицаний двух конъюнктов, называется законом
Выберите один ответ:
контрапозиции
транзитивности
Де Моргана
поглощения
Дано соответствие Г = (X, Y, G), где X = {a, b, c}, Y = {1, 2, 3}, G = {(a, 1), (a, 3), (b, 2), (c, 3)}. Какими свойствами обладает Г?
Выберите один или несколько ответов:
Всюду определенность
Функциональность
Сюръективность
Инъективность
В комнате общежития живут трое студентов. У них есть 4 разные чашки, 5 разных блюдец и 6 разных чайных ложек. Сколькими способами они могут накрыть стол для чаепития (каждый студент получает одну чашку, одно блюдце и одну ложку)?
Ответ:
Булева функция f = (1101) называется
Выберите один ответ:
конъюнкцией
дизъюнкцией
импликацией
стрелкой Пирса
штрихом Шеффера
суммой по модулю два
Логическое значение высказывания
… .
Ответ:
Если множество вершин графа конечно, то граф называется
Выберите один ответ:
циклическим
взвешенным
конечным
орграфом
