назад

Итоговый тест

  1. Граф, все ребра которого ациклические называется

    a) Деревом;
    б) Двудольным графом;
    в) Полным графом;
    г) Остовом графа.

  2. Цикломатическое число равно ... , где р-ребра, b-вершины, k-связные компоненты

    а) ν=p-b+k;
    б) ν=p+b-k;
    в) ν=p-b+1;
    г) ν=k-b+1.

  3. Теорема Форда-Фалкерсона гласит

    а) Максимальная величина потока Rmax через сеть S равна максимальной из пропускных способностей Сmax ее простых сечений;
    б) Максимальная величина потока Rmax через сеть S равна минимальной из пропускных способностей С min ее простых сечений;
    в) Минимальная величина потока Rmin через сеть S равна максимальной из пропускных способностей Сmax ее простых сечений;
    г) Минимальная величина потока Rmin через сеть S равна минимальной из пропускных способностей С min ее простых сечений;

  4. Бинарное отношение, обладающее свойством при любом а: а ┐R a называется ...

    а) Рефлексивным;
    б) Антирефлексивным;
    в) Симметричным;
    г) Антисимметричным.

  5. Бинарное отношение, являющееся рефлексивным, антисимметричным и транзитивным называется ...

    а) Бинарное отношение.
    б) Отношение строгого порядка;
    в) Отношение эквивалентности;
    г) Отношение нестрогого порядка;

  6. Какое из предложений является высказыванием ?

    а) Х,У : Р(Х,У)Q{Х,У};
    б) {ХN: Х>0};
    в) С добрым утром!;
    г) Вечереет.

  7. Переменная xi, при изменении которой значение функции f(x1,x2,...xi,...xn) не изменяется называется ...

    а) Независимой;
    б) Действительной;
    в) Фиктивной;
    г) Зависимой.

  8. Рангом терма r называется ...

    а) Количество минтермов, входящих в данный терм.
    б) Количество переменных, входящих с отрицанием в данный терм;
    в) Количество операций, входящих в данный терм;
    г) Количество переменных, входящих в данный терм;

  9. Функция, для которой выполняется Z=f(X1,X2,...,Xn), Z*=┐f(┐X1,┐X2,...,┐Xn) называется ...

    а) Самодвойственной функцией;
    б) Двойственной функцией;
    в) Монотонной функцией;
    г) Линейной функцией.

  10. Определить диаметр графа

    а) 1;
    б) 2;
    в) 3;
    г) 4.

  11. Определить ДНФ функции X1X2

    а) ┐X1┐X2;
    б) X1┐X2;
    в) ┐X1┐X2 X1X2 X1┐X2;
    г) X1X2 ┐X1┐X2 ┐X1X2.

  12. Определить F=AB\C

    а)
    б)
    в)
    г)

  13. Составьте функцию по данной таблице
    x y f
    0 0 0
    0 1 1
    1 0 0
    1 1 0

    а) XY
    б) ┐YX;
    в) ┐XY;
    г) ┐X┐Y;

  14. Найти МДНФ функции f=å(0,2,3,4,8,10,11)

    а) ┐X1┐X3┐X4 ┐X2X4X3┐X2
    б) X2┐X4┐X3X2 X2X3X4
    в) X1┐X3X4┐X2 X1X3X4
    г) X1 X3┐X4 ┐X2X4 X1X2X3

  15. Преобразуйте функцию к базису {┐,&}. f=xyz

    а) ┐(┐x┐y┐z);
    б) (xy┐z);
    в) ┐(xy┐z);
    г) ┐(┐x┐yz)

  16. Какое из выражений не является множеством ?

    а) N\{1,3,5};
    б) JQ;
    в) {x/x2-4=0};
    г) {x2+y2=z2}.

  17. Какое из данных множеств не является подмножеством множества A={a,b} ?

    а) Ø;
    б) {a};
    в) {b,a};
    г) {a,b}.

  18. Что представляет собой данная область Z ?

    а) (AB C D);
    б) B\DA C;
    в) (DA) C B;
    г) (BD)\A\C).

  19. Декартовым произведением множеств А12,...,Аk называется множество, элементами которого являются ...

    а) Все кортежи длины n;
    б) Упорядоченные пары элементов;
    в) Пары элементов;
    г) Нет правильного ответа.

  20. Какое из соответствий является инъекцией ?

    а) XY

    б) XY

    в) XY

    г) XY

  21. Каким свойством не обладает отношение эквивалентности ?

    а) Рефлексивно;
    б) Транзитивно;
    в) Симметрично;
    г) Антисимметрично.

  22. Каким свойством отличается отношение строгого и нестрогого порядка ?

    а) Транзитивность;
    б) Антисимметричность;
    в) Рефлексивность;
    г) Симметричность.

  23. Какое из выражений не является высказыванием ?

    а) 2*2=7;
    б) 2*3=6;
    в) x+3=7, x=1;
    г) 2x+8=10.

  24. Укажите, какая операция принимает следующие значения ?
    x y f
    0 0 0
    0 1 0
    1 0 0
    1 1 1

    а) Конъюнкция;
    б) Дизъюнкция;
    в) Импликация;
    г) Отрицание.

  25. Для построения СДНФ нужно
    1. Построить ДНФ;
    2. Проверить критерий ложности;
    3. Добавить элементы вида ...

    а) Xi ┐Xi;
    б) Xi ┐Xi;
    в) Xi Xi;
    г) ┐Xi ┐Xi.

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

    а) Конъюнкция и отрицание;
    б) Конъюнкция и дизъюнкция;
    в) Импликация и эквивалентность;
    г) Дизъюнкция и импликация.

  27. Выбрать правильный ответ

    а) (XY)Z(┐X┐Z);
    б) XYZ┐X┐Z;
    в) XYZ┐X┐Z;
    г) (XY)Z(┐X┐Z).