Главная / Алгоритмы и дискретные структуры /
Дискретный анализ / Тест 5
Дискретный анализ - тест 5
Упражнение 1:
Номер 1
Любая функция алгебры логики представима единственным образом в виде:
Ответ:
 (1) полинома Жегалкина 
 (2) конъюнктивной нормальной формы 
 (3) дизъюнктивной нормальной формы 
 (4) суперпозиции немонотонной и несамодвойственной функции 
Номер 2
Функция алгебры логики, зависящая от переменных, представима в виде полинома Жегалкина:
Ответ:
 (1) единственным образом 
 
(2) способами 
 
(3) способами 
 
(4) способами 
Номер 3
Укажите, какие функции алгебры логики могут быть представлены в виде полинома Жегалкина:
Ответ:
 (1) все функции алгебры логики 
 (2) все несамодвойственные функции алгебры логики 
 (3) все функции алгебры логики, за исключением тождественного нуля и тождественной единицы 
 (4) все функции алгебры логики, существенно зависящие не менее, чем от трех переменных 
Упражнение 2:
Номер 1
Сколько существует различных многочленов Жегалкина от переменных:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Сколько коэффициентов в многочлене Жегалкина от трех переменных:
Ответ:
 (1) 1 
 (2) 2 
 (3) 3 
 (4) 4 
 (5) 5 
 (6) 6 
 (7) 7 
 (8) 8 
 (9) 9 
 (10) 10 
Номер 3
Укажите функцию, представление которой в виде полинома Жегалкина содержит конъюнкцию с двумя или более переменными:
Ответ:
 (1) немонотонная 
 (2) нелинейная 
 (3) не самодвойственная 
 (4) не сохраняющая единицу 
Упражнение 3:
Номер 1
Укажите системы функций, не являщихся полными:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Укажите системы функций, не являющихся полными:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Укажите полные системы функций:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 4:
Номер 1
Укажите полные системы функций:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Укажите полную систему функций:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Укажите полную систему функций:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 5:
Номер 1
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 6:
Номер 1
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Многочлен Жегалкина для функции имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 7:
Номер 1
Основная лемма критерия полноты обосновывает возможность, при определенных условиях, получения функций:
Ответ:
 (1) константа 0, константа 1, тождество 
 (2) константа 0, константа 1, отрицание 
 (3) константа 0, константа 1, конъюнкция 
 (4) константа 0, константа 1, дизъюнкция 
Номер 2
Укажите необходимое свойство системы функций, из которых можно получить набор функций :
Ответ:
 (1) наличие функции, сохраняющей ноль 
 (2) отсутствие функции, сохраняющей ноль 
 (3) наличие функции, не сохраняющей ноль 
Номер 3
Укажите необходимое свойство системы функций, из которых можно получить набор функций :
Ответ:
 (1) отсутствие функции, сохраняющей единицу 
 (2) наличие функции, не сохраняющей единицу 
 (3) отсутствие функции, не сохраняющей единицу 
 (4) наличие функции, сохраняющей единицу 
Упражнение 8:
Номер 1
Укажите необходимое свойство системы функций, из которых можно получить набор функций :
Ответ:
 (1) наличие самодвойственной функции 
 (2) отсутствие самодвойственной функции 
 (3) отсутствие несамодвойственной функции 
 (4) наличие несамодвойственной функции 
Номер 2
Укажите необходимое свойство системы функций, из которых можно получить набор функций :
Ответ:
 (1) наличие монотонной функции 
 (2) отсутствие монотонной функции 
 (3) наличие немонотонной функции 
 (4) отсутствие немонотонной функции 
Номер 3
Укажите необходимые свойства системы функций, из которых можно получить набор функций :
Ответ:
 (1) наличие линейной функции 
 (2) отсутствие линейной функции 
 (3) наличие нелинейной функции 
 (4) отсутствие нелинейной функции 
Упражнение 9:
Номер 1
С помощью каких операций можно получить конъюнкцию из любой нелинейной функции алгебры логики:
Ответ:
 
(1) замена переменных и суперпозиция с функциями
 
 
(2) замена переменных и суперпозиция с функциями
 
 
(3) замена переменных и суперпозиция с функциями
 
 
(4) только суперпозиция с функциями
 
Номер 2
С помощью каких операций можно получить отрицание из любой немонотонной функции алгебры логики:
Ответ:
 (1) только замена переменных 
 
(2) замена переменных и суперпозиция с функциями
 
 
(3) замена переменных и суперпозиция с функциями
 
 
(4) только суперпозиция с функциями
 
Номер 3
С помощью каких операций можно получить константу из любой несамодвойственной функции алгебры логики:
Ответ:
 (1) только замена переменных 
 
(2) замена переменных и суперпозиция с функциями
 
 
(3) только суперпозиция с функциями
 
 
(4) замена переменных и суперпозиция с функциями
 
Упражнение 10:
Номер 1
Для того, чтобы система функций была полна, необходимо и достаточно, чтобы:
Ответ:
 
(1) целиком не содержалась ни в одном из замкнутых классов
 
 
(2) целиком содержалась хотя бы в одном из замкнутых классов
 
 
(3) целиком содержалась во всех замкнутых классах
 
Номер 2
Для того, чтобы система функций была полна, необходимо и достаточно, чтобы:
Ответ:
 
(1) для хотя бы одного класса из
среди функций системы
нашлась функция, этому классу принадлежащая  
 
(2) для любого класса из
среди функций системы
нашлась функция, этому классу принадлежащая  
 
(3) для любого класса из
среди функций системы
нашлась функция, этому классу не принадлежащая  
 
(4) для хотя бы одного класса из
среди функций системы
нашлась функция, этому классу не принадлежащая  
Номер 3
Критерий полноты - это:
Ответ:
 (1) необходимое условие полноты системы функций алгебры логики 
 (2) достаточное условие полноты системы функций алгебры логики 
 (3) необходимое и достаточное условие полноты системы функций алгебры логики 
 (4) индекс массы тела 
Упражнение 11:
Номер 1
Объект может быть выбран различными способами, после этого объект может быть выбран различными способами. Тогда:
Ответ:
 
(1) объект
может быть выбран
различными способами 
 
(2) объект
может быть выбран
различными способами 
 
(3) объект
может быть выбран
различными способами 
 
(4) объект
может быть выбран
различными способами 
Номер 2
Объект может быть выбран различными способами, объект может быть выбран различными способами, одновременный выбор объектов и невозможен. Тогда:
Ответ:
 
(1) выбор объекта
может быть осуществлен
различными способами 
 
(2) выбор объекта
может быть осуществлен
различными способами 
 
(3) выбор объекта
может быть осуществлен
различными способами 
 
(4) выбор объекта
может быть осуществлен
различными способами 
Номер 3
Имеется 4 конверта и 5 марок. Сколько существует способов выбрать конверт и марку для одного письма:
Ответ:
 (1) 4 
 (2) 5 
 (3) 9 
 (4) 20 
Упражнение 12:
Номер 1
Имеется 5 путевок на Байкал и 8 путевок на Родос. Сколько существует способов выбрать одну поездку?
Ответ:
 (1) 5 
 (2) 8 
 (3) 13 
 (4) 40 
Номер 2
К основным задачам комбинаторики относятся:
Ответ:
 (1) вопрос о существовании конфигурации заданных объектов 
 (2) подсчет числа конфигураций 
 (3) приближенный подсчет числа конфигураций 
 (4) перечисление конфигураций 
Номер 3
К задачам комбинаторики относятся:
Ответ:
 (1) перечисление конфигураций 
 (2) оптимизация перечисления конфигураций 
 (3) оптимизация построения конфигураций 
Упражнение 13:
Номер 1
К модельным задачам комбинаторики относятся:
Ответ:
 (1) задача о числе функций (отображений) 
 (2) задача о размещении объектов по ящикам 
 (3) задача о числе слов в алфавите 
 (4) задача линейной фильтрации 
Номер 2
Задача о числе функций (отображений) и задача о размещении объектов по ящикам
Ответ:
 (1) находятся во взаимнооднозначном отношении 
 (2) описывают принципиально различные конфигурации объектов 
Номер 3
Сколько существует упорядоченных размещений 2 объектов по 2 ящикам:
Ответ:
 (1) 2 
 (2) 4 
 (3) 6 
 (4) 8 
Упражнение 14:
Номер 1
Упорядоченное размещение объектов по ящикам предполагает, что:
Ответ:
 (1) каждый ящик содержит упорядоченную последовательность объектов 
 (2) каждый ящик содержит не упорядоченную последовательность объектов 
Номер 2
Для двух чисел Стирлинга 1 рода, не равных нулю, и :
Ответ:
 (1) их знаки будут совпадать 
 (2) их знаки будут противоположными 
Номер 3
Для двух чисел Стирлинга 1 рода, не равных нулю, и :
Ответ:
 (1) их знаки будут совпадать 
 (2) их знаки будут противоположными 
 (3) эти числа равны нулю 
Упражнение 15:
Номер 1
Укажите количество всевозможных отображений из множества в множество , где - конечное множество из элементов, - конечное множество из элементов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Укажите количество всевозможных размещений различных объектов по различным ящикам:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Укажите количество различных слов длины в алфавите из символов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 16:
Номер 1
Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично":
Ответ:
 (1) 12 
 (2) 64 
 (3) 81 
 (4) 128 
Номер 2
Укажите количество способов разместить 4 шарика по 5 лункам:
Ответ:
 (1) 20 
 (2) 512 
 (3) 625 
 (4) 1024 
Номер 3
Укажите количество различных слов длиной в 3 символа в алфавите из 5 символов:
Ответ:
 (1) 15 
 (2) 125 
 (3) 243 
 (4) 256 
Упражнение 17:
Номер 1
Укажите выражения, равные количеству инъективный отображений из множества в множество , где - конечное множество из элементов, - конечное множество из элементов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Укажите выражения, равные количеству всевозможных размещений различных объектов по различным ящикам при условии, что в каждом ящике не более 1 объекта:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Укажите выражения, равные количеству различных слов длины , в которых все символы различны, в алфавите из символов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 18:
Номер 1
Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки:
Ответ:
 (1) 0 
 (2) 1 
 (3) 3 
 (4) 4 
Номер 2
Укажите количество способов разместить 4 шарика по 5 лункам при условии, что в каждой лунке не более 1 шарика:
Ответ:
 (1) 12 
 (2) 20 
 (3) 120 
 (4) 128 
Номер 3
Укажите количество различных слов длиной в 3 символа, в которых все символы различны, в алфавите из 5 символов:
Ответ:
 (1) 15 
 (2) 30 
 (3) 60 
 (4) 125 
Упражнение 19:
Номер 1
Укажите выражения, равные количеству взаимнооднозначных отображений из множества на себя, где - конечное множество из элементов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Укажите выражения, равные количеству всевозможных размещений различных объектов по различным ящикам при условии, что в каждом ящике не более 1 объекта:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Укажите выражения, равные количеству различных слов длины , в которых все символы различны, в алфавите из символов:
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 20:
Номер 1
Укажите количество способов поставить трем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки::
Ответ:
 (1) 1 
 (2) 3 
 (3) 6 
 (4) 9 
Номер 2
Укажите количество способов разместить 4 шарика по 4 лункам при условии, что в каждой лунке не более 1 шарика:
Ответ:
 (1) 4 
 (2) 16 
 (3) 24 
 (4) 64 
Номер 3
Укажите количество различных слов длиной в 5 символов, в которых все символы различны, в алфавите из 5 символов:
Ответ:
 (1) 5 
 (2) 25 
 (3) 60 
 (4) 120 
Упражнение 21:
Номер 1
Числа Стирлинга первого рода - это:
Ответ:
 (1) коэффициенты при разложении любого полинома степени n виде суммы степеней переменной 
 
(2) коэффициенты при разложении полинома вида
виде суммы степеней переменной 
Номер 2
Чему равно число Стирлинга первого рода при :
Ответ:
 (1) 0 
 (2) 1 
Номер 3
Чему равно число Стирлинга первого рода при :
Ответ:
 (1) 0 
 (2) 1 
Упражнение 22:
Номер 1
Чему равно число Стирлинга первого рода :
Ответ:
 (1) 0 
 (2) 1 
 (3) 10 
Номер 2
Чему равно число Стирлинга первого рода :
Ответ:
 (1) 0 
 (2) 1 
Номер 3
В записи числа Стирлинга первого рода индекс означает, что:
Ответ:
 
(1) это коэффициент при переменной в степени
 
 
(2) это коэффициент при переменной в степени