ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1356
Скачиваний: 1
48
Ответы
1.1.
C
k
n
;
1.5.
n
2
n
−
1
;
2.1.
2
2
n
−
1
;
2.2.
2(
n
≥
1)
;
4.1.
x
α
1
1
x
α
2
2
. . . x
α
n
n
;
4.2.
x
¯
α
1
1
∨
x
¯
α
2
2
∨
. . .
∨
x
¯
α
n
n
;
4.5.
Указание:
использовать
метод
математической
индукции;
5.9.
а)
по
определению
U
∗
(
x
1
, x
2
, . . . , x
n
) = ¯
U
(¯
x
1
,
¯
x
2
, . . . ,
¯
x
n
)
, использовать законы де Моргана
и закон двойного отрицания;
6.5. а)
2
n
−
k
+ 2
k
−
1
;
б)
1
3
(2
n
−
(
−
1)
n
)
;
7.3. а)
K
1
⊆
K
2
, но может быть и строгое включение;
б)
K
1
⊃
⊂
/
K
2
,
например,
M
1
=
{
xy,
¯
x
}
и
M
2
=
{
¯
x
}
имеем
K
1
= [
xy
]
, а
K
2
=
Б
\
[¯
x
]
;
д)
см. б);
8.6.
Если
f
(
x
1
, x
2
, . . . , x
n
)
– самодвойственная функция, то на
любой паре противоположных наборов она принимает противоположные
значения. Следовательно, число пар наборов, на которых самодвой-
ственная функция
f
(
x
1
, x
2
, . . . , x
n
)
принимает значение 1, равно числу
пар противоположных наборов (длины
n
), т.е.
|
N
f
|
= 2
n
−
1
;
9.2.
Пусть
f
(
x
1
, x
2
, . . . , x
n
)
принимает противоположные значения на любых двух
соседних наборах. Пусть
f
(0
,
0
, . . . ,
0) =
σ
, тогда
f
(
α
1
, α
2
, . . . , α
n
) = ¯
σ
,
если число
∥
α
α
∥
нечетно и
f
(
α
1
, α
2
, . . . , α
n
) =
σ
, если
∥
α
α
∥
– четно.
Пусть
P
σ
(
x
1
, x
2
, . . . , x
n
) =
x
1
⊕
x
2
⊕
. . .
⊕
x
n
⊕
σ
, тогда
N
f
=
N
P
σ
.
В силу единственности представления функций полиномом
f
=
P
σ
и,
следовательно,
f
∈
L
. Обратное неверно;
10.2. б)
при нечетных
n
;
в)
при
n
̸
= 4
k
−
1
, k
= 1
,
2
, . . .
;
10.3. б)
3
∗
2
2
n
−
2
;
д)
3
∗
2
n
−
1
;
ж)
(2
2
n
−
2
2
n
−
1
)
/
2
;
11.2.
Предварительно доказать справедливость следу-
ющих равенств:
f
(
x
1
, x
2
, . . . , x
n
) =
x
i
f
1
(
x
1
, x
2
, . . . , x
n
)
∨
f
2
(
x
1
, x
2
, . . . , x
n
)
;
f
(
x
1
, x
2
, . . . , x
n
) = (
x
i
∨
f
3
(
x
1
, x
2
, . . . , x
n
))
f
4
(
x
1
, x
2
, . . . , x
n
)
,
f
1
, f
2
, f
3
, f
4
–
булевы функции;
11.3.
Две функции.
49
Литература
1. Белоусов А.И. Дискретная математика / А.И. Белоусов, С.Б. Тка-
чев. - М.: изд-во МГТУ им. Н.Э. Баумана, 2001. - 743 с.
2. Лавриков И.А. Задачи по теории множеств, математической логике
и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. - М.: Физ-мат.
лит., 1995. - 255 с.
3. Лихтарников
Л.М.
Математическая
логика.
Курс
лекций.
Задачник-практикум и решения / Л.М. Лихтарников, Т.Г. Су-
качева. - СПб.: Лань, 1999. - 285 с.
4. Москинова Г.И. Дискретная математика / Г.И. Москинова. - М.:
Логос, 2000. - 238 с.
5. Перязев Н.А. Основы теории булевых функций / Н.А. Перязев. -
М.: Физматлит, 1999. - 109 с.
6. Яблонский С.В. Введение в дискретную математику / С.В. Яблон-
ский. - М.: Высш. школа, 2001. - 384 с.
50
Содержание
§1.
Булевы наборы. Единичный
n
-мерный куб . . . . . . . . . . . . . . . . . .
3
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
§2
Способы задания булевых функций. Элементарные функции.
Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
§3.
Основные эквивалентности алгебры высказывания . . . . . . . . . . . .
9
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
§4.
Дизъюнктивная и конъюнктивная нормальные формы . . . . . .
10
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
§5.
Совершенные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
§6.
Полином Жегалкина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
§7.
Операция замыкания. Замкнутые классы . . . . . . . . . . . . . . . . . . . . .
26
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
§8.
Двойственность и класс самодвойственных функций . . . . . . . . .
27
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
§9.
Линейность и класс линейных функций . . . . . . . . . . . . . . . . . . . . . . . .
29
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
§10. Классы функций, сохраняющих константы . . . . . . . . . . . . . . . . . .
30
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
§11. Монотонность и класс монотонных функций . . . . . . . . . . . . . . . . . .
31
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
§12. Полнота и замкнутые классы. Критерий Поста . . . . . . . . . . . . . . .
33
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
§13. Построение минимальных и кратчайших дизъюнктивных
нормальных форм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
51
Составители: Кацаран Татьяна Константиновна,
Кабанцова Лариса Юрьевна
Редактор Тихомирова Ольга Александровна