Тесты по ДМ(ТЭАКиТ)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

Университет «Туран»

Факультет «Академия кино и телевидения»

Кафедра ПИиРЭТ

ТЕСТОВЫЕ ВОПРОСЫ

для экзамена

по дисциплине

ДИСКРЕТНАЯ МАТЕМАТИКА

для студентов специальности 050704 «ВТиПО»

Количество тестовых вопросов	200
Составитель	Дадаева И. Г.

Алматы 2011

[q]3:1: Сколькими способами можно раскрасить квадрат, разделенный на четыре части, если имеется пять различных красок и допускается раскрашивание разных частей в один цвет?

[a] 120

[a] 5

[a] 1024

[a] [+] 625

[a] 20

[q]3:1: Логическая функция f(x,y) задана своими значениями на последовательности наборов значений аргументов (0,0), (0,1), (1,0), (1,1): f = ( 0 0 1 1 ). Найдите ее совершенную конъюнктивную нормальную форму (СКНФ).

[a] ( V ) (x V )

[a] [+] (x V y ) (x V )

[a] (x V y ) ( V y)

[a] & V &y

[a] (x V ) ( V y )

[q]3:1: Укажите эквивалентные формулы:

1) 2) 3)

[a] 2, 3

[a] 1, 2

[a] [+] 1, 3

[a] 1, 2, 3

[a] нет таких

[q]3:1: Какая из приведенных систем логических функций является функционально полной?

[a] {xy, 1, 0 }

[a] [+] {x&y , }

[a] {x&y, x y}

[a] {x&y, 0, 1}

[a] {xyz, x&y, 0}

[q]3:1: Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции f(x,y)= x → y имеет вид

[a] x &y V x&

[a] [+] & V &y V x&y

[a] & V &y

[a] (V) (Vy) (xVy)

[a] x&y V x& V &y V&

[q]3:1: Пусть Х- множество, |X|=4. Сколько существует биективных отображений этого множества в себя?

[a] 16

[a] 256

[a] 64

[a] [+] 24

[a] 512

[q]3:1: В матрице указаны веса ребер связного неориентированного четырехвершинного графа. Найдите вес минимального остовного дерева.

 1 2 3

1  5 4

2 5  2

3 4 2 

[a] 7

[a] 8

[a] 6

[a] 5

[a] 9

[q]3:1: Найдите цикломатическое число графа, заданного множеством вершин X={1, 2, 3, 4, 5, 6} и отношением на этом множестве: | x-y | >=3.

[a] 3

[a] 2

[a] [+] 1

[a] 5

[a] 0

[q]3:1: Из 150 школьников все мальчики собирали марки. 52 мальчика собирали марки Африки, 34 мальчика- марки Америки, 10 мальчиков собирали только марки Америки. Сколько среди школьников было девочек?

[a] 75

[a] 66

[a] [+] 88

[a] 56

[a] 80

[q]3:1: Какой граф называется эйлеровым?

[a] граф, не содержащий циклов

[a] не связный плоский граф

[a] [+] граф, имеющий цикл, содержащий все его ребра

[a] граф, имеющий один цикл

[a] граф, который можно раскрасить тремя красками

[q]3:1: Какое из перечисленных множеств – счетное?

[a] множество всех иррациональных чисел

[a] [+] множество всех целых чисел

[a] множество вещественных чисел отрезка [0; 1]

[a] множество вещественных чисел отрезка [-10; 10]

[a] множество всех точек I квадранта плоскости

[q]3:1: Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал четырех различных цветов? (все полосы должны быть разного цвета)

[a] 64

[a] 81

[a] [+] 24

[a] 4

[a] 12

[q]3:1: Логическая функция f(x,y) задана своими значениями на последовательности наборов значений аргументов (0,0), (0,1), (1,0), (1,1):

f = ( 0 1 1 0 ). Найдите ее совершенную конъюнктивную нормальную форму (СКНФ).

[a] [+] (x V y ) ( V )

[a] (y V x ) ( x & y )

[a] ( V ) (x V )

[a] &V &y

[a] (x V y) ( V y)

[q]3:1:Укажите, какие из трех заданных формул эквивалентны:

1) 2) 3)

[a] 2, 3

[a] 1, 2

[a] [+] 1, 3

[a] 1, 2, 3

[a] нет таких

[q]3:1: Какая из приведенных систем логических функций не является функционально полной?

[a] {x  y }

[a] { , x y}

[a] {x y, x y, 1}

[a] {x V y, }

[a] [+] {x &y, x V y }

[q]3:1: Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции f(x,y)= x y имеет вид

[a] & V x&y

[a] [+] &y V x&

[a] & V &y

[a] x&y V x&

[a] (xV) (Vy)

[q]3:1: В матрице указаны веса ребер связного неориентированного четырехвершинного графа. Найдите вес минимального остовного дерева.

• 2 1 3

2  2 2

1 2  1

3 2 1 

[a] 3

[a] 7

[a] 5

[a] [+] 4

[a] 2

[q]3:1: Найдите цикломатическое число графа, заданного множеством вершин X={0,1,2,3,4,5} и отношением на этом множестве G: |x-y|>=2.

[a] 4

[a] [+] 5

[a] 6

[a] 3

[a] 7

[q]3:1: На потоке обучаются 50 студентов. Из них 28 человек любят программирование, 15-мат. логику, 13 не любят ни мат. логику, ни программирование. Сколько студентов любят только программирование?

[a] 6

[a] 20

[a] 35

[a] [+] 22

[a] 8

[q]3:1: Какой граф называется деревом?

[a] несвязный граф с одним циклом

[a] граф, который можно правильно раскрасить двумя красками

[a] [+] связный граф без циклов

[a] граф, в котором каждая пара вершин смежна

[a] связный граф с одним циклом

[q]3:1: Полином Жегалкина для функции f(x, y) = имеет вид

[a] 1 x

[a] x y xy

[a] 1 x xy

[a] [+] 1 y xy

[a] y xy

[q]3:1: Является ли функция f(x, y), заданная таблицей

х	у	f(x,y)
0	0	0
0	1	1
1	0	0
1	1	0

сохраняющей нуль, сохраняющей единицу, самодвойственной?

[a] да да да

[a] нет да да

[a] да да нет

[a] нет да нет

[a] [+] да нет нет

[q]3:1: Какая из приведенных функций тождественно ложная?

[a] a~a

[a] a V a

[a] a 

[a] [+] a &

[a] a | a

[q]3:1: Сколько всевозможных подмножеств содержит множество А ={0, 2, 4, 6, 8, 10, 12, 14, 16, 18}?

[a] [+] 1024

[a] 2008

[a] 2048

[a] 3016

[a] 4096

[q]3:1: Сколько существует всевозможных функциональных отображений множества А во множество В?

А ={1, 2, 3, 4} В={5, 6, 7}

[a] 12

[a] 1024

[a] [+] 81

[a] 256

[a] 7

[q]3:1: Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, если каждая из них в числе встречается не более одного раза?

[a] [+] 720

[a] 2160

[a] 2520

[a] 7776

[a] 120

[q]3:1: Сколько элементов содержит множество А × В, если А ={1, 2, 3, 4} и В={3, 1, 5}?

[a] 5

[a] 7

[a] 11

[a] [+] 12

[a] 64

[q]3:1: Из данного множества формул выделите ту, которая имеет вид конъюнктивной нормальной формы (КНФ)

[a]

[a] [+]

[a]

[a]

[a]

[q]3:1: Найдите равные множества в данной последовательности:

1) (А \ В) ∩ С 2) (В \ А) ∩ С 3) (С \ В) ∩ А

[a] [+] 1 и 3

[a] 1 и 2

[a] 2 и 3

[a] 1, 2, 3

[a] нет таких

[q]3:1: Сколько элементов содержит множество (В \ А) × А, если А ={1, 2, 3, 4, 5} В={3, 4, 5}?

[a] [+] 0

[a] 3

[a] 5

[a] 10

[a] 15

[q]3:1: Пусть А – множество натуральных четных чисел; В – множество натуральных чисел, кратных трем. Найдите разность В \ А.

[a] множество натуральных чисел, кратных шести

[a] множество натуральных чисел, не кратных шести

[a] множество четных натуральных чисел, не кратных трем

[a] множество натуральных чисел, не кратных трем

[a] [+] множество натуральных чисел, кратных трем и нечетных

[q]3:1: Найдите пересечение множеств Х и Y (X  Y), если X = x | 1  x  3, Y = y | 2  y  4

[a] x | 1  x  4

[a] [+] x | 2  x  3

[a] 2, 3

[a] 1, 2, 3, 4

[a] y | 2  y  4

[q]3:1: Сколькими способами можно расставить 5 книг на полке?

[a] 10

[a] 25

[a] [+] 120

[a] 360

[a] 5

[q]3:1: Чему равна мощность множества А = 1, 3, 5, 7, 9?

[a] 8

[a] 9

[a] 1

[a] [+] 5

[a] 945

[q]3:1: Какое их перечисленных множеств имеет мощность континуума?

[a] множество всех четных чисел, кратных семи

[a] множество всех рациональных чисел

[a] [+] множество вещественных чисел отрезка [3, 4]

[a] множество всех целых отрицательных чисел

[a] множество всех чисел, являющихся степенями двойки

[q]3:1: Укажите среди данного набора множеств пустое множество

[a] [+]

[a]

[a]

[a]

[a]

[q]3:1: Из данного множества формул выделите то, которое имеет вид дизъюнктивной нормальной формы

[a] [+]

[a]

[a]

[a]

[a]

[q]3:1: Найдите симметрическую разность (АВ) множеств А = 2, 3, 4 и В = 4, 5, 6

[a] 2, 3, 4, 5, 6

[a] 5, 6

[a] 4

[a] 2, 3

[a] [+] 2, 3, 5, 6

[q]3:1: Дана матрица бинарного отношения 1 1 0 0 0

0 1 1 0 0

0 0 1 0 1

1 0 0 1 0

0 0 1 0 1

Является ли это отношение рефлексивным, симметричным, транзитивным?

[a] нет, нет, да

[a] да, нет, да

[a] нет, да, нет

[a] да, да, нет

[a] [+] да, нет, нет

[q]3:1: Какая из функций тождественно истинная?

[a]

[a] [+]

[a]

[a]

[a]

[q]3:1: Сколькими способами можно дать клички четырем щенкам, имея шесть различных кличек? (все щенки должны быть названы по-разному)

[a] 15

[a] [+] 360

[a] 1296

[a] 256

[a] 24

[q]3:1: Логическая функция f(x,y) задана своими значениями на последовательности наборов значений аргументов (0,0), (0,1), (1,0), (1,1): f = ( 1 0 1 0 ). Найдите ее совершенную конъюнктивную нормальную форму (СКНФ).

[a]

[a]

[a] [+]

[a]

[a]

[q]3:1: Укажите эквивалентные формулы: 1) 2) 3) a | b

[a] [+] 2, 3

[a] 1, 2

[a] 1, 3

[a] 1, 2, 3

[a] нет таких

[q]3:1: Какая из приведенных систем логических функций является функционально полной?

[a] {x y , 1 }

[a] {x y, x &y}

[a] {x y, 0}

[a] {x &y, 0}

[a] [+] {x V y, }

[q]3:1: Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции f(x,y,z)=x V y имеет вид

[a] [+] &y V x& V x&y

[a] x&y V &

[a] & V x& V x&y

[a] & V x&y

[a] (xVy) (V)

[q]3:1: Сколько различных трехразрядных натуральных чисел можно получить, используя цифры 2,3,5,9?

[a] 81

[a] 4

[a] 16

[a] [+] 64

[a] 24

[q]3:1: В матрице указаны веса ребер связного неориентированного четырехвершинного графа. Найдите вес минимального остовного дерева.

• 5 1 8

5  2 1

1 2  3

8 1 3 

[a] [+] 4

[a] 5

[a] 2

[a] 6

[a] 8

[q]3:1: Найдите цикломатическое число графа, заданного множеством вершин X={1, 2, 3, 4, 5, 6 } и отношением на этом множестве |x-y| <3.

[a] 5

[a] 2

[a] 0

[a] 3

[a] [+] 4

[q]3:1: Из тридцати сотрудников отдела английский язык знают 19 человек, немецкий- 17 человек, пятеро не знают ни английского, ни немецкого. Сколько человек знают только немецкий язык?

[a] 10

[a] [+] 6

[a] 8

[a] 2

[a] 12

[q]3:1: Какой граф называется бихроматическим?

[a] граф, не имеющий циклов

[a] связный граф с одним циклом

[a] плоский несвязный граф

[a] [+] граф, который можно правильно раскрасить двумя красками

[a] граф, имеющий цикл, проходящий через все вершины

[q]3:1: Полином Жегалкина для функции f(x, y) = x V y имеет вид

[a] 1x

[a] [+] xyxy

[a] x xy

[a] 1yxy

[a] yxy

[q]3:1: Является ли функция f(x, y), заданная таблицей

х	у	f(x, y)
0	0	0
0	1	1
1	0	1
1	1	1

сохраняющей нуль, сохраняющей единицу, самодвойственной?

[a] да, да, да

[a] нет, да, нет

[a] да, нет, нет

[a] [+] да, да, нет

[a] нет, нет, да

[q]3:1: Какая из приведенных функций тождественно ложная?

[a] [+] ~

[a] a V a

[a] a 

[a] a & а

[a] a | a

[q]3:1: Сколько всевозможных подмножеств содержит множество

А ={a, b, c, d, e, f}?

[a] 4

[a] 6

[a] 36

[a] 32

[a] [+] 64

[q]3:1: Сколько существует биективных отображений множества А во множество В?

А ={1, 2, 3} В={5, 6, 7}

[a] 9

[a] [+] 6

[a] 27

[a] 3

[a] 18

[q]3:1: Сколько элементов содержит множество А × В, если А ={3, 4, 5, 8} и В={7, 1, 5, 9}?

[a] 32

[a] 1

[a] 8

[a] 256

[a] [+] 16

[q]3:1: Из данного множества формул выделите ту, которая имеет вид конъюнктивной нормальной формы (КНФ)

[a]

[a]

[a]

[a]

[a] [+]

[q]3:1: Найдите равные множества среди трех данных множеств:

1) (А \ В) (В \ А) 2) А ∆ В 3) (А В) \ (А В)

[a] 1 и 2

[a] 1 и 3

[a] 2 и 3

[a] [+] 1, 2, 3

[a] нет таких

[q]3:1: Какое из перечисленных множеств – счетное?

[a] множество всех иррациональных чисел

[a] множество всех точек плоскости

[a] множество вещественных чисел отрезка [5; 7]

[a] множество всех вещественных чисел

[a] [+] множество всех четных чисел

[q]3:1: Сколько элементов содержит множество (В \ А) × А, если А ={2, 3, 4, 5}, В={4, 5, 6}?

[a] 7

[a] 3

[a] [+] 4

[a] 81

[a] 12

[q]3:1: Сколькими способами можно выбрать 2 разных галстука из 8 висящих в шкафу?

[a] 8

[a] 28

[a] 16

[a] 56

[a] [+] 64

[q]3:1: Пусть А – множество четных чисел; В – множество чисел, кратных трем. Найдите пересечение .

[a] [+] множество чисел, кратных шести

[a] множество чисел, не кратных шести

[a] множество чисел, кратных трем

[a] множество чисел, не кратных трем

[a] множество нечетных чисел