Дискретная математика. ОПД. 4 курс.

Вариант.

11. Эйлеров путь содержит:

А) Все вершины графа;

Б) Все ребра графа;

В) Все ребра и все вершины графа.

12. Укажите плоский граф:

а) б;

б) а;

в) оба графа;

г) нет правильного ответа.

13. Алгори́ тм Бору́ вки — это алгоритм нахождения:

а) минимального остовного дерева в графе;

б) минимального ребра в графе;

в) максимального дерева в графе.

14. Необходимым условием существования гамильтоновых цепей и циклов является:

а) связность графа;

б) несвязность графа;

в) четность графа.

15. Формальная логика содержит:

А) понятие, умозаключение.

Б) суждение, умозаключение.

В) понятие, суждение, умозаключение.

16. Логические константы это:

А) Конкретные частные утверждения;

Б) Логические утверждения;

В) Частные утверждения.

17. Определите, какая из следующих формул является тождественно истинной для формулы :

А)

Б)

В)

Г)

18. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

19. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

20. Какая таблица истинности изображена на рисунке?

А) Конъюнкция;

Б) Дизъюнкция;

В) Отрицание.

21. Два множества А и В, состоящие из одинаковых элементов: А=В, называют:

А) Противоположными;

Б) Сходными;

В) Равными.

22. Закон коммутативности это:

А) , .

Б) , .

В)

Г) ,

Д)

Е) , .

Ж) ,

Вариант.

11. Связный граф называется эйлеровым, если:

А) Существует замкнутая цепь, проходящая через каждое его ребро;

Б) Существует не замкнутая цепь, проходящая через каждое его ребро;

В) Нет правильного ответа.

12. Граф, в котором каждые две вершины смежны:

а) пустой граф;

б)полный граф.

В) связный граф

Г) плоский граф

13. Какой алгоритм используется для нахождения минимального остовного дерева в данном графе:

а) алгоритм Крускала;

б) алгоритм Прима;

в) алгоритм Борувки.

14. Подграфом графа G = (V, X)... подмножеством V, называется граф G1 = (V1, X1), множество дуг Х1 которого состоит из тех и только тех дуг графа G, оба конца которых лежат в V1.

а) малым;

б)непорожденным;

в) порожденным.

15. Форма мышления, фиксирующая основные существенные признаки объекта:

А) Понятие;

Б) Суждение;

В) Содержание.

16. Электронные схемы с одним или несколькими входами и одним выходом, через которые проходят электрические сигналы, представляющие цифры 0 и 1, это:

А) Логические формы;

Б) Логические переменные;

В) Логические элементы.

17. Определите, какая из следующих формул является тождественно истинной для формулы :

А)

Б)

В)

Г)

18. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

19. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

20. Какая таблица истинности изображена на рисунке?

А) Эквивалентность;

Б) Импликация;

В) Отрицание.

21. Для описания соответствий между множествами используют понятие … одного множества на другое.

А)Отображения

Б) Соответствие

В) Объединение

22. Закон ассоциативности это:

А) , .

Б) , .

В)

Г) ,

Д)

Е) , .

Ж) ,

Вариант.

11. Какой из графов является полуэйлеровым?

А) 1;

Б) 1 и 3;

В) 2.

12. Какой граф не является плоским:

а) 1, 2, 4;

б) 1 и 3;

в) 1.

13. Какой алгоритм используется для нахождения минимального остовного дерева в данном графе:

и т. д.

а) алгоритм Крускала;

б) алгоритм Прима;

в) алгоритм Борувки.

14. Сколько эффективных алгоритмов решения имеет задача коммивояжера:

а) больше чем одно;

б) одно;

в) ни одного.

15. Совокупность существенных признаков объекта:

А) Объем;

Б) Содержание;

В) Понятие.

16. Запоминающее устройство, хранящее 1 бит информации:

А) Триггер;

Б) Детерминатор;

В) Преобразователь.

17. Определите, какая из следующих формул является тождественно истинной для формулы

А)

Б)

В)

Г)

Д)

18. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

19. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

20. Какая таблица истинности изображена на рисунке?

А) Эквивалентность;

Б) Импликация;

В) Отрицание.

21. Отображение е: А-> А называется …, если каждому аргументу оно ставит в соответствие себя.

А) Тождественным

Б) Непересекающимся

В) Дополнением

22. Закон дистрибутивности это:

А) , .

Б) , .

В)

Г) ,

Д)

Е) , .

Ж) ,

Вариант.

11. Всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называют:

А) Курсальной;

Б) Уникурсальной;

В) Непрерывной.

12. Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он:

а) связный;

б) несвязный;

в) полный.

13. Прочитайте формулировку и определите алгоритм нахождения минимального остовного дерева:

Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.

а) алгоритм Крускала;

б) алгоритм Прима;

в) алгоритм Борувки.

14. Если в графе есть несколько ребер с одинаковым весом, сколько минимальных остовных деревьев может он иметь?

а) больше чем одно;

б) одно;

в) ни одного.

15. Высказывание – это…

А) Мышление, образующее множество теорий и доказательств;

Б) Форма суждения, в которой, что-либо не является истинной;

В) Форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними.

16. Устройство для сложения двоичных чисел:

А) Полусумматор;

Б) Сумматор;

В) Триггер.

17. Определите, какая из следующих формул является тождественно истинной для формулы

А)

Б)

В)

Г)

Д)

18. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

19. Упростите формулу , используя законы алгебры логики:

А) a v c;

Б) ;

В) ;

Г) a•(c v b•d);

Д) ;

Е) ;

Ж) ;

З) a•(b v c•d);

И)

20. Название данной таблицы истинности:

А)Отрицание;

Б) конъюнкции;

В) импликации.

21. Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности называются:

А) Свойства эквивалентности;

Б) Классами эквивалентности;

В) Нет правильного ответа.

22. Законы де Моргана это:

А) , .

Б) , .

В)

Г) ,

Д)

Е) , .

Ж) ,