3. Материалы для подготовки к тесту базового уровня

Таблица 5

№ темы

Название темы

Элементы темы, вошедшие в тест

1.2

Элементы комбинаторики

Выборки. Сочетания и размещения без повторений и с с повторениями, перестановки.

Правило произведения и правило суммы, формулы подсчета числа сочетаний и размещений.

1.3

Булевы функции и способы их задания

Булевы функции. Задание булевой функции таблицей истинности и вектором значений. Элементарные функции. Задание функций формулами. Основные равносильности над множеством функций .

1.4.

Совершенные дизъюнктивные и конъюнктивные нормальные формы

Двойственные функции. Принцип двойственности. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ).

1.6.

Классы Поста и замыкание

Полином Жегалкина. Функции, сохраняющие 0, 1. Самодвойственные, монотонные, линейные функции. Замыкание системы булевых функций. Замкнутость классов Поста.

1.7

Полнота системы булевых функций

Полнота системы булевых функций. Критерий полноты Поста. Базисы

Таблица 7

№блока

Формулировка задания

Варианты ответа

1

Сколько существует булевых векторов длины 11, у которых 1,3,4, 6 и 7 координаты равны 0?

(1) 462

(2) 32

(3) 64

(4) 2048

2

Сколько существует булевых векторов длины 9, у которых ровно 5 координат равны 0?

(1) 32

(2) 16

(3) 126

(4) 3034

3

Сопоставьте вектор значений каждой из следующих функций

А. ;

Б. ;

В. ;

Г.

(1)

(2)

(3)

(4)

4

Условию удовлетворяет функция, заданная формулой

(1)

(2)

(3)

(4)

5

Вектор значений функции, заданной формулой , равен

(1)

(2)

(3)

(4)

6

Если длина вектора значений функции равна 512, то число аргументов функции равно

(1) 9

(2) 16

(3) 7

(4) 5

7

Вектор значений функции, двойственной функции , равен

(1)

(2)

(3)

(4)

8

Формула двойственна формуле

(1)

(2)

(3)

(4)

9

Функция задана таблицей

СДНФ функции имеет вид

(1)

(2)

(3)

(4)

10

Функция задана таблицей

СКНФ функции имеет вид

(1)

(2)

(3)

(4)

11

Выберите утверждение, верное для функции .

(1) ,

(2) ,

(3) ,

(4) ,

12

Выберите самодвойственную функцию.

(1)

(2)

(3)

(4)

13

Выберите вектор, предшествующий вектору .

(1)

(2)

(3)

(4)

14

Выберите условие, при выполнении которого функция немонотонна.

(1)

(2)

(3)

(4)

15

Выберите монотонную функцию.

(1)

(2)

(3)

(4)

16

Полином Жегалкина функции имеет вид

(1)

(2)

(3)

(4)

17

Выберите нелинейную функцию.

(1)

(2)

(3)

(4)

18

Выберите класс, которому принадлежит функция .

(1)

(2)

(3)

(4)

19

Выберите полную систему функций.

(1)

(2)

(3)

(4)

20

Выберите систему функций, являющуюся базисом.

(1)

(2)

(3)

(4)

Таблица 6

1

2

3

4

5

6

7

8

9

10

3

3

А.3

Б.1

В.4

Г.2

1

4

1

3

3

1

3

11

12

13

14

15

16

17

18

19

20

2

1

3

3

4

1

3

2

3

4