Kopia_Testy_po_DM_informatika
.docB) 1) л 2) и 3) л
$$$ 116
Какие из следующих высказываний истинны (и), а какие – ложны (л) ?
1) если 2х2=4, то 2<3
2) если 2х2=4, то 2>3
3) если 2х2=5, то 2<3
4)если 2х2=5, то 2>3
D) 1) и 2) л 3) и 4) и
$$$ 117
Постройте логическую формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.
E)
$$$ 118
Найдите область истинности предиката х + 2 < 3х − 4
С) (3; +∞)
$$$ 119
Какое из предложений не является высказыванием?
E) A >0
$$$ 120
Какие из следующих высказываний истинны (и), а какие – ложны (л) (переменные принимают значения из R- множества вещественных чисел)?
1) x ( |x| 0) 2) yR (y2+y+1=0) 3) x ( x3 < x2 )
D) 1) и 2) л 3) и
$$$ 121
Пусть А(х), В(х) – любые предикаты. Какие из следующих четырех формул эквивалентны формуле А(х) → ?
1) А(х) В(х) 2) 3) В(х)→ 4)
B) 2, 3
$$$ 122
Сколькими способами можно раскрасить квадрат, разделенный на 4 части, если имеется 6 различных красок и не допускается раскрашивание разных частей в один цвет?
C) 360
$$$ 123
Найдите хроматическое число графа, заданного множеством вершин X={0,1,2,3,4,5} и отношением на этом множестве G: |x-y|>=2.
A) 4
$$$ 124
Какой граф является однохроматическим?
C) нуль - граф
$$$ 125
Найдите хроматическое число графа, заданного множеством вершин X={1, 2, 3, 4, 5, 6} и отношением на этом множестве : | x-y | >=3.
B) 3
$$$ 126
Найдите диаметр графа, заданного множеством вершин X={1, 2, 3, 4, 5, 6} и отношением на этом множестве : | x-y | >=3.
D) 3
$$$ 127
Найдите диаметр графа, заданного множеством вершин X={0,1,2,3,4,5} и отношением на этом множестве G: |x-y|>=2.
E) 2
$$$ 128
Какой граф называется деревом?
C) связный граф без циклов
$$$ 129
Пусть Х и Y - два множества, |X|=3, |Y|=5. Сколько существует инъективных отображений XY?
E) 60
$$$ 130
Пусть Х и Y - два множества, |X|=3, |Y|=5. Сколько существует функциональных отображений XY ?
B) 125
$$$ 131
На множестве А= {1, 2, 3, 4} задано бинарное отношение {(1,3), (1,4), (3, 1), (4, 1), (2,3)}. Является ли оно 1)рефлексивным, 2)антирефлексивным, 3)симметричным, 4)антисимметричным, 5)транзитивным?
A) 1) нет 2) да 3) нет 4) нет 5) нет
$$$ 132
Функции f(x1, …,xn) и g(x1,…,xn) называются двойственными друг другу, если для всех наборов значений переменных выполняется равенство
D) f(x1, …, xn) =
$$$ 133
Дуга транспортной сети называется насыщенной, если
B) поток на ней равен пропускной способности
$$$ 134
Какой граф называется гамильтоновым?
C) содержащий простой цикл, проходящий через все вершины графа
$$$135
Граф называется ориентированным, если
B) он содержит только дуги
$$$ 136
Вершины графа называются смежными, если
B) они соединены ребром или дугой
$$$ 137
Диаметр графа - это
C) самое большое расстояние в графе
$$$ 138
Цикломатическое число графа показывает
D) количество независимых циклов графа
$$$ 139
Хроматическое число графа показывает
A) минимальное число красок, необходимое для правильной раскраски графа
$$$ 140
Радиус графа - это
E) максимальное удаление от центра
$$$ 141
Сколькими способами можно раскрасить квадрат, разделенный на четыре части, если имеется пять различных красок и не допускается раскрашивание разных частей в один цвет?
E) 120
$$$ 142
Логическая функция f(x,y) задана своими значениями на последовательности наборов значений аргументов (0,0), (0,1), (1,0), (1,1): f = ( 0 0 1 1 ). Найдите ее совершенную дизъюнктивную нормальную форму (СДНФ).
D) х& V х&y
$$$ 143
Укажите эквивалентные формулы:
1) 2) 3)
A) 2, 3
$$$ 144
Какая из приведенных систем логических функций является функционально полной?
D) {x&y, xy, 1}
$$$ 145
Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции f(x,y)= x ~ y имеет вид
A) x &y V &
$$$ 146
Пусть Х- множество, |X|=5. Сколько существует инъективных отображений этого множества в себя?
B) 120
$$$ 147
В матрице указаны веса ребер связного неориентированного четырехвершинного графа. Найдите вес минимального остовного дерева.
5 7 6
5 2 4
7 2 3
6 4 3
B) 10
$$$ 148
Найдите цикломатическое число графа, заданного множеством вершин X={1, 2, 3, 4, 5} и отношением на этом множестве: 5≤| x+y | ≤8.
C) 3
$$$ 149
Пусть Х - множество, |X|=6. Сколькими способами можно разбить это множество на 3 подмножества таких, что первое из них содержит 3 элемента, второе - 2 элемента, третье - 1 элемент?
D) 60
$$$ 150
Какой граф называется неориентированным?
C) граф, содержащий только ребра
$$$ 151
Какое из перечисленных множеств не является счетным?
A) множество всех иррациональных чисел
$$$ 152
Из 37 студентов, изучающих иностранные языки, немецким языком владеют 15 человек, английским- 15 человек, французским-14. Английским и французским владеют 4 человека, немецким и французским - 2 человека, немецким и английским-2 человека. Сколько человек владеют всеми тремя языками?
E) 1
$$$ 153
Логическая функция f(x,y) задана своими значениями на последовательности наборов значений аргументов (0,0), (0,1), (1,0), (1,1):
f = ( 0 1 1 1 ). Найдите ее совершенную конъюнктивную нормальную форму (СКНФ).
E) (x V y)
$$$ 154
Укажите, какие из трех заданных формул эквивалентны:
1) 2) ()() 3)
D) 1, 2, 3
$$$ 155
Какая из приведенных систем логических функций не является функционально полной?
E) {x &y, x V y }
$$$ 156
Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции f(x,y)= x | y имеет вид
A) & V &y V x&
$$$ 157
Сколько можно построить бинарных отношений на множестве мощности 3?
B) 512
$$$ 158
Найдите цикломатическое число графа, заданного множеством вершин X={1,2,3,4,5} и отношением на этом множестве G: |x-y|>=3.
C) 0
$$$ 159
Сколькими способами можно разбить множество из 5 объектов на 3 непустые части?
C) 25
$$$ 160
Какой граф является однохроматическим?
B) нуль - граф
$$$ 161
Полином Жегалкина для функции f(x, y) = x V y имеет вид
B) x y xy
$$$ 162
Является ли функция f(x, y), заданная таблицей
х |
у |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
сохраняющей нуль, сохраняющей единицу, самодвойственной?
A) нет нет да
$$$ 163
Какая из приведенных функций тождественно ложная?
A) a ~
$$$ 164
Сколько всевозможных подмножеств содержит множество А ={1, 3, 5, 7, 9, 11, 13}?
E) 128
$$$ 165
Сколько существует всевозможных функциональных отображений множества А во множество В?
А ={x, y, z} В={5, 6, 7, 8}
D) 24
$$$ 166
Сколько четырехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?
C) 625
$$$ 167
Сколько элементов содержит множество (А\B) × В, если А ={1, 2, 3, 4, 6} и В={3, 1, 5}?
B) 9
$$$ 168
Из данного множества формул выделите ту, которая имеет вид дизъюнктивной нормальной формы (ДНФ)
A)
$$$ 169
Найдите равные множества в данной последовательности:
1) (А \ В) ∩ С 2) (С А) \ В 3) (С \ В) ∩ А
D) 1, 2, 3
$$$ 170
Сколько элементов содержит множество (В А) × А, если А ={1, 2, 3, 4, 5} В={3, 4, 6}?
D) 10
$$$ 171
Полином Жегалкина для функции f(x, y) = →y имеет вид
D) 1 y xy
$$$ 172
Является ли функция f(x, y), заданная таблицей
х |
у |
f(x,y) |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
сохраняющей нуль, сохраняющей единицу, самодвойственной?
A) да да да
$$$ 173
Какая из приведенных функций тождественно ложная?
A) a ~
$$$ 174
Сколько всевозможных подмножеств содержит множество А ={1, 3, 5, 7, 9}?
E) 32
$$$ 175
Сколько существует всевозможных функциональных отображений множества B во множество A?
А ={1, 2, 3, 4} В={5, 6, 7}
C) 64
$$$ 176
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, если каждая из них может встречаться не один раз?
B) 216
$$$ 177
Сколько элементов содержит множество (АB) × В, если А ={1, 2, 3, 4} и В={3, 1, 5}?
D) 15
$$$ 178
Из данного множества формул выделите ту, которая имеет вид
полинома Жегалкина
E) 1 x
$$$ 179
Найдите равные множества в данной последовательности:
1) (C ∩ В) \ A 2) (В \ А) ∩ С 3) (С \ В) ∩ А
B) 1 и 2
$$$ 180
Сколько элементов содержит множество (В А) \ А, если А ={1, 2, 3, 4, 5} В={3, 4, 5}?
A) 0
$$$ 181
Пусть А – множество натуральных чисел, кратных шести; В – множество натуральных чисел, кратных трем. Найдите объединение ВА.
E) множество натуральных чисел, кратных трем
$$$ 182
Найдите пересечение множеств Х и Y (X Y), если X = x | 1 x 5, Y = y | 2 y 4
E) y | 2 y 4
$$$ 183
Сколькими способами можно разместить 7 человек за круглым столом?
C) 5040
$$$ 184
Найдите пересечение множеств А и D, если известно, что ABCD
D) A
$$$ 185
Какое их перечисленных множеств не является множеством мощности континуума?
A) множество всех четных чисел, кратных пяти
$$$ 186
Найдите полином Жегалкина для функции f(x,y), имеющей на наборах (0, 0), (0,1), (1,0), (1,1) значения (1001).
B) xy1
$$$ 187
Как называется логическая функция f(x1, …,xn) такая, что f(1,1, …,1)=1?
D) сохраняющая единицу
$$$ 188
Найдите симметрическую разность (АВ) множеств А = 1,2, 3, 4, 5 и В = 4, 5, 6, 7
E) 1, 2, 3, 6, 7
$$$ 189
Дана матрица бинарного отношения 0 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) нет, нет, нет
$$$ 190
Какая из функций тождественно истинная?
B)
$$$ 191
Граф называется неориентированным, если
C) он содержит только ребра
$$$ 192
Сколькими способами можно выбрать две разные книги для чтения из пяти имеющихся?
D) 10 $$$ 193
Для какой логической операции таблица истинности имеет вид
х |
у |
f(x,y) |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
E) конъюнкция $$$ 194
Для какой логической операции таблица истинности имеет вид
х |
у |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
C) эквивалентность
$$$ 195
Для какой логической операции таблица истинности имеет вид
х |
у |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
B) импликация
$$$ 196
Сколькими способами можно разложить пять одинаковых шаров по двум различным урнам?
A) 6
$$$ 197
Сколькими способами можно разложить пять разных шаров по двум различным урнам? C) 32
$$$ 198
Когда одно множество называется подмножеством другого? C) когда каждый элемент первого множества является элементом второго
$$$ 199
Для какой логической операции таблица истинности имеет вид
х |
у |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
E) стрелка Пирса
$$$ 200
Для какой логической операции таблица истинности имеет вид
х |
у |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
D) штрих Шеффера