Kopia_Testy_po_DM_informatika

B) 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 (y²+y+1=0) 3) x ( x³ < x² )

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. Сколько существует инъективных отображений XY?

E) 60

$$$ 130

Пусть Х и Y - два множества, |X|=3, |Y|=5. Сколько существует функциональных отображений XY ?

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(x₁, _…,x_n) и g(x₁,…,x_n) называются двойственными друг другу, если для всех наборов значений переменных выполняется равенство

D) f(x₁, …, x_n) =

$$$ 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(x₁, _…,x_n) такая, что 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) штрих Шеффера