Проверочный тест
1.
Номер вектора
равен:
1.
2.
3.
4.
2. Если вектор значений функции имеет 64 координаты, то число ее аргументов равно
1. 64 2. 32 3. 8 4. 6
3.
Выбрать функции, удовлетворяющие
условию
:
1.
2.
3.
4.
4. Каждой формуле поставить в соответствие равносильную формулу.
1.
2.
3.
4.
а)
б)
в)
г)
1 |
2 |
3 |
4 |
|
|
|
|
5. Выбрать функции, для которых переменная существенная:
1.
2.
3.
4.
6. Выбрать функции, для которых переменная фиктивная:
1.
2.
3.
4.
7. Выбрать функции, равные функции (1010):
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.
а)
б)
в)
г)
1 |
2 |
3 |
4 |
|
|
|
|
13. Каждой функции поставить в соответствие ту дизъюнкцию, которая входит в ее СКНФ:
1.
2.
3.
4.
а)
б)
в)
г)
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. Выбрать функции, сохраняющие константы 0 и 1:
1.
2.
3.
4.
19.
Выбрать векторы, предшествующие вектору
:
1.
2.
3.
4.
20.
Выбрать утверждения, не противоречащие
тому, что функция
монотонная:
1.
2.
3.
4.
21. Выбрать линейные функции:
1.
2.
3.
4.
22. Выбрать линейные функции:
1.
2.
3.
4.
23.
Выбрать классы, которым принадлежит
функция
:
1. 2. 3. 4. 5.
24.
Таблица Поста системы функций
имеет следующий вид:
Функции |
Классы Поста |
||||
|
|
|
|
|
|
|
+ |
+ |
– |
– |
– |
|
+ |
– |
+ |
+ |
– |
Выберете условия,
которым обязательно должна удовлетворять
функция
,
чтобы система
была полной:
1.
2.
3.
4.
5.
6.
25. Выберете условия, которыми нужно дополнить приведенную ниже таблицу Поста системы функций с тем, чтобы эта система оказалась базисом:
Функции |
Классы Поста |
||||
|
|
|
|
|
|
|
+ |
– |
+ |
– |
– |
|
– |
+ |
+ |
– |
+ |
|
+ |
– |
|
|
|
1.
2.
3.
4.
5.
6.
Ответы к упражнениям и тесту части 1
2.2.б)
16.
Указание.
Вектор,
одинаково читающийся слева направо и
справа налево, однозначно определяется
первой половиной своих координат.
Первые четыре его координаты можно
выбрать
способами.
2.2.б)
,
,
,
,
,
,
,
.
2.7.в) Переменная - фиктивная, переменные , - существенные.
2.8.в) Переменная
-
фиктивная, переменные
,
- существенные; искомая функция -
.
2.9.в)
.
2.11.б)
.
2.13.в)
;
г)
.
2.12. б)
.
Переменная - существенная, а переменные , - фиктивные.
2.15.б) 9.
Указание.
Функция
обращается в ноль, если
и
равны одновременно 0. Есть три набора
значений переменных
,
при которых
(0,0, или 0,1, или
1,0). И есть три
набора значений переменных
,
при которых
.
Следовательно,
обращается в нуль на девяти векторах.
2.17.
в)
.
г)
.
2.18. б)
.
2.19. в)
;
г)
.
2.20.
д)
.
2.21.
д)
.
23. б)
,
2.22. в)
,
;
г)
,
.
2.26. в)
Рассмотрим системы
и
.
Имеем:
или
.
Следовательно,
и
.
Таким образом, каждая функция полной
системы
реализуется формулой над
.
Следовательно, условия теоремы о полноте
двух систем выполнены и, значит,
- полная система.
г)
Пусть
и
.
Система
- полная и, поскольку
,
то каждая функция этой системы выражается
формулой над
.
Таким образом, условия теоремы о полноте
выполнены и, значит, система
-
полная система.
2.28. в)
;
г)
.
2.29. в)
;
г)
.
2.30 б)
,
,
,
.
2.31 д)
Указание. Пусть
.
Тогда
вектор
значений
этой
функции имеет вид
.
Значит,
таких функций столько же, сколько
булевых векторов длины
,
т.е.
.
2.33. б) Элементарных самодвойственных функций 2-х переменных нет.
2.32. б)
,
,
,
.
2.35. б)
32. 2.37. б)
32.
2.39. а)
.
2.40.б)
только
.;
в)
не принадлежит ни одному из классов.
2.41.б)
,
принадлежит только
.
2. 42.в) Таблица Поста:
Функции |
Классы Поста |
||||
|
|
|
|
|
|
|
– |
+ |
– |
– |
– |
|
|
– |
|
|
|
Вывод: система полная.
г) Таблица Поста:
Функции |
Классы Поста |
||||
|
|
|
|
|
|
0 |
+ |
– |
– |
+ |
+ |
1 |
– |
|
|
+ |
+ |
|
|
|
|
+ |
|
Вывод: система неполная.
2.43.в)
Функции |
Классы функций |
||||
|
|
|
|
|
|
0 |
+ |
– |
– |
+ |
+ |
1 |
– |
+ |
– |
+ |
+ |
|
+ |
+ |
– |
+ |
– |
|
+ |
– |
– |
– |
+ |
Имеем один базис:
г)
Функции |
Классы функций |
||||
|
|
|
|
|
|
|
– |
– |
– |
– |
– |
|
– |
– |
– |
– |
– |
Имеем два базиса:
и
.